In the field of efficient concurrent ordered indices, traditional structures like concurrent binary search trees, B-trees, and skip lists primarily focus on providing good worst-case guarantees. However, in real workloads, access rates to objects are often non-uniform, leading to uneven access distributions.
While several efficient distribution-adaptive data structures exist, achieving efficiency in the concurrent case is often complex.
The Splay Tree stands out as the most prominent distribution-adaptive data structure, offering the key advantage of not storing any balancing information, thus providing reasonable performance improvements under extremely skewed workloads, such as Zipfian workloads.
This paper introduces a splay-like rotation design for concurrent binary search trees. Instead of moving an accessed node to the root, this rotation design uses two depth thresholds based on static optimality complexity calculated from the access count of the node: a node is rotated only when it significantly exceeds the upper threshold, and rotations stop before reaching the lower threshold.
This design aims to preserve the main practical benefit of splaying under skewed workloads while reducing contention near the root.
We present two variants of the rotation design: one using an exact 64-bit access counter per node and another using a 6-bit approximate counter. We prove static optimality for the corresponding sequential read-only tree and evaluate both rotation designs implemented on top of the concurrent AVL tree by Bronson et al.
Our experiments show that this approach can enhance throughput across several skewed workloads.
Blogger's Review: This research presents an innovative solution in the realm of concurrent data structures, effectively leveraging the advantages of splay trees to enhance performance under non-uniform loads. It demonstrates a solid integration of theory and practice, making it a topic worth further exploration and study.