> Persistent memory brings new challenges to persistent hash tables in both performance (scalability) and functionality. We identify that the key is to reduce both unnecessary PM reads and writes, whereas prior work solely focused on reducing PM writes and ignored many practical issues such as PM management and concurrency control, and traded off instant recovery capability. Our solution is Dash, a holistic approach to scalable PM hashing. Dash combines both new and existing techniques, including (1) fingerprinting to reduce PM accesses, (2) optimistic locking, and (3) a novel bucket load balancing technique. Using Dash, we adapted extendible hashing and linear hashing to work on PM. On real Intel Optane DCPMM, Dash scales with up to ∼3.9× better performance than prior state- of-the-art, while maintaining desirable properties, including high load factor and sub-second level instant recovery.
> Byte-addressable persistent memory (PM) brings hash tables the potential of low latency, cheap persistence and instant recovery.
> We present Dash, a holistic approach to building dynamic and scalable hash tables on real PM hardware with all the aforementioned properties.
> Dash-enabled hash tables can achieve up to ∼3.9×higher performance with up to over 90% load factor and an instant recovery time of 57ms regardless of data size."
Section 1.2:
> Dash uses a combination of new and existing techniques that are carefully engineered to achieve this goal.
> 1. We adopt fingerprinting that was used in PM tree structures to avoid unnecessary PM reads during record probing. The idea is to generate fingerprints (one-byte hashes) of keys and place them compactly to summarize the possible existence of keys.
> 2. Instead of traditional bucket-level locking, Dash uses an optimistic, lightweight flavor of it that relies on verification to detect conflicts, rather than (expensive) shared locks. This allows Dash to avoid PM writes for search operations.
> 3. Dash retains desirable properties. We propose a new load balancing strategy to postpone segment splits with improved space utilization. To support instant recovery, we limit the amount of work to be done upon recovery to be small ..., and amortize recovery work to runtime. Compared to prior work that handles PM programming issues in ad hoc ways, Dash uses PM programming models ... to systematically handle crash consistency, PM allocation and achieve instant recovery.
> Although these techniques are not all new, Dash is the first to integrate them for building hash tables that scale without sacrificing features on real PM.
4 comments
[ 0.16 ms ] story [ 19.7 ms ] thread> Byte-addressable persistent memory (PM) brings hash tables the potential of low latency, cheap persistence and instant recovery.
> We present Dash, a holistic approach to building dynamic and scalable hash tables on real PM hardware with all the aforementioned properties.
> Dash-enabled hash tables can achieve up to ∼3.9×higher performance with up to over 90% load factor and an instant recovery time of 57ms regardless of data size."
Section 1.2:
> Dash uses a combination of new and existing techniques that are carefully engineered to achieve this goal.
> 1. We adopt fingerprinting that was used in PM tree structures to avoid unnecessary PM reads during record probing. The idea is to generate fingerprints (one-byte hashes) of keys and place them compactly to summarize the possible existence of keys.
> 2. Instead of traditional bucket-level locking, Dash uses an optimistic, lightweight flavor of it that relies on verification to detect conflicts, rather than (expensive) shared locks. This allows Dash to avoid PM writes for search operations.
> 3. Dash retains desirable properties. We propose a new load balancing strategy to postpone segment splits with improved space utilization. To support instant recovery, we limit the amount of work to be done upon recovery to be small ..., and amortize recovery work to runtime. Compared to prior work that handles PM programming issues in ad hoc ways, Dash uses PM programming models ... to systematically handle crash consistency, PM allocation and achieve instant recovery.
> Although these techniques are not all new, Dash is the first to integrate them for building hash tables that scale without sacrificing features on real PM.