ARTS 是左耳朵耗子发起的一项打卡活动，每个人每周至少一个 Algorithm，Review 一篇英文文章，总结一个工作中的技术 Tip，以及 Share 一个传递价值观的东西。我非常认同这些行为的价值，决定参与，计划坚持至少一年，看看能带来什么改变。这是第一周内容，花了不少时间，但是它至少解决了很久没有输出内容的困境，使断更已久的博客继续活了下来，感觉不错！

Algorithm：

160： Intersection of Two Linked Lists (Easy)

这道题是要找出两个链表的交点，要求时间 On 空间 O1，我的思路是先分别遍历一遍获得队列长度（此时如果终点不相同说明不相交返回 null），获得长度之差 n 后，让长的队列先遍历 n 个，然后二者就对齐了，一起遍历，返回相同节点。看过答案后发现我的思路和代码太啰嗦，根据公式 a + c + b = b + c + a（c是两个队列公共部分长度），让两个队列遍历到终点后选择相反队列起点继续遍历，长度之差自然就消失了，随后一定会同步，这里还有个技巧是根据节点本身，而不是 next 对象判断队列遍历结束，可以使没有相交和相交两种情况融合为一个 if pa != pb 判断（这也要求下面判断 a、b是否为空，而不是a.next和b.next是否为空，避免漏掉都是 null 的情况导致无限循环）。

        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            ListNode pa = headA, pb = headB;
            while (pa != pb) {
                pa = pa == null ? headB : pa.next;
                pb = pb == null ? headA : pb.next;
            }
            return pa;
        }

Review：

Efficient data transfer through zero copy

这是一篇介绍零拷贝概念的经典文章，非常清晰易懂，亮点是将应用程序优化同操作系统知识、组成原理知识都联系起来，深入浅出，值得收藏。它以硬盘读数据然后用 socket 发送这一高频场景讲起，分别介绍了传统 IO API（使用 read、send 系统调用）和 NIO API 中的 transferTo（使用 sendfile 系统调用）的处理过程，包括系统调用产生的内核态切换流程。

在传统 API 中，数据从硬盘复制到内核 Read Buffer、再到用户程序内存、再到内核 Socket Buffer、最后到达网卡缓存中，一共 4 次复制过程（两次 sys call 产生 4 次上下文切换）。使用 sendTo 调用时可以使数据复制过程降至 2 次（省去内核地址和用户程序内存之间的两次复制），实际上甚至可以达到仅 1 次复制，这依赖 Linux 2.4 版内核开始支持的网卡 gather operations 技术（尚不理解），DMA 直接操作网卡读内核缓存，使内核 Read Buffer 到 Socket Buffer 的复制过程也省去了，只剩下从硬盘读到内核缓存一次复制。根据文中不同场景性能测试零拷贝可以减少 65% 耗时，虽然 CPU 计算东西很快，但是并不擅长复制大量数据，每一小块数据复制都要经过内存 - 多级 Cache - 指令执行这样的步骤，在有限并行度上进行顺序读写。

零拷贝概念强调的是没有通过 CPU 复制数据，而外围设备（网卡、硬盘）和内存之间数据传输是通过 DMA 控制器进行。我觉得该技术本身很简单，核心就是 sendTo 和 send 系统调用的差异，而提出零拷贝似乎有创造概念之嫌疑，因为该场景是读取后立刻就发送的数据复制，假如需要对数据进行任何逻辑处理后再发送（例如序列化、编辑等），则依然需要传统 API 以及 CPU 参与。

Tip：

非对称加密应用：ssh免密登陆、中间人攻击、Trust on first use

最近为了方便 rsync 传输文件，把树莓派、VPS 等所有 ssh 登陆都改为免密登陆。提到 ssh 免密登陆，很容易想到一种方法是将密码提前存下来，在登陆远程服务器时自动提交给对方进行验证。但实际上是要把本机的公钥 public-key 放到服务器上，这里谁验证谁似乎反过来了，这是为什么？

这是因为我错误的把对称加密思路套用在了 ssh 所使用的非对称加密中，对称加密最大的问题时需要在安全连接建立前将密码传给对方以供验证（当 ssh 连接建立后，连接通道是加密的、安全的），这个过程中如果有中间人监听到密码凭证，进而伪造身份进行中间人攻击（Man-in-the-middle attack，MITM，攻击者在中间分别和两端通信，控制整个会话），实际上更大的问题是密码泄漏以及可能存在暴力破解，甚至还有撞库等无法控制的外部因素，免密登陆则从根本上不再需要密码（禁止密码登陆）可以避免了这些问题，而更关注 MITM。

而使用非对称加密，放在对方服务器上的是自己的、可以公开的公钥 public-key，对方将其存放到 authorized_keys 文件中，意味着认可该身份连接，相当于白名单，因此剩下的问题就变成了：申请连接时，服务器如何判断其身份真的是白名单内的客户（而不是别人拿着公钥冒充的）？

首先客户端会将公钥发给服务器，服务器在白名单中匹配到后会发起 challenge 质询请求，即用该公钥加密这个质询，发给客户端，客户端使用私钥解密后再发给服务器，服务器判断是自己刚刚产生质询则通过认证。实际上在这个认证阶段前面还有版本协商阶段、密钥后算法协商阶段，因此认证阶段的一切数据传输已经经过了会话密钥加密，这是对称加密，但是通过用服务器的公钥私钥进行非对称加密协商得到的，这也是客户端 know_hosts 文件的目的，记录服务器的公钥，记录已连接过的信息。如果上面过程已经正常建立，则中间人攻击无法实施，只有第一次双方建立连接，交换公钥时就存在中间人攻击，攻击者记录并篡改双方交换公钥都是自己的，才有可能实现。这种模式称为 Trust on first use（TOFU），和未知端点交互时，以第一次使用（连接）的信息当作后续信任依据。

参考：

SSH登录认证详解

图解SSH原理

图解SSH原理及两种登录方式 （图很好，文字有一些不正确的地方）

Share：

Writing Is Thinking

观点1：Writing Is Thinking，写作是一种独特和必要的思考形式。

写作是一个线性过程，迫使大脑中的各种松散、纠缠的连接，通过一个狭窄的缝隙进行严格检查。讨论扩大了各种可能性，而写作则将其缩小为最必要和本质的部分。正如我之前总结的，学习和输入类似于 map/flatMap 操作，而总结和输出类似于 reduce 操作，从 map 到 reduce 很难，因为需要 shuffle、sort、merge、schedule、rebalance 等一系列努力，但是如果不进行 reduce，原始数据难以发挥价值，存在检索缓慢、脏数据和异常格式，甚至因为存储有限而被逐渐清理。

观点2：Just Write，写就对了。

一位陶艺老师将她的课堂分为两组。 第一组将根据他们制作的最好的一个陶罐来评分。 第二组将根据他们制作的陶罐数量来评分。 学期末，邀请两组学生分享他们最好的陶罐， 然而最好的陶罐是第二组学生生产的，他们原本任务是数量而不是质量。非常不可思议，而又合情合理，量变是质变的前提。只有写足够多的内容，才能真正熟练掌握这一技能，形成不断思考、输出、反馈形成正向循环。