CN106844650A - A kind of daily record merges the merging method and system of tree - Google Patents

Abstract

The present invention proposes a log merge tree merging method and system, the method includes a real merging step, data merging and metadata merging to generate Real SSTable, data merging is merging SSTable; virtual merging step, generating Virtual SSTable, only for metadata The data is merged, and the data source of the Virtual SSTable is recorded; the reading step of the Real SSTable is to read the Real SSTable, and when the key falls in the key range of the Real SSTable, directly search for the value corresponding to the key on the Real SSTable; The step of reading the Virtual SSTable; during the reading process, the Virtual SSTable is merged, and the Virtual SSTable is changed into a Real SSTable.

Description

Method and system for merging log merging trees

technical field

The invention relates to the technical field of log merging numbers, in particular to a method and system for merging log merging trees.

Background technique

Log-Structured Merge Tree (LSM-Tree for short) consists of multiple components, including a memory component and multiple disk components. The size of the components grows exponentially. Its architecture is shown in Figure 2. The memory component has a memory table ( Memtable), each disk component is composed of one or more sorted string tables (SSTable), the main idea of LSM-Tree is to save the write or update of data in the memory, after reaching the specified threshold, these Operations are sequentially written to the storage device. Update operations such as insert, update, and delete are served by memory components, and operations such as search and scan are served by all components. It adopts an off-site update method. Therefore, in the LSM-tree, the same key There may be multiple versions of value. The delete operation just adds a delete mark in the memory component, but does not actually delete the data. In the subsequent compact process, the data will be deleted and merged according to the old and new versions of the same key and the delete mark. Perform sorting operations between different keys, generate new SSTable files, and delete old SSTable files.

In order to keep the LSM-tree efficient for future read and write operations, it is necessary to continuously move data from high components to low components. When the size of a certain component exceeds the threshold, its compaction operation is triggered. Each data movement is It is carried out between adjacent components, during which part of the data of the two components is sorted, and invalid data and old data are deleted. This process is called compaction. Take Figure 3 as an example. When component C2 exceeds the threshold, select an SSTable T22 in component C2 To merge, select SSTable T32 and T33 that overlap with the key-range of T22 in component C2 from component C3. Merge T22, T32, and T33 into three new SSTables, T35, T36, and T37; and place the newly constructed SSTable in C3. In this way, data T22 is moved down from component C2 to component C3.

Compaction will control the IO operation of LSM-Tree-based key/value storage. During the Compaction process, key-value pairs will flow from the smaller level (lower level) to the larger level (higher level). Due to the limitation of the preset capacity of each layer, the key The slow flow of value pairs like the larger level will cause the system to suspend writing. Figure 4 shows the process of reading and writing a key-value pair from the smaller level to the larger level. During the compaction process, a key-value pair will be read into Write many times, even in the same layer, the reason is that the compaction process is a round-robin scheduling, and the polling speed in the smaller level layer will be faster than the larger level layer, and the result is that a key-value pair is moved to the corresponding The adjacent layer has participated in multiple compaction processes before, and this severe write amplification phenomenon causes frequent write pauses, thereby reducing the write performance of the system.

The existing solutions to the LSM-Tree write amplification problem mainly include the following methods:

Technical Solution 1: Enlarge the conditions for triggering compaction in traditional LSM-Tree, that is, increase the threshold value of each component. The main disadvantage is that it can only alleviate the problem of write amplification from component 0 to component 1, and write amplification still exists in subsequent levels. question.

Technical solution 2: bLSM divides the key into multiple key ranges, so that the compaction falls in a small number of key ranges, and avoids compaction of data in irrelevant key ranges. As shown in Figure 5, assuming that there are continuous data insertions in the range of N~Q, Then only the compaction in the range of N~Q will be triggered, and the compaction in other ranges will not be triggered, as shown in Fig. 5 . Its main disadvantage is that the write amplification problem caused by compaction in a certain key range cannot be avoided.

bLSM was published in Proceedings of the 2012ACM SIGMOD International Conference on Management of Data.

Technical solution 3: VT-Tree will judge that when a key-value pair does not have other versions of the key-value pair corresponding to the same key in consecutive layers, it can directly cross these layers to reach the layer containing the same key value or the last layer. This saves the I/O overhead caused by the movement of key-value pairs across multiple layers, as shown in Figure 6. Its main disadvantage is that it cannot alleviate the write amplification problem caused by compaction of hot data.

VT-Tree was presented at the 11th USENIX Conference on File and Storage Technologies (FAST’13)

Technical solution 4: In Wisckey, the key and value are stored separately in the LSM-Tree, that is, the key and value pointers are stored in the LSM-Tree, while the real data of the value is stored elsewhere. Therefore, during the compaction process, only The key and value pointers will be read and written repeatedly, as shown in Figure 7. Its main disadvantage is that the key is repeatedly read and written due to compaction. In some scenarios with large keys, the write amplification problem of LSM-Tree still exists.

Wisckey presented at the 14th USENIX Conference on File and Storage Technologies (FAST’16)

Contents of the invention

The purpose of the present invention is to solve the LSM-Tree write amplification problem caused by the repeated reading and writing of data in the LSM-Tree due to the merging (same layer & cross-layer) of data in the above-mentioned prior art, and propose a method for merging log merge trees and system.

The present invention proposes a method for merging log merging trees, including:

The real merging step includes data merging and metadata merging, and generates a Real SSTable, wherein the data merging is merging the SSTable, and the metadata merging includes merging key range, file number, and file size information;

The virtual merging step generates a Virtual SSTable, and only merges the metadata, and the merging of the metadata includes merging key range, file number, and file size information, and records the data source of the Virtual SSTable;

The step of reading the Real SSTable is to read the Real SSTable, wherein when the key falls in the key range of the Real SSTable, directly search the corresponding value of the key on the Real SSTable;

In the reading step of the Virtual SSTable, when the key falls in the key range of the Virtual SSTable, the data source corresponding to the key in the Virtual SSTable is searched through the metadata information, and the value corresponding to the key is searched in the Real SSTable ;

The merging step of the Virtual SSTable is to merge the Virtual SSTable during the reading process, so as to change the Virtual SSTable into a Real SSTable, thereby improving the reading performance.

Described real merging step comprises:

11. Read the key/value of each Real SSTable in turn;

12. By merging and sorting, write the qualified key/value into the fixed-size Real SSTable in sequence;

13. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

The virtual merging step includes:

21. Collect metadata of Real SSTable;

22. Obtain a new key range according to the key range in Real SSTable, covering all Real SSTable ranges;

23. Divide the new key range into N according to the number N of Real SSTables, representing N Virtual SSTables, where the file size of the Virtual SSTable is set to be the same as that of the Real SSTable, and the file numbers of the Virtual SSTable are unified through the virtual merge process The data source is all Real SSTables involved in the virtual merge.

The reading steps of the Virtual SSTable include

41. Determine whether the key to be searched falls in the key range of the Virtual SSTable;

42. Return if not in

43. If yes, find the data source through the metadata of the Virtual SSTable, that is, Real SSTables;

44. Search key according to the index of Real SSTable;

45. If found, return the value of the key;

46. If not found, then search for the next Real SSTable until all the Real SSTables contained in the data source of the Virtual SSTable are searched;

47. If still not found, return.

The merging steps of the Virtual SSTable include

51. Get the data source Real SSTables of Virtual SSTable;

52. Read the key/value of each Real SSTable in turn;

53. By merging and sorting, write the key/value that meets the conditions into the fixed-size Real SSTable in sequence;

54. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

The present invention also proposes a log merge tree merging system, including:

The real merging module includes data merging and metadata merging, and generates a Real SSTable, where data merging is merging SSTables, and metadata merging includes merging key range, file number, and file size information;

The virtual merging module is used to generate a Virtual SSTable, and only merges metadata, and the merging of metadata includes merging key range, file number, and file size information, and records the data source of the Virtual SSTable;

The reading module of Real SSTable is used for reading described Real SSTable, wherein when key falls in the key range of described Real SSTable, then directly search the value value corresponding to key on described Real SSTable;

The reading module of the Virtual SSTable is used to find the data source corresponding to the key in the Virtual SSTable through the metadata information when the key falls in the key range of the Virtual SSTable, and to find the value corresponding to the key in the RealSSTable value;

The merging module of the Virtual SSTable is used for merging the Virtual SSTable during the reading process, changing the Virtual SSTable into a Real SSTable, thereby improving the reading performance.

Described real merge module comprises:

11. Read the key/value of each Real SSTable in turn;

12. By merging and sorting, write the qualified key/value into the fixed-size Real SSTable in sequence;

13. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

The virtual merging module includes:

21. Collect metadata of Real SSTable;

22. Obtain a new key range according to the key range in Real SSTable, covering all Real SSTable ranges;

23. Divide the new key range into N according to the number N of Real SSTables, representing N Virtual SSTables, where the file size of the Virtual SSTable is set to be the same as that of the Real SSTable, and the file numbers of the Virtual SSTable are unified through the virtual merge process The data source is all Real SSTables involved in the virtual merge.

The reading module of the Virtual SSTable includes

41. Determine whether the key to be searched falls in the key range of the Virtual SSTable;

42. Return if not in

43. If yes, find the data source through the metadata of the Virtual SSTable, that is, Real SSTables;

44. Search key according to the index of Real SSTable;

45. If found, return the value of the key;

46. If not found, then search for the next Real SSTable until all the Real SSTables contained in the data source of the Virtual SSTable are searched;

47. If still not found, return.

The merge module of the Virtual SSTable includes

51. Get the data source Real SSTables of Virtual SSTable;

52. Read the key/value of each Real SSTable in turn;

53. By merging and sorting, write the key/value that meets the conditions into the fixed-size Real SSTable in sequence;

54. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

As can be seen from the above scheme, the present invention has the advantages of:

1. The present invention can reduce the write amplification problem caused by merging, thereby improving the writing performance of the system, and it is orthogonal to other methods for reducing the write amplification problem of LSM-Tree, and can be superimposed and used;

2. The present invention can reduce the amount of I/O in merging, and prolong its service life for storage devices such as SSDs;

Fig. 1 shows the performance evaluation of the present invention and RocksDB, as can be seen from Fig. 1, the advantage of the present invention is:

Under Write-intensive (write-intensive) load, the overall performance is increased by 30% to 1 times;

Under Read-intensive (read-intensive) load, the overall performance is basically the same as RocksDB;

The LSM-Tree itself is mainly used for Write-intensive loads.

Description of drawings

Fig. 1 is a performance evaluation figure of the present invention;

Figure 2 is an LSM-Tree architecture diagram;

Figure 3 is an example diagram of LSM-Tree Compaction;

Figure 4 is a flow diagram of the key-value pairs during the Compaction process of the LSM-Tree;

Figure 5 is a bLSM diagram;

Figure 6 is a VT-Tree diagram;

Figure 7 is a Wisckey diagram;

Fig. 8 is the specific flow chart of real merger;

Fig. 9 is the specific flowchart of virtual merger;

Figure 10 is a flow chart of reading Virtual SSTable;

Figure 11 is a merged diagram of Virtual SSTable;

Figure 12 is a diagram of the impact of different VCTs on write performance;

Figure 13 is a diagram of the influence of different VCTs on I/O volume and merge time;

Figure 14 is a graph showing the influence of different MCTs on read performance.

detailed description

The following is the overall process of the present invention, as follows:

1. Real merger

Real merging includes data merging and metadata merging, and the resulting SSTable is Real SSTable. Among them, data merging is SSTable merging, and metadata merging includes merging key range, file number, file size and other information. The specific process is shown in Figure 8.

11. Read the key/value of each Real SSTable in turn;

12. By merging and sorting, write the qualified key/value order into a fixed-size Real SSTable (the default is 2MB)

13. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

2. Virtual merger

The SSTable generated by the virtual merge is a Virtual SSTable. Virtual merge only merges metadata. Metadata merging includes merging key range, file number, file size, etc., and recording which Real SSTables the Virtual SSTable is composed of (called parentSST), which is the data source of the Virtual SSTable. The specific process is shown in Figure 9.

21. Collect the metadata of the Real SSTable involved in the virtual merge;

22. According to the key range in the Real SSTable, a new key range is obtained, covering the range of all the above Real SSTables;

23. Divide the new key range into N according to the number N of Real SSTables in the virtual merge. The range of these N keys represents N Virtual SSTables, and the file size is uniformly set to be the same as the size of the Real SSTable (default is 2MB) , the file number is uniformly assigned through the virtual merge process, and the data source is all the Real SSTables involved in this virtual merge.

3. Reading of Real SSTable

The reading process of Real SSTable (same as traditional LSM-Tree-based key-value systems, such as LevelDB and RocksDB): when the key falls in the key range of Real SSTable, directly search for the value corresponding to the key.

4. Reading of Virtual SSTable

The reading process of Virtual SSTable: When the key falls in the key range of Virtual SSTable, find the corresponding data source of Virtual SSTable through the metadata information, that is, Real SSTable, and find the value corresponding to the key in Real SSTable. The specific process As shown in Figure 10.

41. Determine whether the key to be searched falls in the key range of the Virtual SSTable;

42. Return if not in

43. If it is, find its data source through the metadata of Virtual SSTable, that is, Real SSTables;

44. Search key according to the index of Real SSTable;

45. If found, return the value of the key;

46. If not found, then search for the next Real SSTable until all the Real SSTables contained in the data source of the VirtualSSTable are searched;

47. If still not found, return;

5. Merge of Virtual SSTable

In order to reduce the impact of the Virtual SSTable on the read performance, the Virtual SSTable will be merged during the read process, turning the Virtual SSTable into a Real SSTable, thereby improving the read performance. The specific process is shown in Figure 11.

51. Obtain the data source of Virtual SSTable—Real SSTables;

52. Read the key/value of each Real SSTable in turn;

53. By merging and sorting, write the qualified key/value order into a fixed-size Real SSTable (the default is 2MB)

54. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

Example 1: Merge operation (combination of virtual merge and real merge)

In the present invention, when a certain layer of the LSM-Tree reaches the threshold, it needs to be merged, and the specific process is as follows:

a. Select the SSTable that needs to be merged;

b. Count the number of Real SSTables contained in these SSTables, denoted as N;

c. If N exceeds the threshold VCT, perform real merging;

d. If N is less than VCT, virtual merge is performed;

Among them, VCT is a parameter to distinguish between real merger and virtual merger. Different VCTs have different effects on mergers:

The smaller the VCT, the more times of actual merging, resulting in larger I/O overhead;

The larger the VCT, the more virtual merge times, although it can save I/O overhead, but the subsequent real merge overhead is larger, resulting in longer merge times;

Figure 12 shows the impact of different VCTs on write performance under the Write-100% load. When VCT=12, the write performance is optimal, mainly due to two aspects: the amount of saved I/O and The total merging time, as specifically shown in FIG. 13 , VCT=12 can save a certain amount of I/O, and the merging time is the least, so in this example, VCT=12 is optimal.

Example 2: Get operation (reading of Real SSTable and Virtual SSTable, merging of Virtual SSTable)

Its basic flow is as follows:

a. Search from top to bottom in LSM-Tree;

b. For each layer of SSTable, locate the SSTable through its metadata information—key range;

c. If it is a Real SSTable, search it directly;

d. If it is a Virtual SSTable, find its data source through the parentSST of the Virtual SSTable, and then search;

e. If not found, continue to locate the corresponding SSTable in this layer or the next layer to search until it is found or finished;

Get operation of the present invention also can relate to the merging of Virtual SSTable, and specific process is as follows:

a. When the Get operation involves a Virtual SSTable, it will judge two values of the current Virtual SSTable: the cumulative number of reads of the Virtual SSTable (R) and the number of Real SSTables contained in the Virtual SSTable (M)

b. When R>RCT&&M>MCT, merge the Virtual SSTable, otherwise do not merge;

Use the cumulative number of reads of the Virtual SSTable and the number of RealSStables contained in the Virtual SSTable as the conditions to trigger the merger of the Virtual SSTable. The main reasons are:

The cumulative number of reads is considered from the perspective of popularity. The higher the popularity, the virtual SSTable is frequently read, and the lower the popularity, the virtual SSTable is rarely read;

The more Real SSTables included in the Virtual SSTable, the worse the read performance; otherwise, the better the read performance;

Therefore, when R and M meet the conditions at the same time, it indicates that the popularity of the current virtual SSTable is high, and the number of real SSTables contained exceeds the threshold range, which will seriously affect the read performance and need to be merged. The default value of RCT is 5, and for the selection of MCT, Figure 14 shows the impact of different MCTs on the read performance.

When MCT=3~5, the read performance is basically the same as RocksDB;

When MCT=7~11, the read performance is poor, the main reason is that the unmerged Virtual SSTable affects the read performance;

Therefore, the selection of MCT needs to consider two factors: read performance and overhead caused by merging. Combining the above two factors, MCT=5 is more appropriate in this example, because 1) the read performance is basically the same as RocksDB; 2) Compared with MCT=3, fewer virtual SSTable merges can be triggered to save resources.

The present invention also proposes a log merge tree merging system, including:

The real merging module includes data merging and metadata merging, and generates a Real SSTable, where data merging is merging SSTables, and metadata merging includes merging key range, file number, and file size information;

The virtual merging module is used to generate a Virtual SSTable, and only merges metadata, and the merging of metadata includes merging key range, file number, and file size information, and records the data source of the Virtual SSTable;

The reading module of Real SSTable is used for reading described Real SSTable, wherein when key falls in the key range of described Real SSTable, then directly search the value value corresponding to key on described Real SSTable;

The reading module of the Virtual SSTable is used to find the data source corresponding to the key in the Virtual SSTable through the metadata information when the key falls in the key range of the Virtual SSTable, and to find the value corresponding to the key in the RealSSTable value;

The merging module of the Virtual SSTable is used for merging the Virtual SSTable during the reading process, changing the Virtual SSTable into a Real SSTable, thereby improving the reading performance.

Described real merge module comprises:

11. Read the key/value of each Real SSTable in turn;

12. By merging and sorting, write the qualified key/value into the fixed-size Real SSTable in order;

13. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

The virtual merging module includes:

21. Collect metadata of Real SSTable;

22. Obtain a new key range according to the key range in Real SSTable, covering all Real SSTable ranges;

23. Divide the new key range into N according to the number N of Real SSTables, representing N Virtual SSTables, where the file size of the Virtual SSTable is set to be the same as that of the Real SSTable, and the file numbers of the Virtual SSTable are unified through the virtual merge process The data source is all Real SSTables involved in the virtual merge.

The reading module of the Virtual SSTable includes

41. Determine whether the key to be searched falls in the key range of the Virtual SSTable;

42. Return if not in

43. If yes, find the data source through the metadata of the Virtual SSTable, that is, Real SSTables;

44. Search key according to the index of Real SSTable;

45. If found, return the value of the key;

46. If not found, then search for the next Real SSTable until all the Real SSTables contained in the data source of the Virtual SSTable are searched;

47. If still not found, return.

The merge module of the Virtual SSTable includes

51. Get the data source Real SSTables of Virtual SSTable;

52. Read the key/value of each Real SSTable in turn;

53. By merging and sorting, write the key/value that meets the conditions into the fixed-size Real SSTable in sequence;

54. After it is full, re-create a new Real SSTable, and continue to write the sorted key/value into it until it is finished.

Claims (10)

1. a kind of daily record merges the merging method of tree, it is characterised in that including：

Real combining step, including data merge and merge with metadata, and generate Real SSTable, wherein data merge into by SSTable is merged, and metadata merges to be included merging key range, file number, file size information；

Empty combining step, generates Virtual SSTable, and only metadata merged, and metadata is merged including closing And key range, file number, file size information, and record the data source of the Virtual SSTable；

The read step of Real SSTable, is read out to the Real SSTable, wherein when key falls in the Real In the key range of SSTable, then the value values corresponding to key are directly searched on the Real SSTable；

The read step of Virtual SSTable, when key falls in the key range of Virtual SSTable, then by unit Data source Virtual SSTable corresponding with key described in data information search, and looked into the Real SSTable Look for the value values corresponding to key；

The combining step of Virtual SSTable, merges in reading process to the Virtual SSTable, by institute State Virtual SSTable and become Real SSTable, so as to lift reading performance.

2. daily record as claimed in claim 1 merges the merging method of tree, it is characterised in that the real combining step includes：

11. key/value for being successively read each Real SSTable；

12. are sorted by merger, and qualified key/value is sequentially written in the Real SSTable of fixed size；

After 13. write completely, a new Real SSTable is re-created, continued sorted key/value write-ins wherein, Until writing.

3. daily record as claimed in claim 1 merges the merging method of tree, it is characterised in that the empty combining step includes：

21. metadata for collecting Real SSTable；

The 22. key range in Real SSTable, obtain new key range, cover all Real SSTable's Scope；

New key range, according to the number N of Real SSTable, are divided into N number of by 23., represent N number of Virtual SSTable, The file size of wherein Virtual SSTable is arranged to identical with the file size of Real SSTable, Virtual The reference number of a document of SSTable passes through empty merging process and distributes unitedly, and data source is then all Real involved in empty merging SSTable。

4. daily record as claimed in claim 1 merges the merging method of tree, it is characterised in that the Virtual SSTable's Read step includes

41. judge whether the key for requiring to look up falls in the key scopes of Virtual SSTable；

42. if it was not then return

If 43. are finding data source, i.e. Real SSTables by the metadata of Virtual SSTable；

44. carry out lookup key according to the index of Real SSTable；

45. if it is found, then return to the value values of key；

If 46. do not find, the lookup of next Real SSTable is carried out, until by the number of Virtual SSTable All searched one time according to the Real SSTable included in source；

If 47., again without finding, return.

5. daily record as claimed in claim 1 merges the merging method of tree, it is characterised in that the Virtual SSTable's Combining step includes

The 51. data source Real SSTables for obtaining Virtual SSTable；

52. key/value for being successively read each Real SSTable；

53. are sorted by merger, and qualified key/value is sequentially written in the Real SSTable of fixed size；

After 54. write completely, a new Real SSTable is re-created, continued sorted key/value write-ins wherein, Until writing.

6. a kind of daily record merges the combination system of tree, it is characterised in that including：

Real merging module, including data merge and merge with metadata, and generate Real SSTable, wherein data merge into by SSTable is merged, and metadata merges to be included merging key range, file number, file size information；

Empty merging module, for generating Virtual SSTable, and only merges to metadata, and metadata merges bag Include merging key range, file number, file size information, and record the data of the Virtual SSTable Source；

The read module of Real SSTable, for being read out to the Real SSTable, wherein when key falls described In the key range of Real SSTable, then the value values corresponding to key are directly searched on the Real SSTable；

The read module of Virtual SSTable, for falling in the key range of Virtual SSTable as key, then leads to Cross metadata information and search the Virtual SSTable data sources corresponding with key, and in the Real SSTable Value values corresponding to middle lookup key；

The merging module of Virtual SSTable, for being merged to the Virtual SSTable in reading process, The Virtual SSTable are become into Real SSTable, so as to lift reading performance.

7. daily record as claimed in claim 6 merges the combination system of tree, it is characterised in that the real merging module includes：

11. key/value for being successively read each Real SSTable；

12. are sorted by merger, and qualified key/value is sequentially written in the Real SSTable of fixed size；

After 13. write completely, a new Real SSTable is re-created, continued sorted key/value write-ins wherein, Until writing.

8. daily record as claimed in claim 6 merges the combination system of tree, it is characterised in that the empty merging module includes：

21. metadata for collecting Real SSTable；

The 22. key range in Real SSTable, obtain new key range, cover all Real SSTable's Scope；

New key range, according to the number N of Real SSTable, are divided into N number of by 23., represent N number of Virtual SSTable, The file size of wherein Virtual SSTable is arranged to identical with the file size of Real SSTable, Virtual The reference number of a document of SSTable passes through empty merging process and distributes unitedly, and data source is then all Real involved in empty merging SSTable。

9. daily record as claimed in claim 6 merges the combination system of tree, it is characterised in that the Virtual SSTable's Read module includes

41. judge whether the key for requiring to look up falls in the key scopes of Virtual SSTable；

42. if it was not then return

If 43. are finding data source, i.e. Real SSTables by the metadata of Virtual SSTable；

44. carry out lookup key according to the index of Real SSTable；

45. if it is found, then return to the value values of key；

If 46. do not find, the lookup of next Real SSTable is carried out, until by the number of Virtual SSTable All searched one time according to the Real SSTable included in source；

If 47., again without finding, return.

10. daily record as claimed in claim 6 merges the combination system of tree, it is characterised in that the Virtual SSTable's Merging module includes

The 51. data source Real SSTables for obtaining Virtual SSTable；

52. key/value for being successively read each Real SSTable；

53. are sorted by merger, and qualified key/value is sequentially written in the RealSSTable of fixed size；

After 54. write completely, a new Real SSTable is re-created, continued sorted key/value write-ins wherein, Until writing.