[PATCH] bcache: insert bkeys without overlap when placeholder missed

[PATCH] bcache: insert bkeys without overlap when placeholder missed

[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.

Signed-off-by: Liu Hua <liusdu@126.com>
---
 drivers/md/bcache/extents.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index c809724e6571..acebe5bdb3f1 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -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);
 
-- 
2.17.1

Re: [PATCH] bcache: insert bkeys without overlap when placeholder missed

[Coly Li]

On 2020/9/22 23:47, Liu Hua wrote:
> 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

> Signed-off-by: Liu Hua <liusdu@126.com>
> ---
>  drivers/md/bcache/extents.c | 10 +++++++---
>  1 file changed, 7 insertions(+), 3 deletions(-)
> 
> diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
> index c809724e6571..acebe5bdb3f1 100644
> --- a/drivers/md/bcache/extents.c
> +++ b/drivers/md/bcache/extents.c
> @@ -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);
>  
> 

Re: [PATCH] bcache: insert bkeys without overlap when placeholder missed

[Coly Li]

On 2020/9/23 23:18, Liu Hua wrote:
> Hi Coly,
> 
>  Thanks for you reply!
> 
> 在 2020/9/22 下午11:51, Coly Li 写道:
>> On 2020/9/22 23:47, Liu Hua wrote:
>>> 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.
>> - 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

Re: [PATCH] bcache: insert bkeys without overlap when placeholder missed

[Liu Hua]

Hope My email client configured correctly this time.

在 2020/9/23 下午11:26, Coly Li 写道:
> On 2020/9/23 23:18, Liu Hua wrote:
>> Hi Coly,
>>
>>  Thanks for you reply!
>>
>> 在 2020/9/22 下午11:51, Coly Li 写道:
>>> On 2020/9/22 23:47, Liu Hua wrote:
>>>> 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')
LBAs of the two process should overlap, otherwise ABC will not fail.

>>    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.
>>> - 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
> 

[PATCH] bcache: insert bkeys without overlap when placeholder missed

[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.

Signed-off-by: Liu Hua <liusdu@126.com>
---
 drivers/md/bcache/extents.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/drivers/md/bcache/extents.c b/drivers/md/bcache/extents.c
index c809724e6571..cc8af08aee8d 100644
--- a/drivers/md/bcache/extents.c
+++ b/drivers/md/bcache/extents.c
@@ -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 overlay = 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 && overlay == false)
+				goto out;
+			break;
 		}
 
 		if (bkey_cmp(k, &START_KEY(insert)) <= 0)
 			continue;
 
+		overlay = true;
+
 		old_offset = KEY_START(k);
 		old_size = KEY_SIZE(k);
 
-- 
2.17.1