?Tree: a Persistent B+-Tree with Low Tail Latency

Tail latency is a critical design issue in recent storage systems. B + -tree, as a fundamental building block in storage systems, incurs high tail latency, especially when placed in persistent memory (PM). Our empirical study specifies two factors that lead to such latency spikes: (i) the internal structural refinement operations (i.e., split, merge, and balance), and (ii) the interference between concurrent operations. The problem is even worse when high concurrency meets with the low write bandwidth of persistent memory. In this paper, we propose a B + -tree variant named µTree. It incorporates a shadow list-based layer to the leaf nodes of a B + -tree to gain benefits from both list and tree data structures. The list layer in PM is exempt from the structural refinement operations since list nodes in the list layer own separate PM spaces, which are organized in an element-based way. Meanwhile, µTree still gains the locality benefit from the tree-based nodes. To alleviate the interference overhead, µTree coordinates the concurrency control between the tree and list layer, which moves the slow PM accesses out of the critical path. We compare µTree to state-of-theart designs of PM-aware B + -tree indices under both YCSB workload and real-world applications. µTree achieves a 99th percentile latency that is one order of magnitude lower and 2.8 -4.7 times higher throughput.