On Wed, Dec 04, 2013 at 10:17:39PM +0000, Filipe David Borba Manana wrote:
> Currently when finding the leaf to insert a key into a btree, if the
> leaf doesn't have enough space to store the item we attempt to move
> off some items from our leaf to its right neighbor leaf, and if this
> fails to create enough free space in our leaf, we try to move off more
> items to the left neighbor leaf as well.
>
> When trying to move off items to the right neighbor leaf, if it has
> enough room to store the new key but not not enough room to move off
> at least one item from our target leaf, __push_leaf_right returns 1 and
> we have to attempt to move items to the left neighbor (push_leaf_left
> function) without touching the right neighbor leaf.
> For the case where the right leaf has enough room to store at least 1
> item from our leaf, we end up modifying (and dirtying) both our leaf
> and the right leaf. This is non-optimal for the case where the new key
> is greater than any key in our target leaf because it can be inserted at
> slot 0 of the right neighbor leaf and we don't need to touch our leaf
> at all nor to attempt to move off items to the left neighbor leaf.
>
> Therefore this change just selects the right neighbor leaf as our new
> target leaf if it has enough room for the new key without modifying our
> initial target leaf - we do this only if the new key is higher than any
> key in the initial target leaf.
>
> While running the following test, push_leaf_right was called by split_leaf
> 4802 times. Out of those 4802 calls, for 2571 calls (53.5%) we hit this
> special case (right leaf has enough room and new key is higher than any key
> in the initial target leaf).
>
> Test:
>
> sysbench --test=fileio --file-num=512 --file-total-size=5G \
> --file-test-mode=[seqwr|rndwr] --num-threads=512 --file-block-size=8192 \
> --max-requests=100000 --file-io-mode=sync [prepare|run]
>
> Results:
>
> sequential writes
>
> Throughput before this change: 65.71Mb/sec (average of 10 runs)
> Throughput after this change: 66.58Mb/sec (average of 10 runs)
>
> random writes
>
> Throughput before this change: 10.75Mb/sec (average of 10 runs)
> Throughput after this change: 11.56Mb/sec (average of 10 runs)
Reviewed-by: Liu Bo <bo.li.liu@xxxxxxxxxx>
-liubo
>
> Signed-off-by: Filipe David Borba Manana <fdmanana@xxxxxxxxx>
> ---
> fs/btrfs/ctree.c | 13 +++++++++++++
> 1 file changed, 13 insertions(+)
>
> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> index 11f9a18..a57507a 100644
> --- a/fs/btrfs/ctree.c
> +++ b/fs/btrfs/ctree.c
> @@ -3613,6 +3613,19 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
> if (left_nritems == 0)
> goto out_unlock;
>
> + if (path->slots[0] == left_nritems && !empty) {
> + /* Key greater than all keys in the leaf, right neighbor has
> + * enough room for it and we're not emptying our leaf to delete
> + * it, therefore use right neighbor to insert the new item and
> + * no need to touch/dirty our left leaft. */
> + btrfs_tree_unlock(left);
> + free_extent_buffer(left);
> + path->nodes[0] = right;
> + path->slots[0] = 0;
> + path->slots[1]++;
> + return 0;
> + }
> +
> return __push_leaf_right(trans, root, path, min_data_size, empty,
> right, free_space, left_nritems, min_slot);
> out_unlock:
> --
> 1.7.9.5
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@xxxxxxxxxxxxxxx
> More majordomo info at http://vger.kernel.org/majordomo-info.html
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
