![]() However, it’s worth to point out that many modern LSM implementations in the database field have something in common: Sorted String Tables. Stating that something is implemented as an LSM Tree doesn’t necessarily say anything about the lookup complexity, or even the internal file layout, only about the conceptual structure. In this light, it’s worth mentioning that, even though LSM Trees are often contrasted with B-Trees, this comparison is not strictly accurate, my highlight here is that LSM Trees allow immutable, mergeable files and the nature of the primary index for the table is a matter of implementation (therefore, even B-Trees can be used as index data structure here). The seminal LSM paper suggests an implementation of the disk resident trees similar to the B-Tree, with the difference that it’s optimized for sequential disk access and the nodes can have a full occupancy (we’ll discuss the occupancy in more details when discussing B-Trees). Let’s start with the Log Structured Merge Trees, as the concept is quite straightforward. We’ll be discussing the examples of mutable and immutable storage when looking at LSM-Trees (Log Structured Merge Trees) and B-Tree variants. Of course, the exact scope of work done by the housekeeping process heavily depends on the concrete implementation. ![]() On the other hand, mutable files may have to be rewritten partially or completely to decrease fragmentation, merge overflow areas and reclaim space occupied by updated or deleted records (as their new contents were written elsewhere). Since amount of allocated files constantly grows, immutable data structures have to merge and rewrite files in order to make sure that the least amount of files is hit during the query, as the requested record might be spread across multiple files. In contrast, mutable data structures employ hierarchical locks and latches in order to ensure on disk data structure integrity, allow multiple readers at the same time but give exclusive ownership for parts of tree to writers.īoth mutable and immutable data structures require some housekeeping in order to optimize performance but for different reasons. Another advantage of immutable files is that data can be read from the disk without any segment locking between operations, which significantly simplifies concurrent access. All of this might slow down both subsequent reads and writes. While this is a nice compromise, sometimes writes fill up all the designated space and overflow areas have to be created. Some databases, instead of doing in-place updates, just mark the outdated record as “deleted” (so that it will eventually be garbage-collected) and append new records to the specially designated update area of the file. After some time, randomly written file might require defragmentation. Some structures require node splitting, that will relocate already written parts. The mutable data structure will be pre-allocated in a single pass, but the subsequent writes will be random. Keeping the data structure immutable favors the sequential writes: data is written on disk in a single pass, append-only. The obvious advantage of the immutable data structures is that the storage overhead can be minimized: we do not have to reserve any extra space for data that is going to be inserted later or for the cases when the updated records require more space than the originally written ones. Here, we’ll be talking about the mutability on disk, so semantics of construction and functional programming related concepts aren’t relevant for the purpose of our discussions. One of the differences between the data structures we’re going to be discussing over the next chapters is mutability (or lack of thereof). ![]() Each of them have their own advantages and disadvantages, so building a database system is always about trade-offs and we’ll try to address some of those as well. Today we’re going to explore one of the types of storage often used in the databases. ![]() Now, it’s time to start moving towards higher level concepts. In the first and second parts, we’ve discussed underlying Operating System mechanisms that help to perform writes on disk. New series on Distributed System concepts in Databases can be found here. If you like the series, check out my book on Database Internals! ![]()
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |