54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.pdf
《54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.pdf》由会员分享,可在线阅读,更多相关《54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.pdf(11页珍藏版)》请在三一文库上搜索。
1、54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 Disruptor你是否听说过呢?它是一种内存消息队列。从功能上讲,它其实有点儿类似Kafka。不过,和Kafka不同的是,Disruptor是线程之间用于消息传递的队列。 它在Apache Storm、Camel、Log4j 2
2、等很多知名项目中都有广泛应用。 之所以如此受青睐,主要还是因为它的性能表现非常优秀。它比Java中另外一个非常常用的内存消息队列ArrayBlockingQueue(ABS)的性能,要高一个数量级, 可以算得上是最快的内存消息队列了。它还因此获得过Oracle官方的Duke大奖。 如此高性能的内存消息队列,在设计和实现上,必然有它独到的地方。今天,我们就来一块儿看下,Disruptor是如何做到如此高性能的?其底层依赖了哪些数据 结构和算法? 基于循环队列的“生产者-消费者模型” 什么是内存消息队列?对很多业务工程师或者前端工程师来说,可能会比较陌生。不过,如果我说“生产者-消费者模型”,估计
3、大部分人都知道。在这个模型 中,“生产者”生产数据,并且将数据放到一个中心存储容器中。之后,“消费者”从中心存储容器中,取出数据消费。 这个模型非常简单、好理解,那你有没有思考过,这里面存储数据的中心存储容器,是用什么样的数据结构来实现的呢? 实际上,实现中心存储容器最常用的一种数据结构,就是我们在第9节讲的队列。队列支持数据的先进先出。正是这个特性,使得数据被消费的顺序性可以得到保 证,也就是说,早被生产的数据就会早被消费。 我们在第9节讲过,队列有两种实现思路。一种是基于链表实现的链式队列,另一种是基于数组实现的顺序队列。不同的需求背景下,我们会选择不同的实现方 式。 如果我们要实现一个无
4、界队列,也就是说,队列的大小事先不确定,理论上可以支持无限大。这种情况下,我们适合选用链表来实现队列。因为链表支持快速地 动态扩容。如果我们要实现一个有界队列,也就是说,队列的大小事先确定,当队列中数据满了之后,生产者就需要等待。直到消费者消费了数据,队列有空闲 位置的时候,生产者才能将数据放入。 实际上,相较于无界队列,有界队列的应用场景更加广泛。毕竟,我们的机器内存是有限的。而无界队列占用的内存数量是不可控的。对于实际的软件开发来 说,这种不可控的因素,就会有潜在的风险。在某些极端情况下,无界队列就有可能因为内存持续增长,而导致OOM(Out of Memory)错误。 在第9节中,我们还
5、讲过一种特殊的顺序队列,循环队列。我们讲过,非循环的顺序队列在添加、删除数据的工程中,会涉及数据的搬移操作,导致性能变差。而 循环队列正好可以解决这个数据搬移的问题,所以,性能更加好。所以,大部分用到顺序队列的场景中,我们都选择用顺序队列中的循环队列。 实际上,循环队列这种数据结构,就是我们今天要讲的内存消息队列的雏形。我借助循环队列,实现了一个最简单的“生产者-消费者模型”。对应的代码我贴到这 里,你可以看看。 为了方便你理解,对于生产者和消费者之间操作的同步,我并没有用到线程相关的操作。而是采用了“当队列满了之后,生产者就轮训等待;当队列空了之后,消 费者就轮训等待”这样的措施。 publ
6、ic class Queue private Long data; private int size = 0, head = 0, tail = 0; public Queue(int size) this.data = new Longsize; 54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 this.size = size; public boo
7、lean add(Long element) if (tail + 1) % size = head) return false; datatail = element; tail = (tail + 1) % size; return true; public Long poll() if (head = tail) return null; long ret = datahead; head = (head + 1) % size; return ret; public class Producer private Queue queue; public Producer(Queue qu
8、eue) this.queue = queue; public void produce(Long data) throws InterruptedException while (!queue.add(data) Thread.sleep(100); public class Consumer private Queue queue; public Consumer(Queue queue) this.queue = queue; public void comsume() throws InterruptedException while (true) Long data = queue.
9、poll(); if (data = null) Thread.sleep(100); else / TODO:.消费数据的业务逻辑. 基于加锁的并发“生产者-消费者模型” 实际上,刚刚的“生产者-消费者模型”实现代码,是不完善的。为什么这么说呢? 如果我们只有一个生产者往队列中写数据,一个消费者从队列中读取数据,那上面的代码是没有问题的。但是,如果有多个生产者在并发地往队列中写入数据, 或者多个消费者并发地从队列中消费数据,那上面的代码就不能正确工作了。我来给你讲讲为什么。 在多个生产者或者多个消费者并发操作队列的情况下,刚刚的代码主要会有下面两个问题: 多个生产者写入的数据可能会互相覆盖;
10、 多个消费者可能会读取重复的数据。 54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 因为第一个问题和第二个问题产生的原理是类似的。所以,我着重讲解第一个问题是如何产生的以及该如何解决。对于第二个问题,你可以类比我对第一个问题 的解决思路自己来想一想。 两个线程同时往队列中添加数据,也就相当于两个线程同时执行类Queue中的add()函数。我们假设队列的
11、大小size是10,当前的tail指向下标7,head指向下标3,也 就是说,队列中还有空闲空间。这个时候,线程1调用add()函数,往队列中添加一个值为12的数据;线程2调用add()函数,往队列中添加一个值为15的数据。在极 端情况下,本来是往队列中添加了两个数据(12和15),最终可能只有一个数据添加成功,另一个数据会被覆盖。这是为什么呢? 为了方便你查看队列Queue中的add()函数,我把它从上面的代码中摘录出来,贴在这里。 54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据
12、结构与算法之美/54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/31 9:33:46 public boolean add(Long element) if (tail + 1) % size = head) return false; datatail = element; tail = (tail + 1) % size; return true; 从这段代码中,我们可以看到,第3行给datatail赋值,然后第4行才给tail的值加一。赋值和tail加一两个操作,并非原子操作。这就会导致这样的情况发生:当线 程1和线程2同时执行add()函
13、数的时候,线程1先执行完了第3行语句,将data7(tail等于7)的值设置为12。在线程1还未执行到第4行语句之前,也就是还未 将tail加一之前,线程2执行了第3行语句,又将data7的值设置为15,也就是说,那线程2插入的数据覆盖了线程1插入的数据。原本应该插入两个数据(12和15) 的,现在只插入了一个数据(15)。 54|算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法 file:/J/geektime/唯一更新QQ群170701297/ebook/数据结构与算法之美/54算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法.html2019/1/
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 54 算法 实战 剖析 性能 队列 Disruptor 背后 数据结构
链接地址:https://www.31doc.com/p-5529946.html