Skip to contentSkip to conversation

bcache: dynamic incremental gc

PATCH Superseded [email protected] 3 participants 8 messages May 11, 2022 – May 24, 2022 bcache (block layer cache)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

PATCH v3 1/1 bcache: dynamic incremental gc

From: ZouMingzhe <[email protected]>

Currently, GC wants no more than 100 times, with at least 100 nodes each time, the maximum number of nodes each time is not limited.

```
static size_t btree_gc_min_nodes(struct cache_set *c)
{
        ......
        min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;
        if (min_nodes < MIN_GC_NODES)
                min_nodes = MIN_GC_NODES;

        return min_nodes;
}
```

According to our test data, when nvme is used as the cache, it takes about 1ms for GC to handle each node (block 4k and bucket 512k). This means that the latency during GC is at least 100ms. During GC, IO performance would be reduced by half or more.

I want to optimize the IOPS and latency under high pressure. This patch hold the inflight peak. When IO depth up to maximum, GC only process very few(10) nodes, then sleep immediately and handle these requests.

bch_bucket_alloc() maybe wait for bch_allocator_thread() to wake up, and and bch_allocator_thread() needs to wait for gc to complete, in which case gc needs to end quickly. So, add bucket_alloc_inflight to cache_set in v3.

```
long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
{
        ......
        do {
                prepare_to_wait(&ca->set->bucket_wait, &w,
                                TASK_UNINTERRUPTIBLE);

                mutex_unlock(&ca->set->bucket_lock);
                schedule();
                mutex_lock(&ca->set->bucket_lock);
        } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
                 !fifo_pop(&ca->free[reserve], r));
        ......
}

static int bch_allocator_thread(void *arg)
{
	......
	allocator_wait(ca, bch_allocator_push(ca, bucket));
	wake_up(&ca->set->btree_cache_wait);
	wake_up(&ca->set->bucket_wait);
	......
}

static void bch_btree_gc(struct cache_set *c)
{
	......
	bch_btree_gc_finish(c);
	wake_up_allocators(c);
	......
}
```

Apply this patch, each GC maybe only process very few nodes, GC would last a long time if sleep 100ms each time. So, the sleep time should be calculated dynamically based on gc_cost.

At the same time, I added some cost statistics in gc_stat, hoping to provide useful information for future work.

---
 drivers/md/bcache/alloc.c  |   2 +
 drivers/md/bcache/bcache.h |   9 ++++
 drivers/md/bcache/btree.c  | 100 ++++++++++++++++++++++++++++++++-----
 3 files changed, 98 insertions(+), 13 deletions(-)
drivers/md/bcache/alloc.c +2 -0
index 097577ae3c47..bb8b16cc2189 100644
@@ -415,7 +415,9 @@ long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
 				TASK_UNINTERRUPTIBLE);
 
 		mutex_unlock(&ca->set->bucket_lock);
+		atomic_inc(&ca->set->bucket_alloc_inflight);
 		schedule();
+		atomic_dec(&ca->set->bucket_alloc_inflight);
 		mutex_lock(&ca->set->bucket_lock);
 	} while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
 		 !fifo_pop(&ca->free[reserve], r));
drivers/md/bcache/bcache.h +9 -0
index 9ed9c955add7..a113a3bc7356 100644
@@ -471,6 +471,14 @@ struct cache {
 };
 
 struct gc_stat {
+	uint64_t		gc_cost;
+	uint64_t		sleep_cost;
+	uint64_t		average_cost;
+	uint64_t		start_time;
+	uint64_t		finish_time;
+	size_t			max_inflight;
+
+	size_t			times;
 	size_t			nodes;
 	size_t			nodes_pre;
 	size_t			key_bytes;
@@ -595,6 +603,7 @@ struct cache_set {
 	 * written.
 	 */
 	atomic_t		prio_blocked;
+	atomic_t		bucket_alloc_inflight;
 	wait_queue_head_t	bucket_wait;
 
 	/*
drivers/md/bcache/btree.c +87 -13

160 lines not on this page · raw message

Signature · 1 line
2.17.1
#1 lore raw
Quoted 68 lines · On 5/11/22 3:39 PM, [email protected] wrote:

From: ZouMingzhe <[email protected]>

Currently, GC wants no more than 100 times, with at least 100 nodes each time, the maximum number of nodes each time is not limited.

```
static size_t btree_gc_min_nodes(struct cache_set *c)
{
         ......
         min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;
         if (min_nodes < MIN_GC_NODES)
                 min_nodes = MIN_GC_NODES;

         return min_nodes;
}
```

According to our test data, when nvme is used as the cache, it takes about 1ms for GC to handle each node (block 4k and bucket 512k). This means that the latency during GC is at least 100ms. During GC, IO performance would be reduced by half or more.

I want to optimize the IOPS and latency under high pressure. This patch hold the inflight peak. When IO depth up to maximum, GC only process very few(10) nodes, then sleep immediately and handle these requests.

bch_bucket_alloc() maybe wait for bch_allocator_thread() to wake up, and and bch_allocator_thread() needs to wait for gc to complete, in which case gc needs to end quickly. So, add bucket_alloc_inflight to cache_set in v3.

```
long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
{
         ......
         do {
                 prepare_to_wait(&ca->set->bucket_wait, &w,
                                 TASK_UNINTERRUPTIBLE);

                 mutex_unlock(&ca->set->bucket_lock);
                 schedule();
                 mutex_lock(&ca->set->bucket_lock);
         } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
                  !fifo_pop(&ca->free[reserve], r));
         ......
}

static int bch_allocator_thread(void *arg)
{
	......
	allocator_wait(ca, bch_allocator_push(ca, bucket));
	wake_up(&ca->set->btree_cache_wait);
	wake_up(&ca->set->bucket_wait);
	......
}

static void bch_btree_gc(struct cache_set *c)
{
	......
	bch_btree_gc_finish(c);
	wake_up_allocators(c);
	......
}
```
Quoted 6 lines

Apply this patch, each GC maybe only process very few nodes, GC would last a long time if sleep 100ms each time. So, the sleep time should be calculated dynamically based on gc_cost.

At the same time, I added some cost statistics in gc_stat, hoping to provide useful information for future work.

Hi Mingzhe,

From the first glance, I feel this change may delay the small GC period, and finally result a large GC period, which is not expected.

But it is possible that my feeling is incorrect. Do you have detailed performance number about both I/O latency  and GC period, then I can have more understanding for this effort.

BTW, I will add this patch to my testing set and experience myself.

Thanks.

Coly Li

[snipped]

#2 lore raw
Quoted 83 lines · Coly Li
Quoted 68 lines · On 5/11/22 3:39 PM, [email protected] wrote:

From: ZouMingzhe <[email protected]>

Currently, GC wants no more than 100 times, with at least 100 nodes each time, the maximum number of nodes each time is not limited.

```
static size_t btree_gc_min_nodes(struct cache_set *c)
{
         ......
         min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;
         if (min_nodes < MIN_GC_NODES)
                 min_nodes = MIN_GC_NODES;

         return min_nodes;
}
```

According to our test data, when nvme is used as the cache, it takes about 1ms for GC to handle each node (block 4k and bucket 512k). This means that the latency during GC is at least 100ms. During GC, IO performance would be reduced by half or more.

I want to optimize the IOPS and latency under high pressure. This patch hold the inflight peak. When IO depth up to maximum, GC only process very few(10) nodes, then sleep immediately and handle these requests.

bch_bucket_alloc() maybe wait for bch_allocator_thread() to wake up, and and bch_allocator_thread() needs to wait for gc to complete, in which case gc needs to end quickly. So, add bucket_alloc_inflight to cache_set in v3.

```
long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
{
         ......
         do {
prepare_to_wait(&ca->set->bucket_wait, &w,
                                 TASK_UNINTERRUPTIBLE);

                 mutex_unlock(&ca->set->bucket_lock);
                 schedule();
                 mutex_lock(&ca->set->bucket_lock);
         } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
                  !fifo_pop(&ca->free[reserve], r));
         ......
}

static int bch_allocator_thread(void *arg)
{
    ......
    allocator_wait(ca, bch_allocator_push(ca, bucket));
    wake_up(&ca->set->btree_cache_wait);
    wake_up(&ca->set->bucket_wait);
    ......
}

static void bch_btree_gc(struct cache_set *c)
{
    ......
    bch_btree_gc_finish(c);
    wake_up_allocators(c);
    ......
}
```
Quoted 6 lines

Apply this patch, each GC maybe only process very few nodes, GC would last a long time if sleep 100ms each time. So, the sleep time should be calculated dynamically based on gc_cost.

At the same time, I added some cost statistics in gc_stat, hoping to provide useful information for future work.

Hi Mingzhe,

From the first glance, I feel this change may delay the small GC period, and finally result a large GC period, which is not expected.

But it is possible that my feeling is incorrect. Do you have detailed performance number about both I/O latency  and GC period, then I can have more understanding for this effort.

Quoted 9 lines

BTW, I will add this patch to my testing set and experience myself.

Thanks.

Coly Li

Hi Coly,

First, your feeling is right. Then, I have some performance number abort before and after this patch. Since the mailing list does not accept attachments, I put them on the gist.

Please visit the page for details:
https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5
mingzhe

Quoted 6 lines

[snipped]

#3 lore raw
Quoted 98 lines · Zou Mingzhe
Quoted 86 lines · Coly Li
Quoted 68 lines · On 5/11/22 3:39 PM, [email protected] wrote:

From: ZouMingzhe <[email protected]>

Currently, GC wants no more than 100 times, with at least 100 nodes each time, the maximum number of nodes each time is not limited.

```
static size_t btree_gc_min_nodes(struct cache_set *c)
{
         ......
         min_nodes = c->gc_stats.nodes / MAX_GC_TIMES;
         if (min_nodes < MIN_GC_NODES)
                 min_nodes = MIN_GC_NODES;

         return min_nodes;
}
```

According to our test data, when nvme is used as the cache, it takes about 1ms for GC to handle each node (block 4k and bucket 512k). This means that the latency during GC is at least 100ms. During GC, IO performance would be reduced by half or more.

I want to optimize the IOPS and latency under high pressure. This patch hold the inflight peak. When IO depth up to maximum, GC only process very few(10) nodes, then sleep immediately and handle these requests.

bch_bucket_alloc() maybe wait for bch_allocator_thread() to wake up, and and bch_allocator_thread() needs to wait for gc to complete, in which case gc needs to end quickly. So, add bucket_alloc_inflight to cache_set in v3.

```
long bch_bucket_alloc(struct cache *ca, unsigned int reserve, bool wait)
{
         ......
         do {
prepare_to_wait(&ca->set->bucket_wait, &w,
                                 TASK_UNINTERRUPTIBLE);

                 mutex_unlock(&ca->set->bucket_lock);
                 schedule();
                 mutex_lock(&ca->set->bucket_lock);
         } while (!fifo_pop(&ca->free[RESERVE_NONE], r) &&
                  !fifo_pop(&ca->free[reserve], r));
         ......
}

static int bch_allocator_thread(void *arg)
{
    ......
    allocator_wait(ca, bch_allocator_push(ca, bucket));
    wake_up(&ca->set->btree_cache_wait);
    wake_up(&ca->set->bucket_wait);
    ......
}

static void bch_btree_gc(struct cache_set *c)
{
    ......
    bch_btree_gc_finish(c);
    wake_up_allocators(c);
    ......
}
```
Quoted 6 lines

Apply this patch, each GC maybe only process very few nodes, GC would last a long time if sleep 100ms each time. So, the sleep time should be calculated dynamically based on gc_cost.

At the same time, I added some cost statistics in gc_stat, hoping to provide useful information for future work.

Hi Mingzhe,

From the first glance, I feel this change may delay the small GC period, and finally result a large GC period, which is not expected.

But it is possible that my feeling is incorrect. Do you have detailed performance number about both I/O latency  and GC period, then I can have more understanding for this effort.

Quoted 9 lines

BTW, I will add this patch to my testing set and experience myself.

Thanks.

Coly Li

Hi Coly,

Quoted 7 lines

First, your feeling is right. Then, I have some performance number abort before and after this patch.
Since the mailing list does not accept attachments, I put them on the gist.

Please visit the page for details:
https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5
mingzhe

The graphs certainly show that peak latency is much lower, that is improvement, and dmesg shows the avail_nbuckets stays about the same so GC is keeping up.

Questions:

1. Why is the after-"BW NO GC" graph so much flatter than the before-"BW NO GC" graph? I would expect your control measurements to be about the same before vs after. You might blkdiscard the cachedev and re-format between runs in case the FTL is getting in the way, or maybe something in the patch is affecting the "NO GC" graphs.

2. I wonder how the latency looks if you zoom into to the latency graph:
If you truncate the before-"LATENCY DO GC" graph at 3000 us then how does the average latency look between the two?

3. This may be solved if you can fix the control graph issue in #1, but the before vs after of "BW DO GC" shows about a 30% decrease in bandwidth performance outside of the GC spikes. "IOPS DO GC" is lower with the patch too. Do you think that your dynamic incremental gc algorithm be tuned to deal with GC latency and still provide nearly the same IOPS and bandwidth as before?

--
Eric Wheeler

Quoted 8 lines
Quoted 6 lines

[snipped]

#4 lore raw
Quoted 34 lines · Eric Wheeler
Quoted 22 lines · Zou Mingzhe
Quoted 10 lines · Coly Li

On 5/11/22 3:39 PM, [email protected] wrote:
Hi Mingzhe,

From the first glance, I feel this change may delay the small GC period, and
finally result a large GC period, which is not expected.

But it is possible that my feeling is incorrect. Do you have detailed performance number about both I/O latency  and GC period, then I can have more understanding for this effort.

Quoted 9 lines

BTW, I will add this patch to my testing set and experience myself.

Thanks.

Coly Li

Hi Coly,

Quoted 7 lines

First, your feeling is right. Then, I have some performance number abort before and after this patch.
Since the mailing list does not accept attachments, I put them on the gist.

Please visit the page for details:
“https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5” mingzhe

The graphs certainly show that peak latency is much lower, that is improvement, and dmesg shows the avail_nbuckets stays about the same so GC is keeping up.

Quoted 7 lines

Questions:

1. Why is the after-"BW NO GC" graph so much flatter than the before-"BW NO GC" graph? I would expect your control measurements to be about the same before vs after. You might blkdiscard the cachedev and re-format between runs in case the FTL is getting in the way, or maybe something in the patch is affecting the "NO GC" graphs.

Hi Eric,

First, I re-format the disk with make-bcache before each fio. Then, the graph after "BW NO GC" is much flatter than the graph before "BW NO GC", I think you may have seen another patch (bcache: allow allocator invalidate bucket in gc) I pushed . I also noticed a drop in iops of at least 20%, but we added a lot of patches between before and after, so it will take some time to figure out which patch is causing it.

Quoted 4 lines

2. I wonder how the latency looks if you zoom into to the latency graph:
If you truncate the before-"LATENCY DO GC" graph at 3000 us then how does the average latency look between the two?

I will test the performance numbers for each patch one by one, and provide more detailed graph and number later.

mingzhe

Quoted 19 lines

3. This may be solved if you can fix the control graph issue in #1, but the before vs after of "BW DO GC" shows about a 30% decrease in bandwidth performance outside of the GC spikes. "IOPS DO GC" is lower with the patch too. Do you think that your dynamic incremental gc algorithm be tuned to deal with GC latency and still provide nearly the same IOPS and bandwidth as before?

--
Eric Wheeler

Quoted 5 lines
Quoted 5 lines

[snipped]

#5 lore raw
Quoted 21 lines · Zou Mingzhe
Quoted 20 lines · Eric Wheeler

On Fri, 20 May 2022, Zou Mingzhe wrote:

Questions:

1. Why is the after-"BW NO GC" graph so much flatter than the before-"BW NO GC" graph?  I would expect your control measurements to be about the same before vs after.  You might blkdiscard the cachedev and re-format between runs in case the FTL is getting in the way, or maybe something in the patch is affecting the "NO GC" graphs.
2. I wonder how the latency looks if you zoom into to the latency graph:
    If you truncate the before-"LATENCY DO GC" graph at 3000 us then how does the average latency look between the two?
3. This may be solved if you can fix the control graph issue in #1, but the before vs after of "BW DO GC" shows about a 30% decrease in bandwidth performance outside of the GC spikes.  "IOPS DO GC" is lower with the patch too.  Do you think that your dynamic incremental gc algorithm be tuned to deal with GC latency and still provide nearly the same IOPS and bandwidth as before?

Quoted 2 lines
Quoted 2 lines
Signature · 1 line
Eric Wheeler

Hi Eric,

I have done a retest round and update all data on "https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5".

First, there is only this patch between before and after, I re-format the disk with make-bcache before each fio. Each case was tested 5 times, and the results are as follows:

                    before after
      NO GC           DO GC          NO GC          DO GC 1    99162.29     97366.28     99970.89     98290.81 2    99897.80     97879.99     96829.14     95548.88 3    98183.49     98834.29     101508.06   98581.53 4    98563.17     98476.61     96866.40     96676.87 5    97059.91     98356.50     96248.10     94442.61

Some details are also shown in the new graph, in addition to the raw data available for download.

I confirm that this patch does not cause a drop in iops. We have some other patches that may have affected the previous test, but this patch works fine.

In fact, we mostly modified the gc handling.

mingzhe

#6 lore raw
Quoted 42 lines · Zou Mingzhe
Quoted 21 lines · Zou Mingzhe
Quoted 20 lines · Eric Wheeler

On Fri, 20 May 2022, Zou Mingzhe wrote:

Questions:

1. Why is the after-"BW NO GC" graph so much flatter than the before-"BW NO GC" graph?  I would expect your control measurements to be about the same before vs after.  You might blkdiscard the cachedev and re-format between runs in case the FTL is getting in the way, or maybe something in the patch is affecting the "NO GC" graphs.
2. I wonder how the latency looks if you zoom into to the latency graph:
    If you truncate the before-"LATENCY DO GC" graph at 3000 us then how does the average latency look between the two?
3. This may be solved if you can fix the control graph issue in #1, but the before vs after of "BW DO GC" shows about a 30% decrease in bandwidth performance outside of the GC spikes.  "IOPS DO GC" is lower with the patch too.  Do you think that your dynamic incremental gc algorithm be tuned to deal with GC latency and still provide nearly the same IOPS and bandwidth as before?

Quoted 2 lines
Quoted 2 lines
Signature · 1 line
Eric Wheeler

Hi Eric,

I have done a retest round and update all data on "https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5".

First, there is only this patch between before and after, I re-format the disk with make-bcache before each fio. Each case was tested 5 times, and the results are as follows:

                    before after
      NO GC           DO GC          NO GC          DO GC 1    99162.29     97366.28     99970.89     98290.81 2    99897.80     97879.99     96829.14     95548.88 3    98183.49     98834.29     101508.06   98581.53 4    98563.17     98476.61     96866.40     96676.87 5    97059.91     98356.50     96248.10     94442.61

Quoted 5 lines

Some details are also shown in the new graph, in addition to the raw data available for download.

I confirm that this patch does not cause a drop in iops. We have some other patches that may have affected the previous test, but this patch works fine.

Looks great, glad to see that it performs well!

What is the 3000us spike on the "after" line of "LATENCY DO GC" at about t=40s ? There is a drop in IOPS and BW on the other graphs at t=40s, too, but I don't see the same behavior on the "NO GC" side.

-Eric

Quoted 14 lines

In fact, we mostly modified the gc handling.

mingzhe

#7 lore raw
Quoted 47 lines · Eric Wheeler
Quoted 41 lines · Zou Mingzhe
Quoted 21 lines · Zou Mingzhe
Quoted 20 lines · Eric Wheeler

On Fri, 20 May 2022, Zou Mingzhe wrote:

Questions:

1. Why is the after-"BW NO GC" graph so much flatter than the before-"BW NO GC" graph?  I would expect your control measurements to be about the same before vs after.  You might blkdiscard the cachedev and re-format between runs in case the FTL is getting in the way, or maybe something in the patch is affecting the "NO GC" graphs.
2. I wonder how the latency looks if you zoom into to the latency graph:
    If you truncate the before-"LATENCY DO GC" graph at 3000 us then how does the average latency look between the two?
3. This may be solved if you can fix the control graph issue in #1, but the before vs after of "BW DO GC" shows about a 30% decrease in bandwidth performance outside of the GC spikes.  "IOPS DO GC" is lower with the patch too.  Do you think that your dynamic incremental gc algorithm be tuned to deal with GC latency and still provide nearly the same IOPS and bandwidth as before?

Quoted 2 lines
Quoted 2 lines
Signature · 1 line
Eric Wheeler

Hi Eric,

I have done a retest round and update all data on "https://gist.github.com/zoumingzhe/69a353e7c6fffe43142c2f42b94a67b5".

First, there is only this patch between before and after, I re-format the disk with make-bcache before each fio. Each case was tested 5 times, and the results are as follows:

                    before after
      NO GC           DO GC          NO GC          DO GC
1    99162.29     97366.28     99970.89     98290.81 2    99897.80     97879.99     96829.14     95548.88 3    98183.49     98834.29     101508.06   98581.53 4    98563.17     98476.61     96866.40     96676.87 5    97059.91     98356.50     96248.10     94442.61

Quoted 5 lines

Some details are also shown in the new graph, in addition to the raw data available for download.

I confirm that this patch does not cause a drop in iops. We have some other patches that may have affected the previous test, but this patch works fine.

Quoted 8 lines

Looks great, glad to see that it performs well!

What is the 3000us spike on the "after" line of "LATENCY DO GC" at about t=40s ? There is a drop in IOPS and BW on the other graphs at t=40s, too, but I don't see the same behavior on the "NO GC" side.

-Eric

Hi, Eric

I tested each case 5 times and used the last result to make this graph, you can check the raw data.

The first 4 times results also have graph in the raw data, you can also find some spikes over  2000us on the "NO GC" side.

So, I don't think the 3000us "spike" at 40s are a problem, it just looks like a system fluctuation.

mingzhe

Quoted 11 lines
Quoted 11 lines

In fact, we mostly modified the gc handling.

mingzhe