Note:
This topic has been translated from a Chinese forum by GPT and might contain errors.Original topic: 请问什么是读放大和写放大
|
username: TiDBer_JlY1JCJ5
In LSM-tree, read amplification and write amplification are mentioned. What do these terms mean? I read an article but still don’t quite understand. Is there a more comprehensible explanation available? Also, why is it said that LSM-tree trades space for time?
Read amplification and write amplification are both issues of LSM-trees. The main reason is that the data structure requires maintaining multiple copies in memory and performing a lot of unnecessary disk operations during the merge process. For more details, you can read this introduction to B-Tree and LSM-Tree:
TiKV | B-Tree vs LSM-Tree
The image you provided is not visible. Please provide the text you need translated.
Read amplification refers to the need for multiple merge operations in an LSM-Tree during range queries to obtain the required data. Since newer data in the upper layers may overwrite older data in the lower layers and there are intersections between layers, multiple merge operations may be necessary to retrieve a segment of data. This results in read amplification, where the amount of data read is greater than the actual data.
Write amplification refers to the need for multiple disk write operations in an LSM-Tree during write operations. Each write operation requires writing data to the log and flushing dirty pages. Even if only one byte of data is modified, the entire page needs to be written to disk. This results in write amplification, where the actual amount of data written is greater than the amount of data modified.
Each change in TiDB is an insertion of a key-value pair, so does write amplification really exist? I don’t think writing logs counts as write amplification. Does TiDB have the concept of flushing dirty pages or block writes? It feels like this is the logic of Oracle and MySQL, right?
The data structure of TiDB is LSM-tree, and write amplification is an issue with LSM-tree.
By trading space for time, the LSM-tree improves write speed, but the cost is increased space usage. Can it be understood this simply?
Read amplification here refers to the situation where a simple read operation becomes more complex, requiring the lookup of more resources to find the data. Write amplification means that any DML statement in TiDB directly writes new data instead of modifying the existing data.
The name LSM-tree (Log-Structured-Merge-Tree) often gives beginners a wrong impression. In fact, unlike B+ trees or red-black trees, which are strictly tree-like data structures, the LSM tree is actually a storage structure. The LSM tree records all operations such as inserts, modifications, and deletions (note that these are operation records) in memory. When these operations reach a certain amount of data, they are then sequentially written to disk in batches. This is different from the B+ tree, where data updates directly modify the corresponding values at the original data location. However, in the LSM tree, data updates are logged; when a piece of data is updated, an update record is directly appended. The purpose of this design is to ensure sequential writes, continuously flushing the Immutable MemTable to persistent storage without modifying the keys in the previous SSTable, thus ensuring sequential writes.
The so-called space amplification refers to the situation where the actual disk space occupied by the data in the storage engine is more than the actual data size. For example, if the actual data size is 10MB but it takes up 25MB of space when stored, then the space amplification factor is 2.5.
Why does space amplification occur? Obviously, in an LSM-based storage engine, data inserts, deletes, and updates are not in-place but wait for compaction to execute on the corresponding key. This means that a key may correspond to multiple values (with delete markers considered as special values), and only one value is truly valid, while the others count as space amplification. Additionally, during the compaction process, the original data cannot be deleted until the operation is complete (to prevent irrecoverable errors), so the same data being compacted can expand up to twice its original size, which also falls under the category of space amplification.
Yes, the space will increase, but with compression, it won’t increase too much.
The storage structure of the database is the foundation for solving many problems. It seems that more research on the LSM tree is necessary.
Is compression the automatic compression of SSTables in an LSM tree?
This topic was automatically closed 60 days after the last reply. New replies are no longer allowed.
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: 
|
username: