Co-designing log-structured merge key-value stores with a non-volatile storage hierarchy

Abstract

The trend of increasing size of datasets in storage-based applications has promoted the research of new methods and technologies for efficiently storing, processing, and analyzing large amounts of data. As a result, Log Structured Merge (LSM) Key-Value Stores (KVSs) have been highly adopted since their design allows high write throughput and enforces sequential disk access patterns. Additionally, with the advent of Non-Volatile Main Memory (NVMM), new storage technologies have emerged that offer faster access times compared to traditional block-based storage devices, thus accelerating KVSs. However, while NVMM devices offer faster access to data, they are typically limited in capacity and are often more expensive. To address this trade-off, contemporary storage solutions harness the capabilities of heterogeneous storage devices in two fundamental manners: caching and tiering. In this dissertation, we show that, on one hand, read-dominated workloads benefit from a caching approach, but their performance degrades under tiering. On the other hand, for write-dominated workloads, the tiering approach presents better performance, while storing the entire dataset on NVMM actually degrades performance. To overcome these challenges, this dissertation proposes KEIGO, a novel storage middleware that al lows LSM-based KVS to efficiently use storage hierarchies composed of NVMM and block-based devices. KEIGO is aware of the different I/O operations done by the KVS (e.g., foreground requests, and background flushes and compactions) and the characteristics of the underlying devices (e.g., concurrency, read/write asymmetry). This knowledge serves as a pivotal factor in optimizing KEIGO’s performance in the face of dynamic and mixed production workloads such as those observed in Nutanix and Meta. Moreover, KEIGO requires minimal code modifications to integrate into production-ready LSM KVSs. Conducted experiments show that KEIGO significantly enhances the throughput of LSM KVS solu tions, including RocksDB, Speedb, and LevelDB, by as much as 12.4×. Furthermore, it substantially reduces tail latency by up to 21.3× over both general-purpose storage solutions and LSM KVSs built from the ground up for hierarchical storage.

O aumento do volume de dados gerido por aplicações orientadas ao armazenamento tem promovido a in vestigação de novos métodos e tecnologias para os armazenar, processar e analisar eficientemente. Como resultado, os sistemas de armazenamento chave-valor (KVS) baseados em Log Structured Merge (LSM) têm sido amplamente adotados, já que o seu desenho permite um elevado débito de escritas e impõe padrões de acesso sequenciais. Além disso, com o desenvolvimento de dispositivos de memória não volátil (NVMM), surgiram novas técnicas de armazenamento que oferecem tempos de acesso mais rápidos comparativamente aos discos tradicionais baseados em blocos, acelerando assim o desempenho das KVSs. Contudo, embora os dispositivos NVMM ofereçam melhor desempenho, são normalmente limitados em termos de capacidade e mais caros. Para resolver este problema, as soluções de armazenamento atuais tiram partido das capacidades de armazenamento heterogéneo de duas formas: caching e tiering. Nesta dissertação demonstramos que, por um lado, as cargas de trabalho dominadas por leituras benefi ciam de caching, mas o seu desempenho degrada com as soluções de tiering. Para as cargas de trabalho dominadas por escritas, a abordagem de tiering é mais benéfica, tendo em conta que o armazenamento de todo o conjunto de dados em NVMM degrada o desempenho. De forma a resolver estes problemas, esta dissertação propõe um novo middleware de armazena mento, KEIGO, que ajuda KVSs a utilizar eficientemente armazenamento hierárquico composto por NVMM e outros dispositivos orientados ao bloco. O KEIGO tem conhecimento das diferentes operações de I/O efectuadas pela KVS (p.ex., pedidos de leitura e escrita, flushes e compactações) e das características dos dispositivos subjacentes (p.ex., concorrência, assimetria de leitura/escrita), permitindo otimizar o desempenho face a cargas de trabalho de produção dinâmicas e mistas, como as da Nutanix e da Meta. Através de uma avaliação compreensiva, mostramos que o KEIGO melhora o débito de LSM KVSs, incluíndo RocksDB, Speedb e LevelDB, em até 12.4×. Reduz ainda a latência em até 21.3× em relação a soluções genéricas e a KVSs criadas especificamente para armazenamento hierárquico.