Garbage collection of preloaded time-based graph data

Patent metadata

Field	Value
Publication number	US-11269768-B2
Application number	US-201916720838-A
Country	US
Kind code	B2
Filing date	Dec 19, 2019
Priority date	Dec 21, 2018
Publication date	Mar 8, 2022
Grant date	Mar 8, 2022

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 that a content selection graph associated with a first timepoint and preloaded into a memory is no longer in use based on determining that another content selection graph associated with a second timepoint and preloaded into the memory is in use, wherein the second timepoint is more current than the first timepoint; and
garbage collecting the content selection graph from the memory.

2. The method of claim 1 , further comprising garbage collecting an orphaned graph from the memory.

3. The method of claim 2 , wherein the garbage collecting the orphaned graph from the memory comprises determining that the orphaned graph is not mapped to a timepoint and is not an outstanding graph that is not yet built.

4. The method of claim 2 , wherein the garbage collecting the orphaned graph from the memory comprises determining that the orphaned graph is not mapped to a timepoint and is not an outstanding graph that is not yet validated.

5. The method of claim 1 , further comprising garbage collecting an unused entity key from the memory.

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

7. The method of claim 5 , further comprising garbage collecting an unused entity blob corresponding to the unused entity key from the memory.

8. The method of claim 1 , further comprising garbage collecting a build data structure that is no longer in use from the memory.

9. The method of claim 1 , further comprising garbage collecting a validation data structure that is no longer in use from the memory.

10. The method of claim 1 , further comprising garbage collecting a graph identifier-to-timepoint mapping that is no longer in use from the memory.

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

12. The method of claim 1 , wherein the garbage collecting the preloaded 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.

13. The method of claim 1 , wherein the content selection graph is associated with streaming video content.

14. 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:
evaluating information associated with an in-memory data structure, comprising determining old graphs in the in-memory data structure based on graph identifier to time-based mappings, determining graphs that are outstanding with respect to being built or validated, and determining orphaned graphs that have been replaced with replacement graphs;
deleting the old graphs; and
deleting the orphaned graphs.

15. The system of claim 14 , wherein the in-memory data structure comprises a cache, and wherein the operations further comprise, obtaining cache keys, obtaining referenced entity keys, determining orphaned entity keys, and deleting the orphaned entity keys.

16. The system of claim 14 , wherein the operations further comprise, obtaining cache keys, obtaining referenced entity keys, and deleting data blobs corresponding to the orphaned entity keys.

17. The system of claim 14 , wherein the in-memory data structure comprises a Redis cache.

18. A non-transitory machine-readable medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations, the operations comprising:
maintaining content selection graphs in an in-memory data structure;
determining expired content selection graphs;
determining orphaned content selection graphs that have been replaced; and
garbage collecting the expired content selection graphs and the orphaned content selection graphs.

19. The non-transitory machine-readable medium of claim 18 , wherein the operations further comprise determining orphaned entity keys, and deleting the orphaned entity keys and data blobs corresponding to the orphaned entity keys.

20. The non-transitory machine-readable medium of claim 18 , wherein the operations further comprise, deleting expired mappings from a set of mappings that relate content selection graphs to start times.

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

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/602

  Details relating to cache prefetching · CPC title

• G06F16/9024

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

• G06F2212/464

  Multimedia object, e.g. image, video · CPC title