Garbage collection of preloaded time-based graph data

Patent metadata

Field	Value
Publication number	US-11720488-B2
Application number	US-202217648555-A
Country	US
Kind code	B2
Filing date	Jan 21, 2022
Priority date	Dec 21, 2018
Publication date	Aug 8, 2023
Grant date	Aug 8, 2023

Abstract

The described technology is generally directed towards garbage collecting content selection graphs and related data from in an in-memory content selection graph data store. When a set of content selection graphs expire, a more current content selection graph set becomes active, and the storage space (e.g., in a Redis cache) used by the expired content selection graphs is reclaimed via garbage collection. Some graphs can be replaced before use, referred to as orphaned graphs, and the storage space for any such orphaned graphs is also reclaimed during garbage collection. Also garbage collected is storage space including related data structures used to generate and validate graphs.

First claim

What is claimed is:

1. A method comprising:
determining, by a system comprising a processor, that a content selection graph preloaded into a memory is no longer in use;
determining that an orphaned graph in the memory is not mapped to a timepoint and is not an outstanding graph that is not yet built or is not yet validated; and
garbage collecting, by the system, the content selection graph and the orphaned graph from the memory.

2. The method of claim 1 , wherein the garbage collecting the content selection graph further comprises garbage collecting an unused entity key from the memory.

3. The method of claim 2 , further comprising determining, by the system, that the unused entity key is unused based on evaluating a set of referenced entity keys against a full set of entity keys scanned from the memory.

4. The method of claim 2 , wherein the garbage collecting further comprises garbage collecting an unused entity blob corresponding to the unused entity key from the memory.

5. The method of claim 1 , wherein the garbage collecting the content selection graph further comprises garbage collecting a build data structure that is no longer in use from the memory.

6. The method of claim 1 , wherein the garbage collecting the content selection graph further comprises garbage collecting a validation data structure that is no longer in use from the memory.

7. The method of claim 1 , wherein the garbage collecting the content selection graph further comprises garbage collecting a graph identifier-to-timepoint mapping that is no longer in use from the memory.

8. The method of claim 1 , wherein the garbage collecting the content selection graph from the memory comprises scanning keys in the memory.

9. The method of claim 1 , wherein the garbage collecting the content selection graph from the memory comprises setting a write mutex on the memory during the garbage collecting, and unlocking the write mutex after the garbage collecting.

10. A system, comprising:
a processor; and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
in response to determining that a content selection graph preloaded into the memory is no longer in use, garbage collecting the content selection graph from the memory, wherein the garbage collecting the content selection graph comprises setting a write mutex on the memory during the garbage collecting, and unlocking the write mutex after the garbage collecting.

11. The system of claim 10 , wherein the garbage collecting further comprises garbage collecting an unused entity key from the memory.

12. The system of claim 11 , wherein the operations further comprise determining that the unused entity key is unused based on evaluating a set of referenced entity keys against a full set of entity keys scanned from the memory.

13. The system of claim 10 , wherein the garbage collecting the content selection graph further comprises garbage collecting a build data structure that is no longer in use from the memory.

14. The system of claim 10 , wherein the garbage collecting the content selection graph further comprises garbage collecting a validation data structure that is no longer in use from the memory.

15. The system of claim 10 , wherein the garbage collecting the content selection graph further comprises garbage collecting a graph identifier-to-timepoint mapping that is no longer in use from the memory.

16. The system of claim 10 , wherein the garbage collecting the content selection graph from the memory comprises scanning keys in the memory.

17. A non-transitory machine-readable medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations, the operations comprising:
in response to determining that a content selection graph preloaded into a memory is no longer in use, garbage collecting the content selection graph from the memory, wherein the garbage collecting the content selection graph comprises:
determining that an unused entity key in the memory is unused based on evaluating a set of referenced entity keys against a full set of entity keys scanned from the memory, and
garbage collecting the unused entity key from the memory.

18. The non-transitory machine-readable medium of claim 17 , wherein the garbage collecting the content selection graph from the memory comprises setting a write mutex on the memory during the garbage collecting, and unlocking the write mutex after the garbage collecting.

19. The non-transitory machine-readable medium of claim 17 , wherein the garbage collecting the content selection graph further comprises garbage collecting a build data structure that is no longer in use from the memory.

20. The non-transitory machine-readable medium of claim 17 , wherein the garbage collecting the content selection graph further comprises garbage collecting a validation data structure that is no longer in use from the memory.

Assignees

• Home Box Office Inc

Inventors

• Lutz Jonathan David
• Gay Allen Arthur
• Carney Dylan

Classifications

• G06F12/0253 Primary

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F12/0862

  with prefetch · CPC title

• G06F16/9024

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

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/602

  Details relating to cache prefetching · CPC title