Comparing B-Tree and LSM Tree

Comparison of B-Tree and LSM Tree

  • LSM Trees are typically faster for writes, whereas B-Trees are thought to be faster for read.
  • Reads are typically slower in LSM Tree because they have to check several different data structures and SSTables at different stages of compaction.

Advantage of LSM Tree :

  • A B-Tree index must write every piece of data at least twice: One to "write ahead log", and once to the tree page (perhaps again on page split).
  • There is also overhead from having to write an entire page at a time, even if only few bytes in that page changed.
  • Log structured indexes also rewrite data multiple times due to repeated compaction and merging of SSTables, but that mostly carries by background threads.

Write Amplification and Disk performance :

  • One write to the database resulting in multiple writes to the disk over the course of database lifetime, is known as write amplification.
  • It is a particular concern on SSDs, which can only overwrite blocks a limited number of times before wearing out.
  • In write heavy application, write amplification has a direct performance cost.
  • Moreover, LSM-Trees are typically able to sustain higher write throughput than B-Tree.
  • LSM tree can be compressed better, and thus often produce smaller files on disk than B-Tree.
  • B-Tree storage engine leave disk space unused due to fragmentation.

Downside  of LSM Tree :

  • The compaction process sometimes interfere with the performance of ongoing reads and write.
  • The response time of queries to log structured storage engine can sometimes be quite high, B-Tree can be more predictable.
  • Another issue with compaction arises at high write throughput: Disk's write bandwidth needs to be shared between write (logging and flushing memtable to disk) and the compaction threads running in the background.
  • If compaction is not configured carefully, it can happen that compaction can not keep up with the rate of incoming writes. Hence,
    • number of unmanaged segments on disk keep growing until you run out of disk space.
    • read will also slow down because they need to check more segment files.
  • So, you need explicit monitoring to detect this situation.

Comments

Post a Comment

Popular posts from this blog

Distributed Lock with Redlock

 Distributed Lock with Redlock Distributed lock systems are used to ensure that only one process or thread can access a particular resource at a time. Redlock is a distributed lock system that was introduced by Redis. The goal of Redlock is to provide a reliable and fault-tolerant distributed lock service.   The Redlock system is designed to work in a distributed environment where multiple instances of a service or application can run concurrently. Each instance of the application can acquire a lock and perform some operations on the resource. The Redlock system ensures that only one instance of the application has access to the resource at a time.   Components of Redlock :   Lock Manager : The Lock Manager is responsible for managing the lock state and deciding which instance of the application can acquire the lock. It receives requests from the applications to acquire or release the lock.   The Lock Manager uses a distributed consensus algorithm to en...
Read more

Distributed Transaction

Distributed Transaction A distributed transaction across multiple database services involves multiple databases that are geographically distributed across  different locations .       Here are some important steps to consider when designing a system for distributed transactions across multiple database services:     Transaction Protocol      Transactional consistency      Concurrency control      Reliability and Fault-tolerance      Performance   Transactional Protocol A distributed transaction protocol is a set of rules and procedures that define how a distributed transaction should be executed across multiple databases .   It is used for Atomic commit across databases    There are several distributed transaction protocols to choose from, each with its own advantages and disadvantages.     Two-Phase Commit (2PC ) :   It is a widely-used protocol that ensures at...
Read more

Storage Engine

Image
Database Storage Engine Two kinds of database storage engine are most popular: Log Structured Storage Engine (SSTable, LSMTree) Page Oriented Storage Engine (B-Tree) Log Structured Storage Engine  Most of the databases internally use a log, which is an append only data file. Log file is an append only sequence of records It is not human readable, binary file Issues Since log file is append only file, so it keeps growing, hence resulting performance issue. While reading data, every time it looks from beginning Performance degrades if number of records are more in the database To mitigate these issues, a new concept came out called Indexing. Index In order to efficiently find the value for a particular key in the database, we need a different data structure, this is called an Index. In General the idea behind them is to keep some additional metadata on the side, which acts as a signpost and helps you to locate the data you want. If you want to search some data in a several different ...
Read more