Differentiated secondary index maintenance in log structured NoSQL data stores

• US 10,078,682 B2
• Filed: 12/21/2015
• Issued: 09/18/2018
• Est. Priority Date: 03/15/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tan, Wei, Tata, Sandeep
• Primary Examiner(s): Khong, Alexander
• Application Number:
  US14/976,183
• Publication Number:
  US 20160188690A1
• Time in Patent Office: 1,002 Days
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

There are provided a system and a computer program product for operating multi-node data stores. The system stores a data table in a first computing node and stores an index table in a second computing node. The index table provides keys used for accessing data in the first computing node and other multi-node data stores. The system performs operations that update or read the data table accessed from the first computing node and the index table accessed from the second computing node. The operations optimizes between latency in updating or reading the data table and the index table and data consistency maintained between data entries in the data table and data entries pointed by indices in the index table.

Claims

1. A system for operating multi-node data stores, the system comprising:

at least one memory device;

at least one processor,

wherein the processor is configured to perform steps of;

storing at least one data table in at least one first computing node;

storing at least one index table in at least one second computing node, the index table providing keys used for accessing data in said first computing node and other multi-node data stores; and

performing operations that update or read the at least one data table accessed from the at least one first computing node and the at least one index table accessed from the at least one second computing node, the operations optimizing between latency in updating or reading the at least one data table and the at least one index table and data consistency maintained between data entries in the at least one data table and data entries pointed by indices in the at least one index table, said processor is further configured to perform;

inserting a new data entry to the at least one data table and synchronously inserting a corresponding new index entry into the at least one index table;

maintaining a corresponding stale index entry in the at least one index table upon the insertion of the corresponding new index entry to the at least one index table;

deleting the corresponding stale index entry in the at least one index table upon receiving a query to the corresponding stale index entry in the at least one index table; and

maintaining the data consistency between the least one index table and the at least one data table in response to receiving the query to the corresponding stale index entry in the at least one index table, the step of deleting the corresponding stale index entry comprising;

accessing the at least one index table by using a value of an index (v_index);

obtaining, from the accessed at least one index table, a first key and a first timestamp, corresponding to the v_index;

accessing the at least one data table by using a value of the first key;

obtaining, the accessed at least one data table, an up-to-date value of the index and an up-to-date timestamp, corresponding to the first key;

comparing the v_index against the up-to-date value of the index; and

determining that an up-to-date index entry is (the v_index ⊕

the value of the first key) if the v_index is equal to the up-to-date value of the index, where ⊕

represents a byte array concatenation operation;

determining that the corresponding stale index entry is (the v_index ⊕

the value of the first key) if the v_index is not equal to the up-to-date value of the index and the first timestamp is made prior to the up-to-date timestamp.

2. The system according to claim 1, wherein the at least one index table includes at least one secondary index, which points to a data entry recorded in the at least one data table.

3. The system according to claim 1, wherein the data recorded in the at least one data table includes at least one tuple <

k, v, t>

, where k represents a key, v represents a new value of the key, and t represents a timestamp which indicates that the new value of the key is added to the at least one data table.

4. The system according to claim 1, wherein the processor is further configured to perform steps of:

invalidating a corresponding stale data entry in the at least one data table upon the insertion of the new data entry into the at least one data table; and

co-existing the corresponding stale index entry and the new index entry in the at least one index table until the query to a query to the corresponding stale index entry is received.

5. The system according to claim 3, wherein the processor is further configured to perform steps of:

synchronously inserting a new index entry into the at least one index table upon inserting a corresponding new data entry to the at least one data table, and

synchronously deleting a corresponding stale index entry in the at least one index table upon the insertion of the corresponding new index entry to the at least one index table.

6. The system according to claim 5, wherein the processor is further configured to perform steps of:

inserting the new data entry, represented by the tuple <

k, v, t>

, to the at least one data table;

inserting the new index entry into the at least one index table, the new index entry represented by a tuple <

v⊕

k, null, t>

, where ⊕

represents a byte array concatenation operation;

reading and obtaining an old value of the key k before the time t; and

deleting the corresponding stale index entry, which is represented by the old value of the key k ⊕

the key k.

7. The system according to claim 6, wherein to perform the deleting, the processor is further configured to mark the corresponding stale index entry as invalid.

8. The system according to claim 6, wherein to perform the reading and obtaining, the processor is further configured to perform steps of:

accessing the at least one data table; and

reading a value of the key k, which was inserted prior to the timestamp t, the read value representing the old value of the key k.

9. The system according to claim 5, wherein once the synchronous inserting is successfully performed in the at least one index table and the at least one data table, the data consistency is maintained between the least one index table and the at least one data table.

10. The system according to claim 3, wherein to perform said operations, the processor is further configured to perform steps of:

asynchronously inserting a new index entry into the at least one index table upon inserting a corresponding new data entry into the at least one data table, and

asynchronously deleting a corresponding stale index entry in the at least one index table.

11. The system according to claim 10, wherein the processor is further configured to perform steps of:

providing a queue which stores, as entries, updates to be performed to the at least one index table;

inserting the corresponding new data entry, represented by the tuple <

k, v, t>

, to the at least one data table;

adding the corresponding inserted new data entry into the provided queue;

sending an acknowledgement to a client node upon adding the corresponding inserted new data entry into the provided queue.

12. The system according to claim 11, wherein a background processing performs the asynchronous insertion of the new index entry to the at least one index table, and performs the asynchronous deletion of the corresponding stale index entry in the at least one index table.

13. The system according to claim 12, wherein the background processing performs steps of:

dequeuing an update, represented by the added new data entry, from the provided queue;

reading and obtaining an old value of the key k before the time t;

deleting the corresponding stale index entry, which is represented by the old value of the key k ⊕

the key k;

inserting the new index entry into the at least one index table, the new index entry represented by a tuple <

v⊕

k, null, t>

.

14. The system according to claim 10, wherein the at least one index table is not updated right away when the new data entry is inserted to the at least one data table.

15. A computer program product for operating multi-node data stores, the computer program product comprising a storage medium that excludes a propagating signal, the storage medium readable by a processing circuit and storing instructions run by the processing circuit for performing a method, said method steps comprising:

storing at least one data table in at least one first computing node;

storing at least one index table in at least one second computing node, the index table providing keys used for accessing data in said first computing node and other multi-node data stores; and

performing operations that update or read the at least one data table accessed from the at least one first computing node and the at least one index table accessed from the at least one second computing node, the operations optimizing between latency in updating or reading the at least one data table and the at least one index table and data consistency maintained between data entries in the at least one data table and data entries pointed by indices in the at least one index table, said operations comprising;

inserting a new data entry to the at least one data table and synchronously inserting a corresponding new index entry into the at least one index table;

maintaining a corresponding stale index entry in the at least one index table upon the insertion of the corresponding new index entry to the at least one index table;

deleting the corresponding stale index entry in the at least one index table upon receiving a query to the corresponding stale index entry in the at least one index table; and

maintaining the data consistency between the least one index table and the at least one data table in response to receiving the query to the corresponding stale index entry in the at least one index table, the step of deleting the corresponding stale index entry comprising;

accessing the at least one index table by using a value of an index (v_index);

obtaining, from the accessed at least one index table, a first key and a first timestamp, corresponding to the v_index;

accessing the at least one data table by using a value of the first key;

obtaining, the accessed at least one data table, an up-to-date value of the index and an up-to-date timestamp, corresponding to the first key;

comparing the v_index against the up-to-date value of the index; and

determining that an up-to-date index entry is (the v_index ⊕

the value of the first key) if the v_index is equal to the up-to-date value of the index, where ⊕

represents a byte array concatenation operation;

determining that the corresponding stale index entry is (the v_index ⊕

the value of the first key) if the v_index is not equal to the up-to-date value of the index and the first timestamp is made prior to the up-to-date timestamp.

16. The computer program product according to claim 15, wherein the at least one index table includes at least one secondary index, which points to a data entry recorded in the at least one data table.

17. The computer program product according to claim 15, wherein the data recorded in the at least one data table includes at least one tuple <

k, v, t>

, where k represents a key, v represents a new value of the key, and t represents a timestamp which indicates that the new value of the key is added to the at least one data table.

18. The computer program product according to claim 15, wherein the method steps further comprise:

invalidating a corresponding stale data entry in the at least one data table upon the insertion of the new data entry into the at least one data table; and

co-existing the corresponding stale index entry and the new index entry in the at least one index table until the query to a query to the corresponding stale index entry is received.

19. The computer program product according to claim 17, wherein the method steps further comprise:

synchronously inserting a new index entry into the at least one index table upon inserting a corresponding new data entry to the at least one data table, and

synchronously deleting a corresponding stale index entry in the at least one index table upon the insertion of the corresponding new index entry to the at least one index table.

20. The computer program product according to claim 19, wherein the method steps further comprise:

inserting the new data entry, represented by the tuple <

k, v, t>

, to the at least one data table;

inserting the new index entry into the at least one index table, the new index entry represented by a tuple <

v⊕

k, null, t>

, where ⊕

represents a byte array concatenation operation;

reading and obtaining an old value of the key k before the time t; and

deleting the corresponding stale index entry, which is represented by the old value of the key k ⊕

the key k.

21. The computer program product according to claim 20, wherein to perform the deleting, the processor is further configured to mark the corresponding stale index entry as invalid.

22. The computer program product according to claim 20, wherein to perform the reading and obtaining, the method steps further comprise:

accessing the at least one data table; and

reading a value of the key k, which was inserted prior to the timestamp t, the read value representing the old value of the key k.

23. The system according to claim 19, wherein once the synchronous inserting is successfully performed in the at least one index table and the at least one data table, the data consistency is maintained between the least one index table and the at least one data table.

24. The computer program product according to claim 17, wherein to perform said operations, the processor is further configured to perform steps of:

asynchronously inserting a new index entry into the at least one index table upon inserting a corresponding new data entry into the at least one data table, and

asynchronously deleting a corresponding stale index entry in the at least one index table.