Ring Buffer 有什么特别?

原文地址: http://mechanitis.blogspot.com/2011/06/dissecting-disruptor-whats-so-special.html​ 作者是 Trisha Gee, LMAX 公司的一位女工程师。

最近我们开源了 LMAX Disruptor​,它是让我们的交易流程变得如此之快的关键。为什么要开源它?因为我们意识到大家对高性能编程的传统认知 ... 有些不对劲。我们找到了一个更好的,更快的在线程间共享数据的方法,如果不把它分享给大家就太自私了。而且,这会使我们看起来很酷。

从这个 网站​ 你可以下载一份解释什么是 Disruptor,以及它为什么如此巧妙和飞快的技术文档。我从这里得到了一些写作帮助,其实我真正做的只是在上面加了一些标点和重新组织了一些我不明白的句子,这太简单了。

我发现要把这些东西一次性解释清楚有些困难,所以我准备一小段一小段的解释它们,以适合我的 NADD​ 听众。

首先 - Ring Buffer。我对 Disruptor 的最初印象只有 Ring Buffer。后来我渐渐明白 Ring Buffer 结构是这个模式的中心,关键之处是 Disruptor 如何控制对它的访问。

Ring Buffer 究竟是什么?

正如名字描述那样 - 它是一个环 (圆形,首尾相接的),你可以把它当作一个缓存 (buffer),用来在一个线程上下文与另一个线程上下文之间传递数据。

(好吧,我是用 Paint 画的。我尝试画草图,希望强迫症没有掺和进来要求我画出完美的圆和直线)。 所以基本上 Ring Buffer 就是拥有一个序号指向下一个可用元素的数组。

如果你持续向 buffer 中写入数据(应该也会从里面读数据),这个序号会一直增长,直到绕过整个环。

要找到数组中当前序号指向的元素,你可以用 mod 运算。

sequence mod array length = array index

因此对于上面的 Ring Buffer,这个算法就是(用 JAVA 的 mod 语法):12 % 10 = 2。很简单。

其实图片里画着 10 个元素完全是一个意外。2 的 N 次方个元素会更好,因为计算机是用二进制思考的。 接下来呢?

如果你从 Wikipedia 查到 Circular Buffers​,你会看到它与我们的实现方式有一个重要的差别-没有指向末尾的指针。我们只有下一个可用的序号。这是刻意的-选择 Ring Buffer 的根本原因是需要支持可靠的消息通信。我们需要把服务发出的消息存储起来,那么当另一个服务发来一个 NAK (拒绝应答信号)​​ 说他们没有收到消息的时候,我们可以重新发送给他们。

Ring Buffer 看起来很理想。它用序号来指出 buffer 的末尾在哪里,而且当它收到一个 NAK 信号的时候,可以重发从那一点到当前序号之间的所有消息:

我们所实现的 Ring Buffer 与传统队列的区别是:buffer 里的对象不会被销毁-它们留在那儿直到下次被覆盖写入。这是与 Wikipedia 上的版本相比我们的实现不需要尾指针的原因。在我们的实现中,确定 Ring Buffer 是否重叠的工作,是由数据结构之外来完成的(这是生产者与消费者行为的一部分-如果你来不及等我写博客说明它,可以自己检出 Disruptor 代码​​)。

Ring Buffer 这么棒是因为...?

我们使用 Ring Buffer 这种数据结构,是因为它给我们提供了可靠的消息传递特性。这个理由就足够了,不过它还有一些其他的优点。

首先,Ring Buffer 比链表要快,因为它是数组,而且有一个容易预测的访问模式。这很不错,对 CPU 高速缓存友好 (CPU-cache-friendly)-数据可以在硬件层面预加载到高速缓存,因此 CPU 不需要经常回到主内存 RAM 里去寻找 Ring Buffer 的下一条数据。

第二点,Ring Buffer 是一个数组,你可以预先分配内存,并保持数组元素永远有效。这意味着内存垃圾收集(GC)在这种情况下几乎什么也不用做。此外,也不像链表那样每增加一条数据都要创建对象-当这些数据从链表里删除时,这些对象都要被清理掉。

文章缺少的部分

我没有提到如何避免环重叠,以及怎么向 Ring Buffer 读、写数据的细节。你也会注意到我在拿它和链表那样的数据结构相比较,我想没人会认为链表是实际问题的解决方案。 有趣的部分来自于拿 Disruptor 和队列之类的实现相比较。队列通常关注于维护队列的头和尾,添加和消费消息一类的东西。所有这些东西我还没有在 Ring Buffer 一节真正提到。这是因为 Ring Buffer 本身并不负责这些事情,我们把这些问题挪到了数据结构的外部。 你可以到这个 网站​ 阅读论文或检出代码获得更详细的信息。也可以去看 Mike 和 Martin去年在 QCon San Francisco 的演讲​。或者,再等我 5 分钟来想想怎么讲后面剩下的东西。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序猿

【学生管理系统C语言】没有用数据库,正在学习C语言的看看吧

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<math.h> # defin...

49711
来自专栏架构说

leetcode打家劫舍问题

https://leetcode-cn.com/problems/house-robber/description/

1782
来自专栏ACM算法日常

PAT-CCCC练习:L2-001.紧急救援

作为一个城市的应急救援队伍的负责人,你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速...

781
来自专栏Aloys的开发之路

OOAD与UML笔记

UML基础介绍 1.UML的定义 统一建模语言(UML)是一种图形化的语言,它可以帮助我们在OOAD过程中标识元素、构建模块、分析过程并可通过文档说明系统中的重...

1998
来自专栏数据魔术师

运筹学教学|修正单纯形法(revised simplex algorithm)代码分享及详细注释

欢声笑语中,小编学会了单纯形法,心里还有点小傲骄!!准备晚上去PUBG里面潇洒一把~ ? 然而,老板突然来电话说,单纯形法有升级的版本!需要我赶紧准备一份代码。...

8807
来自专栏牛客网

拼多多、网易、华为面经

统共面试了三家公司,本来打算偷懒不打算写面经,不过还是写一下吧,如果能帮到人的应该也算是件好事,具体的事件太久忘了

2121
来自专栏好好学java的技术栈

“365算法每日学计划”:03打卡-贪心算法

自从开始做公众号开始,就一直在思考,怎么把算法的训练做好,因为思海同学在算法这方面的掌握确实还不够。因此,我现在想做一个“365算法每日学计划”。

2372
来自专栏ACM算法日常

为什么vjudge上他人公开的代码要以图片形式显示?

vjudge用图片来显示代码,应该是为了避免抄袭。在较低水平的oier中,已经有交别人的代码来通过题目的风气。举个例子,洛谷上抄袭代码情况极其严重,而u...

1102
来自专栏程序人生

谈谈状态机

题记:上周做 BBL 里讲了我们 Tubi TV 内部做 DSL 的一些简单实践,大家反馈不错。有同事建议我给大家先补补 FSM,之后再进阶 CFG,可能会更顺...

3697
来自专栏斑斓

MongoDB的数据建模

MongoDB是一种面向Document的NoSQL数据库,如果我们还是按照RDB的方式来思考MongoDB的数据建模,则不能有效地利用MongoDB的优势;然...

3446

扫码关注云+社区

领取腾讯云代金券