PIPQ: Strict Insert-Optimized Concurrent Priority Queue

Concurrent data structures are at the heart of modern applications and thus, their efficient and scalable implementation is of great importance. Priority queues, particularly, are widely used data structures with many applications in diverse domains [5, 24, 20, 21, 22, 32, 3, 13, 6]. Applications include graph and encoding algorithms, big data analysis, task scheduling and load balancing, event-driven simulation, query optimization, databases (e.g., in transaction management, deadlock handling, process handling), network routing, and more.

A priority queue supports two operations: insert, which inserts a key-value pair in the priority queue, and delete-min, which deletes and returns the element with the smallest key (indicating the highest priority) in the queue.

The last decade has been characterized by innovations in the design of priority queues focusing mainly on improving the performance of delete-min [18, 1, 30, 26, 24, 33], which is unquestionably a sequential bottleneck for most designs, since these operations all target the same highest priority element. These innovations focus mostly on relaxing the semantics of the priority queue itself to allow for more parallelism when serving the delete-min operation. In relaxed designs, the rank of the removed element is within some defined bound of the highest priority element, although it may not be the highest priority element itself. However, relaxed semantics are not sufficient for many applications in which the single highest priority element must be removed each time. Some examples that may require strict semantics include risk management systems to ensure critical tasks are addressed first, real-time systems such as medical systems and devices, which must optimally treat patients, and in security applications in which high-priority messages or threats must be processed ahead of all other requests.

Despite the highlighted importance of such strict behavior of priority queues in many applications, the focus on relaxed priority queues in the last decade left a clear gap in literature and made the performance of state-of-the-art strict priority queues significantly inferior to their relaxed counterparts. However, if relaxation is not a viable option, the performance of applications needing strict semantics will always be limited by the underlying priority queue. In this paper, we fill this gap as follows. Optimizing on delete-min in the strict setting is difficult due to its sequential nature. Thus, while still aiming to alleviate the performance impact of the pessimistic nature of delete-min, we shift our focus to maximizing the performance and parallelism of insert operations. In fact, achieving a significant speedup for insert operations can offset the overhead of the delete-min operations. Beyond that, there is a class of applications for which the performance of insert operations is important. Examples include graph analytics [17], data series analysis [5, 20, 21, 22], and computation over streamed data [23].

The core intuition is to improve the performance of insert operations by using a set of data structures, one per thread, to avoid synchronization with other threads when the inserted element is not among those with the highest priority. When this condition is met, which we claim to be the common case for many applications [17, 5, 20, 21, 22, 23], insertions can effectively be embarrassingly parallel. This ensures perfect scalability, Non-Uniform Memory Access (NUMA)-awareness, and near-optimal performance.

We developed this intuition into PIPQ¹¹1Pronounced “Pip Q”, standing for Parallel Inserts Priority Queue., our linearizable, concurrent priority queue whose main strength is its high-performance insert operation. PIPQ’s design encompasses a hierarchical structure:

• $\mathrm{■}$

  In the first level, called the worker level, we deploy one min-heap [16] per thread. Insertions are performed to the thread’s min-heap unless the thread has observed the highest priority element to be inserted.

• $\mathrm{■}$

  The second level, called the leader level, collects the highest-priority elements in PIPQ, hence creating a set of candidate elements to be returned by delete-min.

Delete operations remove elements from the leader level, which contains the most minimal element(s) inserted by each thread, and thus the most minimal element(s) in the entire structure. To avoid degrading the performance of delete-min due to this hierarchical structure, we employ the combining technique [15, 9] to minimize contention between concurrent removals.

We develop PIPQ in C++²²2The source code for PIPQ is publicly available here: https://github.com/sss-lehigh/pipq and compare its performance against two state-of-the-art strict linearizable priority queues, namely the Lindén-Jonsson priority queue [18], and the Lotan-Shavit priority queue [28]. Experiments are conducted on an Intel server equipped with 96 cores over four processors. Applications include a microbenchmark, in which threads execute a mix of workloads, and benchmarks that mimic the access patterns generated by recent applications of priority queues, in which inserting is a dominating factor. Evaluation of the widely used single-source shortest path (SSSP) algorithm is additionally included in the extended version of the paper. Across experiments, our evaluation reveals that the proposed algorithm exhibits great performance benefits compared to competitors when insertions dominate the workload. Importantly, PIPQ does not sacrifice performance in workloads exhibiting an equal split of both operations, nor in delete-min heavy workloads.

Lotan and Shavit [28] were the first to use a Skiplist [25] as a concurrent priority queue, a design which has since largely become the standard for implementing concurrent priority queues. Notably, the Lotan and Shavit [28] concurrent priority queue is not linearizable, instead achieving the weaker condition of being quiescently consistent [16]. Sundell and Tsigas [29] created a lock-free, linearizable concurrent priority queue based on a skip-list. Lindén and Jonsson then presented their strict, linearizable priority queue algorithm [18]; their enhancement of Lotan and Shavit’s priority queue to the delete-min operation delays physical deletion of elements to improve performance. The evaluation provided by Lindén and Jonsson shows that their priority queue consistently outperforms that of Sundell and Tsigas for various types of experiments. Braginsky et al. [4] similarly use a skiplist-based design, modifying data nodes to be lock-free chunks and leveraging elimination to speed up concurrent delete-mins, and inserts that insert to the first chunk. While PIPQ is optimized to increase the parallelism of insert operations, the work in [4] still uses a non-thread-local structure but reduces synchronization through coalescing elements. Zhang and Dechev [31] implement a lock-free priority queue based on a multi-dimensional list. Their implementation is only quiescently consistent. Similar to these solutions, PIPQ aims to create a strict linearizable priority queue, but with a new design which does not include use of a skip-list and aims to optimize insertions, all while achieving linearizability.

More recent work on priority queues has focused on relaxed solutions. In these designs, the element removed by a delete-min may not be the highest priority element itself, but is within some defined bound of it. Spraylist [1] is a well-known relaxed priority queue, and many other relaxed solutions have been proposed [30, 33, 27, 26, 24]. Unlike these relaxed solutions that optimize for the delete-min operation, PIPQ provides a strict priority queue that optimizes for insert.

A recent related work of interest is the Stealing Multi-Queue (SMQ) priority scheduler by Postnikova et al. [24], which innovates on the prior Multi-Queues work [26]. SMQ uses a design similar to that of the worker level of PIPQ, such that it maintains per-thread heaps. As a result, insert operations are optimized, and, in addition to that, it relaxes the semantics of the delete-min operation with the use of the so-called stealing buffers. Despite their similarities, removing the relaxation of SMQ would require additional synchronization, which is effectively the goal accomplished by PIPQ.

PIPQ is a linearizable priority queue that provides the traditional priority queue API: Insert, which inserts some key-value pair, and DeleteMin, which removes the element with the smallest (i.e., highest priority) key in the structure. Our priority queue supports duplicate keys and/or values. Figure 1 illustrates PIPQ’s architecture, including an example instantiation relevant to a specific thread (red / bolded).

To create highly parallel insertions, PIPQ maintains a two-level hierarchy of supporting data structures. The two levels include the worker level and the leader level. The worker level provides fast, parallel insertions with minimal synchronization because each thread $p$ inserts to its own worker-level heap, $H_p$. Each $H_p$ is implemented as a conventional min-heap protected by a single global lock. The simplicity of this level’s design is justified by the fact that most of the time no other threads need access to $H_p$, as subsequently discussed. At the leader level, the algorithm maintains a sorted linked list $L$ of keys, which stores the highest priority elements in PIPQ, and is meant to serve delete-min requests.

Elements may be inserted to the worker or leader level and may move between levels in order to maintain the following invariant: for each thread $p$, every element in $L$ tagged with $p$ (that is, $p$ inserted the element into the global data structure) has greater or equal priority than the highest priority element in the worker-level heap of $p$, $H_p$. This ensures that when we remove the highest priority element from the leader level, it is, in fact, the highest priority element in the priority queue, allowing us to achieve linearizability without relaxing operation semantics. The items in red in Figure 1 provide an example instantiation of PIPQ relative to a specific thread, denoted thread 1. The highest priority element in $H_1$ has priority 8. The corresponding nodes inserted by thread 1 in $L$ have a higher priority (smaller value of the key, k) than 8, and are ordered in $L$ by k.

A thread $p$ invoking insert on PIPQ will insert to the leader level only when the new element is of higher priority than the highest priority element in $H_p$ (or when $H_p$ is empty). Otherwise, the element will be inserted into $H_p$. The leader level is intentionally kept small (explained below), so we expect most insertions to occur at the worker level.

The delete-min operation leverages the combining technique [15, 9] as used in several prior works [8, 10, 7, 19]. Electing one thread to perform a sequence of delete-min operations, which are inherently sequential, avoids the costly contention of many threads attempting to access and remove the highest priority element in the leader-level linked list. We call this thread the coordinator. A thread $p$ that performs a delete-min operation on PIPQ first announces its operation and then attempts to become the leader of its Non-Uniform Memory Access (NUMA) node. Leaders of each NUMA node compete to become the coordinator; thus, there are up to $n$ leaders competing for the coordinator role at any given time, where $n$ is the number of NUMA nodes in the machine. The coordinator is responsible for serving the delete-min operations of threads that execute on its NUMA node. Thus, either $p$ will become the coordinator and complete its own request along with the other requests of its NUMA node, or its request will be completed by some other thread of its NUMA node that won the race to become the coordinator.

Depending on the sequence of insert and delete-min operations, the leader-level linked list $L$ may grow and shrink arbitrarily. However, the size of $L$ is an important factor in the overall performance of PIPQ. In fact, having many elements in $L$ hinders the performance of insertions for two reasons. First, traversals on $L$ involve many elements. Second, a large size of $L$ increases the likelihood that an insertion has to act at the leader level as opposed to at the worker level, since the range of the priority of elements in $L$ increases with its size. For these reasons, we limit the size of $L$ by requiring insertions to move elements from $L$ down to its worker-level heap if the number of elements that the thread has inserted in $L$ exceeds a certain threshold, which we call CNTR_MAX.

On the other hand (and less intuitively), having too few elements in $L$ hinders the performance of delete-min operations. To successfully linearize delete-min operations while ensuring the properties that $L$ needs to satisfy, each thread has to have at least two of the elements it has inserted in $L$; the justification for requiring at least two elements is detailed in Section 5.1. If this requirement is not met, the coordinator must promote an element from the thread’s worker-level heap. Having few elements in $L$ means that the coordinator would need to perform such a promotion more frequently. We address this issue by defining a second threshold, CNTR_MIN (with a value less than that of CNTR_MAX), and use it to introduce a helping mechanism.

The idea behind helping is that a thread can do work that does not directly impact the operation it is performing but can “help” other operations complete their work in a more efficient manner. Since threads performing the delete-min operation must wait on the coordinator, we initiate helping during this waiting period to reduce the work required by the coordinator. Specifically, if the number of elements inserted by some thread $p$ in $L$ is less than CNTR_MIN, $p$ will promote an element from $H_p$ up to the leader level instead of waiting for the coordinator to eventually do so.

We maintain an array of atomic counters containing one slot per thread such that each thread $p$’s slot in the counters array stores the number of elements currently in $L$ that were inserted by $p$ to the global structure. We refer to $p$’s counter value as $L\mathrm{\_}coun{t}_p$. The use of helping and the gap between CNTR_MIN and CNTR_MAX is meant to achieve the following two goals: (1) it is less costly for a waiting thread $p$ to help by moving elements from $H_p$ to $L$, compared to the coordinator needing to do so; thus, we reduce the frequency with which the coordinator must do additional work, and (2) by helping only when $L\mathrm{\_}coun{t}_p$ is less than the minimum threshold (which is, in turn, less than the maximum threshold), we reduce the frequency with which an insertion has to move an element down from the leader level to the worker level.

Before discussing the details of PIPQ, it is important to highlight that the leader-level linked list, $L$, differs from traditional linked lists in that it requires tracking which thread inserts each element in order to move them to the corresponding worker-level min-heap when necessary. To do so, $L$ stores tuples (key,val,tid_p), where tid_p represents the unique identifier of the thread, $p$, that first inserted this key-value pair in the priority queue. $L$ is sorted based on the key and supports the following operations: a) L-Insert(key, val, tid_p), which inserts the tuple (key,val,tid_p) in $L$; b) L-DeleteMin, which deletes and returns the element with the smallest (highest priority) key in $L$; and c) L-DeleteMaxP(lead_largest, tid_p), which removes the element with the largest (least priority) key that was inserted to PIPQ by the thread with identifier tid_p (to be subsequently inserted into $H_p$).

Figure 2 contains flow diagrams for the DeleteMin and Insert APIs of PIPQ. Recall the invariant maintained between levels, such that the priority of each element in $L$ must be greater than or equal to the priority of the highest priority element from their respective worker level heaps. Deciding on which level to insert, as well as the movement of elements between levels, aims to maintain this invariant. Pseudocode for the leader-level APIs is provided in Section 5.1 and their helper (search) functions are provided in Appendix A. The entire pseudocode of PIPQ is provided in the extended version of the paper.

A sketch of the proof of PIPQ’s linearizability is provided in Appendix B due to space constraints. The complete proof and an analysis of PIPQ’s single-threaded worst-case performance are included in the extended version of the paper.

We conduct our experiments on a machine running Ubuntu 22.04.3 LTS equipped with four Intel Xeon Platinum 8160 processors containing a total of 96 cores split between four NUMA nodes. Our code is written in C++ and compiled with -std=c++20 -O3 -mcx16. Our data points represent the average of three trials performed for five seconds each. Threads are pinned to cores using a NUMA node by NUMA node policy. Hyperthreading is disabled.

We compare PIPQ with the following two state-of-the-art, strict priority queues: Lotan-Shavit [28] and Lindén-Jonsson [18]. Lotan-Shavit [28] is a priority queue implemented on top of Fraser’s skiplist [11]. The delete-min operation is implemented by traversing the lowest-level linked list, and atomically marking the first unmarked node as logically deleted. This data structure is not linearizable but is quiescently consistent [16]. Lindén-Jonsson [18] extends the Lotan-Shavit design by batching the physical deletions once a certain threshold of logically deleted nodes has been met. Lindén-Jonsson outperforms Sundell and Tsigas’ linearizable priority queue algorithm [29] and Herlihy and Shavit’s [16] lock-free adaptation of the LS priority queue [28].

We test different applications, workloads, and data access patterns: a traditional microbenchmark to evaluate concurrent data structures; a designated thread experiment, where each thread performs either insert or delete-min, but not both; and a phased experiment, in which the workload changes in phases. We additionally evaluate the single-source shortest path graph algorithm, which is included only in the extended version of the paper.

In this paper we presented PIPQ, a strict, linearizable concurrent priority queue. Its design focuses on increasing the performance and parallelism of insert operations as opposed to focusing on the sequential bottleneck of delete-min operations, as done by the majority of prior work. PIPQ achieves this by allowing insert operations to utilize per-thread data structures in the common case. Our evaluation confirms that with PIPQ’s design, it is possible to achieve high performance and scalability under various access patterns and runtime configurations.