Data block storage method and apparatus, and electronic device

1. A data block storage method applied to a database employing a Log-Structured Merge (LSM) tree, wherein the LSM tree includes a data structure having N layers, and a storage space of an i th layer is less than a storage space of an (i+1) th layer, i being an integer from 0 to N−1, and the method comprising:

obtaining, by a processor, M pieces of ordered data from a memory according to a data sequence, M being an integer greater than 0;

compressing, by the processor, the M pieces of ordered data to obtain one MicroBlock;

iterating, by the processor, the obtaining and the compressing to generate a plurality of MicroBlocks;

sequentially writing, by the processor, the MicroBlocks to a current MacroBlock in the 0 th layer of the LSM tree until a size of the current MacroBlock reaches a preset value;

after the size of the current MacroBlock reaches the preset value, writing, by the processor, a next MicroBlock into a next MacroBlock until the 0 th layer is filled up with a plurality of MacroBlocks;

determining, by the processor, a to-be-merged j th layer in the LSM tree, j being an integer from 0 to N−1;

merging, by the processor, MacroBlocks in the j th layer to the (j+1) th layer, wherein the merging does not cause all MacroBlocks in the (j+1) th layer to be rewritten; and

emptying, by the processor, the j th layer, the emptied j th layer being used for storing a MacroBlock transferred from the (j−1) th layer, wherein the merging, by the processor, MacroBlocks in the j th layer to the (j+1) th layer comprises:

determining, by the processor, whether a first MacroBlock in the j th layer and MacroBlocks in the (j+1) th layer have one or more identical keys;

in response to determining that the first MacroBlock in the j th layer and the MacroBlocks in the (j+1) th layer have no identical key, directly transferring, by the processor, the first MacroBlock to the (j+1) th layer;

in response to determining that the first MacroBlock in the j th layer and a second MacroBlock in the (j+1) th layer have one or more identical keys, reading, by the processor, all of one or more key-value pairs of the first MacroBlock and all of one or more key-value pairs of the second MacroBlock;

updating, by the processor, one or more values corresponding to the one or more identical keys in the second MacroBlock to be one or more values corresponding to the one or more identical keys in the first MacroBlock to obtain an updated second MacroBlock;

generating, by the processor, a new MacroBlock by sequentially arranging key-value pairs in the first MacroBlock other than key-value pairs corresponding to the one or more identical keys and key-value pairs in the updated second MacroBlock; and

storing, by the processor, the new MacroBlock to the (j+1) th layer.

2. The data block storage method according to claim 1 , wherein the determining, by the processor, a to-be-merged j th layer in the LSM tree comprises:

determining, by the processor, a layer in the LSM tree with a remaining storage space insufficient of storing to-be-stored data as the j th layer.

3. The data block storage method according to claim 2 , wherein the to-be-stored data is a to-be-written MicroBlock received at the 0 th layer, and the method further comprises: if the remaining storage space of the 0 th layer is less than a size of one MacroBlock, determining, by the processor, that the 0 th layer is unable to store the to-be-written MicroBlock.

4. The data block storage method according to claim 2 , wherein the to-be-stored data is a MacroBlock from a layer immediately above the j th layer in the LSM tree.

5. The data block storage method according to claim 1 , wherein the determining a to-be-merged j th layer in the LSM tree comprises:

determining a layer in the LSM tree with a remaining storage space less than a preset capacity as the j th layer.

6. The data block storage method according to claim 1 , wherein a size of each MacroBlock stored in the N layers of the LSM tree is a preset fixed value.

7. An apparatus, comprising:

one or more processors; and

a memory storing instructions executable by the one or more processors to cause the one or more processors to perform operations comprising:

obtaining M pieces of ordered data from a memory according to a data sequence, M being an integer greater than 0;

compressing the M pieces of ordered data to obtain one MicroBlock;

iterating the obtaining and the compressing to generate a plurality of MicroBlocks;

sequentially writing the MicroBlocks to a current MacroBlock in the 0 th layer of a Log-Structured Merge (LSM) tree until a size of the current MacroBlock reaches a preset value, wherein the LSM tree includes a data structure having N layers, and a storage space of an i th layer is less than a storage space of an (i+1) th layer, i being an integer from 0 to N−1;

after the size of the current MacroBlock reaches the preset value, writing a next MicroBlock into a next MacroBlock until the 0 th layer is filled up with a plurality of MacroBlocks;

determining a to-be-merged j th layer in the LSM tree, j being an integer from 0 to N−1;

merging MacroBlocks in the j th layer to the (j+1) th layer, wherein the merging does not cause all MacroBlocks in the (j+1) th layer to be rewritten; and

emptying the j th layer, the emptied j th layer being used for storing a MacroBlock transferred from the (j−1) th layer, wherein the merging MacroBlocks in the j th layer to the (j+1) th layer comprises:

determining whether a first MacroBlock in the j th layer and MacroBlocks in the (j+1) layer have one or more identical keys;

in response to determining that the first MacroBlock in the j th layer and the MacroBlocks in the (j+1) th layer have no identical key, directly transferring the first MacroBlock to the (j+1) th layer;

in response to determining that the first MacroBlock in the j th layer and a second MacroBlock in the (j+1) th layer have one or more identical keys, reading all of one or more key-value pairs of the first MacroBlock and all of one or more key-value pairs of the second MacroBlock;

updating one or more values corresponding to the one or more identical keys in the second MacroBlock to be one or more values corresponding to the one or more identical keys in the first MacroBlock to obtain an updated second MacroBlock;

generating a new MacroBlock by sequentially arranging key-value pairs in the first MacroBlock other than key-value pairs corresponding to the one or more identical keys and key-value pairs in the updated second MacroBlock; and

storing the new MacroBlock to the (j+1) th layer.

8. The apparatus according to claim 7 , wherein the determining a to-be-merged j th layer in the LSM tree comprises:

determining a layer in the LSM tree with a remaining storage space insufficient of storing to-be-stored data as the j th layer.

9. The apparatus according to claim 8 , wherein the to-be-stored data is a to-be-written MicroBlock received at the 0 th layer, and the operations further comprise: if the remaining storage space of the 0 th layer is less than a size of one MacroBlock, determining that the 0 th layer is unable to store the to-be-written MicroBlock.

10. The apparatus according to claim 8 , wherein the to-be-stored data is a MacroBlock from a layer immediately above the j th layer in the LSM tree.

11. The apparatus according to claim 7 , wherein the determining a to-be-merged j th layer in the LSM tree comprises:

determining a layer in the LSM tree with a remaining storage space less than a preset capacity as the j th layer.

12. The apparatus according to claim 7 , wherein a size of each MacroBlock stored in the N layers of the LSM tree is a preset fixed value.

13. One or more non-transitory computer-readable storage media configured with instructions executable by one or more processors to cause the one or more processors to perform operations comprising:

obtaining M pieces of ordered data from a memory according to a data sequence, M being an integer greater than 0;

compressing the M pieces of ordered data to obtain one MicroBlock;

iterating the obtaining and the compressing to generate a plurality of MicroBlocks;

sequentially writing the MicroBlocks to a current MacroBlock in the 0 th layer of a Log-Structured Merge (LSM) tree until a size of the current MacroBlock reaches a preset value, wherein the LSM tree includes a data structure having N layers, and a storage space of an i th layer is less than a storage space of an (i+1) th layer, i being an integer from 0 to N−1;

after the size of the current MacroBlock reaches the preset value, writing a next MicroBlock into a next MacroBlock until the 0 th layer is filled up with a plurality of MacroBlocks;

determining a to-be-merged j th layer in the LSM tree, j being an integer from 0 to N−1;

merging MacroBlocks in the j th layer to the (j+1) th layer, wherein the merging does not cause all MacroBlocks in the (j+1) th layer to be rewritten; and

emptying the j th layer, the emptied j th layer being used for storing a MacroBlock transferred from the (j−1) th layer, wherein the merging MacroBlocks in the j th layer to the (j+1) th layer comprises:

determining whether a first MacroBlock in the j th layer and MacroBlocks in the (j+1) th layer have one or more identical keys;

in response to determining that the first MacroBlock in the j th layer and the MacroBlocks in the (j+1) th layer have no identical key, directly transferring the first MacroBlock to the (j+1) th layer;

in response to determining that the first MacroBlock in the j th layer and a second MacroBlock in the (j+1) th layer have one or more identical keys, reading all of one or more key-value pairs of the first MacroBlock and all of one or more key-value pairs of the second MacroBlock;

updating one or more values corresponding to the one or more identical keys in the second MacroBlock to be one or more values corresponding to the one or more identical keys in the first MacroBlock to obtain an updated second MacroBlock;

generating a new MacroBlock by sequentially arranging key-value pairs in the first MacroBlock other than key-value pairs corresponding to the one or more identical keys and key-value pairs in the updated second MacroBlock; and

storing the new MacroBlock to the (j+1) th layer.

14. The one or more non-transitory computer-readable storage media according to claim 13 , wherein the determining a to-be-merged j th layer in the LSM tree comprises:

determining a layer in the LSM tree with a remaining storage space insufficient of storing to-be-stored data as the j th layer.

15. The one or more non-transitory computer-readable storage media according to claim 14 , wherein the to-be-stored data is a to-be-written MicroBlock received at the 0 th layer, and the operations further comprise: if the remaining storage space of the 0 th layer is less than a size of one MacroBlock, determining that the 0 th layer is unable to store the to-be-written MicroBlock.

16. The one or more non-transitory computer-readable storage media according to claim 14 , wherein the to-be-stored data is a MacroBlock from a layer immediately above the j th layer in the LSM tree.

17. The one or more non-transitory computer-readable storage media according to claim 13 , wherein the determining a to-be-merged j th layer in the LSM tree comprises:

determining a layer in the LSM tree with a remaining storage space less than a preset capacity as the j th layer.