Searching entity-key associations using in-memory objects

• US 9,047,328 B2
• Filed: 11/19/2012
• Issued: 06/02/2015
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Mooser, Jonathan
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US13/681,347
• Publication Number:
  US 20140143256A1
• Time in Patent Office: 925 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

Disclosed are a method and system for searching entities and keys that are associated with each other using entity-key associations stored in an in-memory object. When a query is issued for retrieving entity-key associations, the disclosed technique searches an in-memory object, such as a binary large object (BLOB) containing a plurality of entity-key association strings that represent the entity-key associations. An entity-key association string includes an entity name of an entity concatenated with a key name of a key that are associated with each other. Searching for the entity-key associations using the entity-key association strings in the BLOB is faster than a conventional search that includes querying multiple tables in a database. The disclosed technique creates the entity-key association strings by reading necessary data from a data structure stored in data storage unit. Both literal and regular expressions are supported without adversely affecting the query performance.

Claims

1. A method comprising:

identifying, for a plurality of entities and a plurality of keys stored in a data structure in a data storage unit, a plurality of entity-key associations, wherein each of the entity-key associations includes an entity and a key that are associated with each other;

creating, for each of the entity-key associations, an entity-key association string by concatenating an entity identification (ID) of the entity in the entity-key association with a key ID of the key in the entity-key association, to produce a plurality of entity-key association strings;

storing the entity-key association strings and a plurality of association value IDs in a plurality of shards, the association value IDs used for retrieving association values of the entity-key associations represented by the entity-key association strings; and

distributing the shards to a plurality of servers in a computer network.

2. The method of claim 1, wherein each of the entity ID and key ID is a string.

3. The method of claim 1, wherein each of the entities is associated with at least one of the keys.

4. The method of claim 1, wherein each of the keys is associated with at least one of the entities.

5. The method of claim 1, wherein each of the entity-key associations has an association value.

6. The method of claim 1, wherein storing the entity-key association strings and the association value IDs in the shards includes:

creating a first in-memory object in a processing system to store the entity-key association strings;

creating a second in-memory object to store the association value IDs.

7. The method of claim 6, wherein the first in-memory object is a binary large object (BLOB).

8. The method of claim 7, wherein the BLOB stores the entity-key association strings in contiguous blocks of memory in the processing system.

9. The method of claim 6, wherein distributing the shards to the servers includes:

splitting the first in-memory object and the second in-memory object into the shards, wherein each of the shards includes a subset of the entity-key associations from the first in-memory object and corresponding association value IDs from the second in-memory object; and

loading the shards into a memory of each of the servers.

10. The method of claim 9 further comprising:

receiving, from a client in the computer network, a query for retrieving a result set including at least one of (i) an entity-key association, or (ii) an association value of the entity-key association, the query including a query parameter that identifies at least one of (i) an entity, or (ii) a key;

searching, at each of the servers in parallel and in response to the query, the shards to obtain the result set based on the query parameter;

obtaining the result set from the servers; and

sending the result set to the client.

11. The method of claim 9 further comprising:

receiving, from a user in a computer user interface that accepts an entity-key association as an input, an entity or a key; and

suggesting, to the user, the other of the entity or the key, wherein the other of the entity or the key is associated with the entity or the key received from the user, and wherein both the entity or the key received from the user and the suggested other of the entity or the key collectively form the input to the computer user interface.

12. The method of claim 1 further comprising:

updating the entity-key association strings when the entities or the keys or the entity-key associations in the data structure are updated.

13. The method of claim 1, wherein creating the entity-key association string includes adding a first string delimiter between the entity ID and the key ID in the entity-key association string.

14. The method of claim 1, where in each of the entity-key association strings is separated by a second string delimiter.

15. A method comprising:

receiving, from a client in a computer system, a query for retrieving an entity-key association, the query including a query parameter that identifies at least one of (i) an entity, or (ii) a key;

searching, at a server in response to the query, a first in-memory object having a plurality of entity-key association strings to obtain the entity-key association based on the query parameter, the entity-key association strings representing entity-key associations of a plurality of entities and a plurality of keys stored in a data structure of a data storage unit, and each of the entity-key association strings including an entity identification (ID) of a first entity concatenated with a key ID of a first key that is associated with the first entity, wherein the entity-key association strings have corresponding association value IDs, the association value IDs stored in a second-in memory object and used for retrieving association values of the entity-key associations represented by the entity-key association strings, wherein the first in-memory object and the second in-memory are split into a plurality of shards, and wherein the shards are distributed to a plurality of servers in a computer network;

obtaining the entity-key association from the first in-memory object; and

sending, to the client, the entity-key association.

16. The method of claim 15, wherein the first in-memory object is a BLOB.

17. The method of claim 15 further comprising:

obtaining an association value of the entity-key association from the second in-memory object.

18. The method of claim 17, wherein searching the first in-memory object at the server includes:

searching, at the servers and in parallel, the shards, each of the shards containing a subset of the entity-key associations from the first in-memory object and corresponding association value IDs from the second in-memory object, each of the servers having a different subset of the shards, and the different subset of the shards loaded into a memory of corresponding servers.

19. An apparatus comprising:

a processor;

an entity-key association identification unit, operatively coupled to the processor, to identify, for a plurality of entities and a plurality of keys stored in a data structure in a data storage unit, a plurality of entity-key associations, wherein each of the entity-key associations includes an entity and a key that are associated with each other, and wherein each of the entity-key associations includes an association value;

an entity-key association string generation unit to create, for each of the entity-key associations, an entity-key association string by concatenating an entity identification (ID) of the entity in the entity-key association with a key ID of the key in the entity-key association;

an entity-key association object creation unit to create

a first in-memory object to store a plurality of entity-key association strings, each of the entity-key association strings representing one of the entity-key associations, and

a second in-memory object to store a plurality of association value IDs of association values, the association values corresponding to the entity-key associations represented by the entity-key association strings; and

an entity-key association distribution unit to

split the first in-memory object and the second in-memory object into a plurality of shards, each of the shards containing a subset of entity-key association strings from the first in-memory object and corresponding association value IDs from the second in-memory object,

distribute the shards to a plurality of servers in a computer network, wherein each of the servers receives a different subset of the shards, and

load the different subset of the shards into a memory of the corresponding servers.

20. The apparatus of claim 19, wherein the first in-memory object is a BLOB.

21. The apparatus of claim 19 further a comprising:

a query processing unit to

receive a query, from a client in the computer network, for retrieving a result set including an entity-key association,

process the query, at the servers and in parallel, to obtain the result set from the shards, and

send the result set to the client.