Granted Patent B2

US 12,373,491 · App. 18/534,160 · Granted Jul 29, 2025

Inventor: Menkae Jeng (San Jose, CA)

Assignee: WALMART APOLLO, LLC

G06F16/9014G06F9/5072

Abstract

Claims (88)

1. A system comprising:

one or more processors; and

one or more non-transitory computer-readable media storing computing instructions configured to, when run on the one or more processors, cause the one or more processors to perform:

determining a common mapping scheme for a plurality of message queues and a plurality of shards for an index message to be committed to the plurality of shards, wherein:

the common mapping scheme comprises:

a respective shard hash range for each of the plurality of shards; and

a mapping function between the plurality of message queues and the plurality of shards;

determining a message hash value for the index message;

determining a target shard of the plurality of shards based on the message hash value and the respective shard hash range for each of the plurality of shards;

determining an intermediate message queue of the plurality of message queues based on the message hash value and the mapping function for the target shard;

storing the index message to the intermediate message queue, as determined; and

causing the index message stored in the intermediate message queue to be committed to the target shard.

2. The system in claim 1 , wherein:

determining the common mapping scheme comprises determining the mapping function; and

determining the mapping function comprises:

determining, based on a shard count for the plurality of shards and a queue count for the plurality of message queues, a sub-shard count for each of the plurality of shards;

determining, based on the shard count and the queue count, a sub-queue count for each of the plurality of message queues;

determining, based on the sub-shard count, one or more respective sub-shard hash ranges for the respective shard hash range for each of the plurality of shards;

determining, based on the sub-queue count, one or more respective sub-queue hash ranges for a respective queue hash range for each of the plurality of message queues; and

determining a bijective function between: (a) each sub-shard of one or more respective sub-shards for each of the plurality of shards and (b) a mapped sub-queue of one or more respective sub-queues for each of the plurality of the message queues, based on a sub-shard hash range for the each sub-shard and a sub-queue hash range for the mapped sub-queue, wherein:

the mapping function comprises the bijective function.

3. The system in claim 2 , wherein the shard count and the queue count are different.

4. The system in claim 2 , wherein a first range size of each of the one or more respective sub-shard hash ranges is equal to a second range size of each of the one or more respective sub-queue hash ranges.

5. The system in claim 2 , wherein:

determining the mapping function further comprises determining a least common multiple of the shard count and the queue count;

determining the sub-shard count for each of the plurality of shards comprises dividing the least common multiple by the shard count; and

determining the sub-queue count for each of the plurality of message queues comprises dividing the least common multiple by the queue count.

6. The system in claim 1 , wherein the computing instructions are further configured, when run on the one or more processors, to cause the one or more processors to perform:

before determining the message hash value for the index message, generating the index message for an item in a data source.

7. The system in claim 1 , wherein:

causing the index message stored in the intermediate message queue to be committed to the target shard comprises causing one of a plurality of update modules to: (a) read, from the intermediate message queue, a batch of one or more queued messages comprising the index message, and (b) commit the batch of the one or more queued messages, as read, to one or more of the plurality of shards comprising the target shard.

8. The system in claim 7 , wherein:

causing the index message stored in the intermediate message queue to be committed to the target shard further comprises determining the one of the plurality of update modules based on a queue count for the plurality of message queues and a updater count for the plurality of update modules.

9. The system in claim 1 , wherein the computing instructions are further configured, when run on the one or more processors, to cause the one or more processors to perform:

causing the common mapping scheme to be applied to a duplicate data center.

10. The system in claim 9 , wherein:

storing the index message to the intermediate message queue further comprises transmitting the index message to be committed to the duplicate data center.

11. A method being implemented via execution of computing instructions configured to run at one or more processors and stored at one or more non-transitory computer-readable media, the method comprising:

determining a common mapping scheme for a plurality of message queues and a plurality of shards for an index message to be committed to the plurality of shards, wherein:

the common mapping scheme comprises:

a respective shard hash range for each of the plurality of shards; and

a mapping function between the plurality of message queues and the plurality of shards;

determining a message hash value for the index message;

determining a target shard of the plurality of shards based on the message hash value and the respective shard hash range for each of the plurality of shards;

determining an intermediate message queue of the plurality of message queues based on the message hash value and the mapping function for the target shard;

storing the index message to the intermediate message queue, as determined; and

causing the index message stored in the intermediate message queue to be committed to the target shard.

12. The method in claim 11 , wherein:

determining the common mapping scheme comprises determining the mapping function; and

determining the mapping function comprises:

determining, based on a shard count for the plurality of shards and a queue count for the plurality of message queues, a sub-shard count for each of the plurality of shards;

determining, based on the shard count and the queue count, a sub-queue count for each of the plurality of message queues;

determining, based on the sub-shard count, one or more respective sub-shard hash ranges for the respective shard hash range for each of the plurality of shards;

determining, based on the sub-queue count, one or more respective sub-queue hash ranges for a respective queue hash range for each of the plurality of message queues; and

determining a bijective function between: (a) each sub-shard of one or more respective sub-shards for each of the plurality of shards and (b) a mapped sub-queue of one or more respective sub-queues for each of the plurality of the message queues, based on a sub-shard hash range for the each sub-shard and a sub-queue hash range for the mapped sub-queue, wherein:

the mapping function comprises the bijective function.

13. The method in claim 12 , wherein the shard count and the queue count are different.

14. The method in claim 12 , wherein a first range size of each of the one or more respective sub-shard hash ranges is equal to a second range size of each of the one or more respective sub-queue hash ranges.

15. The method in claim 12 , wherein:

determining the mapping function further comprises determining a least common multiple of the shard count and the queue count;

determining the sub-shard count for each of the plurality of shards comprises dividing the least common multiple by the shard count; and

determining the sub-queue count for each of the plurality of message queues comprises dividing the least common multiple by the queue count.

16. The method in claim 11 , further comprising at least one of:

before determining the message hash value for the index message, generating the index message for an item in a data source; or

causing the common mapping scheme to be applied to a duplicate data center, wherein storing the index message to the intermediate message queue further comprises transmitting the index message to be committed to the duplicate data center.

17. The method in claim 11 , wherein:

causing the index message stored in the intermediate message queue to be committed to the target shard comprises causing one of a plurality of update modules to: (a) read, from the intermediate message queue, a batch of one or more queued messages comprising the index message, and (b) commit the batch of the one or more queued messages, as read, to one or more of the plurality of shards comprising the target shard.

18. The method in claim 17 , wherein:

causing the index message stored in the intermediate message queue to be committed to the target shard further comprises determining the one of the plurality of update modules based on a queue count for the plurality of message queues and a updater count for the plurality of update modules.

19. A non-transitory computer-readable media storing computing instructions that, when executed by one or more processors, cause the one or more processors to perform operations comprising:

determining a common mapping scheme for a plurality of message queues and a plurality of shards for an index message to be committed to the plurality of shards, wherein:

the common mapping scheme comprises:

a respective shard hash range for each of the plurality of shards; and

a mapping function between the plurality of message queues and the plurality of shards;

determining a message hash value for the index message;

determining a target shard of the plurality of shards based on the message hash value and the respective shard hash range for each of the plurality of shards;

determining an intermediate message queue of the plurality of message queues based on the message hash value and the mapping function for the target shard;

storing the index message to the intermediate message queue, as determined; and

causing the index message stored in the intermediate message queue to be committed to the target shard.

20. The non-transitory computer-readable media of claim 19 , wherein:

determining the common mapping scheme comprises determining the mapping function; and

determining the mapping function comprises:

determining, based on a shard count for the plurality of shards and a queue count for the plurality of message queues, a sub-shard count for each of the plurality of shards;

determining, based on the shard count and the queue count, a sub-queue count for each of the plurality of message queues;

determining, based on the sub-shard count, one or more respective sub-shard hash ranges for the respective shard hash range for each of the plurality of shards;

determining, based on the sub-queue count, one or more respective sub-queue hash ranges for a respective queue hash range for each of the plurality of message queues; and

determining a bijective function between: (a) each sub-shard of one or more respective sub-shards for each of the plurality of shards and (b) a mapped sub-queue of one or more respective sub-queues for each of the plurality of the message queues, based on a sub-shard hash range for the each sub-shard and a sub-queue hash range for the mapped sub-queue, wherein:

the mapping function comprises the bijective function.

Assignments (1)

Continuity (1)

References Cited (13)