Lecture

LSM Trees: Performance Analysis and Design Choices

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture delves into the analysis of the performance of Log-Structured Merge (LSM) trees, focusing on the trade-offs between write throughput and read speed. The instructor discusses the design choices involved in LSM trees, such as workload characterization, multi-level data structures, and the impact of storage heterogeneity. Various strategies to enhance performance, including thread local arrays and skip-list designs, are explored. Experiments with different setups, like Intel Xeon CPUs and varying cache sizes, are presented to showcase the practical implications of these design decisions. The lecture concludes with insights on leveraging Bloom filters and leveled merges to optimize LSM tree performance.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Related concepts (32)

Xeon

Xeon (ˈziːɒn ) is a brand of x86 microprocessors designed, manufactured, and marketed by Intel, targeted at the non-consumer workstation, server, and embedded system markets. It was introduced in June 1998. Xeon processors are based on the same architecture as regular desktop-grade CPUs, but have advanced features such as support for ECC memory, higher core counts, more PCI Express lanes, support for larger amounts of RAM, larger cache memory and extra provision for enterprise-grade reliability, availability and serviceability (RAS) features responsible for handling hardware exceptions through the Machine Check Architecture.

Cache (computing)

In computing, a cache (kæʃ ) is a hardware or software component that stores data so that future requests for that data can be served faster; the data stored in a cache might be the result of an earlier computation or a copy of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache, which is faster than recomputing a result or reading from a slower data store; thus, the more requests that can be served from the cache, the faster the system performs.

Xeon Phi

Xeon Phi was a series of x86 manycore processors designed and made by Intel. It was intended for use in supercomputers, servers, and high-end workstations. Its architecture allowed use of standard programming languages and application programming interfaces (APIs) such as OpenMP. Xeon Phi launched in 2010. Since it was originally based on an earlier GPU design (codenamed "Larrabee") by Intel that was cancelled in 2009, it shared application areas with GPUs.

CPU cache

A CPU cache is a hardware cache used by the central processing unit (CPU) of a computer to reduce the average cost (time or energy) to access data from the main memory. A cache is a smaller, faster memory, located closer to a processor core, which stores copies of the data from frequently used main memory locations. Most CPUs have a hierarchy of multiple cache levels (L1, L2, often L3, and rarely even L4), with different instruction-specific and data-specific caches at level 1.

Skylake (microarchitecture)

Skylake is Intel's codename for its sixth generation Core microprocessor family that was launched on August 5, 2015, succeeding the Broadwell microarchitecture. Skylake is a microarchitecture redesign using the same 14 nm manufacturing process technology as its predecessor, serving as a tock in Intel's tick–tock manufacturing and design model. According to Intel, the redesign brings greater CPU and GPU performance and reduced power consumption. Skylake CPUs share their microarchitecture with Kaby Lake, Coffee Lake, Cannon Lake, Whiskey Lake, and Comet Lake CPUs.

Related lectures (34)

File Organization: Storage and Cache Management

Explores file and page organization in databases, cache management, and log-structured files.

Caches - Performance

Explores cache memory performance evaluation, covering benchmarks, Amdahl's law, CPU performance, memory hierarchy, cache optimizations, and multilevel caches.

Buffer Management: DBMS and Replacement Policies Log in to Mediaspace to watch this video

Explores buffer management in DBMS, covering replacement policies and disk storage importance.

Cache Memory

Explores cache memory design, hits, misses, and eviction policies in computer systems, emphasizing spatial and temporal locality.

Transactional Memory: Hardware Simplification