Show HN: Aphelo – A Redis-like store in C++ with Progressive Rehashing
8 hours ago
- #hash-table
- #latency
- #systems-design
- The author built a Redis-like in-memory database in C++ called Aphelo and encountered a critical performance issue: hash table resizing caused unpredictable 200ms latency spikes, known as the 'stop-the-world' problem.
- Traditional hash tables resize by doubling the bucket array and rehashing all keys at once, an O(N) operation that blocks all requests, which is unacceptable for customer-facing APIs.
- To solve this, Aphelo implements progressive rehashing, where two hash tables (newer and older) are maintained during resizing, and migration work is distributed across subsequent GET, SET, or DEL operations.
- Each operation moves a fixed number of buckets (e.g., 128) from older to newer, amortizing the O(N) cost invisibly across O(N) operations, eliminating latency spikes.
- This approach transforms a large blocking operation into many incremental ones, a principle applicable beyond databases to garbage collection, log compaction, and system rebalancing.
- After implementation, Aphelo achieved 172,716 SET requests per second on consumer hardware with no latency spikes during resizing, proving the importance of addressing tail latency for user experience.