View source for Log-structured merge-tree

{{Short description|Data structure}}
{{more footnotes|date=April 2013}}

{{Infobox data structure
| name = Log-structured merge-tree
| type = Hybrid (two tree-like components)
| invented_by = [[Patrick O'Neil]], Edward Cheng, Dieter Gawlick, [[Elizabeth O'Neil]]
| invented_year = 1996
| find_min_worst = O(N)
| insert_worst = O(1) (amortised)
| delete_min_worst = O(N)
| insert_avg = O(1) (amortised)
| find_min_avg = O(N)
| delete_min_avg = O(N)
}}
In [[computer science]], the '''log-structured merge-tree''' (also known as '''LSM tree''', or '''LSMT'''<ref>{{Cite book|last1=Zhang|first1=Weitao|last2=Xu|first2=Yinlong|last3=Li|first3=Yongkun|last4=Li|first4=Dinglong|title=2016 IEEE 22nd International Conference on Parallel and Distributed Systems (ICPADS) |chapter=Improving Write Performance of LSMT-Based Key-Value Store |date=December 2016|chapter-url=https://ieeexplore.ieee.org/document/7823794|pages=553–560|doi=10.1109/ICPADS.2016.0079|isbn=978-1-5090-4457-3 |s2cid=13611447 }}</ref>) is a [[data structure]] with performance characteristics that make it attractive for providing [[Database index|indexed]] access to files with high insert volume, such as [[transaction log|transactional log data]]. LSM trees, like other [[search tree]]s, maintain key-value pairs. LSM trees maintain data in two or more separate structures, each of which is optimized for its respective underlying storage medium; data is synchronized between the two structures efficiently, in batches.

One simple version of the LSM tree is a two-level LSM tree.<ref>{{Cite journal |last1=O’Neil |first1=Patrick |last2=Cheng |first2=Edward |last3=Gawlick |first3=Dieter |last4=O’Neil |first4=Elizabeth |date=1996-06-01 |title=The log-structured merge-tree (LSM-tree) |url=https://www.cs.umb.edu/~poneil/lsmtree.pdf |journal=Acta Informatica |language=en |volume=33 |issue=4 |pages=351–385 |doi=10.1007/s002360050048 |s2cid=12627452 |issn=1432-0525}}</ref> As described by [[Patrick O'Neil]], a two-level LSM tree comprises two [[Tree (data structure)|tree-like]] structures, called C<sub>0</sub> and C<sub>1</sub>. C<sub>0</sub> is smaller and entirely resident in memory, whereas C<sub>1</sub> is resident on disk. New records are inserted into the memory-resident C<sub>0</sub> component. If the insertion causes the C<sub>0</sub> component to exceed a certain size threshold, a contiguous segment of entries is removed from C<sub>0</sub> and merged into C<sub>1</sub> on disk. The performance characteristics of LSM trees stem from the fact that each component is tuned to the characteristics of its underlying storage medium, and that data is efficiently migrated across media in rolling batches, using an algorithm reminiscent of [[merge sort]]. Such tuning involves writing data in a sequential manner as opposed to as a series of separate random access requests. This optimization reduces seek time in [[Hard disk drive|hard-disk drives]] (HDDs) and latency in [[Solid-state drive|solid-state drives]] (SSDs).
[[File:LSM Tree.png|alt=Diagram illustrating compaction of data in a log-structured merge tree|thumb|Diagram illustrating compaction of data in a log-structured merge tree]]

Most LSM trees used in practice employ multiple levels. Level 0 is kept in main memory, and might be represented using a tree. The on-disk data is organized into sorted ''runs'' of data. Each run contains data sorted by the index key. A run can be represented on disk as a single file, or alternatively as a collection of files with non-overlapping key ranges. To perform a query on a particular key to get its associated value, one must search in the Level 0 tree and also each run.
The Stepped-Merge version of the LSM tree<ref>{{Cite journal |last1=Jagadish |first1= H.V. |last2=Narayan |first2=P.P.S. | last3 = Seshadri | first3 = S. | last4=Sudarshan | first4 = S. | last5 = Kanneganti | first5=Rama| date=1997 |title=Incremental Organization for Data Recording and Warehousing |url=https://www.vldb.org/conf/1997/P016.PDF |journal=Proceedings of the VLDB Conference | publisher=VLDB Foundation |pages=16–25 }}</ref> is a variant of the LSM tree that supports multiple levels with multiple tree structures at each level.

A particular key may appear in several runs, and what that means for a query depends on the application.  Some applications simply want the newest key-value pair with a given key. Some applications must combine the values in some way to get the proper aggregate value to return. For example, in [[Apache Cassandra]], each value represents a row in a database, and different versions of the row may have different sets of columns.<ref>{{Cite web|url=http://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra|archive-url=https://web.archive.org/web/20140213134601/http://www.datastax.com/dev/blog/leveled-compaction-in-apache-cassandra|url-status=dead|archive-date=February 13, 2014|title=Leveled Compaction in Apache Cassandra : DataStax|date=February 13, 2014}}</ref>

In order to keep down the cost of queries, the system must avoid a situation where there are too many runs.

Extensions to the 'leveled' method to incorporate [[B+ tree]] structures have been suggested, for example bLSM<ref>{{Cite book |last1=Sears |first1=Russell |last2=Ramakrishnan |first2=Raghu |title=Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data |chapter=BLSM |date=2012-05-20 |chapter-url=https://doi.org/10.1145/2213836.2213862 |series=SIGMOD '12 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=217–228 |doi=10.1145/2213836.2213862 |isbn=978-1-4503-1247-9|s2cid=207194816 }}</ref> and Diff-Index.<ref>{{Citation |last1=Tan |first1=Wei |title=Diff-Index: Differentiated Index in Distributed Log-Structured Data Stores |date=2014 |url=https://openproceedings.org/EDBT/2014/edbticdt2014industrial_submission_17.pdf |publisher=OpenProceedings.org |language=en |doi=10.5441/002/edbt.2014.76 |access-date=2022-05-22 |last2=Tata |first2=Sandeep |last3=Tang |first3=Yuzhe |last4=Fong |first4=Liana}}</ref> LSM-tree was originally designed for write-intensive workloads. As increasingly more read and write workloads co-exist under an LSM-tree storage structure, read data accesses can experience high latency and low throughput due to frequent invalidations of cached data in buffer caches by LSM-tree compaction operations. To re-enable effective buffer caching for fast data accesses, a Log-Structured buffered-Merged tree (LSbM-tree) is proposed and implemented.<ref>{{Cite conference |author= Dejun Teng|author2= Lei Guo|author3= Rubao Lee|author4=Feng Chen|author5=Yanfeng Zhang|author6= Siyuan Ma|author7=Xiaodong Zhang | title="A Low-cost Disk Solution Enabling LSM-tree to Achieve High Performance for Mixed Read/Write Workloads" |conference= ACM Transactions on Storage | year=2018 |pages = 1–26| doi=10.1145/3162615 }}</ref>

== References ==
{{reflist}}

;General
* {{Cite journal | last1 = O'Neil | first1 = Patrick E.| last2 = Cheng | first2 = Edward| last3 = Gawlick | first3 = Dieter| last4 = O'Neil | first4 = Elizabeth|author4-link=Elizabeth O'Neil| title = The log-structured merge-tree (LSM-tree)| doi = 10.1007/s002360050048| journal = Acta Informatica| volume = 33| issue = 4| pages = 351–385| date=June 1996 | citeseerx = 10.1.1.44.2782| s2cid = 12627452}}
* {{Cite book | last1 = Li | first1 = Yinan| last2 = He | first2 = Bingsheng| last3 = Luo | first3 = Qiong| last4 = Yi | first4 = Ke| chapter = Tree Indexing on Flash Disks| doi = 10.1109/ICDE.2009.226 | title = 2009 IEEE 25th International Conference on Data Engineering| pages = 1303–6| year = 2009 | isbn = 978-1-4244-3422-0 | citeseerx = 10.1.1.144.6961| s2cid = 2343303}}
* {{Cite journal | last1 = Luo | first1 = Chen| last2 = Carey | first2 = Michael J.|author2-link=Michael_J._Carey_(computer_scientist)| title = LSM-based storage techniques: a survey | doi = 10.1007/s00778-019-00555-y| journal = The VLDB Journal | date=July 2019 | volume = 29| pages = 393–418| arxiv = 1812.07527| s2cid = 56178614}}

==External links==
* [http://www.benstopford.com/2015/02/14/log-structured-merge-trees An Overview of Log Structured Merge Trees]

{{CS trees}}

[[Category:Trees (data structures)]]
[[Category:Database index techniques]]