Optimized record placement in defragmenting graph database

Patent metadata

Field	Value
Publication number	US-11880302-B2
Application number	US-202117480258-A
Country	US
Kind code	B2
Filing date	Sep 21, 2021
Priority date	Jun 29, 2017
Publication date	Jan 23, 2024
Grant date	Jan 23, 2024

Abstract

Methods and systems are disclosed for optimizing record placement in defragmenting a graph database. Issues with fragmented data within a graph database are addressed on the record level by placing data that is frequently accessed together contiguously within memory. For example, a dynamic rule set may be developed based on dynamically analyzing access patterns of the graph database, policies, system characteristics and/or other heuristics. Based on statistics regarding normal query patterns, the systems and methods may identify an optimal position for certain types of edges that are often traversed with respect to particular types of nodes.

First claim

What is claimed is:

1. A system comprising:
a processor; and
memory coupled to the processor, the memory comprising computer executable instructions that, when executed by the processor, performs a method comprising:
receiving a write request to write data to a graph database, the write request including an entity and a property;
accessing a dynamic ruleset associated with the write request, wherein the dynamic ruleset optimizes record placement in the graph database and is based on a statistical access pattern associated with at least one of a node or an edge in the graph database, the node or the edge relating to the entity or the property;
based on the dynamic ruleset, determining a number of records for storing the entity and the property in the graph database;
determining a first memory location for at least one of the entity or the property; and
allocating, for the number of records, a contiguous block of records for the first memory location such that the first memory location is located proximate to a second memory location for the node or the edge.

2. The system of claim 1 , wherein receiving the write request comprises:
parsing the write request to extract the data; and
identifying the entity based on the extracted data.

3. The system of claim 2 , wherein the extracted data is used to create, in the graph database, at least one of an additional node or an additional edge in the graph database.

4. The system of claim 2 , wherein identifying the entity based on the extracted data includes determining a memory location of the entity.

5. The system of claim 1 , wherein the statistical access pattern characterizes traversal of one or more edges from a first node to a second node within the graph database for one or more queries.

6. The system of claim 5 , wherein characterizing the traversal of the one or more edges includes identifying one or more edge types or one or more node types associated with the one or more edges.

7. The system of claim 5 , wherein characterizing the traversal of the one or more edges includes logging a number of node types traversed during the traversal of the one or more edges.

8. The system of claim 1 , wherein at least one rule in the dynamic ruleset defines at least one of:
arranging records and a corresponding property contiguously; or
placing property data frequently used in a context of the entity in close proximity to the entity.

9. The system of claim 1 , wherein determining the number of records for storing the entity and the property includes identifying memory requirements for types of nodes that represent the entity.

10. The system of claim 1 , wherein the method further comprises:
after allocating the contiguous block of records, writing at least one of the entity or the property to the contiguous block of records.

11. The system of claim 1 , wherein allocating the contiguous block of records for the first memory location corresponds to allocating the contiguous block of records for the first memory location adjacent to the second memory location.

12. A method comprising:
receiving a write request to write data to a graph database, the write request including an entity and a property;
accessing a dynamic ruleset associated with the write request, wherein the dynamic ruleset optimizes record placement in the graph database and is based on a statistical access pattern associated with at least one of a node or an edge in the graph database, the node or the edge relating to the entity or the property;
based on the dynamic ruleset, determining a number of records for storing the entity and the property in the graph database;
determining a first memory location for at least one of the entity or the property; and
allocating, for the number of records, a contiguous block of records for the first memory location such that the first memory location is located proximate to a second memory location for the node or the edge.

13. The method of claim 12 , further comprising:
identifying the entity is marked as dirty in the graph database; and
in response to identifying the entity is marked as dirty, initiating a defragmentation process.

14. The method of claim 13 , wherein identifying the entity is marked as dirty comprises identifying a dirty flag marking the entity, the dirty flag indicating that one or more rules of the dynamic ruleset have been violated.

15. The method of claim 13 , wherein identifying the entity is marked as dirty comprises adding the entity to a defragmentation queue, the defragmentation process being initiated when a number of entities in the defragmentation queue exceeds a threshold value.

16. The method of claim 13 , wherein identifying the entity is marked as dirty comprises:
identifying, in the graph database, two or more records associated with the entity; and
marking the two or more records as dirty.

17. The method of claim 12 , further comprising:
receiving a read request associated with the entity; and
in response to the read request, traversing at least one of a node or an edge associated with the entity in the graph database.

18. The method of claim 17 , wherein traversing the at least one of the node or the edge identifies one or more memory records violating one or more record placement rules.

19. The method of claim 12 , further comprising:
determining to execute a defragmentation process based on at least one of:
detecting data deletion in one or more records associated with the graph database;
detecting expiration of a periodic time period for defragmentation; or
detecting an addition of one or more records associated with the graph database.

20. A device comprising:
a processor; and
memory coupled to the processor, the memory comprising computer executable instructions that, when executed by the processor, performs a method comprising:
receiving a write request to write data to a graph database, the write request including an entity and a property;
accessing a dynamic ruleset associated with the write request, wherein the dynamic ruleset optimizes record placement in the graph database and is based on a statistical access pattern associated with at least one of a node or an edge in the graph database, the node or the edge relating to the entity or the property;
based on the dynamic ruleset, determining a number of records for storing the entity and the property in the graph database;
determining a first memory location for at least one of the entity or the property; and
allocating, for the number of records, a contiguous block of records for the first memory location such that the first memory location is located proximate to a second memory location for the node or the edge.

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Kvalnes Åge
• Karlberg Jan-Ove
• Kreutzer Tor
• Johansen Amund
• Valvåg Steffen

Classifications

• G06F12/0653 Primary

  with centralised address assignment · CPC title

• G06F16/288

  Entity relationship models · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F40/205 Primary

  Parsing · CPC title

• G06F16/24553

  of query operations · CPC title