Scaling Embedded Key-Value Storage with a Local Partitioning Layer
Resumo
Embedded key-value stores such as LMDB, LevelDB and RocksDB are widely used due to their low deployment complexity, and efficient local persistence. However, operations within a single database are constrained by the synchronization and resource management mechanisms of the underlying storage engine, limiting concurrency under highly parallel workloads. This paper presents a partitioning layer that distributes data across multiple storage engine instances while exposing a unified key-value interface. The architecture uses fine-grained key-to-partition assignment through a routing index and partition-level synchronization. It also supports hash-based lock-striping strategy and optional workload-aware repartitioning. The design is storage-engine agnostic and requires no modifications to existing embedded databases. Experiments with YCSB workloads and multiple storage engines reach up to 2× the throughput of standalone instances on single-key operations, and show the costs of range scans, repartitioning, and extra resource use.Referências
Chu, H. (2026). Lightning memory-mapped database (lmdb). [link]. Ubuntu package liblmdb-dev, version 0.9.31.
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010). Benchmarking cloud serving systems with ycsb. In Proceedings of SoCC ’10, page 143–154.
Curino, C., Jones, E., Zhang, Y., and Madden, S. (2010). Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow., 3(1–2):48–57.
Dean, J. and Ghemawat, S. (2026). Leveldb. [link]. Ubuntu package libleveldb-dev, version 1.23.
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007). Dynamo: amazon’s highly available key-value store. SIGOPS Oper. Syst. Rev., 41(6):205–220.
DeWitt, D. and Gray, J. (1992). Parallel database systems: the future of high performance database systems. Commun. ACM, 35(6):85–98.
Didona, D. and Zwaenepoel, W. (2019). Size-aware sharding for improving tail latencies in in-memory key-value stores. In USENIX NSDI, NSDI’19.
George, L. (2011). HBase: The Definitive Guide. O’Reilly Media.
Goulart, H., Trombeta, J., Franco, Á., and Mendizabal, O. (2023). Achieving enhanced performance combining checkpointing and dynamic state partitioning. In SBAC-PAD.
Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition.
Hong, B., Kwon, Y., Ahn, J. H., and Kim, J. (2016). Adaptive and flexible key-value stores through soft data partitioning. In 2016 IEEE 34th International Conference on Computer Design (ICCD), pages 296–303.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, pages 359–392.
Lakshman, A. and Malik, P. (2010). Cassandra: a decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44(2):35–40.
Lim, H., Han, D., Andersen, D. G., and Kaminsky, M. (2014). Mica: a holistic approach to fast in-memory key-value storage. In Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation, NSDI’14, page 429–444, USA. USENIX Association.
Luiz, D. and Mendizabal, O. (2024). Lightweight asynchronous repartitioning for local state partitioned systems. In Proceedings of the 25th Brazilian Symposium on High Performance Computing Systems. SBC.
Luiz, D. P. and Mendizabal, O. M. (2026). Stall-free asynchronous state repartitioning with a proactive workload tracking window. Concurrency and Computation: Practice and Experience, 38(3):e70581.
Mao, Y., Kohler, E., and Morris, R. T. (2012). Cache craftiness for fast multicore keyvalue storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, page 183–196, New York, NY, USA. Association for Computing Machinery.
Meta Platforms, Inc. (2026). Rocksdb. [link]. Ubuntu package librocksdb-dev, version 8.9.1.
O’Neil, P., Cheng, E., Gawlick, D., and O’Neil, E. (1996). The log-structured merge-tree (lsm-tree). Acta Informatica, 33:351–385.
Quamar, A., Kumar, K. A., and Deshpande, A. (2013). Sword: Scalable workload-aware data placement for transactional workloads. In International Conference on Extending Database Technology (EDBT).
Cooper, B. F., Silberstein, A., Tam, E., Ramakrishnan, R., and Sears, R. (2010). Benchmarking cloud serving systems with ycsb. In Proceedings of SoCC ’10, page 143–154.
Curino, C., Jones, E., Zhang, Y., and Madden, S. (2010). Schism: a workload-driven approach to database replication and partitioning. Proc. VLDB Endow., 3(1–2):48–57.
Dean, J. and Ghemawat, S. (2026). Leveldb. [link]. Ubuntu package libleveldb-dev, version 1.23.
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., and Vogels, W. (2007). Dynamo: amazon’s highly available key-value store. SIGOPS Oper. Syst. Rev., 41(6):205–220.
DeWitt, D. and Gray, J. (1992). Parallel database systems: the future of high performance database systems. Commun. ACM, 35(6):85–98.
Didona, D. and Zwaenepoel, W. (2019). Size-aware sharding for improving tail latencies in in-memory key-value stores. In USENIX NSDI, NSDI’19.
George, L. (2011). HBase: The Definitive Guide. O’Reilly Media.
Goulart, H., Trombeta, J., Franco, Á., and Mendizabal, O. (2023). Achieving enhanced performance combining checkpointing and dynamic state partitioning. In SBAC-PAD.
Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming, Revised Reprint. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition.
Hong, B., Kwon, Y., Ahn, J. H., and Kim, J. (2016). Adaptive and flexible key-value stores through soft data partitioning. In 2016 IEEE 34th International Conference on Computer Design (ICCD), pages 296–303.
Karypis, G. and Kumar, V. (1998). A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM Journal on Scientific Computing, pages 359–392.
Lakshman, A. and Malik, P. (2010). Cassandra: a decentralized structured storage system. SIGOPS Oper. Syst. Rev., 44(2):35–40.
Lim, H., Han, D., Andersen, D. G., and Kaminsky, M. (2014). Mica: a holistic approach to fast in-memory key-value storage. In Proceedings of the 11th USENIX Conference on Networked Systems Design and Implementation, NSDI’14, page 429–444, USA. USENIX Association.
Luiz, D. and Mendizabal, O. (2024). Lightweight asynchronous repartitioning for local state partitioned systems. In Proceedings of the 25th Brazilian Symposium on High Performance Computing Systems. SBC.
Luiz, D. P. and Mendizabal, O. M. (2026). Stall-free asynchronous state repartitioning with a proactive workload tracking window. Concurrency and Computation: Practice and Experience, 38(3):e70581.
Mao, Y., Kohler, E., and Morris, R. T. (2012). Cache craftiness for fast multicore keyvalue storage. In Proceedings of the 7th ACM European Conference on Computer Systems, EuroSys ’12, page 183–196, New York, NY, USA. Association for Computing Machinery.
Meta Platforms, Inc. (2026). Rocksdb. [link]. Ubuntu package librocksdb-dev, version 8.9.1.
O’Neil, P., Cheng, E., Gawlick, D., and O’Neil, E. (1996). The log-structured merge-tree (lsm-tree). Acta Informatica, 33:351–385.
Quamar, A., Kumar, K. A., and Deshpande, A. (2013). Sword: Scalable workload-aware data placement for transactional workloads. In International Conference on Extending Database Technology (EDBT).
Publicado
03/11/2026
Como Citar
LUIZ, Douglas Pereira; MENDIZABAL, Odorico Machado.
Scaling Embedded Key-Value Storage with a Local Partitioning Layer. In: SIMPÓSIO EM SISTEMAS COMPUTACIONAIS DE ALTO DESEMPENHO (SSCAD), 27. , 2026, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2026
.
p. 510-523.
DOI: https://doi.org/10.5753/sscad.2026.34969.
