Pattern for integrating primary and secondary data stores in a sharded data domain

• US 10,025,710 B2
• Filed: 04/30/2014
• Issued: 07/17/2018
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Inventors: Sardina, Jason, Olkhovskii, Alexei, Lowell, Robert P.
• Primary Examiner(s): Gofman, Alex
• Assistant Examiner(s): Dewan, Kamal K
• Application Number:
  US14/266,412
• Publication Number:
  US 20150317340A1
• Time in Patent Office: 1,539 Days
• Field of Search: 707803, 707704, 707999008, 707999101, 707999102, 707999103, 707E17007, 711114, 711133, 714 612, 714E1113
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• 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/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 2212/603 of operating mode, e.g. cache mode or local memory mode

Abstract

Example systems and methods for integrating a sharded primary data store (e.g., a source-of-truth relational database management system), a secondary data store (e.g., external cache) and an external global index are described. The approach implements a modified read-through/write-through data access pattern that integrates read and write flows in order to support high-concurrency environments while maintaining immediate consistency between all three stores. Writes are handled using a three-phase flow that avoids concurrency-related race conditions and the need to block in the secondary store in order to maintain cross-store consistency. Reads are never dirty and will repair the secondary store as needed, presenting an immediately consistent view of data to application consumers.

Claims

1. A method comprising:

receiving, by a data access logic (DAL) framework comprising one or more processors, a request for a write operation of a record, the DAL framework managing cache persistence associated with a sharded database, a secondary data store, and an alternative key global indexes (AKGI) database, the secondary data store being configured to act as a read cache to offload read activity from the sharded database;

initializing the secondary data store by (1) updating metadata of the record in the secondary data store, the metadata comprising a primary key (PK) associated with the record, and an alternative key (AK) hash value associated with the record, (2) not changing content data of the record when the record is not a new aggregate, and (3) storing a null payload in the content data of the record when the record is a new aggregate, wherein updating the metadata of the record in the secondary data store comprises;

setting a transaction-specific time-to-live (TTL) for the record, the transaction-specific TTL being specified by an application that requested the write operation; and

setting a check-and-set (CAS) value for the record;

performing, based on the PK and the AK hash value, the write operation of the record in the AKGI database and the sharded database, respectively, in a single coordinated transaction in which a modification of the AKGI database is completed before modifying the sharded database; and

updating the content data of the record in the secondary data store, in a finalization phase of the secondary data store, by (1) resetting the metadata, including the transaction-specific TTL, and (2) persisting aggregate data and AKGI data to the secondary data store in response to determining that;

(i) the write operation is successfully completed and the record is committed to the sharded database and the AKGI database, and (ii) the CAS value has not been changed during the transaction-specific TTL.

2. The method of claim 1, wherein performing the write operation of the record in the AKGI database and the sharded database comprises performing the write operation of the record in the sharded database after the write operation of the record is performed in the AKGI database.

3. The method of claim 1, wherein:

initializing the secondary data store comprises setting an optimistic locking value associated with the record; and

performing the write operation of the record in the AKGI database and the sharded database comprises performing the write operation of the record in the AKGI database and the sharded database in response to determining that the optimistic locking value has not been changed.

4. The method of claim 1, further comprising:

writing the content data of the record in the secondary data store in response to a determination that the secondary data store does not include the record.

5. The method of claim 1, further comprising:

performing a delete operation of the record in the AKGI database in response to a determination that the write operation of the record in the AKGI database is not successfully completed.

6. The method of claim 1, further comprising:

modifying the AK hash value associated with the record in response to a determination that the write operation of the record in the AKGI database is not successfully completed.

7. The method of claim 1, further comprising:

determining that initializing the secondary data store is not successfully completed; and

logging the record in a cache failure log table comprising the PK associated with the record and a timestamp associated with the record.

8. The method of claim 1, wherein the secondary data store is an external cache that is physically separate from the sharded database.

9. An apparatus comprising:

a memory configured to store data and one or more sets of instructions; and

one or more processors coupled to the memory, the one or more processors configured to execute the one or more sets of instructions and perform operations comprising;

receiving a request for a write operation of a record in a secondary data store associated with a sharded database and an alternative key global indexes (AKGI) database, the secondary data store being configured to act as a read cache to offload read activity from the sharded database;

determining whether the secondary data store includes the record; and

in response to a determination that the secondary data store includes the record;

initializing the secondary data store by (1) updating metadata of the record in the secondary data store, the metadata comprising a primary key (PK) associated with the record and an alternative key (AK) hash value associated with the record, (2) not changing content data of the record when the record is not a new aggregate, and (3) storing a null payload in the content data of the record when the record is a new aggregate, wherein updating the metadata of the record in the secondary data store comprises;

setting a transaction-specific time-to-live (TTL) for the record, the transaction-specific TTL being specified by an application that requested the write operation; and

setting a check-and-set (CAS) value for the record;

performing, based on the PK and the AK hash value, the write operation of the record in the AKGI database and the sharded database, respectively, in a single coordinated transaction in which a modification of the AKGI database is completed before modifying the sharded database; and

updating the content data of the record in the secondary data store, in a finalization phase of the secondary data store, by (1) resetting the metadata, including the transaction-specific TTL, and (2) persisting aggregate data and AKGI data to the secondary data store in response to determining that;

(i) the write operation is successfully completed, and (ii) the CAS value has not been changed during the transaction-specific TTL.

10. The apparatus of claim 9, wherein the apparatus comprises a data access layer (DAL) that manages cache persistence associated with the secondary data store and the sharded database.

11. The apparatus of claim 9, wherein performing the write operation of the record in the AKGI database and the sharded database comprises performing the write operation of the record in the sharded database after the write operation of the record is performed in the AKGI database.

12. The apparatus of claim 9, wherein:

initializing the secondary data store comprises setting an optimistic locking value associated with the record; and

performing the write operation of the record in the AKGI database and the sharded database comprises performing the write operation of the record in the AKGI database and the sharded database in response to determining that the optimistic locking value has not been changed.

13. The apparatus of claim 9, wherein the operations performed by the one or more processors further comprise:

writing the content data of the record in the secondary data store in response to a determination that the secondary data store does not include the record.

14. The apparatus of claim 9, wherein the operations performed by the one or more processors further comprise:

performing a delete operation of the record in the AKGI database in response to a determination that the write operation of the record in the AKGI database is not successfully completed.

15. The apparatus of claim 9, wherein the operations performed by the one or more processors further comprise:

modifying the AK hash value associated with the record in response to a determination that the write operation of the record in the AKGI database is not successfully completed.