Algorithm：

117: Populating Next Right Pointers in Each Node II (Medium)

填充二叉树的各个节点的下一同层节点。这道题有个 Follow up：You may only use constant extra space. 我在开始一直在想如何用常数空间解决，尝试像BFS一样的遍历顺序但用指针串起来，定义 last 和 current 节点，不停用 current 的左右子节点链接到last后面，并推进 current=current.next直到最后，最终每层右侧节点无法处理，进入死胡同。后来看到中文题目才明白 Follow up 是进阶要求而不是必须项，于是先用队列 BFS 实现出来，这时想到 BFS 中每一层可以用 length 约束控制本层边界，也可以用一个新队列只放这一层内容，而这正是链表法解这道题的思路，即遍历当前层链表，取所有 children 形成下一层的新链表，当前链表遍历至 next == null 说明该切换至下一链表，这需要保存和利用下一层的 head 节点。

    public Node connect(Node root) {
        if (root == null) return null;
        Node curr = root;
        Node head = null, level = null;
        // children
        while (curr != null) {
            // start new level list
            if (head == null) {
                head = new Node();
                level = head;
            }
            // add level
            if (curr.left != null) {
                level.next = curr.left;
                level = level.next;
            }
            if (curr.right != null) {
                level.next = curr.right;
                level = level.next;
            }
            curr = curr.next;
            if (curr == null) {
                // next level
                curr = head.next;
                head = null;
            }
        }
        return root;
    }

Review：

Linkedin: How we reduced latency and cost-to-serve by merging two systems

这篇文章介绍了一个在微服务架构中不常见的场景，合并服务。首先拆分服务更符合一般架构发展方向，使服务更加松耦合、隔离影响、更易扩展等，但是这也带了更多延迟、硬件资源消耗、服务成本和运营成本。文章通过一个具体案例结合一些记录数据，证明了他们减少了服务延迟并减少了大量成本（适合给老板看）。总结出拆分与合并是一个平衡过程，需要不断根据设计落地后运行效果重新评估。

语言积累：Identity services, power many other applications, downstream services, cost-to-serve, operational overheads, re-evaluate some of our assumptions, incurred additional network hops, a right balance to strike in deconstructing systems, gradually ramped the change, decommission, annual savings

Tip：

Asynchonous vs Non-blocking

异步与非阻塞，在不同语境和场景下定义不同，有时可以互换，有时却略有不同。

1、在网络编程的IO模型中

在经典的《UNIX Network Programming》第六章中，作者将IO模型分为 blocking IO、nonblocking IO、IO multiplexing (select, poll)、signal driven IO、asynchronous IO (aio) 五种模型。首先将所有IO操作分为1等待数据阶段和2从内核复制数据到用户进程阶段，前4种模型因为都需要在阶段2阻塞（blocking IO 和 IO multiplexing 在阶段1阻塞，nonblocking IO 和 signal driven IO 在阶段1不阻塞）。按照 POSIX 定义：同步IO操作会使请求进程阻塞直到IO操作完成，异步IO操作不会引起请求进程阻塞。因此前四种都是同步模型，只有最后一种 aio 模型在所有阶段都不阻塞，符合异步定义。

其中值得注意的是 ，虽然 IO 多路复用模型（select、poll）在两个阶段都会阻塞，但它第一个 select 调用可以同时等待多个 IO 事件（这种循环称为 polling），这比单独 polling 一个 nonblocking IO 更加高效，在优化为 epoll 后更是处理海量连接的关键技术。

2、在更通用的一般编程语境中

首先阻塞和同步是一回事，即调用一个API，它阻塞当前线程直到返回结果回来。

其次，非阻塞API指调用它时如果不能立刻返回结果，就返回错误而不进行等待，例如 tryLock() 这类函数，与此同时有别的办法进行更有效的等待，比如做其他事、过会重试或快速失败，一般不会 polling in a tight loop。

最后，异步是指该API始终立刻返回，并在后台（其他线程）继续完成该请求，并通过一些其他方式拿到结果。

3、在 OpenResty 等协程场景中

在学习 OpenResty 的过程中，情况又有些不同，例如调用 os.execute("sleep 1"), ngx.sleep(1), shell.run([[sleep 1]]) 时会产生非常不同的影响。第一个 os.execute 是原生 Lua 提供用于命令调用的阻塞 API，第二个是 OpenResty 提供的非阻塞 API，第三个是 OpenResty 新版1.15中提供的非阻塞 shell 调用。使用 sleep 暂停睡眠还可以做成非阻塞，那后续执行什么？这似乎有点不可思议！

这是因为，基于Nginx的模型，OpenResty 代码是执行在一个进程中的不同协程中，这时的阻塞和非阻塞是针对这整个进程而言的，第一个阻塞 API 即 os.execute("sleep 1") 会指让整个进程处于休眠状态，使 CPU 空闲（如果对核心进行了亲和性绑定），而调用后两种非阻塞 API，则当前协程通过 yield 进行让步，使调度器执行别的协程，直到满足执行条件后再回来 resume。

参考：

https://stackoverflow.com/questions/2625493/asynchronous-vs-non-blocking

https://moonbingbing.gitbooks.io/openresty-best-practices/content/ngx_lua/sleep.html

Share：

从抄书到开源之巅：章亦春的程序人生

最近在学习 OpenResty 的过程中，不断出现 agentzh 张亦春的名字，也不断产生好奇：春哥是如何创造这么优秀的项目，以及如何推动这么成功的周边生态，要知道 OpenResty 在国外比国内更流行，不像国内那些大公司以战略和 KPI 推动的所谓开源项目，不仅很少走出国门甚至很少走出关系户。

看到这篇几年前的春哥的访谈，一顿觉得大牛果然是不一样，中学时代就有那么多神奇的历史，更不用说大学时代就能得到 Perl 发明人的赞扬这类成就。但是一顿刺激恐怕过几天就不剩下什么，况且盲目和别人比较也只是平添心魔（应该与昨天的自己比较），仔细想想我觉得以下两点启发更多：

第一点，抄书和抄代码。春哥举例到他中学时在没有人教（估计2000年时他也无法上网）的情况下自学《C语言程序设计》，因为看不懂也不知道学习方法，就从第一页开始一个字一个字地手抄，直到觉得不用继续手抄。另一个他是学习 Nginx 源码时，白天上班对着 Kindle 抄源码，晚上回家来回踱步在脑海回想白天抄的代码，直到融会贯通，理解其奥妙。他提到这些方法的奥秘是延缓阅读速度，不会遗漏每一个重要细节：眼到，手到，心到。

这点我也逐步领悟到，慢其实是一种快，很多时候追求速度，长期看反而是最慢的路径，比如很多基础课程（像操作系统、网络、体系），看一堆速成和浅薄的教程，也不如静下心来啃一本系统的大部头收获更多。另外对于自己经常面对的领域技术，如果每次通过速成解决当前问题，那今后也会遇到更多问题并且不断反复，反而更应该花时间系统性的通读文档或源码等。

第二点，始终保护好最初对编程的好奇和兴趣。主流技术和思想在不断变化，同时每个人都有最适合自己的成长道路，在这种情况下只有向内追寻和坚持，才能逐步积累出自己独特的东西，而这也正是坚持的正向反馈。