Indexing system

• US 9,501,506 B1
• Filed: 12/16/2013
• Issued: 11/22/2016
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fontoura, Marcus, Meredith, Daniel N., Rohde, Douglas Lee Taylor, Palekar, Mahesh S., Shankar, Asim, Baylor, Denis Murray, Rasscevskis, Zigmars, Csomai, Andras
• Primary Examiner(s): Leroux, Etienne
• Application Number:
  US14/107,848
• Time in Patent Office: 1,072 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/328 Management therefor

Abstract

A hybrid-sharded index includes document-sharded posting lists and term-sharded posting lists. Implementations include systems and methods for updating a hybrid-sharded index. For example, a method may include receiving updates to the hybrid-sharded index and generating, at a first leaf node, replacement posting lists and change information for a respective second leaf node. The method may also include dividing the replacement posting lists into portions, a portion having associated change information and being associated with a respective one of the second leaf nodes and sending the portions to respective leaf nodes. At a particular leaf node of the second leaf nodes, the method includes merging a received portion into an updated posing list portion, swapping the updated posting list portion into memory. During the swap, the change information and the updated posting list portion are used to respond to a query with an older version of the hybrid-sharded index.

Claims

1. A method comprising:

receiving, using at least one processor of a first leaf node in a distributed environment, updates to a hybrid-sharded index, the hybrid-sharded index including document-sharded posting lists and term-sharded posting lists;

generating, using the at least one processor of the first leaf node that received an update, replacement posting lists and change information for a respective second leaf node;

dividing the replacement posting lists into portions, a portion having associated change information and being associated with a respective one of the second leaf nodes;

sending the portions to respective second leaf nodes; and

at a particular leaf node of the second leaf nodes;

merging, using at least one processor of the particular leaf node, a received portion into an updated posting list portion,

swapping the updated posting list portion into memory, and

during the swap, using the change information and the updated posting list portion to respond to a query with an older version of the hybrid-sharded index.

2. The method of claim 1, wherein the change information includes an inverse translation table.

3. The method of claim 2, wherein the inverse translation table translates new document identifiers to old document identifiers.

4. The method of claim 1, wherein the updated posting list portion includes the change information.

5. The method of claim 1, wherein the change information includes a delete list and an insert list.

6. The method of claim 1, further comprising ceasing to use the change information when the swap is complete.

7. The method of claim 1, wherein the dividing comprises:

determining whether a document in the update is in a first set of documents or in a second set of documents;

when the document is in the first set, generating the replacement posting list as a document-sharded posting list, wherein the replacement posting list is an updated posting list; and

when the document is in the second set, generating the replacement posting list as a term-sharded posting list and performing the dividing, sending, and merging.

8. The method of claim 1, further comprising:

storing the change information in persistent memory, so that a version of the change information is stored for a period for a batch update; and

recovering a prior version of the hybrid-sharded index using the stored change information.

9. The method of claim 1, wherein using the change information includes translating local document identifiers in the updated posting list portion to local identifiers for the older version.

10. A system comprising:

distributed computing devices represented as leaf nodes and a root node; and

an index of documents, the index being distributed across the leaf nodes, the documents being assigned to respective leaf nodes, and wherein a first leaf node includes;

memory storing document-sharded posting lists for some or all terms associated with documents in a first set of documents that are assigned to the first leaf node, and

memory storing term-sharded posting lists for terms assigned to the first leaf node without regard to leaf node assignments for documents identified in the term-sharded posting lists,

wherein the first leaf node includes;

at least one processor,

memory storing instructions that, when executed by the at least one processor, cause the first leaf node to;

receive an update for documents assigned to the first leaf node,

determine that the update affects the at least one document-sharded posting list and, responsive to the determining, generate an updated document-sharded posting list for the at least one document-sharded posting list, and

determine that the update affects a term-sharded posting list for a term assigned to a second leaf node, the term being associated with at least one document in a second set of documents that are assigned to the first leaf and not in the first set of documents and, responsive to the determining;

generate change information for the documents associated with the term,

generate an updated term-sharded posting list for the term, and

provide the change information and the updated term-sharded posting list to the second leaf node.

11. The system of claim 10, wherein the term assigned to the second leaf node is a first term and wherein the instructions further include instructions that, when executed, cause the first leaf node to:

receive an updated term-sharded posting list portion for a second term from a third leaf node, the second term being assigned to the first leaf node;

receive an updated term-sharded posting list portion for the second term from a fourth leaf node;

merge the updated term-sharded posting list portion from the third leaf node with the updated term-sharded posting list portion from the fourth leaf node to generate a new term-sharded posting list for the second term; and

and use the new term-sharded posting list for the second term in responding to queries.

12. The system of claim 11, wherein as part of using the new term-sharded posting list for the second term, the instructions further include instructions that, when executed, cause the first leaf node to:

apply change information for the portion from the fourth node and the portion from the third leaf node to the new term-sharded posting list so that the first leaf node responds to at least some queries with a current version of the term-sharded posting list.

13. The system of claim 12, wherein the change information includes an inverse translation table.

14. The system of claim 13, wherein the inverse translation table translates new document identifiers to old document identifiers.

15. The system of claim 11, wherein as part of using the new term-sharded posting list for the second term, the instructions further include instructions that, when executed, cause the first leaf node to:

swap the new term-sharded posting list into memory in portions; and

during the swap, apply change information for the portion from the fourth leaf node and change information for the portion from the third leaf node to the new term-sharded posting list so that the first leaf node responds to a query with a prior version of the term-sharded posting list.

16. The system of claim 15, wherein applying the change information occurs for a majority of queries until the first leaf node notifies the root node that the swap is complete.

17. The system of claim 16, wherein after swapping the new term-sharded posting list into memory and prior to notifying the root node, the first leaf node responds to a plurality of queries using the new term-sharded posting list without applying the change information.

18. The system of claim 11, wherein the instructions further include instructions that, when executed, cause the first leaf node to perform the merging when it is determined that a current version of the term-sharded posting list for the second term is stored in slower access memory.

19. The system of claim 10, wherein determining that the update affects the posting list for the term assigned to the second leaf node includes:

determining that the update affects a document that is not in the first set of documents;

determining that the term is associated with the document; and

determining that the term fails to meet a popularity threshold.

20. The system of claim 19, wherein determining that the update affects the posting list for the term assigned to the second leaf node further includes determining that the term is assigned to the second leaf node by applying a function to an identifier for the term.

21. The system of claim 10, wherein the updated term-sharded posting list includes an identifier for the first leaf node.

22. A system comprising:

distributed computing devices represented as leaf nodes and a root node;

an index of documents, the index being distributed across the leaf nodes, the documents being assigned to respective leaf nodes, and wherein a first leaf node includes;

memory storing document-sharded posting lists for some or all terms associated with documents in a first set of documents that are assigned to the first leaf node, and

memory storing term-sharded posting lists for terms assigned to the first leaf node without regard to leaf node assignments for documents identified in the term-sharded posting lists,

wherein the first leaf node includes;

at least one processor,

memory storing instructions that, when executed by the at least one processor, cause the first leaf node to;

receive an update for documents in the first set of documents and, responsive to the receiving, update at least some of the document-sharded posting lists;

receive an updated term-sharded posting list portion for a first term from a second leaf node, the first term being assigned to the first leaf node;

receive an updated term-sharded posting list portion for the first term from a third leaf node; and

generate a new term-sharded posting list for the first term using the portion from the third leaf node and the portion from the second leaf node.

23. The system of claim 22, wherein generating the new term-sharded posting list includes:

concatenating the portion from the second leaf node and the portion from the third leaf node with a portion generated by the first leaf node.

24. The system of claim 22, wherein generating the new term-sharded posting list further includes:

receiving change information from the second leaf node for the portion from the second leaf node; and

concatenating the change information to the end of the portion from the second leaf node, so that the portion from the second leaf node includes the change information.

25. The system of claim 22, wherein the portion from the second leaf node includes an identification of the second leaf node that is retained in the new term-sharded posting list.