数据结构与算法之美
王争
前Google工程师
立即订阅
71217 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

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

什么是内存消息队列?对很多业务工程师或者前端工程师来说,可能会比较陌生。不过,如果我说“生产者 - 消费者模型”,估计大部分人都知道。在这个模型中,“生产者”生产数据,并且将数据放到一个中心存储容器中。之后,“消费者”从中心存储容器中,取出数据消费。
这个模型非常简单、好理解,那你有没有思考过,这里面存储数据的中心存储容器,是用什么样的数据结构来实现的呢?
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(48)

  • Smallfly
    没有读过 Disruptor 的源码,从老师的文章理解,一个线程申请了一组存储空间,如果这组空间还没有被完全填满之前,另一个线程又进来,在这组空间之后申请空间并添加数据,之后第一组空间又继续填充数据,那在消费时如何保证队列是按照添加顺序读取的呢?

    即使控制读取时前面不能有空闲空间,是为了保证能按内存空间顺序消费,但是如果生产的时候没有保证顺序存储,似乎就不满足队列的条件了。
    2019-01-30
    1
    21
  • 老杨同志
    尝试回答老师的思考题

    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
    16
  • 想当上帝的司机
    为什么3到6没有完全写入前,7到9无法读取,不是两个写入操作吗
    2019-01-30
    3
    13
  • Keep-Moving
    思考题:加锁批量生成ID,使用时就不用加锁了
    2019-01-30
    8
  • disruptor使用环的数据结构,内存连续,初始化时就申请并设置对象,将原本队列的头尾节点锁的争用转化为cas操作,并利用Java对象填充,解决cache line伪共享问题
    2019-02-23
    6
  • xuery
    项目中有使用过分布式id生成器,但是不知道具体是怎么实现的,参考今天的Disruptor的思路:
    1. id生成器相当于一个全局的生产者,可以提前生成一批id
    2. 对于每一张表,可以类似于Disruptor的消费者思路,从id生成器中申请一批id,用作当前表的id使用,当然申请一批id对于id生成器来说是需要加锁操作的
    2019-04-11
    1
    3
  • 且听疯吟
    __sync_fetch_and_add操作即可实现原子自增的操作。
    2019-03-20
    3
  • 阳仔
    后面有补充这门课的内容吗?我看到老师回复说会补充,为何没有在评论区中反馈呢?对后面学习这门课的学生很困惑啊

    “生产者申请连续空间后,后续往队列添加元素就不需要加锁了,因为这个存储单元是这个线程独享的”

    这个不好理解,添加元素的不是有可能多个线程吗?那不是会产生竞争资源吗?

    希望得到解惑

    2019-05-31
    2
  • futute
    弱弱地问一下,后来老师补充过这节课的内容吗?我看完后,跟以前留言的同学有相同的感觉。
    2019-04-12
    1
  • QQ怪
    雪花算法可以根据不同机子生成不同的id
    2019-03-08
    1
  • belongcai蔡炳榕
    看完还是有很多困惑(可能跟我不了解线程安全有关)
    一是申请一段连续存储空间,怎么成为线程独享的呢?生产者ab分别申请后,消费者为啥无法跨区域读取呢
    二是这种方法应该是有实验证明效率高的,私下去了解下。

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

    2019-01-30
    1
    1
  • 神盾局闹别扭
    有个问题,按照老师所说,a线程只写1-3区块,b线程只写4-6块,假设a线程先写了块1,切换到线程b,b写块4,然后再切回线程a,a写块2。虽然没有数据覆盖问题,但是最终块1-6的顺序不是按写入先后顺序排布的,读取不是乱套了吗,怎么解决这个问题?求老师能说的详细点。
    2019-01-30
    1
  • K战神
    而是采用了“当队列满了之后,生产者就轮训等待;当队列空了之后,消费者就轮训等待”这样的措施。~是不是有错别字?轮询?
    2019-01-30
    1
  • 编程界的小学生
    我们用的百度的uid生成器,底层是雪花算法,有那么几段规则,根据机器ip和时间进行唯一性
    2019-11-24
  • 美美
    disruptor可以再详细点吗?感觉没过瘾
    2019-11-19
  • 庄小P
    这个真的不是很能理解了,看完没啥感觉呀,没说清楚为什么申请了内存空间就不需要加锁?
    2019-11-06
  • 阿西吧
    Discruptor 还通过缓存行填充的黑科技,充分利用了CPU的高速缓存
    2019-10-25
  • 为了吃方便面
    这样处理后,消息的顺序怎么保证?
    2019-10-04
  • ttttt
    我的理解:disruptor是对一小部分区间加锁。
    2019-10-04
  • Song╮承諾
    这不就是分布式锁
    2019-09-18
收起评论
48
返回
顶部