System, method, and recording medium for reducing memory consumption for in-memory data stores
First Claim
Patent Images
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, andwherein 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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
11 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
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.
-
Specification