# US 10,372,605 B2 · Generational garbage collector for trees under multi-version concurrency control > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,605 B2 - Document ID: US10372605B2 - Status: Granted - Kind: B2 - Application number: 15/637,080 - Filed: 2017-06-29 - Published: 2018-06-28 - Granted: 2019-08-06 - Earliest claimed: 2016-12-27 - Assignees: EMC IP Holding Company LLC - Applicants: EMC IP Holding Company LLC - Inventors: Mikhail Danilov; Konstantin Buinov; Mikhail Malygin; Kirill Gusakov; Vladimir Prikhodko - Web page: https://patentgrep.com/patent/US10372605B2 ## CPC - G06F 12/0276: {Generational garbage collection} - G06F 3/06: Digital input from, or digital output to, record carriers {, e.g. RAID, emulated record carriers or networked record carriers} - G06F 3/0608: {Saving storage space on storage systems} - G06F 3/064: {Management of blocks} - G06F 3/0673: {Single storage device} - G06F 16/2246: {Trees, e.g. B+trees} - G06F 2212/1041: Resource optimization - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 3) The system of claim 3, wherein the old chunk capacity efficiency utilization threshold is higher than the young chunk capacity efficiency utilization threshold. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) The system of claim 1, wherein the frozen trees are only scanned once. ### Claim 7 (depends on 1) The system of claim 1, wherein the young elements are elements that have a shorter lifetime than the immortal elements. ### Claim 8 (depends on 1) The system of claim 1, wherein the old elements are elements that have existed longer than the young elements. ### Claim 9 (depends on 1) 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. ### Claim 10 (depends on 1) 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. ### Claim 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. ### Claim 12 (depends on 11) 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. ### Claim 13 (depends on 11) 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. ### Claim 14 (depends on 13) The method of claim 13, wherein the old chunk capacity efficiency utilization threshold is higher than the young chunk capacity efficiency utilization threshold. ### Claim 15 (depends on 14) 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. ### Claim 16 (depends on 11) The method of claim 11, wherein the frozen trees are only scanned once. ### Claim 17 (depends on 11) The method of claim 11, wherein the young elements are elements that have a shorter lifetime than the immortal elements. ### Claim 18 (depends on 11) The method of claim 11, wherein the old elements are elements that have existed longer than the young elements. ### Claim 19 (depends on 11) 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. ### Claim 20 (depends on 11) 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. ### Claim 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 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.