Shulou(Shulou.com)06/01 Report--

This article will explain in detail what the LSM used in the database refers to. The content of the article is of high quality, so the editor will share it with you for reference. I hope you will have a certain understanding of the relevant knowledge after reading this article.

Many databases use LSM Tree's storage model, including LevelDB,HBase,Google BigTable,Cassandra,InfluxDB. So in the interview process will often be asked, the latest review of the principle of LSM Tree.

Characteristics

In general, the performance of data writing is greatly improved by converting a large number of random writes to sequential writes, although partial read performance is sacrificed at the same time.

It is only suitable for storing data whose key values are ordered and writing is larger than reading, or where the read operation is usually continuous with key values.

Storage model WAL

It is often used when designing a database. When inserting a piece of data, the data is written sequentially into the WAL file and then inserted into the MemTable in memory. This ensures the persistence of the data, will not lose the data, and is written sequentially, the speed is very fast. When the program hangs and restarts, the MemTable in memory can be recovered from the WAL file.

MemTable

MemTable corresponds to the WAL file, which is the storage structure of the contents of the file in memory, which is usually implemented in SkipList. MemTable provides an operation interface for writing, deleting and reading kmurv data. Internally, the KMurv pairs are stored sequentially according to the key value, so that it is convenient to quickly serialize to the SSTable file, still keeping the order of the data.

Immutable Memtable

As the name implies, Immutable Memtable is a read-only MemTable in memory. Because the memory is limited, we usually set a threshold. When the memory occupied by MemTable reaches the threshold, it is automatically converted to Immutable Memtable,Immutable Memtable and MemTable. The difference between Immutable Memtable,Immutable Memtable and MemTable is that it is read-only, and the system will generate a new MemTable for write operations to continue to write.

The reason for using Immutable Memtable is to avoid blocking write operations when serializing the contents of MemTable to disk.

SSTable

SSTable is the orderly storage of the data in MemTable on disk, and its internal data is arranged from small to large according to key. Usually in order to speed up the search, it is necessary to add a data index to the SSTable, so that you can quickly read and locate the specified KMTV data.

The hierarchical structure commonly used in SSTable, such as in LevelDB. When the data in the MemTable reaches the specified threshold, a new SSTable is created at the Level 0 layer. When the number of files under a certain Level exceeds a certain value, a SSTable file under this Level will be merged with a higher-level SSTable file. Because the KMurv data in SSTable are orderly, which is equivalent to a multi-way merge sort, the merge operation is quite fast, and finally generate a new SSTable file and delete the old file, thus completing a merger process.

Implementation writing of common operations

In LSM Tree, the write operation is quite fast, you only need to write the contents of the current operation sequentially in the WAL file, and then write the KLV data to MemTable after success. Although the disk IO is done once, because it is a sequential append write operation, it is relatively efficient and does not slow down the write speed. Writing data into MemTable is actually inserting a piece of data into SkipList, and the process is quite simple and fast.

Update

In fact, the update operation does not really exist, it is no different from writing a KMurv data, but when reading, it will start to find the data from the SSTable file of the Level0 layer, and the data must be newer in the lower-level SSTable file than in the high-level file, so you can always read the latest data. In other words, there may be multiple data with the same key value in the entire LSM Tree at this time, and the old value will be deleted only when the SSTable file is merged later.

Delete

Delete a record of the operation is more special, not immediately delete the data from the file, but record the delete operation mark of the key, the same as the insert operation, the insert operation inserts the k-del v value, while the delete operation inserts the k-del tag, which will be deleted only when the SSTable file is merged.

Compaction

As data continues to serialize from Immutable Memtable to SSTable files on disk, the number of SSTable files increases, and there may be many update and delete operations that do not immediately operate on the file, but just store a record of the operation, resulting in a large number of data with the same key value in the entire LSM Tree, taking up disk space.

In order to save disk space and control the number of SSTable files, multiple SSTable files need to be merged to generate a new SSTable file. For example, there are five 10-line SSTable files to be merged into a 50-line SSTable file, but there may be data with duplicate key values, and we only need to keep the latest one. At this time, the newly generated SSTable may only have 40 rows of records.

We usually use the method of hierarchical merging in the process of use, which has the following characteristics:

Each layer contains a large number of SSTable files, and the range of key values is not repeated, so the query operation only needs to query one file at this layer. (the first layer is special. Key values may fall in multiple files and do not apply to this feature.)

When the number of files on the first layer reaches the specified number, one of the files will be merged into the files on the upper layer.

Read

The reading efficiency of LSM Tree is not high. When you need to read the data of the specified key, first look for it in the MemTable and Immutable MemTable in memory. If it is not found, then continue to start from the Level layer 0. If you cannot find it, you will find it from the higher-level SSTable file. If the search fails, the data of this key does not exist in the entire LSM Tree. If the data for this key is found anywhere in the middle, the data found in this path is up-to-date.

The range of key values of the SSTable file at each layer is not duplicated, so you only need to look for one of the SSTable files to determine whether the data for the specified key exists in this layer. The Level 0 layer is special because the data is written directly to this layer by Immutable MemTable, so the key value range of the SSTable file in the Level 0 layer may be duplicated, and you may need to look for multiple files when looking for data.

Optimized reading

Because this kind of reading efficiency is very poor, some optimizations are usually carried out, such as the Mainfest file in LevelDB, which records some key information of the SSTable file, such as the number of Level layers, file name, minimum key value, maximum key value, etc., this file is usually not too large, can be put into memory, can help quickly locate the SSTable file to be queried, and avoid frequent reading.

Another frequently used method is the Bloom filter parser, which is an effective way to use memory to determine whether a file contains a keyword.

The idea of LSM Tree is very practical, converting random writes to sequential writes to greatly improve the performance of write operations, but at the expense of partial read performance.

Because of the characteristics of time series database, the algorithm of using LSM Tree is very suitable. Continuously write a large amount of data, data and time-related, encoded into key values, it is easy to make key values orderly. Read operations are relatively small, and usually do not read the value of a single key, but data over a period of time, which reduces the disadvantage of poor read performance of LSM Tree. On the contrary, because the data is arranged in order of key values in SSTable, it is also efficient to read large chunks of continuous data.

On the use of the database LSM refers to what is shared here, I hope the above content can be of some help to you, can learn more knowledge. If you think the article is good, you can share it for more people to see.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.