Skip to contentSkip to conversation

A trial to improve btrfs b-tree node balancing for higher fill rates

PATCH Sun Yangkai 1 participant 1 message Oct 6, 2025 Btrfs file system

lore
Share & tools
lore
#0 lore raw

I want to share some thoughts on the b-tree node balancing strategy in btrfs. Please point me to any previous discussions if I missed them.

Things started at when I'm learning the btrfs on-disk format, and using btrfs ins tree to check trees on my fs. I found something like this (I don't recall the precise figure, so I'm going with ~n as a ballpark figure.):

level 0: ... // I don't care in this case
level 1: ~350 (...)
level 2: 2 (avg fanout: ~170) // Why cannot merged into one node??? level 3: 1 (avg fanout: 2) // Okay as the root node of the tree

(The fanout of the nodes can also be considered as its fill rate for the btree implementation in btrfs.) After further checking, the nodes on level 2 has ~180 items and ~160 items, while one node can contain up to 493 items. This made me confused since one node can easily contain all the items, and the tree will be one level lower. I wanted to find out why the two nodes are not merged. So I went through the source code and found something like this:

[...]
} else if (ins_len < 0 && btrfs_header_nritems(b) <

    BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 2) {
        if (*write_lock_level < level + 1) {
            *write_lock_level = level + 1;
            btrfs_release_path(p);
            return -EAGAIN;
        }
        reada_for_balance(p, level);
        ret = balance_level(trans, root, p, level);

[...]

It seems that when a node contains less than half items, btrfs will try to rebalance the tree. But obviously, it didn't work as expected, which led me to investigate the balance_level() function more deeply. And I found this:

[...]
if (btrfs_header_nritems(mid) >
BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
return 0;
[...]

Wait... So balance_level is called, do nothing and return 0 if the node fill rate is between 25% and 50% ??! I got more confused. So I went to check the git history. And things goes more clear(or not?).

The condition in the second code slice(I'll call it c2 for short) was introduced in commit bb8039515d7c1(Btrfs: merge on the way down during deletes), which also introduced the balance_level() function back in 2007 — the very early days of btrfs.

While the condition in the first code slice(I'll call it c1 for short) is introduced in 7b78c170dc4f538c(Btrfs: Only prep for btree deletion balances when nodes are mostly empty) later in 2009, to avoid unnecessary calls to balance_level, and some code prepare for the balance.

They were both BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4(25% for short) until cfbb9308463f6d(Btrfs: balance btree more often), in which we changed c1 to 50% as it is today.

So it's totally a mistake and we can just remove c2, and keep c1 as 50% or change it to 25% to keep the current behavior, right?

Actually, no. IMO neither 25% nor 50% will work well. I don't know the exact reason why Chris tried to balance btree more often in commit cfbb9308463f6d, but at least it suggests that 25% didn’t seem appropriate in his view. As the example I mentioned earlier in this email, some nodes that could be merged are not merged.

And I also found that the average fanout of the nodes falls somewhere between 250 and 290—less than 60% of their full capacity after conducting research on my own and my friends' devices. This is quite low in my opinion, as it implies that many nodes have a fanout below 260. As a result, we end up wasting roughly half of our disk space, I/O, memory, and cache just to store and read/write these underfilled nodes IIRC, which is fairly frustrating. Unfortunately, that’s the situation we’re dealing with at the moment.

Should we just change it to 50%? The answer is also no. Actually, the previous Chris's patch I mentioned tried to balance both node and leaf with fill rate under 50%. But neither of them comes to reality. Node, as I mentioned, is still 25%. And leaf, is changed to 1/3 in d717aa1d31c36cb because of ...

Quoted 3 lines

btrfs_split_leaf and btrfs_del_items can end up in a loop where one is constantly spliting a given leaf and the other is constantly merging it back with the adjacent nodes.

Oops... The system experiences thrashing during sequences of inserts and deletes, and therefore, 50% is not viable, right? Well, actually, it will not work with current balancing strategy, which always redistributes items from a underfilled node to its left sibling and borrows from its right sibling. Merging is archived by deleting the right sibling if it is empty.

But by introducing hysteresis, we can eliminate the loop entirely and work well with 50%. Additionally, this approach will promote more frequent b-tree balancing as originally intended in commit cfbb9308463f6d, leading to a higher average node fill rate. As a result, we can eliminate the various drawbacks associated with a low fill rate.

The core principle is to avoid merging nodes if the resulting node would be nearly full. However, we also aim to prevent leaving any node less than half full. To achieve this, we can attempt to borrow some items from its sibling nodes. Since we've checked that we cannot merge with the siblings, we know the siblings will have sufficient items for us to borrow from. So this will always work well.

I'm not an expert of b-trees, so I went to read some paper. If I understand the papers correctly, my idea fits the condition described in /Robust balancing in B-trees/. That means we can get sublinear rebalancing cost.

So I started to rewrite the balancing strategy. After some debugging and testing, the patch seems working well on my machine. And, the average fanout has increased from ~260 to ~350 over the following few days. \o/

Theoretically, a higher fill rate (or average fanout) improves both space utilization and performance. However, it may also lead to more frequent balancing operations. As a result, the overall performance impact of this patch across different workloads remains unclear. But I am personally optimistic about its potential.

When it comes to the leaf nodes, I've observed that some of them remain underfilled, containing only a small number of items. On my machine, leaf nodes with more than 14,000B of free space account for about 2% of the total. This situation is clearly suboptimal, and I'm considering whether a similar method could be applied to optimize rebalancing leaf nodes. However, since we are dealing with variable-length items and there is no upper bound on item size within the leaf nodes, pushing items between sibling nodes becomes more challenging, making the balancing process considerably more complex.

I would greatly appreciate your thoughts and feedback on this. Have others observed similar issues with node fill rates in their btrfs deployments? Are there edge cases or workloads where this balancing strategy might perform suboptimally that I haven't considered? I'm also glad to share anything I've learned about the node balancing strategy.

For those interested in testing, I've attached a preliminary patch. Please note it's not yet production-ready. I'm particularly interested in:

* Performance benchmarks across different workloads

* Reports on node fill rate in various usage scenarios

* Any regression reports or unexpected behavior

Regarding leaf node optimization, I'm wondering if anyone has investigated similar hysteresis-based or sibling-borrowing strategies specifically for leaf nodes.

Looking forward to a productive discussion on how we can collectively improve btrfs's b-tree efficiency.

Best regards,

Sun Yangkai

fs/btrfs/ctree.c +361 -422
index 74e6d7f3d266..232065935a85 100644
@@ -31,12 +31,34 @@ static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
 static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 		      const struct btrfs_key *ins_key, struct btrfs_path *path,
 		      int data_size, int extend);
-static int push_node_left(struct btrfs_trans_handle *trans,
-			  struct extent_buffer *dst,
-			  struct extent_buffer *src, int empty);
-static int balance_node_right(struct btrfs_trans_handle *trans,
-			      struct extent_buffer *dst_buf,
-			      struct extent_buffer *src_buf);
+static int node_balance_move_l(struct btrfs_trans_handle *trans,
+			       struct extent_buffer *l,
+			       struct extent_buffer *r,
+			       int dst_max);
+static int node_balance_move_r(struct btrfs_trans_handle *trans,
+			       struct extent_buffer *l,
+			       struct extent_buffer *r,
+			       int dst_max);
+
+/*
+ * Defines the high watermark threshold for node rebalancing.
+ * When a node's item count exceeds this value (currently 90% of capacity),
+ * it is considered too full and will not appear as node merge result.
+ */
+static int node_balance_himark(struct btrfs_fs_info *fs_info)
+{
+	return BTRFS_NODEPTRS_PER_BLOCK(fs_info) * 9 / 10;
+}
+
+/*
+ * Defines the low watermark threshold for node rebalancing.
+ * When a node's item count falls below this value (60% of capacity),
+ * it is considered too empty and items will not be taken from it during rebalancing.
+ */
+static int node_balance_lomark(struct btrfs_fs_info *fs_info)
+{
+	return BTRFS_NODEPTRS_PER_BLOCK(fs_info) * 6 / 10;
+}
 /*
  * The leaf data grows from end-to-front in the node.  this returns the address
  * of the start of the last item, which is the stop of the leaf data stack.
@@ -852,20 +874,92 @@ struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
 	return eb;
 }
 
+static void update_node_key(struct btrfs_trans_handle *trans,
+			    struct extent_buffer *parent,
+			    int pslot,
+			    const struct btrfs_disk_key *key)
+{
+	int ret;
+
+	ret = btrfs_tree_mod_log_insert_key(parent, pslot,
+					    BTRFS_MOD_LOG_KEY_REPLACE);
+	BUG_ON(ret < 0);
+	btrfs_set_node_key(parent, key, pslot);
+	btrfs_mark_buffer_dirty(trans, parent);
+}
+
+static noinline int promote_to_root(struct btrfs_trans_handle *trans,
+				    struct btrfs_root *root,
+				    struct btrfs_path *path,
+				    int level,
+				    struct extent_buffer *parent)
+{
+	struct extent_buffer *child;
+	int ret = 0;
+
+	ASSERT(btrfs_header_nritems(parent) == 1);
+
+	child = btrfs_read_node_slot(parent, 0);
+	if (IS_ERR(child))
+		return PTR_ERR(child);
+
+	btrfs_tree_lock(child);
+	ret = btrfs_cow_block(trans, root, child, parent, 0, &child,
+			      BTRFS_NESTING_COW);
+	if (ret) {
+		btrfs_tree_unlock(child);
+		free_extent_buffer(child);
+		return ret;
+	}
+
+	ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
+	if (ret < 0) {
+		btrfs_tree_unlock(child);
+		free_extent_buffer(child);
+		btrfs_abort_transaction(trans, ret);
+		return ret;
+	}
+	rcu_assign_pointer(root->node, child);
+
+	add_root_to_dirty_list(root);
+	btrfs_tree_unlock(child);
+
+	path->locks[level] = 0;
+	path->nodes[level] = NULL;
+	btrfs_clear_buffer_dirty(trans, parent);
+	btrfs_tree_unlock(parent);
+	/* once for the path */
+	free_extent_buffer(parent);
+
+	root_sub_used_bytes(root);
+	ret = btrfs_free_tree_block(trans, btrfs_root_id(root), parent, 0, 1);
+	/* once for the root ptr */
+	free_extent_buffer_stale(parent);
+	if (ret < 0) {
+		btrfs_abort_transaction(trans, ret);
+		return ret;
+	}
+	return 0;
+}
 /*
  * node level balancing, used to make sure nodes are in proper order for
  * item deletion.  We balance from the top down, so we have to make sure
  * that a deletion won't leave an node completely empty later on.
  */
 static noinline int balance_level(struct btrfs_trans_handle *trans,
-			 struct btrfs_root *root,
-			 struct btrfs_path *path, int level)
+				  struct btrfs_root *root,
+				  struct btrfs_path *path, int level)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
-	struct extent_buffer *right = NULL;
-	struct extent_buffer *mid;
-	struct extent_buffer *left = NULL;
+	struct extent_buffer *r = NULL;
+	struct extent_buffer *m;
+	struct extent_buffer *l = NULL;
 	struct extent_buffer *parent = NULL;
+	u32 l_nr = 0;
+	u32 m_nr;
+	u32 r_nr = 0;
+	u32 total_nr;
+	u8 total_nodes;
 	int ret = 0;
 	int wret;
 	int pslot;
@@ -874,12 +968,12 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 
 	ASSERT(level > 0);
 
-	mid = path->nodes[level];
+	m = path->nodes[level];
 
 	WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK);
-	WARN_ON(btrfs_header_generation(mid) != trans->transid);
+	WARN_ON(btrfs_header_generation(m) != trans->transid);
 
-	orig_ptr = btrfs_node_blockptr(mid, orig_slot);
+	orig_ptr = btrfs_node_blockptr(m, orig_slot);
 
 	if (level < BTRFS_MAX_LEVEL - 1) {
 		parent = path->nodes[level + 1];
@@ -891,234 +985,154 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	 * by promoting the node below to a root
 	 */
 	if (!parent) {
-		struct extent_buffer *child;
-
-		if (btrfs_header_nritems(mid) != 1)
+		if (btrfs_header_nritems(m) != 1)
 			return 0;
 
 		/* promote the child to a root */
-		child = btrfs_read_node_slot(mid, 0);
-		if (IS_ERR(child)) {
-			ret = PTR_ERR(child);
-			goto out;
-		}
-
-		btrfs_tree_lock(child);
-		ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
-				      BTRFS_NESTING_COW);
-		if (ret) {
-			btrfs_tree_unlock(child);
-			free_extent_buffer(child);
-			goto out;
-		}
-
-		ret = btrfs_tree_mod_log_insert_root(root->node, child, true);
-		if (ret < 0) {
-			btrfs_tree_unlock(child);
-			free_extent_buffer(child);
-			btrfs_abort_transaction(trans, ret);
-			goto out;
-		}
-		rcu_assign_pointer(root->node, child);
-
-		add_root_to_dirty_list(root);
-		btrfs_tree_unlock(child);
-
-		path->locks[level] = 0;
-		path->nodes[level] = NULL;
-		btrfs_clear_buffer_dirty(trans, mid);
-		btrfs_tree_unlock(mid);
-		/* once for the path */
-		free_extent_buffer(mid);
-
-		root_sub_used_bytes(root);
-		ret = btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
-		/* once for the root ptr */
-		free_extent_buffer_stale(mid);
-		if (ret < 0) {
-			btrfs_abort_transaction(trans, ret);
-			goto out;
-		}
-		return 0;
+		return promote_to_root(trans, root, path, level, m);
 	}
-	if (btrfs_header_nritems(mid) >
-	    BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
-		return 0;
 
 	if (pslot) {
-		left = btrfs_read_node_slot(parent, pslot - 1);
-		if (IS_ERR(left)) {
-			ret = PTR_ERR(left);
-			left = NULL;
-			goto out;
-		}
-
-		btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
-		wret = btrfs_cow_block(trans, root, left,
-				       parent, pslot - 1, &left,
-				       BTRFS_NESTING_LEFT_COW);
-		if (wret) {
-			ret = wret;
+		l = btrfs_read_node_slot(parent, pslot - 1);
+		if (IS_ERR(l)) {
+			ret = PTR_ERR(l);
+			l = NULL;
 			goto out;
 		}
+		btrfs_tree_lock_nested(l, BTRFS_NESTING_LEFT);
+		l_nr = btrfs_header_nritems(l);
 	}
 
 	if (pslot + 1 < btrfs_header_nritems(parent)) {
-		right = btrfs_read_node_slot(parent, pslot + 1);
-		if (IS_ERR(right)) {
-			ret = PTR_ERR(right);
-			right = NULL;
-			goto out;
-		}
-
-		btrfs_tree_lock_nested(right, BTRFS_NESTING_RIGHT);
-		wret = btrfs_cow_block(trans, root, right,
-				       parent, pslot + 1, &right,
-				       BTRFS_NESTING_RIGHT_COW);
-		if (wret) {
-			ret = wret;
+		r = btrfs_read_node_slot(parent, pslot + 1);
+		if (IS_ERR(r)) {
+			ret = PTR_ERR(r);
+			r = NULL;
 			goto out;
 		}
+		btrfs_tree_lock_nested(r, BTRFS_NESTING_RIGHT);
+		r_nr = btrfs_header_nritems(r);
 	}
 
-	/* first, try to make some room in the middle buffer */
-	if (left) {
-		orig_slot += btrfs_header_nritems(left);
-		wret = push_node_left(trans, left, mid, 1);
-		if (wret < 0)
-			ret = wret;
-	}
+	total_nodes = !!l + !!r;
+	if (total_nodes == 0)
+		return 0;
 
-	/*
-	 * then try to empty the right most buffer into the middle
-	 */
-	if (right) {
-		wret = push_node_left(trans, mid, right, 1);
-		if (wret < 0 && wret != -ENOSPC)
-			ret = wret;
-		if (btrfs_header_nritems(right) == 0) {
-			btrfs_clear_buffer_dirty(trans, right);
-			btrfs_tree_unlock(right);
-			ret = btrfs_del_ptr(trans, root, path, level + 1, pslot + 1);
-			if (ret < 0) {
-				free_extent_buffer_stale(right);
-				right = NULL;
-				goto out;
-			}
-			root_sub_used_bytes(root);
-			ret = btrfs_free_tree_block(trans, btrfs_root_id(root),
-						    right, 0, 1);
-			free_extent_buffer_stale(right);
-			right = NULL;
-			if (ret < 0) {
-				btrfs_abort_transaction(trans, ret);
+	m_nr = btrfs_header_nritems(m);
+	total_nr = l_nr + m_nr + r_nr;
+	/* These nodes can be merged into fewer nodes */
+	if (total_nr <= node_balance_himark(fs_info) * total_nodes) {
+		if (l) {
+			ret = btrfs_cow_block(trans, root, l, parent,
+					      pslot - 1, &l, BTRFS_NESTING_LEFT_COW);
+			if (ret)
 				goto out;
-			}
-		} else {
-			struct btrfs_disk_key right_key;
-			btrfs_node_key(right, &right_key, 0);
-			ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
-					BTRFS_MOD_LOG_KEY_REPLACE);
-			if (ret < 0) {
-				btrfs_abort_transaction(trans, ret);
+			orig_slot += l_nr;
+			wret = node_balance_move_l(trans, l, m, node_balance_himark(fs_info));
+			if (wret < 0) {
+				ret = wret;
 				goto out;
 			}
-			btrfs_set_node_key(parent, &right_key, pslot + 1);
-			btrfs_mark_buffer_dirty(trans, parent);
-		}
-	}
-	if (btrfs_header_nritems(mid) == 1) {
-		/*
-		 * we're not allowed to leave a node with one item in the
-		 * tree during a delete.  A deletion from lower in the tree
-		 * could try to delete the only pointer in this node.
-		 * So, pull some keys from the left.
-		 * There has to be a left pointer at this point because
-		 * otherwise we would have pulled some pointers from the
-		 * right
-		 */
-		if (unlikely(!left)) {
-			btrfs_crit(fs_info,
-"missing left child when middle child only has 1 item, parent bytenr %llu level %d mid bytenr %llu root %llu",
-				   parent->start, btrfs_header_level(parent),
-				   mid->start, btrfs_root_id(root));
-			ret = -EUCLEAN;
-			btrfs_abort_transaction(trans, ret);
-			goto out;
-		}
-		wret = balance_node_right(trans, mid, left);
-		if (wret < 0) {
-			ret = wret;
-			goto out;
 		}
-		if (wret == 1) {
-			wret = push_node_left(trans, left, mid, 1);
-			if (wret < 0)
+		if (r && btrfs_header_nritems(m) > 0) {
+			struct btrfs_disk_key r_key;
+
+			ret = btrfs_cow_block(trans, root, r, parent,
+					      pslot + 1, &r, BTRFS_NESTING_RIGHT_COW);
+			if (ret)
+				goto out;
+			// XXX: different with v5
+			wret = node_balance_move_r(trans, m, r, node_balance_himark(fs_info));
+			if (wret < 0) {
 				ret = wret;
+				goto out;
+			}
+			btrfs_node_key(r, &r_key, 0);
+			update_node_key(trans, parent, pslot + 1, &r_key);
 		}
-		BUG_ON(wret == 1);
-	}
-	if (btrfs_header_nritems(mid) == 0) {
-		btrfs_clear_buffer_dirty(trans, mid);
-		btrfs_tree_unlock(mid);
+		ASSERT(btrfs_header_nritems(m) == 0);
+		btrfs_clear_buffer_dirty(trans, m);
+		btrfs_tree_unlock(m);
 		ret = btrfs_del_ptr(trans, root, path, level + 1, pslot);
 		if (ret < 0) {
-			free_extent_buffer_stale(mid);
-			mid = NULL;
+			free_extent_buffer_stale(m);
+			m = NULL;
 			goto out;
 		}
 		root_sub_used_bytes(root);
-		ret = btrfs_free_tree_block(trans, btrfs_root_id(root), mid, 0, 1);
-		free_extent_buffer_stale(mid);
-		mid = NULL;
+		ret = btrfs_free_tree_block(trans, btrfs_root_id(root), m, 0, 1);
+		free_extent_buffer_stale(m);
+		m = NULL;
 		if (ret < 0) {
 			btrfs_abort_transaction(trans, ret);
 			goto out;
 		}
+		/* Update the path */
+		if (l) {
+			if (btrfs_header_nritems(l) > orig_slot) {
+				path->nodes[level] = l;
+				path->slots[level + 1] -= 1;
+				path->slots[level] = orig_slot;
+				l = NULL;
+			} else {
+				ASSERT(r);
+				path->nodes[level] = r;
+				path->slots[level] = orig_slot - btrfs_header_nritems(l);
+				r = NULL;
+			}
+		} else {
+			path->nodes[level] = r;
+			r = NULL;
+		}
 	} else {
-		/* update the parent key to reflect our changes */
-		struct btrfs_disk_key mid_key;
-		btrfs_node_key(mid, &mid_key, 0);
-		ret = btrfs_tree_mod_log_insert_key(parent, pslot,
-						    BTRFS_MOD_LOG_KEY_REPLACE);
-		if (ret < 0) {
-			btrfs_abort_transaction(trans, ret);
+		if (max(l_nr, r_nr) <= node_balance_lomark(fs_info))
 			goto out;
-		}
-		btrfs_set_node_key(parent, &mid_key, pslot);
-		btrfs_mark_buffer_dirty(trans, parent);
-	}
 
-	/* update the path */
-	if (left) {
-		if (btrfs_header_nritems(left) > orig_slot) {
-			refcount_inc(&left->refs);
-			/* left was locked after cow */
-			path->nodes[level] = left;
-			path->slots[level + 1] -= 1;
-			path->slots[level] = orig_slot;
-			if (mid) {
-				btrfs_tree_unlock(mid);
-				free_extent_buffer(mid);
+		if (l_nr > r_nr) {
+			struct btrfs_disk_key m_key;
+
+			orig_slot += l_nr;
+			ret = btrfs_cow_block(trans, root, l, parent, pslot - 1, &l,
+					      BTRFS_NESTING_LEFT_COW);
+			if (ret)
+				goto out;
+			wret = node_balance_move_r(trans, l, m, (m_nr + l_nr) / 2 + 1);
+			if (wret < 0) {
+				ret = wret;
+				goto out;
 			}
+			btrfs_node_key(m, &m_key, 0);
+			update_node_key(trans, parent, pslot, &m_key);
+			path->slots[level] = orig_slot - btrfs_header_nritems(l);
 		} else {
-			orig_slot -= btrfs_header_nritems(left);
-			path->slots[level] = orig_slot;
+			struct btrfs_disk_key r_key;
+
+			ret = btrfs_cow_block(trans, root, r, parent, pslot + 1, &r,
+					      BTRFS_NESTING_RIGHT_COW);
+			if (ret)
+				goto out;
+			wret = node_balance_move_l(trans, m, r, (m_nr + r_nr) / 2 + 1);
+			if (wret < 0) {
+				ret = wret;
+				goto out;
+			}
+			btrfs_node_key(r, &r_key, 0);
+			update_node_key(trans, parent, pslot + 1, &r_key);
 		}
 	}
+
 	/* double check we haven't messed things up */
 	if (orig_ptr !=
 	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
 		BUG();
 out:
-	if (right) {
-		btrfs_tree_unlock(right);
-		free_extent_buffer(right);
+	if (r) {
+		btrfs_tree_unlock(r);
+		free_extent_buffer(r);
 	}
-	if (left) {
-		if (path->nodes[level] != left)
-			btrfs_tree_unlock(left);
-		free_extent_buffer(left);
+	if (l) {
+		btrfs_tree_unlock(l);
+		free_extent_buffer(l);
 	}
 	return ret;
 }
@@ -1132,20 +1146,24 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 					  struct btrfs_path *path, int level)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
-	struct extent_buffer *right = NULL;
-	struct extent_buffer *mid;
-	struct extent_buffer *left = NULL;
+	struct extent_buffer *r = NULL;
+	struct extent_buffer *m;
+	struct extent_buffer *l = NULL;
 	struct extent_buffer *parent = NULL;
+	u32 l_nr = -1;
+	u32 r_nr = -1;
 	int ret = 0;
-	int wret;
 	int pslot;
 	int orig_slot = path->slots[level];
+	u64 orig_ptr;
 
 	if (level == 0)
 		return 1;
 
-	mid = path->nodes[level];
-	WARN_ON(btrfs_header_generation(mid) != trans->transid);
+	m = path->nodes[level];
+	WARN_ON(btrfs_header_generation(m) != trans->transid);
+
+	orig_ptr = btrfs_node_blockptr(m, orig_slot);
 
 	if (level < BTRFS_MAX_LEVEL - 1) {
 		parent = path->nodes[level + 1];
@@ -1157,121 +1175,102 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 	/* first, try to make some room in the middle buffer */
 	if (pslot) {
-		u32 left_nr;
-
-		left = btrfs_read_node_slot(parent, pslot - 1);
-		if (IS_ERR(left))
-			return PTR_ERR(left);
-
-		btrfs_tree_lock_nested(left, BTRFS_NESTING_LEFT);
-
-		left_nr = btrfs_header_nritems(left);
-		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
-			wret = 1;
-		} else {
-			ret = btrfs_cow_block(trans, root, left, parent,
-					      pslot - 1, &left,
-					      BTRFS_NESTING_LEFT_COW);
-			if (ret)
-				wret = 1;
-			else {
-				wret = push_node_left(trans, left, mid, 0);
-			}
-		}
-		if (wret < 0)
-			ret = wret;
-		if (wret == 0) {
-			struct btrfs_disk_key disk_key;
-			orig_slot += left_nr;
-			btrfs_node_key(mid, &disk_key, 0);
-			ret = btrfs_tree_mod_log_insert_key(parent, pslot,
-					BTRFS_MOD_LOG_KEY_REPLACE);
-			if (ret < 0) {
-				btrfs_tree_unlock(left);
-				free_extent_buffer(left);
-				btrfs_abort_transaction(trans, ret);
-				return ret;
-			}
-			btrfs_set_node_key(parent, &disk_key, pslot);
-			btrfs_mark_buffer_dirty(trans, parent);
-			if (btrfs_header_nritems(left) > orig_slot) {
-				path->nodes[level] = left;
-				path->slots[level + 1] -= 1;
-				path->slots[level] = orig_slot;
-				btrfs_tree_unlock(mid);
-				free_extent_buffer(mid);
-			} else {
-				orig_slot -=
-					btrfs_header_nritems(left);
-				path->slots[level] = orig_slot;
-				btrfs_tree_unlock(left);
-				free_extent_buffer(left);
-			}
-			return 0;
+		l = btrfs_read_node_slot(parent, pslot - 1);
+		if (IS_ERR(l)) {
+			ret = PTR_ERR(l);
+			l = NULL;
+			goto out;
 		}
-		btrfs_tree_unlock(left);
-		free_extent_buffer(left);
+		btrfs_tree_lock_nested(l, BTRFS_NESTING_LEFT);
+		l_nr = btrfs_header_nritems(l);
 	}
-
-	/*
-	 * then try to empty the right most buffer into the middle
-	 */
 	if (pslot + 1 < btrfs_header_nritems(parent)) {
-		u32 right_nr;
+		r = btrfs_read_node_slot(parent, pslot + 1);
+		if (IS_ERR(r)) {
+			ret = PTR_ERR(r);
+			r = NULL;
+			goto out;
+		}
+		btrfs_tree_lock_nested(r, BTRFS_NESTING_RIGHT);
+		r_nr = btrfs_header_nritems(r);
+	}
 
-		right = btrfs_read_node_slot(parent, pslot + 1);
-		if (IS_ERR(right))
-			return PTR_ERR(right);
+	if (!l && !r)
+		return 1;
 
-		btrfs_tree_lock_nested(right, BTRFS_NESTING_RIGHT);
+	if (min(l_nr, r_nr) == BTRFS_NODEPTRS_PER_BLOCK(fs_info)) {
+		ret = 1;
+		goto out;
+	}
+	if (l_nr <= r_nr) {
+		struct btrfs_disk_key m_key;
+		int target_nr;
 
-		right_nr = btrfs_header_nritems(right);
-		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
-			wret = 1;
+		ret = btrfs_cow_block(trans, root, l, parent, pslot - 1, &l,
+				      BTRFS_NESTING_LEFT_COW);
+		if (ret)
+			goto out;
+		orig_slot += l_nr;
+		if (l_nr >= node_balance_himark(fs_info))
+			target_nr = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
+		else
+			target_nr = (btrfs_header_nritems(m) + l_nr) / 2;
+		ret = node_balance_move_l(trans, l, m, target_nr);
+		if (ret)
+			goto out;
+		btrfs_node_key(m, &m_key, 0);
+		update_node_key(trans, parent, pslot, &m_key);
+		if (btrfs_header_nritems(l) > orig_slot) {
+			path->nodes[level] = l;
+			path->slots[level + 1] -= 1;
+			path->slots[level] = orig_slot;
+			l = NULL;
+			btrfs_tree_unlock(m);
+			free_extent_buffer(m);
 		} else {
-			ret = btrfs_cow_block(trans, root, right,
-					      parent, pslot + 1,
-					      &right, BTRFS_NESTING_RIGHT_COW);
-			if (ret)
-				wret = 1;
-			else {
-				wret = balance_node_right(trans, right, mid);
-			}
+			path->slots[level] = orig_slot - btrfs_header_nritems(l);
 		}
-		if (wret < 0)
-			ret = wret;
-		if (wret == 0) {
-			struct btrfs_disk_key disk_key;
+	} else {
+		struct btrfs_disk_key r_key;
+		int target_nr;
 
-			btrfs_node_key(right, &disk_key, 0);
-			ret = btrfs_tree_mod_log_insert_key(parent, pslot + 1,
-					BTRFS_MOD_LOG_KEY_REPLACE);
-			if (ret < 0) {
-				btrfs_tree_unlock(right);
-				free_extent_buffer(right);
-				btrfs_abort_transaction(trans, ret);
-				return ret;
-			}
-			btrfs_set_node_key(parent, &disk_key, pslot + 1);
-			btrfs_mark_buffer_dirty(trans, parent);
-
-			if (btrfs_header_nritems(mid) <= orig_slot) {
-				path->nodes[level] = right;
-				path->slots[level + 1] += 1;
-				path->slots[level] = orig_slot -
-					btrfs_header_nritems(mid);
-				btrfs_tree_unlock(mid);
-				free_extent_buffer(mid);
-			} else {
-				btrfs_tree_unlock(right);
-				free_extent_buffer(right);
-			}
-			return 0;
+		ret = btrfs_cow_block(trans, root, r, parent, pslot + 1, &r,
+				      BTRFS_NESTING_RIGHT_COW);
+		if (ret)
+			goto out;
+		if (r_nr >= node_balance_himark(fs_info))
+			target_nr = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
+		else
+			target_nr = (btrfs_header_nritems(m) + r_nr) / 2;
+		ret = node_balance_move_r(trans, m, r, target_nr);
+		if (ret)
+			goto out;
+		btrfs_node_key(r, &r_key, 0);
+		update_node_key(trans, parent, pslot + 1, &r_key);
+		if (btrfs_header_nritems(m) <= orig_slot) {
+			path->nodes[level] = r;
+			path->slots[level + 1] += 1;
+			path->slots[level] = orig_slot - btrfs_header_nritems(m);
+			r = NULL;
+			btrfs_tree_unlock(m);
+			free_extent_buffer(m);
 		}
-		btrfs_tree_unlock(right);
-		free_extent_buffer(right);
 	}
-	return 1;
+
+	if (orig_ptr !=
+	    btrfs_node_blockptr(path->nodes[level], path->slots[level]))
+		BUG();
+
+out:
+	if (l) {
+		btrfs_tree_unlock(l);
+		free_extent_buffer(l);
+	}
+	if (r) {
+		btrfs_tree_unlock(r);
+		free_extent_buffer(r);
+	}
+	return ret;
 }
 
 /*
@@ -2548,21 +2547,12 @@ static void fixup_low_keys(struct btrfs_trans_handle *trans,
 			   const struct btrfs_path *path,
 			   const struct btrfs_disk_key *key, int level)
 {
-	int i;
-	struct extent_buffer *t;
-	int ret;
-
-	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
+	for (int i = level; i < BTRFS_MAX_LEVEL; i++) {
 		int tslot = path->slots[i];
 
 		if (!path->nodes[i])
 			break;
-		t = path->nodes[i];
-		ret = btrfs_tree_mod_log_insert_key(t, tslot,
-						    BTRFS_MOD_LOG_KEY_REPLACE);
-		BUG_ON(ret < 0);
-		btrfs_set_node_key(t, key, tslot);
-		btrfs_mark_buffer_dirty(trans, path->nodes[i]);
+		update_node_key(trans, path->nodes[i], tslot, key);
 		if (tslot != 0)
 			break;
 	}
@@ -2677,156 +2667,105 @@ static bool check_sibling_keys(const struct extent_buffer *left,
 	return false;
 }
 
-/*
- * try to push data from one node into the next node left in the
- * tree.
- *
- * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
- * error, and > 0 if there was no room in the left hand block.
- */
-static int push_node_left(struct btrfs_trans_handle *trans,
-			  struct extent_buffer *dst,
-			  struct extent_buffer *src, int empty)
+static int node_balance_move_l(struct btrfs_trans_handle *trans,
+			       struct extent_buffer *l,
+			       struct extent_buffer *r,
+			       int dst_max)
 {
-	struct btrfs_fs_info *fs_info = trans->fs_info;
-	int push_items = 0;
-	int src_nritems;
-	int dst_nritems;
+	int npush;
+	int l_nr = btrfs_header_nritems(l);
+	int r_nr = btrfs_header_nritems(r);
 	int ret = 0;
 
-	src_nritems = btrfs_header_nritems(src);
-	dst_nritems = btrfs_header_nritems(dst);
-	push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
-	WARN_ON(btrfs_header_generation(src) != trans->transid);
-	WARN_ON(btrfs_header_generation(dst) != trans->transid);
-
-	if (!empty && src_nritems <= 8)
-		return 1;
+	WARN_ON(btrfs_header_generation(l) != trans->transid);
+	WARN_ON(btrfs_header_generation(r) != trans->transid);
 
-	if (push_items <= 0)
+	npush = dst_max - l_nr;
+	if (npush <= 0)
 		return 1;
 
-	if (empty) {
-		push_items = min(src_nritems, push_items);
-		if (push_items < src_nritems) {
-			/* leave at least 8 pointers in the node if
-			 * we aren't going to empty it
-			 */
-			if (src_nritems - push_items < 8) {
-				if (push_items <= 8)
-					return 1;
-				push_items -= 8;
-			}
-		}
-	} else
-		push_items = min(src_nritems - 8, push_items);
+	npush = min(npush, r_nr);
 
-	/* dst is the left eb, src is the middle eb */
-	if (check_sibling_keys(dst, src)) {
+	if (check_sibling_keys(l, r)) {
 		ret = -EUCLEAN;
 		btrfs_abort_transaction(trans, ret);
 		return ret;
 	}
-	ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items);
+
+	ret = btrfs_tree_mod_log_eb_copy(l, r, l_nr, 0, npush);
 	if (ret) {
 		btrfs_abort_transaction(trans, ret);
 		return ret;
 	}
-	copy_extent_buffer(dst, src,
-			   btrfs_node_key_ptr_offset(dst, dst_nritems),
-			   btrfs_node_key_ptr_offset(src, 0),
-			   push_items * sizeof(struct btrfs_key_ptr));
 
-	if (push_items < src_nritems) {
+	copy_extent_buffer(l, r, btrfs_node_key_ptr_offset(l, l_nr),
+				 btrfs_node_key_ptr_offset(r, 0),
+				 npush * sizeof(struct btrfs_key_ptr));
+
+	if (npush < r_nr) {
 		/*
 		 * btrfs_tree_mod_log_eb_copy handles logging the move, so we
 		 * don't need to do an explicit tree mod log operation for it.
 		 */
-		memmove_extent_buffer(src, btrfs_node_key_ptr_offset(src, 0),
-				      btrfs_node_key_ptr_offset(src, push_items),
-				      (src_nritems - push_items) *
-				      sizeof(struct btrfs_key_ptr));
+		memmove_extent_buffer(r, btrfs_node_key_ptr_offset(r, 0),
+					 btrfs_node_key_ptr_offset(r, npush),
+					 (r_nr - npush) * sizeof(struct btrfs_key_ptr));
 	}
-	btrfs_set_header_nritems(src, src_nritems - push_items);
-	btrfs_set_header_nritems(dst, dst_nritems + push_items);
-	btrfs_mark_buffer_dirty(trans, src);
-	btrfs_mark_buffer_dirty(trans, dst);
+
+	btrfs_set_header_nritems(r, r_nr - npush);
+	btrfs_set_header_nritems(l, l_nr + npush);
+	btrfs_mark_buffer_dirty(trans, l);
+	btrfs_mark_buffer_dirty(trans, r);
 
 	return ret;
 }
 
-/*
- * try to push data from one node into the next node right in the
- * tree.
- *
- * returns 0 if some ptrs were pushed, < 0 if there was some horrible
- * error, and > 0 if there was no room in the right hand block.
- *
- * this will  only push up to 1/2 the contents of the left node over
- */
-static int balance_node_right(struct btrfs_trans_handle *trans,
-			      struct extent_buffer *dst,
-			      struct extent_buffer *src)
+static int node_balance_move_r(struct btrfs_trans_handle *trans,
+			       struct extent_buffer *l,
+			       struct extent_buffer *r,
+			       int dst_max)
 {
-	struct btrfs_fs_info *fs_info = trans->fs_info;
-	int push_items = 0;
-	int max_push;
-	int src_nritems;
-	int dst_nritems;
+	int npush;
+	int l_nr = btrfs_header_nritems(l);
+	int r_nr = btrfs_header_nritems(r);
 	int ret = 0;
 
-	WARN_ON(btrfs_header_generation(src) != trans->transid);
-	WARN_ON(btrfs_header_generation(dst) != trans->transid);
-
-	src_nritems = btrfs_header_nritems(src);
-	dst_nritems = btrfs_header_nritems(dst);
-	push_items = BTRFS_NODEPTRS_PER_BLOCK(fs_info) - dst_nritems;
-	if (push_items <= 0)
-		return 1;
+	WARN_ON(btrfs_header_generation(l) != trans->transid);
+	WARN_ON(btrfs_header_generation(r) != trans->transid);
 
-	if (src_nritems < 4)
+	npush = dst_max - r_nr;
+	if (npush <= 0)
 		return 1;
 
-	max_push = src_nritems / 2 + 1;
-	/* don't try to empty the node */
-	if (max_push >= src_nritems)
-		return 1;
+	npush = min(npush, l_nr);
 
-	if (max_push < push_items)
-		push_items = max_push;
-
-	/* dst is the right eb, src is the middle eb */
-	if (check_sibling_keys(src, dst)) {
+	if (check_sibling_keys(l, r)) {
 		ret = -EUCLEAN;
 		btrfs_abort_transaction(trans, ret);
 		return ret;
 	}
 
+	memmove_extent_buffer(r, btrfs_node_key_ptr_offset(r, npush),
+				 btrfs_node_key_ptr_offset(r, 0),
+				 r_nr * sizeof(struct btrfs_key_ptr));
 	/*
 	 * btrfs_tree_mod_log_eb_copy handles logging the move, so we don't
 	 * need to do an explicit tree mod log operation for it.
 	 */
-	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(dst, push_items),
-				      btrfs_node_key_ptr_offset(dst, 0),
-				      (dst_nritems) *
-				      sizeof(struct btrfs_key_ptr));
-
-	ret = btrfs_tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
-					 push_items);
+	ret = btrfs_tree_mod_log_eb_copy(r, l, 0, l_nr - npush, npush);
 	if (ret) {
 		btrfs_abort_transaction(trans, ret);
 		return ret;
 	}
-	copy_extent_buffer(dst, src,
-			   btrfs_node_key_ptr_offset(dst, 0),
-			   btrfs_node_key_ptr_offset(src, src_nritems - push_items),
-			   push_items * sizeof(struct btrfs_key_ptr));
 
-	btrfs_set_header_nritems(src, src_nritems - push_items);
-	btrfs_set_header_nritems(dst, dst_nritems + push_items);
+	copy_extent_buffer(r, l, btrfs_node_key_ptr_offset(r, 0),
+				 btrfs_node_key_ptr_offset(l, l_nr - npush),
+				 npush * sizeof(struct btrfs_key_ptr));
 
-	btrfs_mark_buffer_dirty(trans, src);
-	btrfs_mark_buffer_dirty(trans, dst);
+	btrfs_set_header_nritems(r, r_nr + npush);
+	btrfs_set_header_nritems(l, l_nr - npush);
+	btrfs_mark_buffer_dirty(trans, l);
+	btrfs_mark_buffer_dirty(trans, r);
 
 	return ret;
 }