SEARCHING ENTITY-KEY ASSOCIATIONS USING IN-MEMORY OBJECTS

• US 20140143256A1
• Filed: 11/19/2012
• Published: 05/22/2014
• 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
• Granted Patent: US 9,047,328 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• 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; and

creating a first in-memory object in a processing system to store the entity-key association strings, each of the entity-key association strings representing one of the entity-key associations.

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

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

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

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

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

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

8. The method of claim 7 further comprising:

creating 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 in the first in-memory object.

9. The method of claim 7, wherein creating the first in-memory object and the second in-memory object includes

splitting the first in-memory object and the second in-memory object into a plurality of 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;

distributing the shards to a plurality of servers in a computer network; 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 in the first in-memory object 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 in the first in-memory object 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 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;

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 a second in-memory object, the second in-memory object having a plurality of association value IDs of association values, the association values corresponding to entity-key associations represented by the entity-key association strings in the first in-memory object.

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

searching, at a plurality of servers in a computer network and in parallel, a plurality of 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.