Database sharding with update layer

• US 10,977,229 B2
• Filed: 05/21/2013
• Issued: 04/13/2021
• Est. Priority Date: 05/21/2013
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Kunnatur, Sandhya, Lassen, Soren Bogh, Curtiss, Michael, Pronin, Pilip
• Primary Examiner(s): Gurmu, Muluemebet
• Application Number:
  US13/899,305
• Publication Number:
  US 20140351203A1
• Time in Patent Office: 2,884 Days
• Field of Search: 707609
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

In one embodiment, a method includes receiving an update of activity associated with one or more content objects associated with a search term. The search term is associated with a number of content objects exceeding a pre-determined threshold number. The content objects associated with the search term are indexed on a list of one or more index servers. The list includes identifier information corresponding to the content objects. The method also includes modifying the list of one or more of the index servers in response to the update.

Claims

1. A method comprising:

by a top aggregator of a social-networking system, receiving an update of user activity associated with one or more content objects associated with a search term that has been parsed from a search query by the top aggregator, the user activity comprising one or more interactions by one or more users of an online social network with one or more content objects, wherein the content objects are of a plurality of different content-object types, and wherein each content object is indexed by a first partition aggregator of the social-networking system on a particular index server of a plurality of index servers;

by the top aggregator, responsive to receiving the update, indexing the one or more content objects on an update layer on a particular index server of a plurality of index servers, wherein each of the index servers stores a list of identifier information corresponding to content objects of a single content-object type of the plurality of different content-object types, and wherein the update layer indexes recent activity and comprises identifier information of the one or more content objects associated with the update;

by a second partition aggregator of the social-networking system associated with the update layer of the particular index server, determining whether the search term has a number of associated content objects indexed on the update layer of the particular index server exceeding a pre-determined threshold number, wherein the pre-determined threshold number is determined based on the content-object type of the content objects associated with the particular index server; and

by the second partition aggregator, at one or more pre-determined times, promoting the identifying information from the update layer to a base layer, wherein the base layer indexes activity previously indexed by the top aggregator on the update layer and comprises identifying information of only a single content-object type, and wherein the base layer comprises identifier information of one or more other content objects of the single content-object type previously associated with the search term.

2. The method of claim 1, wherein the promoting the identifying information comprises, by one or more computing devices, adding identifier information of the one or more content objects associated with the user activity to the update layer in response to the update of the user activity.

3. The method of claim 1, wherein the promoting the identifying information comprises, by one or more computing devices, providing an indication in the update layer that the one or more content objects associated with the user activity are no longer associated with the search term because one of the one or more users deleted the one or more content objects.

4. The method of claim 1, further comprising, by one or more computing devices, returning one or more search results of a search query comprising the search term and an other search term associated with one or more content objects indexed by a term server, the search result being determined at least in part on the one or more content objects associated with the user activity and one or more content objects determined through an intersection of the identifier information of the one or more lists of content object associated with the search term and identifier information of one or more lists of content objects associated with the other search term.

5. The method of claim 1, further comprising:

by the top aggregator, generating one or more lists associated with an other search term on one or more index servers in response to a number of content objects associated with the other search term exceeding the pre-determined threshold number; and

by the top aggregator, populating the one or more lists associated with the other search term with identifier information of one or more of the content objects associated with the other search term indexed by a term server.

6. The method of claim 5, further comprising, by the top aggregator, deleting the other search term and the one or more of the lists associated with the other search term from the term server.

7. One or more computer-readable non-transitory storage media embodying software configured when executed to:

by a top aggregator of a social-networking system, receive an update of user activity associated with one or more content objects associated with a search term that has been parsed from a search query by the top aggregator, the user activity comprising one or more interactions by one or more users of an online social network with one or more content objects, wherein the content objects are of a plurality of different content-object types, and wherein each content object is indexed by a first partition aggregator of the social-networking system, on a particular index server of a plurality of index servers;

by the top aggregator, responsive to receiving the update, index the one or more content objects on an update layer on a particular index server of a plurality of index servers, wherein each of the index servers stores a list of identifier information corresponding to content objects of a single content-object type of the plurality of different content-object types, and wherein the update layer indexes recent activity and comprises identifier information of the one or more content objects associated with the update;

by a second partition aggregator of the social-networking system associated with the update layer of the particular index server, determine whether the search term has a number of associated content objects indexed on the update layer of the particular index server exceeding a pre-determined threshold number, wherein the pre-determined threshold number is determined based on the content-object type of the content objects associated with the particular index server; and

by the second partition aggregator, at one or more pre-determined times, promote the identifying information from the update layer to a base layer, wherein the base layer indexes activity previously indexed by the top aggregator on the update layer and comprises identifying information of only a single content-object type, and wherein the base layer comprises identifier information of one or more other content objects of the single content-object type previously associated with the search term.

8. The media of claim 7, wherein the promoting the identifying information comprises, by one or more computing devices, adding identifier information of the one or more content objects associated with the user activity to the update layer in response to the update of the user activity.

9. The media of claim 7, wherein the promoting the identifying information comprises, by one or more computing devices, providing an indication in the update layer that the one or more content objects associated with the user activity are no longer associated with the search term because one of the one or more users deleted the one or more content objects.

10. The media of claim 7, wherein the software is further configured to return one or more search results of a search query comprising the search term and an other search term associated with one or more content objects indexed by a term server, the search result being determined at least in part on the one or more content objects associated with the user activity and one or more content objects determined through an intersection of the identifier information of the one or more lists of content object associated with the search term and identifier information of one or more lists of content objects associated with the other search term.

11. The media of claim 7, wherein the software is further configured to:

by the top aggregator, generate one or more lists associated with an other search term on one or more index servers in response to a number of content objects associated with the other search term exceeding the pre-determined threshold number; and

by the top aggregator, populate the one or more lists associated with the other search term with identifier information of one or more of the content objects associated with the other search term indexed by a term server.

12. The media of claim 11, wherein the software is further configured to delete the other search term and the one or more of the lists associated with the other search term from the term server.

13. A social-networking system device comprising:

a top aggregator;

a first partition aggregator;

a second partition aggregator;

one or more processors; and

one or more computer-readable non-transitory storage media coupled to the processors and embodying software to;

receive, by the top aggregator, an update of user activity associated with one or more content objects associated with a search term that has been parsed from a search query by the top aggregator, the user activity comprising one or more interactions by one or more users of an online social network with one or more content objects, wherein the content objects are of a plurality of different content-object types, and wherein each content object is indexed by the first partition aggregator on a particular index server of a plurality of index servers;

responsive to receiving the update, index, by the top aggregator, the one or more content objects on an update layer on a particular index server of a plurality of index servers, wherein each of the index servers stores a list of identifier information corresponding to content objects of a single content-object type of the plurality of different content-object types, and wherein the update layer indexes recent activity and comprises identifier information of the one or more content objects associated with the update;

determine, by the second partition aggregator, whether the search term has a number of associated content objects indexed on the update layer of the particular index server exceeding a pre-determined threshold number, wherein the pre-determined threshold number is determined based on the content-object type of the content objects associated with the particular index server; and

at one or more pre-determined times, promote, by the second partition aggregator, the identifying information from the update layer to a base layer, wherein the base layer indexes activity previously indexed by the top aggregator on the update layer and comprises identifying information of only a single content-object type, and wherein the base layer comprises identifier information of one or more other content objects of the single content-object type previously associated with the search term.

14. The device of claim 13, wherein the promoting the identifying information comprises adding identifier information of the one or more content objects associated with the user activity to the update layer in response to the update of the user activity.

15. The device of claim 13, wherein the promoting the identifying information comprises, by one or more computing devices, adding identifier information of the one or more content objects associated with the user activity to the update layer in response to the update of the user activity.

16. The method of claim 1, wherein the base layer is updated at pre-determined time intervals and the update layer is updated at the time of the update.

17. The method of claim 1, wherein the plurality of index servers comprises a first index server storing a list of identifier information corresponding to content objects of a first content-object type, and a second index server storing a list of identifier information corresponding to content objects of a second content-object type.

18. The method of claim 1, wherein each content object of a particular content-object type is indexed on a particular index server of the plurality of index servers, each index server storing a list of identifier information corresponding to content objects of a single content-object type.

19. The method of claim 1, further comprising:

by the top aggregator, receiving a search query from a client system of the user of the online social network, the search query comprising a short search term and a long search term, the long search term being comprised in a hash set of search terms and the short search term being excluded from the hash set of search terms;

by the first partition aggregator, retrieving a first posting list from the base layer that corresponds to the short search term;

by the second partition aggregator, retrieving a second posting list from the update layer that corresponds to the long search term; and

by the top aggregator, sending to the client system instructions to display a search results interface, the search results interface comprising a plurality of references that correspond to the intersection of the first posting list and the second posting list.