数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法

Disruptor的雏形
循环队列
高性能的并发队列
两阶段写入
重复数据问题
数据覆盖问题
顺序队列
链式队列
Disruptor的优化思路
加锁的解决方法
多生产者多消费者问题
AvailableBuffer
RingBuffer
队列
高性能、并发、全局唯一ID
循环队列
无锁的实现
加锁的实现
生产者-消费者模型
ID生成器设计
多线程安全的内存队列
并发生产者-消费者模型
内存消息队列
课后思考
总结引申
高性能队列Disruptor底层依赖的是哪些数据结构和算法?

该思维导图由 AI 生成,仅供参考

Disruptor 你是否听说过呢?它是一种内存消息队列。从功能上讲,它其实有点儿类似 Kafka。不过,和 Kafka 不同的是,Disruptor 是线程之间用于消息传递的队列。它在 Apache Storm、Camel、Log4j 2 等很多知名项目中都有广泛应用。
之所以如此受青睐,主要还是因为它的性能表现非常优秀。它比 Java 中另外一个非常常用的内存消息队列 ArrayBlockingQueue(ABS)的性能,要高一个数量级,可以算得上是最快的内存消息队列了。它还因此获得过 Oracle 官方的 Duke 大奖。
如此高性能的内存消息队列,在设计和实现上,必然有它独到的地方。今天,我们就来一块儿看下,Disruptor 是如何做到如此高性能的?其底层依赖了哪些数据结构和算法?

基于循环队列的“生产者 - 消费者模型”

什么是内存消息队列?对很多业务工程师或者前端工程师来说,可能会比较陌生。不过,如果我说“生产者 - 消费者模型”,估计大部分人都知道。在这个模型中,“生产者”生产数据,并且将数据放到一个中心存储容器中。之后,“消费者”从中心存储容器中,取出数据消费。
这个模型非常简单、好理解,那你有没有思考过,这里面存储数据的中心存储容器,是用什么样的数据结构来实现的呢?
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

Disruptor是一种高性能的内存消息队列,采用循环队列数据结构和加锁的并发“生产者-消费者模型”。文章介绍了内存消息队列的概念和生产者-消费者模型,讨论了循环队列的优势以及可能出现的数据覆盖和重复读取问题。解决并发问题的方法是通过加锁来保证操作的原子性,但Disruptor采用了更高效的处理方法,使得其在高性能方面表现出色。Disruptor实现了“两阶段写入”的方法,通过批量申请存储单元和避免加锁来提高写入和读取性能。文章还引申到了ID生成器的设计问题。总体而言,Disruptor的设计思路简单而高效,展示了“大道至简”的设计理念。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(80)

  • 最新
  • 精选
  • 郭小菜
    一直追老师的课程,每期的质量都很高,收获很多。但是这期确实有点虎头蛇尾,没有把disruptor的实现原理讲得特别明白。不是讲得不好,只是觉得结尾有点突兀,信息量少了。但是瑕不掩瑜,老师的课程总体质量绝对是杠杠的!

    作者回复: 你说的没错。这节课有点不详细,我抽空重新补充下。抱歉。

    2019-02-09
    7
    14
  • belongcai蔡炳榕
    看完还是有很多困惑(可能跟我不了解线程安全有关) 一是申请一段连续存储空间,怎么成为线程独享的呢?生产者ab分别申请后,消费者为啥无法跨区域读取呢 二是这种方法应该是有实验证明效率高的,私下去了解下。

    作者回复: 这节课我抽空再补充下。不好意思。

    2019-01-30
    4
    10
  • 沉睡的木木夕
    还是没说加存储单元是干嘛的啊,为什么在往队列添加元素之前申请存储单元就不用加锁了?能说的在详细点么

    作者回复: 这节课我重新补充下,不好意思。

    2019-01-30
    1
  • 小予
    一个线程一次读取n个元素,那另外一个线程想要读取元素时,必须等前一个线程的n个元素读取完,本质上读取还是单线程的,不明白这样为何能提高性能,希望老师能解释一下其原理。🙏🙏

    作者回复: 不用等的,可以直接读取后面的n个

    2019-07-30
  • Geek_c33c8e
    老师,线程池的实现是单个线程往队列插入任务,单个线程去队列去任务吗,所以不会处理并发控制吗

    作者回复: 这里讲的时候没涉及并发问题,实际上会有的

    2019-04-13
  • Tattoo
    这就是面试中考的消息队列吗?

    作者回复: 不是的。这里应该是线程消息队列。你指的消息队列是跨进程的。

    2019-02-01
  • 老杨同志
    尝试回答老师的思考题 1)分库分表也可以使用自增主键,可以设置增加的步长。8台机器分别从1、2、3。。开始,步长8. 从1开始的下一个id是9,与其他的不重复就可以了。 2)上面同学说的redis或者zk应该也能生成自增主键,不过他们的写性能可能不能支持真正的高并发。 3)开放独立的id生成服务。最有名的算法应该是snowflake吧。snowflake的好处是基本有序,每秒钟可以生成很大的量,容易水平扩展。 也可以把今天的disrupt用上,用自己生成id算法,提前生成id存入disrupt,预估一下峰值时业务需要的id量,比如提前生成50万;
    2019-01-30
    9
    98
  • ɴɪᴋᴇʀ
    我看到很多读者对文中这段话”3 到 6 没有完全写入数据之前,7 到 9 的数据是无法读取的“这句话都不是理解,我仔细看了下disruptor的设计方案,统一来回答一下: 每个线程都是一个生产者。对于其中一个生产者申请写入n个元素,则返回列队中对应的最大下标位置(比如当前申请写入3个,从下标3开始,返回的最大下标就是6),456就是这个生产者所申请到的独享空间。生产者同时会带有一个标记,记录当前写入成功的下标(比如当前写入到5,标记的值就为5,用来标记自身是否全部写入完成),这是对于单独的一个生产者。对于多个生产者来说,都是如此的,比如有两个生产者,A申请了456,B申请了789,此时A写入到了5,A的标记是5,B写入到了8,B的标记是8,队列中对应6和9的位置是没有数据的。这样是没有问题的,此刻暂停,来看下多消费者同时读数据。消费者A*申请到读取3个元素,消费中B*申请读到了3个元素,那么要申请的连续最大元素个数就是6,对应此刻的下标就是9,这里会触发disruptor的设计机制,从3开始,会依次检测对位置的元素是否生产成功,此刻这里A写到了5,B写到了8,6位置还没有生产成功的,那么机制就会返回可消费的最大下标,也就是5,然后消费者只会读取下标4到5两个元素进行消费。也就是文中小争哥所说的”3 到 6 没有完全写入数据之前,7 到 9 的数据是无法读取的“->其实就是disruptor找到了还没有生产出的元素,后面的数据都是无法读取的,其实很简单。不知道这里的解释看懂了没有,有兴趣的话可以自己去看下disruptor的设计实现,而且图片会比文字更加直观。
    2020-10-14
    6
    42
  • Smallfly
    没有读过 Disruptor 的源码,从老师的文章理解,一个线程申请了一组存储空间,如果这组空间还没有被完全填满之前,另一个线程又进来,在这组空间之后申请空间并添加数据,之后第一组空间又继续填充数据,那在消费时如何保证队列是按照添加顺序读取的呢? 即使控制读取时前面不能有空闲空间,是为了保证能按内存空间顺序消费,但是如果生产的时候没有保证顺序存储,似乎就不满足队列的条件了。
    2019-01-30
    6
    37
  • 想当上帝的司机
    为什么3到6没有完全写入前,7到9无法读取,不是两个写入操作吗
    2019-01-30
    10
    21
收起评论
显示
设置
留言
80
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部