16 Why Circular Queues Are Suitable for Node Data Stream Caching #

Hello, I’m Ishikawa.

In the previous lectures, we discussed the stack data structure. Now let’s take a look at queues. Queues may not be unfamiliar to you. Unlike stacks, queues usually follow the principle of First In, First Out (FIFO). You can think of it as the line you have to wait in when buying coffee in a café. Generally, those who arrive first are served first, and those who come last are served last. It is not allowed to cut in line. If you cut in line, it will disrupt the waiting time for everyone.

Implementing a queue is not complex in itself. What’s important is understanding the application of queues in programming. Since we are discussing JavaScript, let’s take a few examples from our daily lives. For example, our browsers use engines to manage threads and tasks. In Node applications, circular queues can be used for data stream caching. In this lecture, we will first quickly understand the core of queues, then explore their use cases in JS engines. Finally, we will answer the opening question of why circular queues are suitable for caching data streams by studying a special type of circular queue.

How to implement a queue and a double-ended queue #

First, let’s take a look at how to implement a simple queue. The core idea of a queue in data structures is similar to queuing up to buy tickets for a movie. The key is that whoever is in the front of the line gets to buy the ticket first. Just like queuing up, in data structures, we have the concept of enqueue and dequeue. Enqueue means adding a person to the end of the queue. The implementation is similar to push in a stack, so we can use push here as well. Next, let’s talk about dequeue. According to the first-in-first-out rule, the person at the front of the queue will dequeue after buying the ticket. It can be implemented using the shift function provided by JavaScript, which removes the first element from an array.

In addition to queues, there is another concept called a double-ended queue (deque). Although we usually follow the first-in-first-out rule when queuing up, there are exceptions in some special cases. For example, when waiting in line for a bus, if everyone agrees, we usually let a lady with a small baby go to the front of the line in extremely hot weather. In JavaScript, there is a method called unshift() that can be used to insert elements in front of the queue. In the example below, we call it dequeAdd. Another scenario is when someone at the end of the queue can’t wait any longer and decides to leave. In this case, we can use the pop() function, similar to popping out of a stack. In the example below, let’s call it dequeRemove.

In JavaScript, we can implement a queue using the following code:

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]);
  }
}

Managing browser tasks through queues #

Now let’s take a look at how the Chrome browser manages threads through queues. First, let’s understand what processes and threads are, and how they are related. Let’s take Chromium as an example, which uses a multi-process architecture. Whenever we open a new page in a browser, it creates a new browser process.

Within a browser process, there are multiple threads. Chromium has two core threads: the main thread and the IO thread. Since the browser is user-facing, the main goal of its architecture is to ensure quick response from the main thread and IO thread. To achieve this, blocking IO or complex calculations are delegated to other threads, and inter-thread communication is handled through message passing.

Therefore, we can say that Chromium uses a highly concurrent, but not necessarily highly parallel, architecture. For the tasks to be executed in the script during page loading, a task queue is used to pass them to the UI main thread through the event loop. If the task can be handled by the main thread, it will be processed. If not, it will be delegated to the IO thread or a special thread for processing, and the result will be communicated back to the main thread through message passing.

In addition to the main thread, IO thread, and special threads, there is also a thread pool in the browser process for handling general tasks. The thread pool shares a task queue. We know that in handling high concurrency, people usually ensure thread safety through locking structures. However, in Chromium’s thread management, locking structures are not encouraged, and instead, the concept of sequential or virtual thread management is advocated. Google believes that sequences themselves inherently have thread safety. How is this achieved? In virtual thread management, only when a task is completed can the next task be potentially assigned to another worker thread in the thread pool. Therefore, the next task is definitely executed based on the result of the previous task. So, although the work between different worker threads is parallel, for a set of tasks that need to be processed sequentially, their execution order is determined.

Here, let’s make an analogy. In project management, we have a requirements pool, which is similar to our task queue, and virtual thread management is like a project manager.

A project manager’s job is to create a project plan based on tasks and the team. For example, for ongoing work with two tasks: design and development, which need to be executed in sequence, the development team says, “I won’t start coding until your design UI is ready.” As a project manager, you treat these two tasks as sequential, meaning Task 2 starts based on the completion of Task 1. Although this solves the thread safety issue, the project manager is also aware that the productivity invested in the project is limited. So, how can resources be more effectively utilized through optimization of productive relationships?

This is where we can use an iterative approach. The design team works on design iteration 1, ensures its completion, and then hands it over to the development team for development. Meanwhile, when the development team is working on the development of iteration 1, the design team is already working on design iteration 2. For the design and development tasks in iteration 1, they are processed sequentially. At the same time, for the two teams, their work is parallel. This reduces project risks and allows for a certain level of concurrency.

So, does this mean that Chromium completely doesn’t support locks? Not exactly. When can lock structures be used then? Let’s take another example. Imagine two employees, one in product management and the other in research and development (worker thread). After the product manager explains the business logic, the R&D team discovers an issue in the discussed flowchart during the development process. Both employees need to simultaneously modify a document, but to avoid overwriting each other’s changes, they agree that only one person should make the changes. In Chromium, when multiple threads (worker threads) can access a data resource, but only one thread is allowed to access these resources or data at a time, locks are used. Chromium uses mutex locks in this case.

Circular Queue and Data Transfer between Threads #

After discussing common queues, let’s take a look at a special type of queue called a circular queue. A circular queue is a queue where the head and the tail are connected. It is also known as a ring buffer and can be used for data transfer between processes or threads.

Now, let’s answer the initial question: why is a circular queue suitable for Node data stream buffering? You might ask why this type of queue is useful. The core benefit of a circular queue is that when a data element is consumed, the remaining elements do not need to be moved. Let’s see how this is achieved. For a circular queue, we generally need two pointers: a head pointer and a tail pointer. The head pointer points to the next location for adding new data, while the tail pointer points to the next location to read data from. When data is read, we increase the tail pointer, and when data is written, we increase the head pointer.

For example, let’s assume we have a buffer of 16 bits. In the first step, we add 4 bits, and the head pointer moves to 3. If we add 3 more bits, the head pointer moves to 6. If we then read the first 4 bits, the tail pointer will be at 4.

To give you a vivid analogy, if you have dined in some restaurants in the United States, you may have seen an order wheel. Customers typically write down their orders on paper and place them on the wheel. The chefs then take the orders off the wheel in order and start cooking. This resembles a circular queue.

So how can we implement this type of circular queue in a program? From an implementation perspective, we usually create two arrays: one is the original array used to define the properties and methods of the circular queue, and the second one is the actual array used to store the data in the circular queue. In the original array, the three key properties are the head pointer, the tail pointer, and the length of the circular queue. Additionally, there are several core methods: getting and setting the properties in the original array, as well as reading and writing data in the circular queue array. This way, a circular queue can be implemented.

Now let’s see how it is applied in caching data streams. This type of circular queue is often used together with the “producer-consumer” pattern and usually includes a mutex lock in the read and write methods of the circular queue to achieve mutual exclusion. As shown in the following diagram, there are four working threads: two producers and two consumers. The producers are responsible for writing data, while the consumers read data. By using locks, only one producer can write at a time, and only one consumer can read when needed.

In the case of caching large amounts of continuously incoming data into the queue and retrieving data from the queue to perform buffering, using a circular queue greatly increases the efficiency of coordination between producers and consumers.

Summary #

In this lecture, we learned about the principle of queues and its application in browser thread management. Then, we learned about the principle of circular queues and their application in buffering data streams. Buffering data streams is evident in many applications, including process management, networking, and file systems. In networking, byte data is transmitted in chunks according to the size of packets. In file systems, data blocks are processed based on the kernel’s buffer size. Therefore, whether it is HTTP data requests and feedback or file transfers to a destination, circular queue buffering is used in the transmission of these data.

Discussion Question #

When we use mutex locks, we find that there is a disadvantage, which is that the shared resource, the circular queue, is only used by one thread at a time, while other threads are blocked. After it is used, the resource is then transferred to other threads. In a sense, this is a pessimistic lock. Besides that, there is another way, which is atomic operations. It is a single mutex operation for a specific value. Do you know how to implement a circular queue buffer using atomic operations?

Looking forward to seeing your sharing in the comments section. Let’s communicate and discuss together. Also, feel free to share today’s content with more friends. See you next time!