Skip to contentSkip to conversation

bcache: insert bkeys without overlap when placeholder missed

PATCH In review Liu Hua 2 participants 4 messages Sep 22, 2020 – Sep 24, 2020 1 message not in the archive bcache (block layer cache)

lore
Share & tools
lore

Liu Hua

author
#0 lore raw

PATCH 1/1 bcache: insert bkeys without overlap when placeholder missed

Btree spliting and garbage collection process will drop placeholders, which may cause cache miss collision. We can insert nonoverlapping bkeys with write lock. It is helpful for performance.

---
 drivers/md/bcache/extents.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
drivers/md/bcache/extents.c +7 -3
index c809724e6571..acebe5bdb3f1 100644
@@ -329,6 +329,7 @@ static bool bch_extent_insert_fixup(struct btree_keys *b,
 
 	uint64_t old_offset;
 	unsigned int old_size, sectors_found = 0;
+	bool overlap = false;
 
 	BUG_ON(!KEY_OFFSET(insert));
 	BUG_ON(!KEY_SIZE(insert));
@@ -340,15 +341,18 @@ static bool bch_extent_insert_fixup(struct btree_keys *b,
 			break;
 
 		if (bkey_cmp(&START_KEY(k), insert) >= 0) {
-			if (KEY_SIZE(k))
-				break;
-			else
+			if (!KEY_SIZE(k))
 				continue;
+			if (replace_key && overlap == false)
+				goto out;
+			break;
 		}
 
 		if (bkey_cmp(k, &START_KEY(insert)) <= 0)
 			continue;
 
+		overlap = true;
+
 		old_offset = KEY_START(k);
 		old_size = KEY_SIZE(k);
 
Signature · 1 line
2.17.1
#1 lore raw
Quoted 5 lines · Liu Hua

Btree spliting and garbage collection process will drop placeholders, which may cause cache miss collision. We can insert nonoverlapping bkeys with write lock. It is helpful for performance.

Could you please to explain more detais about,
- How does "Btree spliting and garbage collection process will drop placeholders" happen?
- And how does the consequence "cache miss collision" happen?
- Do you observe performance improvement? If yes, which part is improved and what is the performance number?

Thanks in advance.

Coly Li

Quoted 40 lines
---
 drivers/md/bcache/extents.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)
drivers/md/bcache/extents.c +7 -3
index c809724e6571..acebe5bdb3f1 100644
@@ -329,6 +329,7 @@ static bool bch_extent_insert_fixup(struct btree_keys *b,
 
 	uint64_t old_offset;
 	unsigned int old_size, sectors_found = 0;
+	bool overlap = false;
 
 	BUG_ON(!KEY_OFFSET(insert));
 	BUG_ON(!KEY_SIZE(insert));
@@ -340,15 +341,18 @@ static bool bch_extent_insert_fixup(struct btree_keys *b,
 			break;
 
 		if (bkey_cmp(&START_KEY(k), insert) >= 0) {
-			if (KEY_SIZE(k))
-				break;
-			else
+			if (!KEY_SIZE(k))
 				continue;
+			if (replace_key && overlap == false)
+				goto out;
+			break;
 		}
 
 		if (bkey_cmp(k, &START_KEY(insert)) <= 0)
 			continue;
 
+		overlap = true;
+
 		old_offset = KEY_START(k);
 		old_size = KEY_SIZE(k);
 

A message that is not in the archive (sent off-list or not yet received): [email protected]

#3 lore raw
Quoted 48 lines · Liu Hua

Hi Coly,

 Thanks for you reply!

Quoted 10 lines · Coly Li
Quoted 5 lines · Liu Hua

Btree spliting and garbage collection process will drop placeholders, which may cause cache miss collision. We can insert nonoverlapping bkeys with write lock. It is helpful for performance.

Could you please to explain more detais about,
- How does "Btree spliting and garbage collection process will drop placeholders" happen?
- And how does the consequence "cache miss collision" happen?

Cache miss process is as following:

A. Insert placeholder with read lock
  - lookup missed cache
  - insert placeholder bkey
B. Read data from backing disk and write to cache
C. Insert real bkey with write lock
  - check and fixup placeholder in bch_extent_insert_fixup.
  - if bkey to be inserted does not match placeholder bkey. Inserting will failed.
    Bcache marks this type of failure as cache miss collision.  we can get this number
    from /sys/block/bcacheX/bcache/cache/stats_total/cache_miss_collision So a failed "c" process will lead the cache miss process fail, even if we have data
in place but metadata failed.  There are two types of reasons causing this failure:

1. Two cache miss processes collide as following (two processes names ABC and A'B'C')
   A
   A'
   B
   B'
   C(will fail)
   C'(will succeed)
2. placeholder bkeys were dropped before "C".  btree_mergesort called from GC and
btree_split will drop "bad" bkeys including placeholder bkeys.

For reason 2,since we hold write lock,if there is no overlaps with existing bkeys.
we can insert bkeys safely. this is what this patch does.

Quoted 8 lines
Quoted 2 lines

- Do you observe performance improvement? If yes, which part is improved and what is the performance number?

Can we treat this patch as a bugfix?  We add a prefetch framework in bcache and find 3% performace
improvement and reduction of collision in an order of one, in spark word-count test with 1G ram
disk as cache. And I think it is helpful both for our situation and original bcache. I can add a test based on original bcache.

Copied. Give me some time to understand your change. Maybe more question will follow up. Thank you for the above detailed information :-)

Coly Li

author
#4 lore raw

Hope My email client configured correctly this time.

Quoted 34 lines · Coly Li
Quoted 33 lines · Liu Hua

Hi Coly,

 Thanks for you reply!

Quoted 10 lines · Coly Li
Quoted 5 lines · Liu Hua

Btree spliting and garbage collection process will drop placeholders, which may cause cache miss collision. We can insert nonoverlapping bkeys with write lock. It is helpful for performance.

Could you please to explain more detais about,
- How does "Btree spliting and garbage collection process will drop placeholders" happen?
- And how does the consequence "cache miss collision" happen?

Cache miss process is as following:

A. Insert placeholder with read lock
  - lookup missed cache
  - insert placeholder bkey
B. Read data from backing disk and write to cache
C. Insert real bkey with write lock
  - check and fixup placeholder in bch_extent_insert_fixup.
  - if bkey to be inserted does not match placeholder bkey. Inserting will failed.
    Bcache marks this type of failure as cache miss collision.  we can get this number
    from /sys/block/bcacheX/bcache/cache/stats_total/cache_miss_collision So a failed "c" process will lead the cache miss process fail, even if we have data
in place but metadata failed.  There are two types of reasons causing this failure:

Quoted 2 lines
Quoted 2 lines

1. Two cache miss processes collide as following (two processes names ABC and A'B'C')

LBAs of the two process should overlap, otherwise ABC will not fail.

Quoted 27 lines
Quoted 13 lines

   A
   A'
   B
   B'
   C(will fail)
   C'(will succeed)
2. placeholder bkeys were dropped before "C".  btree_mergesort called from GC and
btree_split will drop "bad" bkeys including placeholder bkeys.

For reason 2,since we hold write lock,if there is no overlaps with existing bkeys.
we can insert bkeys safely. this is what this patch does.

Quoted 8 lines
Quoted 2 lines

- Do you observe performance improvement? If yes, which part is improved and what is the performance number?

Can we treat this patch as a bugfix?  We add a prefetch framework in bcache and find 3% performace
improvement and reduction of collision in an order of one, in spark word-count test with 1G ram
disk as cache. And I think it is helpful both for our situation and original bcache. I can add a test based on original bcache.

Copied. Give me some time to understand your change. Maybe more question will follow up. Thank you for the above detailed information :-)

Coly Li