#ARTS #2021 #Week-26 July 4th, 2021

Algorithm - 算法

本周算法完成的是 [[归并排序]] 的相关内容，包括最常见的递归版、类似于 [[希尔排序]] 的迭代算法，同时完成了三道利用归并排序原理的题目：[[求数组小和]]、[[求数组中的逆序对数量]]、[[求数组中的大两倍数对数量]]，其中最后一题还涉及到了 [[滑动窗口]] 的相关知识

Review - 英文技术文章阅读与点评

本周的深度阅读我选择了著名的 The C10K problem，在加入至我的 Omni Focus 两年后终于想起来阅读了……

Review 这一标题说的是「点评」，其实一定程度上有不要完全阅读学习而是融入自己的思考做出一些批判的意味，在阅读这篇文章前、这篇最初于 2003 年完成的文章前、这篇仅仅解决了一万并发的文章前，我确实是想着融入自己的思考做出一些现代更好的解决方案的，然而，读了之后，我剩下的几乎只是惊叹。

这篇文章出现于千兆网络出现的时代，即网络瓶颈由硬件走向软件的时代，那时作者所描述的五种解决方案，可以说哪怕现在都是主流。

方案一：使用同步非阻塞 Level-Triggered（水平触发）

作者这里引用的是经典的 select 和 poll，并且也描述了 /dev/poll, kqueue, epoll

作者在这里并没有对 select 到 poll 的具体原因做出详细说明，仅仅是点明了不受 FD_SETSIZE 限制，因此我打算借此简单的扩展开来。

如果在网上搜索过 select 和 poll 的区别，可以看到说法都是「select 最多 1024 个」，但这其实并不准确，这一限制由 FD_SETSIZE 所设定，在 glibc 实现中被错误的硬编码为了 1024，但真正导致 select 被放弃全面转向 poll 的原因实际上是资源占用 —— 如果阅读文档可以看到，select 所接收的参数只有一个 fd_set 结构体，而不是一个数组，这一结构体大小其实是固定的 —— 固定容纳长达 FD_SETSIZE = 1024 个文件描述符的大小，并且所使用的文件描述符也被强制限制为了 0~(FD_SETSIZE-1) 即 0-1023，也就是说，一方面，即使所需要监听的文件描述符只有一个，也会造成多余空间被浪费并且出现多余的拷贝代价，而另一方面，即使你要监听的文件描述符只有 1 个，而这个恰巧超过了 1023 那么也是没有办法的 —— select 使用「数组下标」作为了文件描述符。

在我之前所知晓的 poll 到 epoll 的升级的主要原因在于 poll 尽管没有了 select 的限制，但还是每次都需要遍历来检测变化情况，当所监听的文件描述符过多，就会造成实际上每次变动的很少、也因此会造成遍历的代价中浪费占用了绝大多数。

而文章中点名了 poll 的另一个问题，或者说是非阻塞水平触发 IO 的另一个问题：对于文件类型的特殊处理。在 Linux 中，O_NONBLOCK 对于文件是没有意义的，在打开时文件不会被真的读入内存，而在 read/write 时会内核触发缺页异常将相应内容真的读入内存，在高并发场景下，这一换页是同步阻塞的，并且即使使用了 sendfile 等相关代价也无法忽视，作者所提出的一大解决方案是利用 mmap + mincore 来作为 workaround

方案二：使用同步非阻塞 Edge-Triggered（边缘触发）

这一方案可以说是目前 epoll 的杀手锏，我是真的没想到那个年代就已经有了……

阅读这里的时候额外的学习到了 Realtime Signal，即利用系统的信号处理机制，当相关的文件描述符状态变更时发送信号以完成边缘触发的能力，当然这一方案应当是只存在历史了，毕竟利用信号量进行编程太困难了，目前主流应该还是 epoll

方案三：异步 IO

这是一个到现在都没有真的实现的方案，也是一个理想方案，文章中所写的内容可以认为基本「过时」了，目前的 Linux 主流发展方向是 io_uring ，并且是准备让所有的系统调用均支持异步而非单纯的 IO 相关操作

方案四：使用线程 + 同步阻塞 IO

这里所讨论的又让我一惊，在读标题时我想到的其实就是经典的多线程模型，然而万万没想到作者在这里讨论的竟然是用户线程，包括现在 Go 杀手锏一般的 M:N 协程机制

方案五：直接把服务器代码写到内核里

这就。。只能说，当年的程序员遇到问题就是搞内核，哪像现在，真遇到内核问题可能只能听天由命了，定位问题都难……

还是方案五：把网络协议栈放到 userspace

这不就是 DPDK？？？真的，完全没想到，我现在能想到的、使用到的高性能解决方案真的在过去就已经提出了概念甚至有了实现

我们现在真的就是「站在巨人的肩膀上」，尽管目前问题已经远远超出了十万级达到了千万甚至亿级，但整体的解决方案依旧是殊途同归

Tip - 本周学到的技术技巧

Redis 利用位图实现连续签到统计

当年我的做法是利用数据库，每次签到存一条签到数据，在签到时查询前一天是否签到过，如果签到过读前一天的连续签到次数+1 写入这次的，如果没有签到过将这次的置为第一天。

真的没想到，Redis 还能这么用，对于签到这种并不需要存储特别精确的可以说使用 Redis bitmap 存储无论在时间还是空间上都是最优解了

Share - 写一篇技术文章

epoll 中的边缘触发