SCALE-OUT INDEXING FOR A DISTRIBUTED SEARCH ENGINE

• US 20200134085A1
• Filed: 10/26/2018
• Published: 04/30/2020
• Est. Priority Date: 10/26/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Liu, Cherami Min, Zhang, Scott Ming, Yu, Jing, Zhao, Bruce Ke, Ruvala, Kunal
• Granted Patent: US 11,347,778 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/162 Delete operations erasing in storage systems G06F3/0652
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/9014 hash tables

Abstract

Methods and systems for data indexing are disclosed. According to some embodiments, an index is split into a number of slots based on a slot power value. Each of the slots is assigned with a slot number. A first subset of the slots is allocated to a first shard mapped to the index. A second subset of the slots is allocated to a second shard mapped to the index. The first subset and the second subset are respectively allocated to the first shard and the second shard based on a shard-slot mapping.

Claims

1. A computer-implemented method of data indexing, comprising:

splitting an index into a plurality of slots based on a slot power value, wherein each of plurality of slots is assigned with a slot number;

allocating a first subset of the slots to a first shard mapped to the index; and

allocating a second subset of the slots to a second shard mapped to the index;

wherein the first subset and the second subset are respectively allocated to the first shard and the second shard based on a shard-slot mapping.

2. The method of claim 1, wherein

the first subset of the slots includes a first slot assigned with a first minimum slot number, and a second slot assigned with a first maximum slot number,

the second subset of the slots includes a third slot assigned with a second minimum slot number, and a fourth slot assigned with a second maximum slot number.

3. The method of claim 1, further comprising:

in response to a request to index a document, determining one of the plurality of slots to store the document by performing a modulus operation between a hash value of a document identifier (ID) of the document and a total number of slots to determine the slot number assigned to the slot to store the document.

4. The method of claim 3, wherein the hash value is represented by a plurality of bits, and the slot number is identified by some of the plurality of bits.

5. The method of claim 1, further comprising:

in response to a request to add a document, determining whether size of the document exceeds a prefer shard size;

suspending the second shard in response to determining that the size of the document exceeds the prefer shard size; and

copying the second shard to produce a third shard, wherein the third shard is a duplicate shard of the second shard.

6. The method of claim 5, further comprising:

deleting a first set of existing documents from the second shard;

deleting a second set of existing documents from the third shard;

creating the third shard as a new shard; and

resuming the second shard;

wherein the slot numbers that host the deleted first set of existing documents are held by the new shard;

wherein the slot numbers that host the deleted second set of existing documents are held by the second shard.

7. The method of claim 5, wherein the prefer shard size is determined based on a maximum shard suspend time and a reallocation speed.

8. The method of claim 1, wherein the plurality of slots comprises 2^N slots, wherein N is the slot power value greater than or equal to zero (0).

9. A non-transitory machine-readable medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations for data indexing, the operations comprising:

splitting an index into a plurality of slots based on a slot power value, wherein each of plurality of slots is assigned with a slot number;

allocating a first subset of the slots to a first shard mapped to the index; and

allocating a second subset of the slots to a second shard mapped to the index;

wherein the first subset and the second subset are respectively allocated to the first shard and the second shard based on a shard-slot mapping.

10. The non-transitory machine-readable medium of claim 9, wherein

the first subset of the slots includes a first slot assigned with a first minimum slot number, and a second slot assigned with a first maximum slot number,

the second subset of the slots includes a third slot assigned with a second minimum slot number, and a fourth slot assigned with a second maximum slot number.

11. The non-transitory machine-readable medium of claim 9, wherein the operations further comprise:

in response to a request to index a document, determining one of the plurality of slots to store the document by performing a modulus operation between a hash value of a document identifier (ID) of the document and a total number of slots to determine the slot number assigned to the slot to store the document.

12. The non-transitory machine-readable medium of claim 11, wherein the hash value is represented by a plurality of bits, and the slot number is identified by some of the plurality of bits.

13. The non-transitory machine-readable medium of claim 9, wherein the operations further comprise:

in response to a request to add a document, determining whether size of the document exceeds a prefer shard size;

suspending the second shard in response to determining that the size of the document exceeds the prefer shard size; and

copying the second shard to produce a third shard, wherein the third shard is a duplicate shard of the second shard.

14. The non-transitory machine-readable medium of claim 13, wherein the operations further comprise:

deleting a first set of existing documents from the second shard;

deleting a second set of existing documents from the third shard;

creating the third shard as a new shard; and

resuming the second shard;

wherein the slot numbers that host the deleted first set of existing documents are held by the new shard;

wherein the slot numbers that host the deleted second set of existing documents are held by the second shard.

15. The non-transitory machine-readable medium of claim 13, wherein the prefer shard size is determined based on a maximum shard suspend time and a reallocation speed.

16. The non-transitory machine-readable medium of claim 9, wherein the plurality of slots comprises 2^N slots, wherein N is the slot power value greater than or equal to zero (0).

17. A data processing system, comprising:

a processor; and

a memory coupled to the processor to store instructions, which when executed by the processor, cause the processor to perform operations, the operations including

splitting an index into a plurality of slots based on a slot power value, wherein each of plurality of slots is assigned with a slot number;

allocating a first subset of the slots to a first shard mapped to the index; and

allocating a second subset of the slots to a second shard mapped to the index;

wherein the first subset and the second subset are respectively allocated to the first shard and the second shard based on a shard-slot mapping.

18. The data processing system of claim 17, wherein

the first subset of the slots includes a first slot assigned with a first minimum slot number, and a second slot assigned with a first maximum slot number,

the second subset of the slots includes a third slot assigned with a second minimum slot number, and a fourth slot assigned with a second maximum slot number.

19. The data processing system of claim 17, wherein the operations further comprise:

in response to a request to index a document, determining one of the plurality of slots to store the document by performing a modulus operation between a hash value of a document identifier (ID) of the document and a total number of slots to determine the slot number assigned to the slot to store the document.

20. The data processing system of claim 19, wherein the hash value is represented by a plurality of bits, and the slot number is identified by some of the plurality of bits.

21. The data processing system of claim 17, wherein the operations further include:

in response to a request to add a document, determining whether size of the document exceeds a prefer shard size;

suspending the second shard in response to determining that the size of the document exceeds the prefer shard size; and

copying the second shard to produce a third shard, wherein the third shard is a duplicate shard of the second shard.

22. The data processing system of claim 21, wherein the operations further include:

deleting a first set of existing documents from the second shard;

deleting a second set of existing documents from the third shard;

creating the third shard as a new shard; and

resuming the second shard;

wherein the slot numbers that host the deleted first set of existing documents are held by the new shard;

wherein the slot numbers that host the deleted second set of existing documents are held by the second shard.

23. The data processing system of claim 21, wherein the prefer shard size is determined based on a maximum shard suspend time and a reallocation speed.

24. The data processing system of claim 17, wherein the plurality of slots comprises 2^N slots, wherein N is the slot power value greater than or equal to zero (0).