"Gaining Constant time Lookup over Unorganized Data"

on YouTube ↗40m

" summary

Builds a disk-backed variant of Clojure’s HAMT as a durable hash index that maps fixed-length hashes to file offsets and delegates record decoding to a data-set SPI, giving sub-millisecond lookups without loading whole files into heap. It requires uniformly random fixed-length hashes (UUID or SHA-256) and is read-only (no updates). Deployed on EFS/SSDs, it shrinks per-JVM memory from gigabytes to a 6 MB root node and cut operational costs substantially.

AI-written summary · about

" chapters (7)

1. 0:00Start
2. 2:07mutual Transport Layer Security (mTLS)
3. 15:09a hunch
4. 18:49Characteristics of a solution
5. 25:18Customer to shard map
6. 31:51non-random hashes
7. 35:24Opening a hash-index

" related talks

• 24mWrite-Optimized Dynamic Hashing for Persistent MemoryMoohyeon Nam · FAST '19
• 14mSEPH: Scalable, Efficient, and Predictable Hashing on Persistent MemoryChao Wang, Junliang Hu, Tsun-Yu Yang, Yuhong Liang, Ming-Chang Yang · OSDI 2023
• 01h 05mImplementing Understandable World Class Hash Tables in C++Eduardo Madrid, Scott Bruce · CppCon 2022
• 34mLightweight RelationsMichael Steindorfer · JVM Language Summit 2017
• 21mUpdate on Raku Persistent Data StructuresDaniel Sockwell · The Raku Conference 2021
• 38mLight and Adaptive Indexing for Immutable DatabasesHåkan Råberg · Strange Loop 2022
• 45mEasy Scaling with Open Source Data StructuresTalip Ozturk · GOTO Chicago 2015
• 27mEfficient shared memory data structuresClaudio Freire · PyCon 2018