• Omar Sandoval's avatar
    Btrfs: implement the free space B-tree · a5ed9182
    Omar Sandoval authored
    The free space cache has turned out to be a scalability bottleneck on
    large, busy filesystems. When the cache for a lot of block groups needs
    to be written out, we can get extremely long commit times; if this
    happens in the critical section, things are especially bad because we
    block new transactions from happening.
    
    The main problem with the free space cache is that it has to be written
    out in its entirety and is managed in an ad hoc fashion. Using a B-tree
    to store free space fixes this: updates can be done as needed and we get
    all of the benefits of using a B-tree: checksumming, RAID handling,
    well-understood behavior.
    
    With the free space tree, we get commit times that are about the same as
    the no cache case with load times slower than the free space cache case
    but still much faster than the no cache case. Free space is represented
    with extents until it becomes more space-efficient to use bitmaps,
    giving us similar space overhead to the free space cache.
    
    The operations on the free space tree are: adding and removing free
    space, handling the creation and deletion of block groups, and loading
    the free space for a block group. We can also create the free space tree
    by walking the extent tree and clear the free space tree.
    Signed-off-by: default avatarOmar Sandoval <osandov@fb.com>
    Signed-off-by: default avatarChris Mason <clm@fb.com>
    a5ed9182
free-space-tree.c 40 KB