System, method, and recording medium for reducing memory consumption for in-memory data stores

• US 10,318,199 B2
• Filed: 11/18/2015
• Issued: 06/11/2019
• Est. Priority Date: 11/18/2015
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hack, Michel H. T., Ren, Yufei, Wang, Yandong, Wu, Xingbo, Zhang, Li
• Primary Examiner(s): Alsip, Michael
• Application Number:
  US14/945,031
• Publication Number:
  US 20170139596A1
• Time in Patent Office: 1,301 Days
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A method for compressing a group of key-value pairs, the method including dividing the group of key-value pairs into a plurality of segments, creating a plurality of blocks, each block of the plurality of blocks corresponding to a segment of the plurality of segments, and compressing each block of the plurality of blocks.

Claims

1. A method for compressing a group of key-value pairs from a key-value store, the method comprising:

dividing the group of key-value pairs into a plurality of segments of a dynamic size comprising a collection of records, the key-value pairs being stored in the key-value store where each row of the key-value store comprises a key-value format;

grouping the plurality of segments together such that the dynamic size of the plurality of segments have an approximately equal usage;

creating a plurality of blocks that each have an equal memory size greater than a greatest size of the approximately equal memory usage of the plurality of segments and labeling a first key-value pair and a last key-value pair in each block,

pairing each of the grouped plurality of segments to a block of the plurality of blocks such that the approximately equal memory usage of the plurality of segments is less than the equal memory size of the paired block;

compressing each block of the plurality of blocks including compressing an uncompressed version of the combined key and value together as the key-value pairs ranging from the first key-value pair to the last key-value pair of the block;

decompressing a block of the plurality of blocks to insert a new key-value pair;

inserting the new key-value pair into the block when the new key-value pair occurs between the first key-value pair and the last key-value pair in the block;

splitting the block into a first block and a second block based on a size of the block after the new key-value pair is inserted when the size of the memory usage of the paired segments exceeds the equal memory size of the corresponding block;

sending, from a front-end server, another request to delete a key-value pair;

locating a block of the plurality of blocks to delete the key-value pair in a memory data storage area of a back-end server;

decompressing a block of the plurality of blocks;

deleting the key-value pair from the block;

checking a size of the block to judge whether the size of the block is approximately equal to the approximately equal memory usage;

combining the block with a second block to make a new block if the size of the block is less than a threshold value difference between the equal memory size and a size of the approximately equal memory usage of the corresponding segment after the deleting; and

compressing the new block or the block,

wherein the splitting and the combining dynamically split and merge neighboring compressed blocks after each of the inserting and the deleting, and

wherein the compressing compresses the uncompressed version of the combined key and value together as the key-value pairs in a single step having one compression performed on the combined key and value.

2. The method of claim 1, further comprising storing the compressed blocks in the memory data storage area of the back-end server.

3. The method of claim 2, further comprising sending, from the back-end server, a compressed block of the compressed blocks to the front-end server.

4. The method of claim 2, further comprising:

sending, from the back-end server, a compressed block of the compressed blocks to the front-end server; and

decompressing the compressed block in the front-end server.

5. The method of claim 1, wherein a size of the segments dynamically changes according to a user input.

6. The method of claim 1, wherein a size of the segments dynamically changes according to a threshold value of the memory data storage area of the back-end server.

7. The method of claim 1, further comprising:

sending, from the front-end server, a first request for a key-value pair;

locating a block of the plurality of blocks that contains the key-value pair in the memory data storage area of the back-end server; and

sending, from the back-end server, the block of the plurality of blocks that contains the key-value pair to the front-end server.

8. The method of claim 7, further comprising:

verifying that the block sent from the back-end server contains the key-value pair requested in said sending the first request;

decompressing the block; and

locating the key-value pair requested in said sending the first request within the decompressed key-value pairs of the block.

9. The method of claim 1, further comprising:

decompressing a block of the plurality of blocks that contains the key-value pair;

absorbing a second request into the key-value pair; and

compressing the block of the plurality of blocks that absorbed the second request.

10. A non-transitory computer-readable recording medium recording a compression program for compressing a group of key-value pairs from a key-value store, the program causing a computer to perform:

dividing the group of key-value pairs into a plurality of segments of a dynamic size comprising a collection of records, the key-value pairs being stored in the key-value store where each row of the key-value store comprises a key-value format;

grouping the plurality of segments together such that the dynamic size of the plurality of segments have an approximately equal memory usage;

creating a plurality of blocks that each have ant equal memory size greater than a greatest size of the approximately equal memory usage of the plurality of segments and labeling a first key-value pair and a last key-value pair in each block,

pairing each of the grouped plurality of segments to a block of the plurality of blocks such that the approximately equal memory usage of the plurality of segments is less than the equal memory size of the paired block;

compressing each block of the plurality of blocks including compressing an uncompressed version of the combined key and value together as the key-value pairs ranging from the first key-value pair to the last key-value pair of the block;

decompressing a block of the plurality of blocks to insert a new key-value pair;

inserting the new key-value pair into the block when the new key-value pair occurs between the first key-value pair and the last key-value pair in the block;

splitting the block into a first block and a second block based on a size of the block after the new key-value pair is inserted when the size of the memory usage of the paired segments exceeds the equal memory size of the corresponding block;

sending, from a front-end server, another request to delete a key-value pair;

locating block of the plurality of blocks to delete the key-value pair in a memory data storage area of a back-end server;

decompressing a block of the plurality of blocks;

deleting the key-value pair from the block;

checking a size of the block to judge whether the size of the block is approximately equal to the approximately equal memory usage;

combining the block with a second block to make a new block if the size of the block is less than a threshold value difference between the equal memory size and a size of the approximately equal memory usage of the corresponding segment after the deleting; and

compressing the new block or the block,

wherein the splitting and the combining dynamically split and merge neighboring compressed blocks after each of the inserting and the deleting, and

wherein the compressing compresses the uncompressed version of the combined key and value together as the key-value pairs in a single step having one compression performed on the combined key and value.

11. A key-value pair compression system for compressing a group of key-value pairs from a key-value store, the system comprising:

a processor; and

a memory configured to cause the processor to perform;

dividing the group of key-value pairs into a plurality of segments of a dynamic size comprising a collection of records, the key-value pairs being stored in the key-value store where each row of the key-value store comprises a key-value format;

grouping the segments together such that the dynamic size of the plurality of segments have an approximately equal memory usage;

creating a plurality of blocks that each have an equal memory size greater than a greatest size of the approximately equal memory usage of the plurality of segments and labeling a first key-value pair and a last key-value pair in each block,

pairing each of the grouped plurality of segments to a block of the plurality of blocks such that the approximately equal memory usage of the plurality of segments is less than the equal memory size of the paired block;

compressing each block of the plurality of blocks including compressing an uncompressed version of the combined key and value together as the key-value pairs ranging from the first key-value pair to the last key-value pair of the block;

decompressing a block of the plurality of blocks to insert a new key-value pair;

inserting the new key-value pair into the block when the new key-value pair occurs between the first key-value pair and the last key-value pair in the block;

splitting the block into a first block and a second block based on a size of the block after the new key-value pair is inserted when the size of the memory usage of the paired segments exceeds the equal memory size of the corresponding block;

sending, from a front-end server, another request to delete a key-value pair;

locating a block of the plurality of blocks to delete the key-value pair in a memory data storage area of a back-end server;

decompressing a block of the plurality of blocks;

deleting the key-value pair from the block;

checking a size of the block to judge whether the size of the block is approximately equal to the approximately equal memory usage;

combining the block with a second block to make a new block if the size of the block is less than a threshold value difference between the equal memory size and a size of the approximately equal memory usage of the corresponding segment after the deleting; and

compressing the new block or the block,

wherein the splitting and the combining dynamically split and merge neighboring compressed blocks after each of the inserting and the deleting, and

wherein the compressing compresses the uncompressed version of the combined key and value together as the key-value pairs in a single step having one compression performed on the combined key and value.