2015 · 92 citations · 29 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureData StructuresParallel ComputingData Locality OptimizationData ParallelismMemory HierarchyMemory Hierarchy OptimizationParallel Data StructuresScalable Data StorageData Memory OrganizationKey-value StoresLog-structured StorageMulticore ArchitecturesMulticore Processor ArchitectureMulticore SystemsRandom Access Memory (Ram)Storage Scaling
Log-structured data stores (LSM-DSs) are widely accepted as the state-of-the-art implementation of key-value stores. They replace random disk writes with sequential I/O, by accumulating large batches of updates in an in-memory data structure and merging it with the on-disk store in the background. While LSM-DS implementations proved to be highly successful at masking the I/O bottleneck, scaling them up on multicore CPUs remains a challenge. This is nontrivial due to their often rich APIs, as well as the need to coordinate the RAM access with the background I/O.
29
Space/time trade-offs in hash coding with allowable errors
Burton H. Bloom · Communications of the ACM · 1970 · 7.5K citations · Full text
Giuseppe DeCandia, Deniz Hastorun, Madan Jampani et al. · 2007 · 3.5K citations
Avinash Lakshman, Prashant Malik · ACM SIGOPS Operating Systems Review · 2010 · 2.6K citations
Bigtable: a distributed storage system for structured data
Fay W. Chang, Jay B. Dean, Sanjay Ghemawat et al. · 2006 · 2K citations