student profile: Ms Oana Balmau


Thesis work

Thesis title: Building High-Performance, Scalable Log-Structured Merge Key-Value Stores

Supervisors: Alan FEKETE , Willy ZWAENEPOEL

Thesis abstract:

Key-value (KV) stores are a widespread solution for handling large-scale data in cloud-based applications. They have several advantages over traditional DBMSs, including simplicity, scalability, and high throughput. The KV store space is vast. KV store systems are available for workloads that fit entirely in memory (e.g., Mica, Redis, and Memcached), as well as for workloads that require persistent storage (e.g., LevelDB, RocksDB). Log-Structured Merge trees (LSMs) are a popular design choice for the latter category. LSMs absorb writes in memory, thus masking the significant latency of I/O. LSM is an appealing design for an emerging type of workloads called HTAP (Hybrid Transactional Analytic Processing) workloads, such as recommender systems (e.g., used in online shopping and advertising), machine learning, time series, and IoT workloads. These workloads involve ingesting large amounts of data from users (which does not fit in memory), reading the data to analyze it, and serving the results back to the users in real time. It is therefore crucial for HTAP workloads to run on systems that provide low latency reads and high throughput writes. While LSM KVs are by design efficient in handling high throughput writes, there are still a number of open challenges before making LSMs fully suitable for HTAP workloads:

  1. Minimizing the reads latency still poses a significant challenge, especially for the tail latency.
  2. The background operations meant to maintain the LSM structure can have significant overhead, impacting both the throughput and latency of user operations.
  3. LSMs should take full advantage of modern multicore machines, being able to scale with the amount of memory and with the number of cores.

The following work addresses part of the issues above:

  1. FloDB (EuroSys ‘17). FloDB is a novel two-level LSM memory component architecture which allows throughput to scale on modern multicore machines with ample memory sizes. FloDB tackles challenge (3) outlined above. The main idea underlying FloDB is to bootstrap the traditional LSM architecture by adding a small in-memory buffer layer on top of the memory component. This buffer offers low-latency operations, masking the write latency of the sorted memory component. Integrating this buffer in the classic LSM memory component to obtain FloDB requires revisiting the algorithms of the user-facing LSM operations (search, update, scan). FloDB’s two layers can be implemented with state-of-the-art, highly-concurrent data structures. This way, FloDB eliminates significant synchronization bottlenecks in classic LSM designs, while offering a rich LSM API.
  2. TRIAD (USENIX ATC ‘17). TRIAD is a new persistent KV store based on LSM trees. TRIAD improves LSM KV throughput by reducing the write amplification arising in the maintenance of the LSM tree structure, through flushing and compaction. TRIAD tackles challenge (2) outlined above. The system uses a holistic combination of three techniques, acting at the three main levels of the LSM architecture. At the LSM memory component level, TRIAD leverages skew in data popularity to avoid frequent I/O operations on the most popular keys. At the storage level, TRIAD amortizes management costs by deferring and batching multiple I/O operations. At the commit log level, TRIAD avoids duplicate writes to storage.

Note: This profile is for a student at the University of Sydney. Views presented here are not necessarily those of the University.