Cache based key-value store mapping and replication

Patent metadata

Field	Value
Publication number	US-9836514-B2
Application number	US-201113502312-A
Country	US
Kind code	B2
Filing date	Nov 7, 2011
Priority date	Nov 7, 2011
Publication date	Dec 5, 2017
Grant date	Dec 5, 2017

Abstract

Technologies are generally described for cache based key-value store mapping and replication. In some examples, key-value stores may be mapped for data structure replication through extraction of file breaks in an existing key-value store by iterating through the store and examining changes in cache addresses to detect jumps in address values. Specially formulated queries may be executed to return the values within an address range that spans a physical storage volume in order to recover full key-value sets that are physically grouped at a current data center including record duplicates. Such sets may be used to replicate or inform the key-value sets at a new location or in a new key-value store allowing construction of a replicated database tree structure complete with record duplications that develop as tables are optimized over time.

First claim

What is claimed is:

1. A method executed on a computing device for key-value store mapping for data structure replication through an extraction of file breaks in a key-value store, the method comprising:
mapping a distribution of a physical storage within a target data center by an extraction of relative data storage locations that employ data query caches from a key-value store of the target data center through:
receiving a number of query set results, wherein the number of the query set results include a location cache element; and
adding the location cache element to a data map, wherein the location cache element includes a NextToken arranged to remove duplicate records within a single query and returns address values within a range of cache addresses that spans a volume of the physical storage within the target data center to recover key-value sets that are physically grouped in a current location, and wherein the key-value store includes a metadata table and a root table to recover the current location of the key-value sets;

iterating through the key-value store to:
identify a step larger than one storage block in the range of the cache addresses which are sequential;
scan differences in the range of the sequential cache addresses to estimate a group of the query set results that include breaks in the physical storage; and
examine the breaks to elucidate a structure of the physical storage;

mapping data divisions and data duplication within the target data center by a comparison of the data map against a detail utilized by the data structure replication, wherein the number of query set results provide the detail;
issuing a record-by-record query to gather data from a previous query set that results in a new data map of the query set in response to a determination that the data map is sufficiently detailed and that a duplication exists between blocks in the physical storage, wherein the record-by-record query includes replicated data and regions from invalidated data query sets;
replicating the data within the target data center to similar structures in a new data center by arranging the data similarly within a key-value system used at the new data center; and
constructing one or more tree structures in the new data center, wherein the one or more tree structures include Merkle trees and Tiger trees.

2. The method according to claim 1 , wherein the key-value store further includes extracted data tables that are not directly accessible to a user.

3. The method according to claim 1 , further comprising:
in response to the determination that the data map is sufficiently detailed, one of issuing contiguous block level queries and synthesizing the contiguous block level queries from previous results to uncover the duplication between the blocks in the physical storage.

4. The method according to claim 1 , further comprising:
in response to a determination that the data map is not sufficiently detailed, issuing a new query.

5. The method according to claim 1 , wherein the number of the query set results is dependent on a stored data size.

6. The method according to claim 1 , wherein the number of the query set results is one to allow highest detail.

7. A computing device adapted to perform key-value store mapping for data structure replication through an extraction of file breaks in a key-value store, the computing device comprising:
a memory; and
a processor coupled to the memory, wherein the processor is operable to execute a data transfer application stored in the memory, and wherein the data transfer application is configured to:
receive a number of query set results that include a location cache element;
add the location cache element to a data map, wherein the location cache element includes a NextToken arranged to remove duplicate records within a single query and returns address values within a range of cache addresses that span a volume of a physical storage in a target data center to recover key-value sets that are physically grouped in a current location, and wherein the key-value store includes a metadata table and a root table to recover the current location of the key-value sets,
iterate through the key-value store to:
identify a step larger than one storage block in the range of the cache addresses which are sequential;
scan differences in the range of the sequential cache addresses to estimate a group of the query set results that include breaks in the physical storage, and
examine the breaks to elucidate a structure of the physical storage;

map data divisions and data duplication within the target data center by a comparison of the data map against a detail utilized by the data structure replication to map data divisions and data duplication within the target data center, wherein the number of query set results provides the detail;
issue a record-by-record query to gather data from a previous query set that results in a new data map of the query set in response to a determination that the data map is sufficiently detailed and that a duplication exists between blocks in the physical storage, wherein the record-by-record query includes replicated data and regions from invalidated data query sets;
replicate data within the target data center to similar structures in a new data center by arrangement of the data similarly within a key-value system used at the new data center; and
construct one or more tree structures in the new data center, wherein the one or more tree structures include Merkle trees and Tiger trees.

8. The computing device according to claim 7 , wherein the data transfer application is further configured to:
in response to the determination that the data map is sufficiently detailed, one of issue contiguous block level queries and synthesize the contiguous block level queries from previous results to uncover duplication between the blocks in the physical storage; and
in response to a determination that the data map is not sufficiently detailed, issue a new query.

9. The computing device according to claim 7 , wherein the one or more tree structures further include hash trees.

10. A computer-readable storage medium having instructions stored thereon for key-value store mapping for data structure replication through an extraction of file breaks in a key-value store, the instructions being executable by at least one processor to perform or cause to be performed operations comprising:
mapping a distribution of a physical storage within a target data center by an extraction of relative data storage locations that employ data query caches from a key-value store of the target data center through:
identifying a number of query set results that include a location cache element;
adding the location cache element to a data map, wherein the location cache element includes a NextToken arranged to remove duplicate records within a single query and returns address values within a range of cache addresses that spans a volume of the physical storage within the target data center to recover key-value sets that are physically grouped in a current location, and wherein the key-value store includes a metadata table and a root table to recover the current location of the key-value sets;

iterating through the key-value store to:
identify a step larger than one storage block in the range of the cache addresses which are sequential;
scan differences in the range of the sequential cache addresses to estimate a group of the query set results that include breaks in the physical storage; and
examine the breaks to elucidate a structure of the physical storage;

mapping data divisions and data duplication within the target data center by a comparison of the data map against a

Assignees

• Kruglick Ezekiel
• Empire Technology Dev Llc

Inventors

• Kruglick Ezekiel

Classifications

• G06F17/30575 Primary

  Physics · mapped topic

• G06F16/27 Primary

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title