os/bluestore: add BtreeAllocator by tchaikov · Pull Request #41828 · ceph/ceph

tchaikov · 2021-06-12T13:26:03Z

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 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 the rebalance of 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.

Checklist

References tracker ticket
Updates documentation if necessary
Includes tests for new functionality or reproducer for bug

Show available Jenkins commands

jenkins retest this please
jenkins test classic perf
jenkins test crimson perf
jenkins test signed
jenkins test make check
jenkins test make check arm64
jenkins test submodules
jenkins test dashboard
jenkins test api
jenkins test docs
jenkins render docs
jenkins test ceph-volume all
jenkins test ceph-volume tox

tchaikov · 2021-06-14T09:50:47Z

per the btree.stats which is not exposed by its wrapper,

average_bytes_per_value: 22.7556: each extent takes 22.75 bytes.
overhead: 40: each b-tree node (which contains up to 256 values) has 40 bytes overhead.

this is much lower than that of AVL tree, where each node contains a single extent, and it takes 80 bytes. please note, each value (extent) only uses 16 bytes for a uint64_t start and a uint64_t end.

tchaikov · 2021-06-14T10:11:44Z

test	AVL	btree
test_alloc_bench	15358 ms	16719 ms
test_alloc_bench_90_300	37853 ms	46812 ms
test_alloc_bench_50_300	37880 ms	43598 ms
test_alloc_bench_10_300	37824	40372 ms
test_alloc_bench_seq/2	577766 ms	827261 ms

tchaikov · 2021-06-14T14:11:01Z

[ RUN      ] Queue.SpawnAsyncRequest
../src/test/rgw/test_rgw_dmclock_scheduler.cc:425: Failure
Value of: context.stopped()
  Actual: false
Expected: true
[  FAILED  ] Queue.SpawnAsyncRequest (0 ms)

https://tracker.ceph.com/issues/42788

tchaikov · 2021-06-14T14:11:27Z

jenkins test make check

tchaikov · 2021-06-15T12:38:11Z

jenkins test make check

aclamk · 2021-06-17T08:34:20Z

I added a memory tracking to aging test: aclamk@0a2279e

Summary:

allocator	fragmented allocs	#frags	free_score	time	mempool	tcmalloc
avl	0.727767%	2.00015	0.756594	15590.9ms	3281490	3283234
bitmap	55.3145%	2.60743	0.583628	4836.3ms	18708994	18710322
btree	0.674791%	2.00038	0.756787	8716.12ms	1844074	1845818
stupid	1.40833%	2.04938	0.749268	29840ms	893859	895612

btree really looks impressive, Kefu @tchaikov !

I guess it really should add btree to mempool accounting.

aclamk

Excellent reduction of used memory!
Must move btree to mempool::bluestore_alloc.

tchaikov · 2021-06-17T09:18:34Z

@aclamk Adam, thank you for profiling the BtreeAllocator! i reformatted the test result in your comment as a table. hope it's fine by you =)

the btree block / node is more of an implementation details which are not exposed as part of its public interface. so i thought it'd be difficult to inject the MEMPOOL_CLASS_HELPERS macro and to define MEMPOOL_DEFINE_OBJECT_FACTORY() in an appropriate way. but it seems we can just pass mempool::bluestore_alloc::pool_allocator<T> to the btree container templates as their allocator template parameter. just updated with this change.

could you take another look?

tchaikov · 2021-06-18T01:15:30Z

@aclamk i reran the aging test with your patch and updated the table in your comment.

tchaikov · 2021-06-18T01:15:30Z

rebased against master.

tchaikov · 2021-06-18T10:14:43Z

jenkins test make check

tchaikov · 2021-06-18T15:48:23Z

jenkins test make check

tchaikov · 2021-06-19T13:04:51Z

i don't think the failures were related to this change.

tchaikov · 2021-06-19T13:05:48Z

@aclamk hi Adam, is there anything else i can do to improve this changeset?

aclamk

This is good work.
In my opinion btree allocator should replace avl in any case.

There should be done some work on replacing avl->btree for 'hybrid' strategy. If so, new thresholds for switching from interval to bitmap mode must be calculated.

tchaikov · 2021-06-24T11:11:35Z

@aclamk yeah, will port the hybrid strategy to btree allocator later on.

BtreeAllocator was added in the commit ceph#41828. Its performance has advantages in some scenarios, but we cannot configure to use Btree mode. Signed-off-by: tan changzhi <544463199@qq.com>

BtreeAllocator was added in the commit ceph#41828. Its performance has advantages in some scenarios, but we cannot configure to use Btree mode. Fixes: https://tracker.ceph.com/issues/65678 Signed-off-by: tan changzhi <544463199@qq.com>

BtreeAllocator was added in the commit ceph#41828. Its performance has advantages in some scenarios, but we cannot configure to use btree mode. Fixes: https://tracker.ceph.com/issues/65678 Signed-off-by: tan changzhi <544463199@qq.com>

BtreeAllocator was added in the commit ceph/ceph#41828. Its performance has advantages in some scenarios, but we cannot configure to use btree mode. Fixes: https://tracker.ceph.com/issues/65678 Signed-off-by: tan changzhi <544463199@qq.com>

BtreeAllocator was added in the commit ceph#41828. Its performance has advantages in some scenarios, but we cannot configure to use btree mode. Fixes: https://tracker.ceph.com/issues/65678 Signed-off-by: tan changzhi <544463199@qq.com> (cherry picked from commit 8d47912)

tchaikov requested review from aclamk and ifed01 June 12, 2021 13:26

github-actions bot added bluestore build/ops core tests labels Jun 12, 2021

tchaikov force-pushed the wip-btree-alloc branch from 3e92640 to 03f973b Compare June 12, 2021 13:29

tchaikov mentioned this pull request Jun 12, 2021

os/bluestore/AvlAllocator: introduce bluestore_avl_alloc_ff_max_* options #41615

Merged

3 tasks

tchaikov added the performance label Jun 12, 2021

tchaikov force-pushed the wip-btree-alloc branch 3 times, most recently from 7fa5d4d to 05a0b3a Compare June 13, 2021 02:04

tchaikov requested a review from a team as a code owner June 13, 2021 02:04

github-actions bot added the crimson label Jun 13, 2021

tchaikov force-pushed the wip-btree-alloc branch 3 times, most recently from a99f9bd to 8877a2c Compare June 14, 2021 09:44

tchaikov force-pushed the wip-btree-alloc branch 2 times, most recently from 19465bc to 03a396a Compare June 14, 2021 10:09

tchaikov force-pushed the wip-btree-alloc branch from aa66020 to 13195a1 Compare June 14, 2021 13:22

tchaikov force-pushed the wip-btree-alloc branch from 13195a1 to 3b154df Compare June 14, 2021 16:40

aclamk requested changes Jun 17, 2021

View reviewed changes

tchaikov force-pushed the wip-btree-alloc branch from 3b154df to 2d3eaac Compare June 17, 2021 09:18

tchaikov force-pushed the wip-btree-alloc branch from 2d3eaac to 88ce819 Compare June 18, 2021 01:13

tchaikov added the wip-kefu-testing label Jun 18, 2021

tchaikov added the wip-kefu-testing2 label Jun 19, 2021

tchaikov added needs-review and removed wip-kefu-testing wip-kefu-testing2 labels Jun 19, 2021

aclamk self-requested a review June 24, 2021 09:42

aclamk approved these changes Jun 24, 2021

View reviewed changes

tchaikov merged commit 827c663 into ceph:master Jun 24, 2021

tchaikov deleted the wip-btree-alloc branch June 24, 2021 11:11

NUABO mentioned this pull request Apr 29, 2024

os/bluestore: allow use BtreeAllocator #57120

Merged

14 tasks

Conversation

tchaikov commented Jun 12, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Checklist

Uh oh!

tchaikov commented Jun 14, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tchaikov commented Jun 14, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tchaikov commented Jun 14, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tchaikov commented Jun 14, 2021

Uh oh!

tchaikov commented Jun 15, 2021

Uh oh!

aclamk commented Jun 17, 2021 • edited by tchaikov Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

aclamk left a comment

Choose a reason for hiding this comment

Uh oh!

tchaikov commented Jun 17, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

tchaikov commented Jun 18, 2021

Uh oh!

tchaikov commented Jun 18, 2021

Uh oh!

tchaikov commented Jun 18, 2021

Uh oh!

tchaikov commented Jun 18, 2021

Uh oh!

tchaikov commented Jun 19, 2021

Uh oh!

tchaikov commented Jun 19, 2021

Uh oh!

aclamk left a comment

Choose a reason for hiding this comment

Uh oh!

tchaikov commented Jun 24, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

tchaikov commented Jun 12, 2021 •

edited

Loading

tchaikov commented Jun 14, 2021 •

edited

Loading

tchaikov commented Jun 14, 2021 •

edited

Loading

tchaikov commented Jun 14, 2021 •

edited

Loading

aclamk commented Jun 17, 2021 •

edited by tchaikov

Loading

tchaikov commented Jun 17, 2021 •

edited

Loading