Technology

Explained: Garbage Collection

19/07/2021 by Tim Niggemeier

Garbage Collection

Unlike hard drives or NOR flash, NAND flash does not have a fixed mapping of logical memory addresses to physical memory addresses. The assignment takes place via mapping tables, which are managed by the firmware of the storage medium. The flash memory itself consists of several thousand blocks, and these in turn are made up of “pages”. A block is the smallest unit that can be erased in one operation. A page is the smallest unit that can be programmed in one operation. This split means that outdated pages cannot easily be used for new data if there is still valid data in the same block. The clear up process of being able to release entire blocks is called “garbage collection”. But how does it work?  

If the storage medium is written, the pages of the free blocks are filled sequentially. It does not matter which logical addresses (LBA) the write accesses are made to. The relationship between LBAs and block or page number is logged in the mapping tables, which are also stored in flash blocks. Let’s take an example: For simplicity’s sake, it is assumed that the whole flash consists of only four blocks of three pages each, and each page contains only one LBA. Furthermore, the internal management data (mapping tables) are not shown. In this example, the storage medium has already been partially filled with a boot image, so that four pages are already occupied:

Figure 1: Four pages written

The host now writes to the following LBA: 7, 4, 7, 4, 7. The first and second entries of LBA 7 and the first entry of LBA 4 are now obsolete (crossed out), as they have already been replaced by newer data:

Figure 2: After write access to the LBA 7, 4, 7, 4, 7

However, since only whole blocks can be erased, these pages can not be released and programmed again immediately. Now only a single free block is available, which now requires the garbage collector to run before the storage medium can accept further data. The valid pages of block 1 and block 2 are copied to block 3 by the garbage collector:

Figure 3: Copying of still valid LBAs into a new block

This releases blocks 1 and 2 and then erases them. Finally, there are again two free blocks available:

Figure 4: Deletion of now free blocks

Garbage Collection Efficiency

The garbage collector usually runs in the background. If the number of free blocks falls below a threshold value, it becomes active as soon as there are no more read and write accesses. He can also be interrupted again at any time. However, if the storage medium is under continuous load, the garbage collector will be activated if the number of free blocks reaches a critical value, as in the example shown above. Early activation of the garbage collector in the background ensures that there are usually enough free blocks available to store even larger amounts of data without reducing the transfer speed due to the running garbage collector. If the garbage collector is active, it searches for the blocks with the highest “garbage collection efficiency” (=E). This indicates how flash friendly stale data can be released from this block and is calculated by the ratio of numbers of outdated pages per block divided by the number of all pages per block.

If E = 1, then no pages need to be copied and the block can be erased directly. If E < 1, pages must be copied before the block is erased. This leads to a greater wearout of the flash. Blocks with descending E are released until enough free blocks are available again.

Overprovisioning

When setting the threshold for free blocks, there must always be a compromise between high write speed and greater wear-out. This problem can be alleviated by increasing the so called “overprovisioning”. This reduces the visible capacity of the storage medium and the ratio of visible capacity to physical capacity. It results in increasing of the average garbage collection efficiency and decreasing wear-out.

The figure below shows the usage of physically available memory. This is a purely quantitative distribution – the three groups (“user data”, “management data” and “overprovisioning”) are not allocated to fixed memory areas. The physical memory forms a pool from which each group can obtain blocks.

Figure 5: Overprovisioning (not to scale)

Most of it is available for payload, a small part is needed for the internal management data (e.g. mapping tables), and a share configurable by the manufacturer of the storage medium is over-provisioning. The overprovisioning cannot be arbitrarily small, since a minimum of free memory must be available to the garbage collector. Applications that do not sequentially write to the medium but mainly execute random write access benefit from a large overprovisioning. Furthermore, reserve blocks are also obtained from this memory if, during the lifetime, flash blocks have to be replaced because of increased bit error numbers (“grown bad blocks”). swissbit