Searching entity-key associations using in-memory objects

• US 9,734,178 B2
• Filed: 04/28/2015
• Issued: 08/15/2017
• 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:
  US14/698,622
• Publication Number:
  US 20150248447A1
• Time in Patent Office: 840 Days
• Field of Search: 707600-831, 707899, 707999001-999206
• 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 multiple entities and multiple keys stored in a data structure in a data storage unit, multiple entity-key associations, wherein at least some 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 multiple entity-key association strings;

creating a first in-memory object in a computer system to store the entity-key association strings, the entity-key association strings representing the entity-key associations; and

performing a search using the first in-memory object to retrieve at least one of (i) an entity-key association of the multiple entity-key associations, or (ii) an association value of the entity-key association.

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 computer 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 at least some of the entity-key associations have corresponding association values.

6. The method of claim 5 further comprising:

creating a second in-memory object to store multiple association value IDs for the entity-key association strings in the first in-memory object, the association value IDs used to retrieve the association values of the entity-key associations represented by the entity-key association strings.

7. The method of claim 6, wherein the second in-memory object is a metafile, the metafile including:

a byte offset of a specified entity-key association string of the entity-key association strings in the first in-memory object,

a specified association value ID for the specified entity-key association string, and

a storage location from where an association value of a specified entity-key association represented by the specified entity-key association string is to be retrieved from using the specified association value ID.

8. The method of claim 6, 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 multiple shards, wherein at least some of the shards include 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 multiple servers in a computer network, and

loading the shards into a memory of at least some of the servers.

9. The method of claim 8, wherein performing the search includes:

receiving, from a client in the computer network, a query for retrieving a result set including at least one of (i) the entity-key association, or (ii) the 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 least some 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.

10. The method of claim 8 further comprising:

receiving, from a user in a computer user interface that accepts the 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.

11. 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.

12. 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.

13. 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.

14. A non-transitory computer-readable storage medium storing computer-readable instructions, the instructions comprising:

instructions for receiving, from a client in a computer system, a query for retrieving a value of a key associated with an entity, the query including (i) an entity ID of the entity (ii) a key ID of the key;

instructions for searching, at a server in the computer system in response to the query, a first in-memory object having multiple entity-key association strings to obtain an entity-key association string that identifies an entity-key association of the entity and the key, the entity-key association string created by concatenating the entity ID of the entity with the key ID of the key;

instructions for obtaining the entity-key association string from the first in-memory object;

instructions for obtaining an association value ID of the entity-key association corresponding to the entity-key association string from a second in-memory object, the obtaining further including obtaining the value of the key from a storage location using the association value ID; and

instructions for sending the value of the key to the client.

15. The computer-readable storage medium of claim 14, wherein the first in-memory object is a BLOB.

16. The computer-readable storage medium of claim 14, wherein the second in-memory object is a metafile, the metafile including:

a byte offset of the entity-key association string in the first in-memory object,

the association value ID for the entity-key association string, and

the storage location from where the value of the key is to be retrieved from using the association value ID.

17. The computer-readable storage medium of claim 14, wherein the instructions for searching the first in-memory object to obtain the entity-key association string includes instructions for:

adding a first string delimiter between the entity ID and the key ID in the entity-key association string.

18. The computer-readable storage medium of claim 14, wherein searching the first in-memory object at the server includes:

searching, at multiple servers in a computer network and in parallel, multiple 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, at least some 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 string generation unit to generate an entity-key association string that represents an entity-key association of an entity and a key associated with the entity in a computing system, the entity key association string generation unit configured to generate the entity-key association string by concatenating an entity identification (ID) of the entity with a key ID of the key;

an entity-key association object creation unit to create;

a first in-memory object to store multiple entity-key association strings, the entity-key association strings corresponding to multiple entity-key associations, the entity-key associations representing associations between multiple entities and multiple keys in the computing system, and

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

a query processing unit configured to perform a search using the first in-memory object to retrieve at least one of (i) an entity-key association of the multiple entity-key associations, or (ii) an association value of the entity-key association.

20. The apparatus of claim 19, wherein the query processing unit is configured to:

receive a query, from a client, for retrieving a value of a specified key of the keys associated with a specified entity of the entities,

obtain an entity-key association string from the first in-memory object, that identifies a specified entity-key association of the specified entity and the specified key,

obtain an association value ID corresponding to the specified entity-key association string from the second in-memory object, and further obtain the value of the specified key from a storage location specified by the association value ID, and

send the value of the key to the client.