3.1

Design of the new sstable

According to the LSMA design scheme, the file structure needs to support the “append” operation, so the original LevelDB sstable architecture can no longer meet the requirements, and a new sstable file format needs to be Figure 1.

There are two issues to consider in this process:

Based on the above considerations, the final design of the new sstable file structure is shown in Figure. 2 a), including a header (header) and multiple old sstable file structures (sst). In the following part, we will explain how to solve the above two problems under this new file structure. For the organization and indexing of the old file sstable, it is realized through the header index sst. The header structure is shown in Figure. 2 b). In order to facilitate reading, the header is set to a fixed length of 100 bytes, of which 4 bytes are used To record the number of ssts, the maximum 12-byte sst tail offset, that is, each new sstable contains at most 12 ssts that can be appended. This avoids including too many ssts, causing huge search time.

Figure 2.

The structure of new sstable.

For the organization and indexing of the old file sstable, it is realized through the header index sst. The header structure is shown in Figure. 2. b). In order to facilitate reading, the header is set to a fixed length of 100 bytes, of which 4 bytes are used To record the number of ssts, the maximum 12-byte sst tail offset, that is, each new sstable contains at most 12 ssts that can be appended. This avoids including too many ssts, causing huge search time.

For concurrency security issues, because the size of the header design is fixed, and the appended file is performed at the end of the file, it will not affects the header, so it can be directly and safely appended (before the append is completed, the header index is multiple ssts of the old version, and the query operation will not be aware of it), only after the appended file is completed, exclusive access to read and update The header is enough, so it is only a 100-byte read and write operation, which basically does not affect the read performance too much, and can also ensure safe access.

In addition to the above-mentioned new sstable file design, some simplified changes have been made to the sst file structure. The modified structure is shown in Figure. 2 c). After the change, the data block and the filter block are bound together, and a data block corresponds to a filter block, instead of creating a new filter block according to the size of the accumulated data records like the original LevelDB. In addition, after the data block and the filter block It also requires 1-byte combination type and 4-byte CRC check code.

Then there is the index block and tail, the index block is the same as the original, and because the filter block and the data block are bound together, there is no need for a separate metadata index block. The tail structure is shown in Figure. 2 d), with a fixed length of 64 bytes. Because there is no metadata index block, the two parts of metadata offset (meta offset) and metadata size (meta size) are deleted, and the filter name (filter name) part in the metadata index block is added. Also added the number of index entries (index count) and the number of key-value entries (kv num) sections.

3.2

Merge Iterator

The difference with the original LevelDB is that the input file may only contain one level, while the file structure has changed, the iterators also need to be redesigned. Finally, there are the following four iterators according to the type of merger, as shown in Figure. 3.

Figure 3.

The depiction of iterator architecture for different files in LSMA.

3.3

The writeback after merging

Writeback refers to the processing of the key-value records retained after cleaning. The original LevelDB just appends to the newly created file. If the file size exceeds the set threshold, just create a new file. However, there are additional cases in the proposed new merge solution, which mainly includes two different ways of writing files:

Figure 4.

The merge scheme that the left side can exceed and the right side cannot for LSMA.

4.1

The input file selection

Because the header of the new sstable file has a fixed length, the maximum number of ssts it contains is limited, so theoretically there should be a new trigger condition compared to the original trigger condition—the number of ssts contained in new sstable reaches the threshold. In the actual implementation process, there are two situations that affect the merging of the file: one is that the new sstable is used as the upper layer input file for merging, then the file will be read and then deleted without exceeding the threshold; the other is that the new sstable If the new sstable is selected as the lower-level file for merging, it is very likely that the upper-level file is appended to the new sstable and the threshold value exceeds the threshold. In this case, just use the new sstable as an input file and participate in reorganization, sorting and cleaning together with the upper-level files.

Since the process of selecting input files in the original LevelDB was too complicated, a new process was redesigned, as shown in Figure. 5. There are two main improvements. Firstly, the expansion by serial number and the expansion by key range are integrated into one function. Specifically, the left side of the file is expanded by key range, and the right side is expanded by sequence number. Secondly, to improve the redundant operation of the step of expanding the upper-level files without increasing the number of lower-level files and not exceeding the file size threshold, in the new selection scheme, the first expansion will calculate the “sub-boundary” of the lower-level file, and then reversely expand the upper-level file set through this “sub-boundary”. Assuming the expanded lower-level file set is g, then the secondary boundary of the lower file set is the position indicated by two dotted lines, that is, the right boundary of file f and the left boundary of file h. Using this sub-boundary as the boundary to reversely expand the upper-level files will definitely not increase the number of lower-level file sets.

Figure 5.

The process of selecting input files for compaction.

4.2

Caching and Versioning

In addition to adding and deleting files in traditional storage engines, files will also be modified. Therefore, separate cache processing is required for modified files, otherwise the consistency of queries will be affected. Because new sstable contains multiple ssts that may have overlapping key ranges, both filters and index blocks are set as arrays, and in order to better adapt to the modified sst, rewrite, we added FilterBlockReader and IndexBlock. The specific implementation timing of the cache update of additional files is to immediately force the relevant content to be read from the hard disk to update the cache after each additional file is generated and closed.

After the cache is updated, the merge process is basically completed, and the rest is the version iteration of the file itself. Also because of the particularity of new sstable addition, the version iteration should also be designed separately for it. First of all, all files different from the previous version should be recorded in VersionEdit, and these files should be merged with the files of the corresponding layer of the previous version to form a new version, recorded in the version chain, queued and processed, as shown in the Figure 6.

Figure 6.

The version iteration of files in LSMA.

In order to permanently save the iterative record of the updated version, the basic attribute of sst count introduced by new sstable is recorded in the manifest file, so as to realize the reconstruction of the LSM-Tree after the database is restarted.

5.1

Experiment setup

The experimental verification environment is shown in Table 1. We also set the key of the key-value record to 16 bytes and the value to 100 bytes, mainly to test its performance on the basis of the effectiveness of the scheme, including LSMA’s merge performance, write performance and query Performance, the specific experimental method is as follows:

Table 1.

The experimental setups.

5.2

Consolidation performance

Continuously write a large amount of data to the storage engine, and then compare the number of merging, IO volume and delay between the LSMA scheme and the original LevelDB scheme under the same conditions.

The comparison of the number of merges is shown in Figure 7. The results show that with the increase of the amount of written data, the number of merges of the LSMA scheme is basically about twice that of LevelDB, and there is a tendency to continue to increase. The comparison of the amount of merged IO is shown in Figure 8. Combining the number of merges, it can be seen that even though the number of merges generated by the LSMA scheme is more, the total IO amount is lower than that of LevelDB. Among them, the amount of read data is maintained at about 55% of LevelDB, and the amount of written data is maintained at about 60%. The difference in read-write ratio is also due to the fact that the amount of data cleaned is less than that of LevelDB.

Figure 7.

The times of compaction.

Figure 8.

The I/O times of compaction.

Merge delay comparison is shown in Figure 9. The maximum delay LSMA scheme for a single merge is comparable to LevelDB, but the minimum delay LSMA is an order of magnitude lower than LevelDB as the amount of written data increases. As shown in Figure 10, the total delay is about 70% of that of LevelDB in the LSMA scheme. Combined with the previous test results, it shows that there are a large number of lightweight merges in the LSMA scheme, which is undoubtedly beneficial and can reduce the probability of write stalls.

Figure 9.

Compaction delay.

Figure 10.

Compaction total delay.

5.3

Write performance

Use the db_bench of LevelDB itself to make slight changes, test and compare the sequential write performance, random write performance and overwrite performance of the LSMA scheme and the original LevelDB scheme under the same conditions.

The sequential write performance test results are shown in Figure 11 and Figure 12. It can be seen that there is not much difference in performance between the two. This is because the merge triggered by sequential write will never overlap the key range, and a single file is directly moved. To the lower layer, the additional advantages of LSMA cannot be reflected. For data writing, the overall performance changes show a trend of first increasing and then decreasing to a stable level. After repeated testing with a large amount of data, it can be stabilized at more than 50% in the later stage. The overwrite performance test results are shown in Figure 13 and Figure 14. It can be seen from the results that the performance of the LSMA scheme is also better than that of LevelDB. However, as the data is written, the amount of data in the storage engine increases, and the performance improvement decreases. Trend. After repeated testing with a large amount of data, it can be stabilized at more than 20% in the later period. In summary, compared with the original LevelDB, the LSMA scheme can improve random write performance by more than 50%, up to 105%, and overwrite by more than 20%, up to 91%

Figure 11.

Average Write Latency.

Figure 12.

Write rate.

Figure 13.

Average write latency.

Figure 14.

Write rate.

5.4

Query performance

In addition, the size of the data block cache is set to 16MB, and the average number of bits per key of the Bloom filter is 4. First, we write the data of certain entries in order, and then compare the sequential reads of the LSMA scheme and the original LevelDB scheme performance, random read performance, missing read performance.

The experimental results of sequential read performance, random read performance, and missing read performance are shown in Figures 15 - 18. Due to the existence of cache and Bloom filter, the read performance of the LSMA scheme and LevelDB is almost There is no gap, even when the amount of data is small, for the improved sst, LSMA will have better various read performance. Even if the amount of data increases, the read performance gap between the LSMA scheme and LevelDB is within 5%.

Figure 15.

Sequential check.

Figure 16.

Random check.

Figure 17.

Missing rate 25%.

Figure 18.

Missing rate 50%.