Analysis and Evaluation of Non-Blocking Interpolation Search Trees

Aleksandar Prokopec, Trevor Brown, Dan AlistarharXiv 2020 · OpenReview

TL;DR

This paper analyzes and evaluates the C-IST, a novel non-blocking concurrent interpolation search tree. It proves the correctness and linearizability of C-IST operations, demonstrating wait-free lookups and lock-free insertions/deletions. The C-IST achieves an impressive $O(\log \log n + p)$ expected time complexity for lookups on smooth data distributions, outperforming existing concurrent search trees in extensive experiments.

What Problem Does This Paper Address?

Traditional concurrent search trees, while offering logarithmic time complexity for operations, can become a bottleneck in highly parallel systems due to contention. Interpolation search trees (ISTs) offer a theoretical advantage with their $O(\log \log n)$ expected time complexity for operations on smooth data distributions, but their sequential nature and lack of robust concurrent implementations have limited their practical adoption. This paper addresses the challenge of creating a non-blocking concurrent interpolation search tree (C-IST) that retains the theoretical performance benefits of ISTs while being suitable for modern multi-core architectures. The goal is to achieve high throughput and scalability by minimizing synchronization overhead and maximizing parallelism.

Methods

The paper provides a rigorous analysis of the C-IST data structure, building upon a previously proposed implementation. Key methodological contributions include:

  • Correctness and Linearizability Proofs: The authors formally prove that the C-IST operations are correct (maintain invariants) and linearizable (appear to execute atomically). This is a crucial step for any concurrent data structure.
  • Non-Blocking Guarantees: They demonstrate that lookups are wait-free (guaranteed to complete in a finite number of steps, regardless of other threads' actions), and insertions/deletions are lock-free (guaranteed to complete eventually, though individual threads might need to help others).
  • Asymptotic Complexity Analysis: The paper derives the worst-case and expected time complexities for C-IST operations. Notably, for smooth key distributions, lookups achieve an expected $O(\log \log n + p)$ time, and insertions/deletions achieve an expected amortized $O(\log \log n + p)$ time, where $p$ is the number of threads.
  • Collaborative Rebuilding: To address potential scalability bottlenecks during tree rebalancing, a collaborative rebuilding mechanism is introduced. This allows multiple threads to work together on rebuilding subtrees, improving efficiency.
  • Extended Experimental Evaluation: A comprehensive set of experiments compares the C-IST against seven state-of-the-art concurrent tree data structures. This evaluation includes performance on various dataset sizes, update rates, parallelism levels, and even specialized workloads like No-SQL databases and Zipfian distributions.

Datasets

The paper does not introduce new datasets but uses synthetic datasets for evaluation. These datasets vary in size (from $2 \times 10^6$ to $10^9$ keys) and update ratios (0%, 1%, 10%, 40%). They also evaluate performance on:

  • No-SQL database workload: Simulating an in-memory database using the DBx1000 system.
  • Zipfian distribution workload: Testing performance with highly skewed key distributions to assess robustness.

Key Insights and Ideas

  • The Power of $O(\log \log n)$: The core insight is that by leveraging interpolation search and a carefully designed concurrent structure, it's possible to achieve expected doubly-logarithmic time complexity for operations, significantly outperforming traditional logarithmic structures, especially on large datasets.
  • Non-Blocking is Key for Scalability: The paper strongly emphasizes that achieving true scalability in highly parallel systems requires non-blocking data structures. The wait-free nature of lookups and lock-free nature of modifications are critical for avoiding deadlocks and maximizing throughput.
  • Collaborative Rebuilding Solves a Bottleneck: The introduction of collaborative rebuilding is a significant practical improvement. It addresses the inherent challenge of concurrent tree modifications by distributing the work of rebalancing, preventing single threads from becoming a bottleneck.
  • Cache Performance Matters: The analysis highlights that the shallow depth of the C-IST (due to its $O(\log \log n)$ complexity) leads to fewer last-level cache (LLC) misses, which is a major factor in its superior performance compared to other structures.
  • Robustness on Skewed Data: While theoretical performance might degrade on extremely skewed data, the experimental results show that C-IST remains surprisingly robust, maintaining competitive performance even in challenging scenarios.

Key Results

  • Correctness and Linearizability: The C-IST is proven to be correct and linearizable.
  • Non-Blocking Guarantees: Lookups are wait-free, and insertions/deletions are lock-free.
  • Performance Gains:
    • C-IST achieves up to 3.5x performance improvement over some competitive data structures and up to 50% over the next best alternative.
  • On average, C-IST operations require significantly fewer pointer hops (cache misses) compared to other tree structures, with depths often below 5.
  • Collaborative rebuilding dramatically reduces the time spent on rebuilding operations, especially at higher update rates and thread counts.
  • Using a multicounter in the root node provides a substantial throughput improvement (15-33%) compared to a simple fetch-and-add counter.
  • Memory Footprint: C-IST exhibits a lower relative space overhead compared to other data structures.

Limitations and Future Work

  • Smoothness Assumption: The optimal $O(\log \log n)$ performance is achieved under the assumption of "smooth" key distributions. While the paper shows good performance even on skewed distributions, the theoretical guarantees are strongest for smooth ones.
  • Arbitrary Key Distributions: For arbitrary key distributions, the C-IST still offers standard logarithmic time bounds, which is competitive but not as groundbreaking as the smooth case.
  • Future Work: The authors suggest that the techniques used in C-IST could be applied to other data structures and that further exploration of its performance on Big Data workloads is warranted. The potential for C-IST to trigger new lines of research is highlighted.

Summary updated

Abstract

We start by summarizing the recently proposed implementation of the first non-blocking concurrent interpolation search tree (C-IST) data structure. We then analyze the individual operations of the C-IST, and show that they are correct and linearizable. We furthermore show that lookup (and several other non-destructive operations) are wait-free, and that the insert and delete operations are lock-free. We continue by showing that the C-IST has the following properties. For arbitrary key distributions, this data structure ensures worst-case $O(\log n + p)$ amortized time for search, insertion and deletion traversals. When the input key distributions are smooth, lookups run in expected $O(\log \log n + p)$ time, and insertion and deletion run in expected amortized $O(\log \log n + p)$ time, where $p$ is a bound on the number of threads. Finally, we present an extended experimental evaluation of the non-blocking IST performance.
BibTeX
@misc{prokopec2020analysis,
  author = {Aleksandar Prokopec and Trevor Brown and Dan Alistarh},
  title = {{Analysis and Evaluation of Non-Blocking Interpolation Search Trees}},
  year = {2020},
  eprint = {2001.00413},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2001.00413},
}
Figure