Generational garbage collector for trees under multi-version concurrency control

Patent metadata

Field	Value
Publication number	US-10372605-B2
Application number	US-201715637080-A
Country	US
Kind code	B2
Filing date	Jun 29, 2017
Priority date	Dec 27, 2016
Publication date	Aug 6, 2019
Grant date	Aug 6, 2019

Abstract

Method of implementing generational garbage collection for trees under MVCC starts by detecting live objects in trees. Trees include normal trees and frozen trees. Poorly-filled young chunks and poorly-filled old chunks of hard-drive memory are identified. Hard-drive memory includes young chunks storing young elements, old chunks storing old elements, and immortal chunks storing immortal elements. One or more old chunks are opened for writes and elements from poorly-filled young chunks and old chunks are copied to one or more opened old chunks. Elements above elements from poorly-filled young chunks and old chunks in the normal trees are updated and stored in the young chunks. One or more immortal chunks are opened for writes and tree leaves of frozen trees from young chunks and from old chunks are copied to one or more opened immortal chunks. All nodes of frozen trees are updated and stored in immortal chunks.

First claim

What is claimed is:

1. A system for implementing generational garbage collection for a plurality of trees under multi-version concurrency control, comprising:
a hard-drive memory including a plurality chunks that are fixed-sized blocks of the hard-drive memory,
wherein the chunks include young chunks that store young elements, old chunks that store old elements, and immortal chunks that store immortal elements;

a processor coupled to the hard-drive memory;
a generational garbage collector coupled to the processor, the generational garbage collector including a normal tree scanner and a frozen tree scanner,
wherein the plurality of trees include a plurality of normal trees and a plurality of frozen trees,
the normal tree scanner
to detect live objects in the plurality of normal trees, wherein objects include tree nodes and tree leaves and are alive when the objects are reachable from a tree root of at least one tree, wherein tree elements include objects and tree roots,
to identify poorly-filled young chunks of the hard-drive memory and poorly-filled old chunks of the hard-drive memory,
to open for writes one or more old chunks,
to copy elements from the poorly-filled young chunks and the poorly-filled old chunks to the one or more opened old chunks,
to update elements above the elements from the poorly-filled young chunks and the poorly-filled old chunks in the normal trees and to store the updated elements in the young chunks, and

the frozen tree scanner
to open for writes one or more immortal chunks,
to copy the tree leaves of the frozen trees from the young chunks and from the old chunks to the one or more opened immortal chunks, and
to update and to store all nodes of the frozen trees in the immortal chunks.

2. The system of claim 1 , wherein the live objects are detected via tracing, wherein for each tree, starting at the tree root, depth-first traversal is used to detect objects currently reachable.

3. The system of claim 1 , wherein the normal tree scanner identifying poorly-filled young chunks and poorly-filled old chunks includes:
determining a capacity efficiency of the young chunks and a capacity efficiency of the old chunks, and
marking each of the young chunks having the capacity efficiency lower than a young chunk capacity efficiency utilization threshold as one of the poorly-filled young chunks, and marking each of the old chunks having the capacity efficiency lower than an old chunk capacity efficiency utilization threshold as one of the poorly-filled old chunks.

4. The system of claim 3 , wherein the old chunk capacity efficiency utilization threshold is higher than the young chunk capacity efficiency utilization threshold.

5. The system of claim 4 , wherein the old chunk capacity efficiency utilization threshold is 50% of a chunk size and young chunk capacity efficiency utilization threshold is 25% of the chunk size.

6. The system of claim 1 , wherein the frozen trees are only scanned once.

7. The system of claim 1 , wherein the young elements are elements that have a shorter lifetime than the immortal elements.

8. The system of claim 1 , wherein the old elements are elements that have existed longer than the young elements.

9. The system of claim 1 , wherein the frozen trees are trees that are never to be modified, wherein the lifetime of the frozen tree is unlimited.

10. The system of claim 1 , wherein during normal execution, only the young chunks are open for writes, wherein all new tree leaves and tree nodes are young elements stored to young chunks.

11. A method of implementing generational garbage collection for a plurality of trees under multi-version concurrency control, comprising:
detecting live objects in a plurality of normal trees,
wherein the plurality of trees include the plurality of normal trees and a plurality of frozen trees,
wherein objects include tree nodes and tree leaves and are alive when the objects are reachable from a tree root of at least one tree, wherein tree elements include objects and tree roots;

identifying poorly-filled young chunks of hard-drive memory and poorly-filled old chunks of the hard-drive memory,
wherein the hard-drive memory includes a plurality chunks that are fixed-sized blocks of the hard-drive memory,
wherein the chunks include young chunks that store young elements, old chunks that store old elements, and immortal chunks that store immortal elements;

opening for writes one or more old chunks;
copying elements from the poorly-filled young chunks and the poorly-filled old chunks to the one or more opened old chunks;
updating elements above the elements from the poorly-filled young chunks and the poorly-filled old chunks in the normal trees and storing the updated elements in the young chunks;
opening for writes one or more immortal chunks;
copying the tree leaves of the frozen trees from the young chunks and from the old chunks to the one or more opened immortal chunks; and
updating and storing all nodes of the frozen trees in the immortal chunks.

12. The method of claim 11 , wherein the live objects are detected via tracing, wherein for each tree, starting at the tree root, depth-first traversal is used to detect objects currently reachable.

13. The method of claim 11 , wherein identifying poorly-filled young chunks and poorly-filled old chunks includes:
determining a capacity efficiency of the young chunks and a capacity efficiency of the old chunks, and
marking each of the young chunks having the capacity efficiency lower than a young chunk capacity efficiency utilization threshold as one of the poorly-filled young chunks, and marking each of the old chunks having the capacity efficiency lower than an old chunk capacity efficiency utilization threshold as one of the poorly-filled old chunks.

14. The method of claim 13 , wherein the old chunk capacity efficiency utilization threshold is higher than the young chunk capacity efficiency utilization threshold.

15. The method of claim 14 , wherein the old chunk capacity efficiency utilization threshold is 50% of a chunk size and young chunk capacity efficiency utilization threshold is 25% of the chunk size.

16. The method of claim 11 , wherein the frozen trees are only scanned once.

17. The method of claim 11 , wherein the young elements are elements that have a shorter lifetime than the immortal elements.

18. The method of claim 11 , wherein the old elements are elements that have existed longer than the young elements.

19. The method of claim 11 , wherein the frozen trees are trees that are never to be modified, wherein the lifetime of the frozen tree is unlimited.

20. The method of claim 11 , wherein during normal execution, only the young chunks are open for writes, wherein all new tree leaves and tree nodes are young elements stored to young chunks.

21. A computer-readable medium having stored thereon instructions, when executed by a processor, causes the processor to perform a method of implementing generational garbage collection for a plurality of trees under multi-version concurrency control, comprising:
detecting live objects in a plurality of normal trees,
wherein the plurality of trees include the plurality of normal trees and a plurality of frozen trees,
wherein objects include tree nodes and tree leaves and are alive when the objects are reachable from a tree root of at least one tree, wherein tree elements include objects and tree roots;

identifying poorly-filled young chunks of hard-drive memory and poorly-filled o

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Buinov Konstantin
• Malygin Mikhail
• Gusakov Kirill
• Prikhodko Vladimir

Classifications

• G06F3/06

  Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers} · CPC title

• G06F12/0276 Primary

  Generational garbage collection · CPC title

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F2212/1041

  Resource optimization · CPC title

• G06F3/0673

  Single storage device · CPC title