16 | 为什么环形队列适合做Node数据流缓存？

Oct 25, 2022
16 | 为什么环形队列适合做Node数据流缓存？-极客时间

下载APP


关闭
讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件
渠道合作
推荐作者
16 | 为什么环形队列适合做Node数据流缓存？

2022-10-25 石川来自北京
《JavaScript进阶实战课》
课程介绍

讲述：石川

时长10:42大小9.77M

你好，我是石川。
前面几讲讲完了栈这种数据结构，我们再来看看队列（queue）。队列对于你来说，可能不算是一种陌生的数据结构，和栈相反，列队通常遵循的是先进先出（FIFO，First In, First Out）的原则。你可以把它想象成在咖啡厅买咖啡时要排的队，基本是先到先得，最后来的最后买到，不能插队。如果你强行插队的话，那每个人的排队时长都会打乱。
只是实现一个队列并不复杂，重要的是，你要理解队列在编程中的应用。既然我们在讲 JS，就举几个身边的例子，比如我们的浏览器就是通过引擎来做线程和任务的管理。在使用 Node 的应用中，环形队列可以用来做数据流的缓存。这一讲，首先我们快速地了解下队列的核心，然后通过它在 JS 引擎了解它们的使用场景，最后我们通过学习一种特殊的环形队列来解答开篇的问题，就是为什么环形队列适合用来缓存数据流。
如何实现队列和双队列首先，我们来看看如何实现一个简单的队列。数据结构中队列的核心思想和我们排队买票看电影一样，关键是谁排在前面，谁就可以先买到票。和排队一样，在数据结构中，我们可以有入队、出队的概念。入队（enqeue），顾名思义就是在队伍后面加了一个人排队。这里的实现和我们看的栈里面的入栈是类似的，所以也可以用 push 来完成。下面我们再来说说出队，按照先入先出的规则，排在最前面的人买完票了以后，就会出队（dequeue）。它的实现可以通过 JavaScript 中自带的 shift，通过 shift，我们可以去掉一个数组里面最开头的一个元素。
除了队列，还有一个概念是双队列（deque）。虽然说通常我们排队的时候，都是遵循先进先出的规则，但是在有些特殊的情况下，也会有特例。比如大家在排队等车，看到一位女士带着很小的宝宝在大热天高温下等待，如果一队的人同意的话，大家一般会让她们排到前面。那么在 JavaScript 中呢，同样有一个 unshift() 的方法可以用来做到插队，我们在下面例子里把它叫做 dequeAdd。还有另外一种情况就是如果有的人在队尾等不及了，也有可能离开，这样的话我们可以借用弹出栈的 pop() 来实现，在下面例子中，我们可以管它叫 dequeRemove 吧。
在 JavaScript 里面，我们可以通过下面的方式来实现一个队列。
class Queue {
  constructor () {
    this.queue = [];
  }
  enqueue(item) {
    return this.queue.push(item);
  }
  dequeue() {
    return this.queue.shift();
  }
  dequeAdd(item) {
    return this.queue.unshift(item);
  }
  dequeRemove(item) {
    return this.queue.pop(item);
  }
  peek() {
    return console.log(this.queue[0]);
  }
}
通过队列看浏览器任务管理下面我们再来看看 Chrome 浏览器是如何通过队列来实现线程管理的。首先我们来了解下进程（process）和线程（thread）分别是什么，之间是什么关系。我们拿 Chromium 来举例，Chromium 用的是多进程的架构（multi-process architecture）。我们在浏览器中每当打开一个新页面的时候，就是一个新的浏览器进程。
在一个浏览器进程里，会有多个线程。Chromium 中有两个核心线程，一个是主线程，另外一个是 IO 线程。因为浏览器是面向前端用户的，所以对于它的架构设计来说，最主要的目标是让主线程和 IO 线程可以快速响应。为了达到这个目的，就要把阻塞 IO 或复杂运算分给其它的线程去处理，线程间通信问题通过消息传递来解决。
所以可以说 Chromium 用的是一个高并发，但不算是高并行的架构。对于页面加载的脚本中要执行的任务，会采用任务队列的方式通过事件循环给到 UI 主线程。如果问题是主线程可以解决的，就会处理，如果处理不了的，就会给到 IO 线程或特殊线程来处理，处理的结果会通过消息通信的方式给到主线程。
在浏览器进程中，除了主线程、IO 线程和特殊线程外，还有一个用来处理通用任务的线程池。线程池有一个共享的任务队列。我们知道，在处理高并发时，人们通常通过锁结构来确保线程安全，而在 Chromium 线程管理当中，并不提倡用锁的结构，而是提倡序列或虚拟线程管理的概念。因为在 Google 看来，序列本身就带有线程安全性。这是怎么做到的呢？因为在虚拟线程管理中，只有当一个任务执行完，下一个任务才有可能被分配到线程池中的另一个工作线程来执行，所以下一个任务肯定是基于上一个任务的结果来执行的。所以虽然对于不同的工作线程来讲，它们之间的工作是并行的，但是对于一组需要串行处理的任务来说，它们的执行是有先后顺序的。
这里我们可以打一个比方，比如我们在项目管理中，会有一个需求池，这个需求池就是我们的任务队列，而虚拟线程管理就如同一个项目经理。
项目经理的工作是根据任务和团队，来制定项目计划。比如根据需求，执行中有两个任务分别是设计和开发，这两个任务需要按顺序来，开发团队说你的设计 UI 没出来，我是不会开始写代码的，这时，作为项目经理，你会把这两个任务作为串行任务，也就是任务 2 的开始基于任务 1 的结束。虽然这解决了线程安全问题，但是同时项目经理也清楚投入到项目的生产力是有限的，怎么能通过生产关系的优化让资源更有效的被利用起来呢？
这时我们可以用迭代的方式。设计团队做迭代 1 中的设计，然后确保完成再交给开发团队来开发。这时当开发团队在做迭代 1 的开发时，设计团队已经在继续做迭代 2 的设计了。对于迭代 1 中设计和开发这两个任务来说，它们是按照序列串行的。同时，对于两个团队来讲，他俩的工作是并行的。这样既降低了项目风险，又可以做到一定程度的并发。
那么这样是说 Chromium 就完全不支持锁了吗？也不是。那什么时候可以用锁结构呢？同样举个例子，这就好比产品和研发两个员工（worker thread），产品宣讲完业务逻辑，研发在开发过程中，发现当时讨论的流程图有个问题，两个人需要同时修改一份流程文档，这个时候为了避免内容被相互覆盖，两个人商量好了，应该只有一个人去改。所以在 Chromium 中，通常当有多个线程（worker thread）可以访问一个数据资源，但是同一时间只允许一个线程来访问这些资源或数据的时候，会用到锁。在 Chromium 当中使用的是互斥锁（mutex）。
环形队列和线程间数据传递说完了常见的队列，我们再来看在一种特殊的队列，就是环形队列。一个环形队列是首尾相连的。它也叫做环形缓冲区（ring buffer），可以用于进程或线程之间的数据传递。
回答开篇的问题：为什么环形队列适合做 Node 数据流缓存？你可能会问这样的队列为什么会有用？那是因为它最核心的好处是当一个数据元素被用掉后，其余数据元素不需要移动其存储位置。我们来看看它是怎么做到这一点的。对于一个环形队列来说，我们一般需要两个指针，一个是头指针，一个是尾指针。头指针指向的是下一个要加入的数据，尾指针指向下一个要读取的数据。当数据被读取时，我们就增加尾指针；当数据被写入的时候，我们就增加头指针。
举个例子，假设我们有一个 16 位的缓冲，第一步，我们加入了 4 位数据，头指针就移动到了 3。如果再加 3 个的话，头指针就移动到了 6。如果这时，我们读取了前 4 个，那么尾指针就会到 4。
用一个形象的比喻，大家如果在美国的一些餐厅吃过饭，可能会见过一个点餐轮盘。来餐厅的顾客一般会把想吃的东西写在纸上，然后放到轮盘上，厨师会按照顺序从轮盘上把点餐的菜单拿下来，然后来做饭。这就很像是一个环形队列。
那么在程序中这种环形队列如何实现呢？从实现的角度，一般会建立两个数组，一个是原数组用来定义环形队列的属性和方法，第二个是实际用来存放数据的环形队列数组。在原数组里面，主要存放 3 个关键属性，分别是头指针、尾指针和环形队列长度。同时，包含几个核心方法：原数组中属性的获取和设置，以及环形队列数组中数据的读和写。通过这种方式，就可以实现一个环形队列了。
下面我们可以来看看它在缓存数据流中的应用。这种环形队列通常会和“生产者，消费者”模式一起用，也通常会加一个互斥锁到环形队列的读、写方法里，用来实现互斥访问。如下图所示，我们可以看到有 4 个工作线程。2 个是生产者，2 个是消费者。 生产者负责写入数据，消费者读取数据。通过加锁的方式，在同一时间，只有一个生产者可以写入，在读的时候，也只有一个消费者可以读取。
在数据流这种大量数据持续进入到列队中，再从队列中取出做缓存处理的情况下，使用环形队列就大大增加了生产者和消费者之间协同合作的效率。
总结在这一讲当中，我们通过对队列的原理介绍，学习了它在浏览器线程管理中的应用；之后通过对环形队列的的原理介绍，学习了它在缓存数据流中的应用。数据流缓冲在很多应用中都有体现，除了进程管理外，在网络和文件系统中，都会用到数据流缓冲。在网络中，字节数据都是按照包的大小分成块儿来传输的；在文件系统中，数据块儿都是根据内核的缓冲大小分成块儿来处理的。所以无论是 HTTP 的数据请求和反馈，还是文件到目的地的传输，这些数据的传输都会用到环形队列缓冲。
思考题在我们用互斥锁的时候，会发现它有一个劣势，就是共享资源，也就是环形队列每次只给一个线程使用，其它线程阻塞，用完后再把资源转让给其它线程，这在某种意义上是一个悲观锁。除此之外，还有另外的一种方式是原子操作，它是针对某个值的单个互斥操作。你知道如何通过原子操作来实现环形队列缓冲吗？
期待在留言区看到你的分享，我们一起交流讨论。另外，也欢迎你把今天的内容分享给更多的朋友。我们下期再见！
分享给需要的人，Ta购买本课程，你将得18元
生成海报并分享
赞 0
提建议
15 | 如何通过哈希查找JS对象内存地址？
17 | 如何通过链表做LRU/LFU缓存？
 写留言
精选留言

由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
