]> git.apps.os.sepia.ceph.com Git - ceph-ci.git/commit
os/bluestore: add BtreeAllocator
authorKefu Chai <kchai@redhat.com>
Sat, 12 Jun 2021 12:58:36 +0000 (20:58 +0800)
committerKefu Chai <kchai@redhat.com>
Fri, 18 Jun 2021 01:13:12 +0000 (09:13 +0800)
commitacc04d103f77fd6b00ecdd6b6a94c41b39114ccc
tree02745e88846334a22d38cf2d60aa102a75477ac4
parent021e7389a3af6d66693f90b0c329f53b8ed5a56f
os/bluestore: add BtreeAllocator

because each AVL tree node needs to keep track of its children, the
overhead of each extent in AvlAllocator is relatively higher than that
of bitmap allocator, per node sizes 80 bytes, per per mempool stats provided
by unittest_alloc_bench. while btree has lower overhead, as it keeps multiple
entries in each node / block, the node size of abseil's btree implementation
defaults to 256, so each node is able to contain up to 256 values. this means
we have lower overhead than the binary-trees like AVL and red-black tree.

but because the overhead of rebalance the btree is higher than that of
binary tree, its takes more CPU cycles when performing alloc-release
than its AVL version. but its upside is that its memory layout is
more compact, under some use case, it might be a better alternative
than AvlAllocator.

Signed-off-by: Kefu Chai <kchai@redhat.com>
src/crimson/os/alienstore/CMakeLists.txt
src/os/CMakeLists.txt
src/os/bluestore/Allocator.cc
src/os/bluestore/BtreeAllocator.cc [new file with mode: 0644]
src/os/bluestore/BtreeAllocator.h [new file with mode: 0644]
src/test/objectstore/Allocator_aging_fragmentation.cc
src/test/objectstore/Allocator_bench.cc