PATTERN FOR INTEGRATING PRIMARY AND SECONDARY DATA STORES IN A SHARDED DATA DOMAIN

• US 20150317340A1
• Filed: 04/30/2014
• Published: 11/05/2015
• Est. Priority Date: 04/30/2014
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Sardina, Jason, Olkhovskii, Alexei, Lowell, Robert P.
• Granted Patent: US 10,025,710 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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;

initializing the secondary data store by updating metadata of the record in the secondary data store, the metadata including a primary key (PK) associated with the record and an alternative key (AK) hash value associated with the record;

performing, based on the PK and the AK hash value, a write operation of the record in the AKGI database and the sharded database, respectively; and

updating content data of the record in the secondary data store in response to determining that the write operation is successfully completed.

2. The method of claim 1, wherein the 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 the initializing the secondary data store comprises setting an optimistic locking value associated with the record, and wherein the performing the write operation of the record 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:

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

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 associated with the record in response to determining 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 the initializing the secondary data store is not successfully completed; and

logging the record in a cache failure log table, that includes 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 database.

9. A method comprising:

receiving, by a data access logic (DAL) framework comprising one or more processors, a request for a read operation of a record, the DAL framework managing cache persistence associated with a sharded database, a level 2 (L2) cache, and an alternative key global indexes (AKGI) database;

determining whether the L2 cache includes the record; and

in response to a determination that the L2 cache includes the record;

generating an alternative key (AK) hash value associated with the record,

searching the L2 cache to identify a primary key (PK) associated with the record using the AK hash value, and

retrieving the record using the PK value.

10. The method of claim 9, further comprising:

in response to a determination that the L2 cache does not include the record, determining whether the AKGI database includes the record

11. The method of claim 10, further comprising:

in response to a determination that the AKGI database includes the record;

returning the PK value,

performing a read-repair operation of the record in the L2 cache, and

returning the record using the PK value.

12. The method of claim 11, further comprising:

in response to a determination that the AKGI database does not include the record, determining whether the sharded database includes the record by broadcasting the request to a plurality of shards of the sharded database.

13. The method of claim 12, further comprising:

in response to a determination that the sharded database includes the record;

performing an additional read-repair operation of the record in the L2 cache and the AKGI database, respectively, and

returning the record using the PK value.

14. 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 level 2 (L2) cache associated with a sharded database and an alternative key global indexes (AKGI) database;

determining whether the L2 cache includes the record; and

in response to a determination that the L2 cache includes the record;

initializing the L2 cache by updating metadata of the record in the L2 cache, the metadata including a primary key (PK) associated with the record and an alternative key (AK) hash value associated with the record,

performing, based on the PK and the AK hash value, a write operation of the record in the AKGI database and the sharded database, respectively, and

updating content data of the record in the L2 cache in response to determining that the write operation is successfully completed.

15. The apparatus of claim 14, wherein the apparatus comprises a dada access layer (DAL) that manages cache persistence associated with the L2 cache and the database.

16. The apparatus of claim 14, wherein the 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.

17. The apparatus of claim 14, wherein the initializing the L2 cache comprises setting an optimistic locking value associated with the record, and wherein the performing the write operation of the record 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.

18. The apparatus of claim 14, further comprising:

in response to a determination that the L2 cache does not include the record, writing the content data of the record in the L2 cache.

19. The apparatus of claim 14, 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.

20. The apparatus of claim 14, further comprising:

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