Bojie Li (李博杰)

（转载自 微软亚洲研究院）

国际计算机系统架构体系学术会议SOSP 2017（Symposium on Operating Systems Principles）此刻正在上海如火如荼地举行。SOSP作为计算机系统领域最顶级的学术大会之一，若论文有幸被收录，影响力自然不言而喻。前不久，微软亚洲研究院与中国科技大学的联合培养博士生李博杰的一篇关于内存键值存储的论文就被该会议收录了。对于绝大多数非计算机行业的人而言，“内存键值存储”可谓大脑知识的盲区，是好奇心号船舶的一片深海。但对于92年的李博杰来说，这却已成为他生活的一部分。关于他的成长故事，可以从这个对我们陌生，而对他却万分熟悉的词语讲起。

Driven by explosive demand on computing power and slowdown of Moore’s law, cloud providers have started to deploy FPGAs into datacenters for workload offloading and acceleration. In this paper, we propose an operating system for FPGA, called Feniks, to facilitate large scale FPGA deployment in datacenters.

Feniks provides abstracted interface for FPGA accelerators, so that FPGA developers can get rid of underlying hardware details. In addtion, Feniks also provides (1) development and runtime environment for accelerators to share an FPGA chip in efficient way; (2) direct access to server’s resource like storage and coprocessor over PCIe bus; (3) an FPGA resource allocation framework throughout a datacenter.

We implemented an initial prototype of Feniks on Catapult Shell and Altera Stratix V FPGA. Our experiements show that device-to-device communication over PCIe is feasible and efficient. A case study shows multiple accelerators can share an FPGA chip independently and efficiently.

（转载自 微软亚洲研究院）

2017年6月19-20日，开源技术盛会LinuxCon + ContainerCon + CloudOpen（LC3）首次在中国举行。两天议程满满，包括 17 个主旨演讲、8 个分会场的 88 场技术报告和微软等公司的技术展览和动手实验。LinuxCon 吸引了众多国际国内互联网巨头、电信巨头和上千名业界人士参会，包括Linux创始人Linus Torvalds，大咖齐聚共同关注业界动态。

The First Asia-Pacific Workshop on Networking (APNet’17) Invited Talk:

Implementing ClickNP: Highly Flexible and High-Performance Network Processing with FPGA + CPU

Abstract: ClickNP is a highly flexible and high-performance network processing platform with reconfigurable hardware, published in SIGCOMM’16. This talk will share our implementation experience of the ClickNP system, both before and after paper submission. Throughout 8 months, we developed 100 elements and 5 network functions for the SIGCOMM paper, resulting in 1K commits and 20K lines of code. After the paper submission, ClickNP continues to develop and extends to a general-purpose FPGA programming framework in our research team, resulting in 300 elements, 86 application projects and 80K lines of code.

(1) Although with high-level languages, programming FPGA is still much more challenging than CPU. We had hard times to understand the behavior and pitfalls of black-box compilers, and shared our findings by enforcing coding style in the ClickNP language design and providing optimizations in the ClickNP compiler.

(2) OpenCL host to kernel communication model is a poor fit for network processing. This talk will elaborate internals of the high performance communication channel between CPU and FPGA.

(3) FPGA compilation takes hours, run-time debugging is hard, and simulation is inaccurate. For case study, we show how we identified and resolved a deadlock bug in the L4 load balancer, leveraging ClickNP debugging functionalities.

[Conference Website] [Slides]

Limited by the small on-chip memory, hardware-based transport typically implements go-back-N loss recovery mechanism, which costs very few memory but is well-known to perform inferior even under small packet loss ratio. We present MELO, an efficient selective retransmission mechanism for hardware-based transport, which consumes only a constant small memory regardless of the number of concurrent connections. Specifically, MELO employs an architectural separation between data and meta data storage and uses a shared bits pool allocation mechanism to reduce meta data on-chip memory footprint. By only adding in average 23B extra on-chip states for each connection, MELO achieves up to 14.02x throughput while reduces 99% tail FCT by 3.11x compared with go-back-N under certain loss ratio.

（本文首发于 知乎，后转载至 微软亚洲研究院）

我们并不是用 FPGA 代替 CPU，而是用 FPGA 加速适合它的计算任务，其他任务仍然在 CPU 上完成，让 FPGA 和 CPU 协同工作。

本回答将涵盖三个问题：

1. 为什么使用 FPGA，相比 CPU、GPU、ASIC（专用芯片）有什么特点？
2. 微软的 FPGA 部署在哪里？FPGA 之间、FPGA 与 CPU 之间是如何通信的？
3. 未来 FPGA 在云计算平台中应充当怎样的角色？仅仅是像 GPU 一样的计算加速卡吗？

（本文首发于 知乎）

中国科大 LUG 的 @高一凡 在 LUG HTTP 代理服务器上部署了 Linux 4.9 的 TCP BBR 拥塞控制算法。从科大的移动出口到新加坡 DigitalOcean 的实测下载速度从 647 KB/s 提高到了 22.1 MB/s（截屏如下）。

（应评论区各位 dalao 要求，补充测试环境说明：是在新加坡的服务器上设置了 BBR，新加坡的服务器是数据的发送方。这个服务器是访问墙外资源的 HTTP 代理。科大移动出口到 DigitalOcean 之间不是 dedicated 的专线，是走的公网，科大移动出口这边是 1 Gbps 无限速（但是要跟其他人 share），DigitalOcean 实测是限速 200 Mbps。RTT 是 66 ms。实测结果这么好，也是因为大多数人用的是 TCP Cubic (Linux) / Compound TCP (Windows)，在有一定丢包率的情况下，TCP BBR 更加激进，抢占了更多的公网带宽。因此也是有些不道德的感觉。）

此次 Google 提交到 Linux 主线并发表在 ACM queue 期刊上的 TCP BBR 拥塞控制算法，继承了 Google “先在生产环境部署，再开源和发论文” 的研究传统。TCP BBR 已经在 Youtube 服务器和 Google 跨数据中心的内部广域网（B4）上部署。

TCP BBR 致力于解决两个问题：

1. 在有一定丢包率的网络链路上充分利用带宽。
2. 降低网络链路上的 buffer 占用率，从而降低延迟。

TCP 拥塞控制的目标是最大化利用网络上瓶颈链路的带宽。一条网络链路就像一条水管，要想用满这条水管，最好的办法就是给这根水管灌满水，也就是：
水管内的水的数量 = 水管的容积 = 水管粗细 × 水管长度
换成网络的名词，也就是：
网络内尚未被确认收到的数据包数量 = 网络链路上能容纳的数据包数量 = 链路带宽 × 往返延迟

TCP 维护一个发送窗口，估计当前网络链路上能容纳的数据包数量，希望在有数据可发的情况下，回来一个确认包就发出一个数据包，总是保持发送窗口那么多个包在网络中流动。

TCP 与水管的类比示意（图片来源：Van Jacobson，Congestion Avoidance and Control，1988）
如何估计水管的容积呢？一种大家都能想到的方法是不断往里灌水，直到溢出来为止。标准 TCP 中的拥塞控制算法也类似：不断增加发送窗口，直到发现开始丢包。这就是所谓的 ”加性增，乘性减”，也就是当收到一个确认消息的时候慢慢增加发送窗口，当确认一个包丢掉的时候较快地减小发送窗口。

标准 TCP 的这种做法有两个问题：

首先，假定网络中的丢包都是由于拥塞导致（网络设备的缓冲区放不下了，只好丢掉一些数据包）。事实上网络中有可能存在传输错误导致的丢包，基于丢包的拥塞控制算法并不能区分拥塞丢包和错误丢包。在数据中心内部，错误丢包率在十万分之一（1e-5）的量级；在广域网上，错误丢包率一般要高得多。

更重要的是，“加性增，乘性减” 的拥塞控制算法要能正常工作，错误丢包率需要与发送窗口的平方成反比。数据中心内的延迟一般是 10-100 微秒，带宽 10-40 Gbps，乘起来得到稳定的发送窗口为 12.5 KB 到 500 KB。而广域网上的带宽可能是 100 Mbps，延迟 100 毫秒，乘起来得到稳定的发送窗口为 10 MB。广域网上的发送窗口比数据中心网络高 1-2 个数量级，错误丢包率就需要低 2-4 个数量级才能正常工作。因此标准 TCP 在有一定错误丢包率的长肥管道（long-fat pipe，即延迟高、带宽大的链路）上只会收敛到一个很小的发送窗口。这就是很多时候客户端和服务器都有很大带宽，运营商核心网络也没占满，但下载速度很慢，甚至下载到一半就没速度了的一个原因。

其次，网络中会有一些 buffer，就像输液管里中间膨大的部分，用于吸收网络中的流量波动。由于标准 TCP 是通过 “灌满水管” 的方式来估算发送窗口的，在连接的开始阶段，buffer 会被倾向于占满。后续 buffer 的占用会逐渐减少，但是并不会完全消失。客户端估计的水管容积（发送窗口大小）总是略大于水管中除去膨大部分的容积。这个问题被称为 bufferbloat（缓冲区膨胀）。

缓冲区膨胀现象图示

缓冲区膨胀有两个危害：

1. 增加网络延迟。buffer 里面的东西越多，要等的时间就越长嘛。
2. 共享网络瓶颈的连接较多时，可能导致缓冲区被填满而丢包。很多人把这种丢包认为是发生了网络拥塞，实则不然。

往返延迟随时间的变化。红线：标准 TCP（可见周期性的延迟变化，以及 buffer 几乎总是被填满）；绿线：TCP BBR （图片引自 Google 在 ACM queue 2016 年 9-10 月刊上的论文 [1]，下同）

有很多论文提出在网络设备上把当前缓冲区大小的信息反馈给终端，比如在数据中心广泛应用的 ECN（Explicit Congestion Notification）。然而广域网上网络设备众多，更新换代困难，需要网络设备介入的方案很难大范围部署。

TCP BBR 是怎样解决以上两个问题的呢？

1. 既然不容易区分拥塞丢包和错误丢包，TCP BBR 就干脆不考虑丢包。
2. 既然灌满水管的方式容易造成缓冲区膨胀，TCP BBR 就分别估计带宽和延迟，而不是直接估计水管的容积。

带宽和延迟的乘积就是发送窗口应有的大小。发明于 2002 年并已进入 Linux 内核的 TCP Westwood 拥塞控制算法，就是分别估计带宽和延迟，并计算其乘积作为发送窗口。然而带宽和延迟就像粒子的位置和动量，是没办法同时测准的：要测量最大带宽，就要把水管灌满，缓冲区中有一定量的数据包，此时延迟就是较高的；要测量最低延迟，就要保证缓冲区为空，网络里的流量越少越好，但此时带宽就是较低的。

TCP BBR 解决带宽和延迟无法同时测准的方法是：交替测量带宽和延迟；用一段时间内的带宽极大值和延迟极小值作为估计值。

在连接刚建立的时候，TCP BBR 采用类似标准 TCP 的慢启动，指数增长发送速率。然而标准 TCP 遇到任何一个丢包就会立即进入拥塞避免阶段，它的本意是填满水管之后进入拥塞避免，然而（1）如果链路的错误丢包率较高，没等到水管填满就放弃了；（2）如果网络里有 buffer，总要把缓冲区填满了才会放弃。

TCP BBR 则是根据收到的确认包，发现有效带宽不再增长时，就进入拥塞避免阶段。（1）链路的错误丢包率只要不太高，对 BBR 没有影响；（2）当发送速率增长到开始占用 buffer 的时候，有效带宽不再增长，BBR 就及时放弃了（事实上放弃的时候占的是 3 倍带宽 × 延迟，后面会把多出来的 2 倍 buffer 清掉），这样就不会把缓冲区填满。

发送窗口与往返延迟和有效带宽的关系。BBR 会在左右两侧的拐点之间停下，基于丢包的标准 TCP 会在右侧拐点停下（图片引自 TCP BBR 论文，下同）
在慢启动过程中，由于 buffer 在前期几乎没被占用，延迟的最小值就是延迟的初始估计；慢启动结束时的最大有效带宽就是带宽的初始估计。

慢启动结束后，为了把多占用的 2 倍带宽 × 延迟消耗掉，BBR 将进入排空（drain）阶段，指数降低发送速率，此时 buffer 里的包就被慢慢排空，直到往返延迟不再降低。如下图绿线所示。

TCP BBR（绿线）与标准 TCP（红线）有效带宽和往返延迟的比较
排空阶段结束后，BBR 进入稳定运行状态，交替探测带宽和延迟。由于网络带宽的变化比延迟的变化更频繁，BBR 稳定状态的绝大多数时间处于带宽探测阶段。带宽探测阶段是一个正反馈系统：定期尝试增加发包速率，如果收到确认的速率也增加了，就进一步增加发包速率。

具体来说，以每 8 个往返延迟为周期，在第一个往返的时间里，BBR 尝试增加发包速率 1/4（即以估计带宽的 5/4 速度发送）。在第二个往返的时间里，为了把前一个往返多发出来的包排空，BBR 在估计带宽的基础上降低 1/4 作为发包速率。剩下 6 个往返的时间里，BBR 使用估计的带宽发包。

当网络带宽增长一倍的时候，每个周期估计带宽会增长 1/4，每个周期为 8 个往返延迟。其中向上的尖峰是尝试增加发包速率 1/4，向下的尖峰是降低发包速率 1/4（排空阶段），后面 6 个往返延迟，使用更新后的估计带宽。3 个周期，即 24 个往返延迟后，估计带宽达到增长后的网络带宽。

网络带宽增长一倍时的行为。绿线为网络中包的数量，蓝线为延迟
当网络带宽降低一半的时候，多出来的包占用了 buffer，导致网络中包的延迟显著增加（下图蓝线），有效带宽降低一半。延迟是使用极小值作为估计，增加的实际延迟不会反映到估计延迟（除非在延迟探测阶段，下面会讲）。带宽的估计则是使用一段滑动窗口时间内的极大值，当之前的估计值超时（移出滑动窗口）之后，降低一半后的有效带宽就会变成估计带宽。估计带宽减半后，发送窗口减半，发送端没有窗口无法发包，buffer 被逐渐排空。

网络带宽降低一半时的行为。绿线为网络中包的数量，蓝线为延迟
当带宽增加一倍时，BBR 仅用 1.5 秒就收敛了；而当带宽降低一半时，BBR 需要 4 秒才能收敛。前者由于带宽增长是指数级的；后者主要是由于带宽估计采用滑动窗口内的极大值，需要一定时间有效带宽的下降才能反馈到带宽估计中。

当网络带宽保持不变的时候，稳定状态下的 TCP BBR 是下图这样的：（我们前面看到过这张图）可见每 8 个往返延迟为周期的延迟细微变化。

往返延迟随时间的变化。红线：标准 TCP；绿线：TCP BBR
上面介绍了 BBR 稳定状态下的带宽探测阶段，那么什么时候探测延迟呢？在带宽探测阶段中，估计延迟始终是使用极小值，如果实际延迟真的增加了怎么办？TCP BBR 每过 10 秒，如果估计延迟没有改变（也就是没有发现一个更低的延迟），就进入延迟探测阶段。延迟探测阶段持续的时间仅为 200 毫秒（或一个往返延迟，如果后者更大），这段时间里发送窗口固定为 4 个包，也就是几乎不发包。这段时间内测得的最小延迟作为新的延迟估计。也就是说，大约有 2% 的时间 BBR 用极低的发包速率来测量延迟。

TCP BBR 还使用 pacing 的方法降低发包时的 burstiness，减少突然传输的一串包导致缓冲区膨胀。发包的 burstiness 可能由两个原因引起：

1. 数据接收方为了节约带宽，把多个确认（ACK）包累积成一个发出，这叫做 ACK Compression。数据发送方收到这个累积确认包后，如果没有 pacing，就会发出一连串的数据包。
2. 下面我们来看 TCP BBR 的效果如何。

首先看 BBR 试图解决的第一个问题：在有随机丢包情况下的吞吐量。如下图所示，只要有万分之一的丢包率，标准 TCP 的带宽就只剩 30%；千分之一丢包率时只剩 10%；有百分之一的丢包率时几乎就卡住了。而 TCP BBR 在丢包率 5% 以下几乎没有带宽损失，在丢包率 15% 的时候仍有 75% 带宽。数据发送方没有足够的数据可传输，积累了一定量的空闲发送窗口。当应用层突然需要传输较多的数据时，如果没有 pacing，就会把空闲发送窗口大小这么多数据一股脑发出去。

100 Mbps，100ms 下的丢包率和有效带宽（红线：标准 TCP，绿线：TCP BBR）

异地数据中心间跨广域网的传输往往是高带宽、高延迟的，且有一定丢包率，TCP BBR 可以显著提高传输速度。这也是中国科大 LUG HTTP 代理服务器和 Google 广域网（B4）部署 TCP BBR 的主要原因。
再来看 BBR 试图解决的第二个问题：降低延迟，减少缓冲区膨胀。如下图所示，标准 TCP 倾向于把缓冲区填满，缓冲区越大，延迟就越高。当用户的网络接入速度很慢时，这个延迟可能超过操作系统连接建立的超时时间，导致连接建立失败。使用 TCP BBR 就可以避免这个问题。

缓冲区大小与延迟的关系（红线：标准 TCP，绿线：TCP BBR）
Youtube 部署了 TCP BBR 之后，全球范围的中位数延迟降低了 53%（也就是快了一倍），发展中国家的中位数延迟降低了 80%（也就是快了 4 倍）。从下图可见，延迟越高的用户，采用 TCP BBR 后的延迟下降比例越高，原来需要 10 秒的现在只要 2 秒了。如果您的网站需要让用 GPRS 或者慢速 WiFi 接入网络的用户也能流畅访问，不妨试试 TCP BBR。

标准 TCP 与 TCP BBR 的往返延迟中位数之比
综上，TCP BBR 不再使用丢包作为拥塞的信号，也不使用 “加性增，乘性减” 来维护发送窗口大小，而是分别估计极大带宽和极小延迟，把它们的乘积作为发送窗口大小。

BBR 的连接开始阶段由慢启动、排空两阶段构成。为了解决带宽和延迟不易同时测准的问题，BBR 在连接稳定后交替探测带宽和延迟，其中探测带宽阶段占绝大部分时间，通过正反馈和周期性的带宽增益尝试来快速响应可用带宽变化；偶尔的探测延迟阶段发包速率很慢，用于测准延迟。

BBR 解决了两个问题：

1. 在有一定丢包率的网络链路上充分利用带宽。非常适合高延迟、高带宽的网络链路。
2. 降低网络链路上的 buffer 占用率，从而降低延迟。非常适合慢速接入网络的用户。

看到评论区很多客户端和服务器哪个部署 TCP BBR 有效的问题，需要提醒：TCP 拥塞控制算法是数据的发送端决定发送窗口，因此在哪边部署，就对哪边发出的数据有效。如果是下载，就应在服务器部署；如果是上传，就应在客户端部署。

如果希望加速访问国外网站的速度，且下载流量远高于上传流量，在客户端上部署 TCP BBR（或者任何基于 TCP 拥塞控制的加速算法）是没什么效果的。需要在 VPN 的国外出口端部署 TCP BBR，并做 TCP Termination & TCP Proxy。也就是客户建立连接事实上是跟 VPN 的国外出口服务器建联，国外出口服务器再去跟目标服务器建联，使得丢包率高、延迟大的这一段（从客户端到国外出口）是部署了 BBR 的国外出口服务器在发送数据。或者在 VPN 的国外出口端部署 BBR 并做 HTTP(S) Proxy，原理相同。

大概是由于 ACM queue 的篇幅限制和目标读者，这篇论文并没有讨论（仅有拥塞丢包情况下）TCP BBR 与标准 TCP 的公平性。也没有讨论 BBR 与现有拥塞控制算法的比较，如基于往返延迟的（如 TCP Vegas）、综合丢包和延迟因素的（如 Compound TCP、TCP Westwood+）、基于网络设备提供拥塞信息的（如 ECN）、网络设备采用新调度策略的（如 CoDel）。期待 Google 发表更详细的论文，也期待各位同行报告 TCP BBR 在实验或生产环境中的性能。

本人不是 TCP 拥塞控制领域的专家，如有错漏不当之处，恳请指正。

[1] Cardwell, Neal, et al. “BBR: Congestion-Based Congestion Control.” Queue14.5 (2016): 50.

Windows API 里面有一个 Beep 函数，作用是发出蜂鸣声。这个蜂鸣功能历史悠久，BIOS 的报警声就是从主板蜂鸣器里出来的，其原理是调用几乎每台机器都有的 Programmable Interval Timer (PIT)。可惜从 Windows Vista 开始，这个函数的行为变成了调用扬声器发声，而不再是使用主板蜂鸣器发声了。

如何在 Windows Vista 以上的系统里使用主板蜂鸣器发声呢？是不是必须写个 Windows 驱动呢？其实利用 WinDbg 内核调试器的功能，只需要一行代码就能搞定。下面一行代码以 800 Hz 的频率让主板蜂鸣器发声 1000 毫秒。

1

n 10; r $t0=800; r $t1=1000; ob 0x43 0xb6; ob 0x42 (1193180/$t0)&0xff; ob 0x42 (1193180/$t0)>>8; ob 0x61 3; .sleep $t1; ob 0x61 0

使用方法：

1. 下载安装 WinDbg
2. 打开内核调试。管理员权限运行

   1	bcdedit /debug on

   ，重启。
3. 管理员权限打开 WinDbg，File->Kernel Debug，选择 “Local” 选项卡，确定。不出意外的话，就会进入 kernel debug session。
4. 输入这段代码，如果你的主板蜂鸣器正常的话，应该就能听到蜂鸣声了。（可惜，截图里不带声音）
   

原理：

1
2
3
4
5
6
7
8
9

n 10;          设置十进制，默认 WinDbg 是 16 进制
r $t0=800;     设置 WinDbg 内部寄存器 t0 为 800，表示发声频率
r $t1=1000;    设置 WinDbg 内部寄存器 t1 为 1000，表示发声时长（毫秒）
ob 0x43 0xb6;  设置 PIT 输出到主板蜂鸣器的 PWM 波周期（这里的 ob 和 Linux 的 outb 相同）
ob 0x42 (1193180/$t0)&0xff;  PWM 波周期的低字节
ob 0x42 (1193180/$t0)>>8;    PWM 波周期的高字节
ob 0x61 3;     开始发声
.sleep $t1;    持续发声 $t1 这么长时间（毫秒）
ob 0x61 0;     发声结束

感谢 负一的平方根 (zzh1996) 出的题。

参考：http://wiki.osdev.org/PC_Speaker

（转载自 微软亚洲研究院）

作为计算机网络领域资历最老的顶级学术会议，ACM SIGCOMM自1977年起已经举办了37届。美国计算机学会（ACM）通信专业组（SIGCOMM）在其主页上无不自豪地将SIGCOMM称为其年度旗舰会议。40年来，从计算机网络教科书里的TCP拥塞控制协议到云数据中心里的软件定义网络（SDN）和网络功能虚拟化（NFV），SIGCOMM见证了众多计算机网络关键技术的诞生与发展。

SIGCOMM的论文以高质量著称，每年只录用40篇左右，录取率在15%左右。全世界的网络研究者都把在SIGCOMM上发表论文视为一种荣誉。每篇论文都经过严格的双盲评审，例如今年有三轮评审，第一轮从225篇选出99篇，第二轮选出66篇，第三轮选出60篇进入程序委员会（PC）讨论，在一天半的会议后决定最终被录用的39篇论文。每篇被录用的论文平均收到了8个评审意见，长达十几页。即使最终没有被录用，这些专家审稿人的意见对论文后续的改进也是很有帮助的。

FAQ for ClickNP: Highly Flexible and High-Performance Network Processing with Reconfigurable Hardware.