Introduction
Modern non-volatile memories, such as Flash and Phase-change memory (PCM), offer high performance but suffer from a critical physical limitation: they wear out. Every write operation causes physical degradation, and after approximately $10^4$ to $10^5$ cycles, a cell becomes unusable.
Standard data structures are typically "wear-blind." In a standard hash table, the random nature of hashing often creates "hot spots"—cells that receive significantly more writes than others. Cuckoo hashing, while popular for its $O(1)$ worst-case lookup time, can be particularly damaging because a single insertion can trigger a chain reaction of evictions and re-writes. This paper introduces a modified cuckoo hashing algorithm designed to implement "wear leveling" directly into the hashing logic, extending the lifespan of modern hardware.
The Wear-Aware Algorithm
The authors propose a "power of $d$ choices" approach to cuckoo hashing. Instead of the standard two hash functions, the algorithm uses $d \ge 3$ hash functions, providing each item with $d$ possible locations.
Each cell in the table maintains a small "wear counter" tracking its total number of writes. When an item is inserted (or re-inserted after eviction), the algorithm follows a "Least-Worn" Rule: it examines all $d$ possible cells and selects the one with the minimum wear count. If the chosen cell is occupied, the resident item is evicted, and the process repeats. To maintain efficiency, the algorithm includes a computational shortcut that calculates the eventual termination wear count in constant time, preventing potential infinite loops.
Theoretical Insights
The core innovation lies in the mathematical shift from $d=2$ to $d \ge 3$. By adding just one more choice, the system's properties change drastically. The authors analyze the hash table as a random $d$-ary hypergraph, where components are primarily trees or unicyclic structures.
As shown in the structural analysis above, the wear values propagate through these components. The authors prove that the maximum wear on any cell is bounded by $\log \log n + O(1)$ with high probability. For any practical table size $n$, this bound is essentially a small constant, ensuring that no single cell becomes a premature point of failure.
Empirical Results
The algorithm's performance was tested using synthetic workloads, including 20 million initial insertions and long-term mixed operations (1 billion delete/insert pairs) to simulate a steady-state system.
The experimental data confirms the theoretical predictions. As seen in the figure above, the maximum wear for standard cuckoo hashing grows steadily with the number of operations. In contrast, the wear-aware version keeps the maximum wear exceptionally low and stable. In long-term tests with an 80% fill ratio, the "least-worn" variant reached a maximum wear of approximately 172 after a billion operations, while standard cuckoo hashing reached approximately 282.
Conclusion
By integrating wear counters and the power of $d$ choices, this approach bridges the gap between high-performance data structures and the physical constraints of non-volatile memory. While the method requires a small amount of extra storage for wear counters and necessitates $d \ge 3$ hash functions (slightly increasing lookup work), it successfully maintains $O(1)$ lookup times while significantly extending the operational life of the underlying memory hardware.
Summary updated