Free strings during BGSAVE/BGAOFRW to reduce copy-on-write by poiuj · Pull Request #905 · valkey-io/valkey

poiuj · 2024-08-13T17:24:43Z

Motivation

Copy-on-write (COW) amplification refers to the issue where writing to a small object leads to the entire page being cloned, resulting in inefficient memory usage. This issue arises during the BGSAVE process, which can be particularly problematic on instances with limited memory. If the BGSAVE process could release unneeded memory, it could reduce memory consumption. To address this, the BGSAVE process calls the madvise function to signal the operating system to reclaim the buffer. However, this approach does not work for buffers smaller than a page (usually 4KiB). Even after multiple such calls, where a full page may be free, the operating system will not reclaim it.
To solve this issue, we can call zfree directly. This allows the allocator (jemalloc) to handle the bookkeeping and release pages when buffers are no longer needed. This approach reduces copy-on-write events.

Benchmarks
To understand how usage of zfree affects BGSAVE and the memory consumption I ran 45 benchmarks that compares my clonewith the vanilla version. The benchmark has the following steps:

Start a new Valkey process
Fill the DB with data sequentially
Run a warmup to randomize the memory layout
Introduce fragmentation by deleting part of the keys
In parallel:
1. Trigger BGSAVE
2. Start 80/20 get/set load

I played the following parameters to understand their influence:

Number of keys: 3M, 6M, and 12M.
Data size. While key themselves are of fixed length ~30 bytes, the value size is 120, 250, 500, 1000, and 2000 bytes.
Fragmentation. I delete 5%, 10%, and 15% of the original key range.

I'm attaching a graph of BGSAVE process memory consumption. Instead of all benchmarks, I show the most representative runs IMO.

For 2000 bytes values peak memory usage is ~53% compared to vanilla. The peak happens at 57% BGSAVE progress.
For 500 bytes values the peak is ~80% compared to vanilla. And happens at ~80% progress.
For 120 bytes the difference is under 5%, and the patched version could even use more memory.

For 12M keys, the peak is ~85% of the vanilla’s. Happens at ~70% mark.
For 6M keys, the peak is ~87% of the vanilla’s. Happens at ~77% mark.
For 3M keys, the peak is ~87% of the vanilla’s Happens at ~80% mark.

Changes

The PR contains 2 changes:

Static buffer for RDB comrpession.
RDB compression leads to COW events even without any write load if we use zfree. It happens because the compression functions allocates a new buffer for each object. Together with freeing objects with zfree it leads to reusing of the memory shared with the main process.
To deal with this problem, we use a pre-allocated constant 8K buffer for compression. If the object size is too big for this buffer, than we fall back to the ad hoc allocation behavior.
Freeing string objects instead of dismissing them
Call to zfree is more expensive than direct call to madvise. But with Add zfree_with_size to optimize sdsfree since we can get zmalloc_size from the header #453 strings use the fast path – zfree_with_size. As a possible next step we can optimize zfree for other data types as well.

Lazily allocate 8KiB buffer to use for compression. This buffer should be large enough for most cases. When a larger buffer is required, rdbSaveLzfStringObject falls back to the ad hoc allocation. This change goes together with the further change that introduces freeing string objects during BGSAVE. It greatly decreases the number of COW events. Otherwise compression allocations reuses the memory freed by string objects. Which leads to COW. Signed-off-by: Vadym Khoptynets <[email protected]>

Instead of dismissing with madvise(MADV_DONTNEED) we free it via the allocator. This has advantage that it allows the allocator to accumulate free buffers to free whole pages. While madvise is nop if the buffer is less than a page. The allocator overhead is minimal, because raw strings (sds) use the fast path. Signed-off-by: Vadym Khoptynets <[email protected]>

codecov · 2024-08-13T23:49:44Z

Codecov Report

All modified and coverable lines are covered by tests ✅

Project coverage is 70.74%. Comparing base (a939cb8) to head (b4446ec).
Report is 6 commits behind head on unstable.

Additional details and impacted files

@@             Coverage Diff              @@
##           unstable     #905      +/-   ##
============================================
+ Coverage     70.59%   70.74%   +0.14%     
============================================
  Files           117      118       +1     
  Lines         63324    63386      +62     
============================================
+ Hits          44704    44841     +137     
+ Misses        18620    18545      -75

Files with missing lines	Coverage Δ
src/object.c	`79.15% <100.00%> (ø)`
src/rdb.c	`76.57% <100.00%> (+0.32%)`	⬆️

... and 19 files with indirect coverage changes

madolson · 2024-10-07T22:31:18Z

I guess a general concern I have is that all of these benchmarks are run on systems that are being stressed. What if the write rate is very low, would we be increasing the CoW usage in the vast majority of cases?

ranshid · 2024-10-09T10:57:16Z

I guess a general concern I have is that all of these benchmarks are run on systems that are being stressed. What if the write rate is very low, would we be increasing the CoW usage in the vast majority of cases?

@madolson if the system is not stressed, is that a very big issue if the CoW is increased?

lets try and define the extra tests we need in order to gain more confidence?
like :

use different value sizes (very small, medium, large)
Test the impact on CoW on idle system
Test performance impact (?)

also IMO @poiuj provided some supporting data, but I think we probably need to improve the results visualization

poiuj · 2024-10-10T16:06:31Z

COW numbers for idle system with 3M keys, depending on value size:
3 bytes values – 0 MiB
45 bytes values – 4 MiB (~1.1% of the memory usage reported by valkey)
100 bytes values – 5 MiB (~0.9%)
250 bytes values – 27 MiB (~2.9%)
500 bytes values – 50 MiB (~3%)
1000 bytes values – 100 MiB (~3.2%)

The overhead seems to be in range of 1-3% approximately.

uriyage · 2024-11-24T15:34:07Z

    comprlen = lzf_compress(s, len, out, outlen);
    if (comprlen == 0) {
-        zfree(out);
+        if (outlen >= LZF_STATIC_BUFFER_SIZE) zfree(out);


Consider: if (out != buffer) zfree(out); it is more clear.

And maybe to avoid the code duplication:

comprlen = lzf_compress(s, len, out, outlen); ssize_t nwritten = comprlen > 0 ? rdbSaveLzfBlob(rdb, out, comprlen, len) :0; if (out != buffer) zfree(out); return nwritten;

uriyage · 2024-11-24T15:34:11Z

 #define RDB_LOAD_ERR_OTHER 2     /* Any other errors */

+/* Size of the static buffer used for rdbcompression */
+#define LZF_STATIC_BUFFER_SIZE (8 * 1024)


consider moving LZF_STATIC_BUFFER_SIZE to rdb.c since it's only used internally

Signed-off-by: Vadym Khoptynets <[email protected]>

ranshid

I like the improvement.
I think that:

we should make sure to test AOF as well
can we bold out the save times in the data collected. they mostly look the same, but I want to make sure we do not sacrifice save time for the memory peak.

ranshid

LGTM

ranshid · 2024-11-27T16:19:31Z

@valkey-io/core-team LGTM but maybe someone has any other concerns?

enjoy-binbin

LGTM, the top commet does not seem to mention the static buffer in lzf

ranshid · 2024-11-27T16:28:25Z

@poiuj can you please check how on earth did the git misspelled your name on the signoff?
the last commiter name is spelled: Vadym Khoptyents
Please ammend the commit in order to satisfy DCO

ranshid · 2024-11-27T16:29:55Z

LGTM, the top commet does not seem to mention the static buffer in lzf

@poiuj lets bring that up in the top comment

This will capture more cases. E.g. hashes. Signed-off-by: Vadym Khoptynets <[email protected]>

poiuj · 2024-11-27T17:07:50Z

The compression change is mentioned in the top comment:

Static buffer for RDB comrpession.
RDB compression leads to COW events even without any write load if we use zfree. It happens because the compression functions allocates a new buffer for each object. Together with freeing objects with zfree it leads to reusing of the memory shared with the main process.
To deal with this problem, we use a static buffer for compression. If the object size is too big for the static buffer, than it falls back to the ad hoc allocation behavior.

@enjoy-binbin @ranshid can you suggest how to clarify the message here?

ranshid · 2024-11-27T17:18:34Z

The compression change is mentioned in the top comment:

Static buffer for RDB comrpession.
RDB compression leads to COW events even without any write load if we use zfree. It happens because the compression functions allocates a new buffer for each object. Together with freeing objects with zfree it leads to reusing of the memory shared with the main process.
To deal with this problem, we use a static buffer for compression. If the object size is too big for the static buffer, than it falls back to the ad hoc allocation behavior.

@enjoy-binbin @ranshid can you suggest how to clarify the message here?

Maybe just mention that you use a constant 8K buffer to hold the comressed size.

ranshid · 2024-11-28T06:05:50Z

@poiuj one thought I just realized is that we are targetting this as a use when JEMalloc is the allocator right? in case we use libc malloc will this introduce a degradation?
Noyt sure HOW important it is to avoid degradation since IMO for any operational installation of valkey jemalloc will probably be used, but maybe we can limit this optimization to JEMAlloc case?

zuiderkwast · 2024-11-28T09:06:04Z

in case we use libc malloc will this introduce a degradation?
Noyt sure HOW important it is to avoid degradation since IMO for any operational installation of valkey jemalloc will probably be used, but maybe we can limit this optimization to JEMAlloc case?

Let's test it with libc malloc before we decide to use conditional code. Maybe it's good for other allocators too..? Btw, libc malloc is different on linux vs freebsd vs macos. (Freebsd's libc malloc is actually jemalloc.)

ranshid · 2024-11-28T11:59:40Z

in case we use libc malloc will this introduce a degradation?
Noyt sure HOW important it is to avoid degradation since IMO for any operational installation of valkey jemalloc will probably be used, but maybe we can limit this optimization to JEMAlloc case?

Let's test it with libc malloc before we decide to use conditional code. Maybe it's good for other allocators too..? Btw, libc malloc is different on linux vs freebsd vs macos. (Freebsd's libc malloc is actually jemalloc.)

Yes. I know about the difference platforms and I agree we better test for it. But I also do not feel very strongly about not offering this only for jemalloc in order to reduce the blast. We often provide many changes which are jemalloc biased since this is practically the production level used allocator.

poiuj · 2024-11-28T13:20:22Z

I've run the benchmark with libc and there is no effect. It doesn't worth to complicate the code with turning off for other allocators.

ranshid · 2024-11-28T14:17:53Z

I've run the benchmark with libc and there is no effect. It doesn't worth to complicate the code with turning off for other allocators.

While I agree about code complications, as @zuiderkwast correctly mentioned it might be different impact on different platforms. I only think that if we are not going to test it on all common platforms we should atleast state that on the release notes. @zuiderkwast WDYT?

ranshid · 2024-11-28T14:24:46Z

note - taking off the run-extra-tests flag, we already have extended tests coverage

ranshid · 2024-11-28T14:29:50Z

-    if (o->encoding == OBJ_ENCODING_RAW) {
-        dismissSds(o->ptr);
-    }
+    freeStringObject(o);


BTW - why do we need to keep the freeStringObject here?

Suggested change

freeStringObject(o);

if (o->encoding == OBJ_ENCODING_RAW) {

dismissSds(o->ptr);

}

We still use freeStringObject in decrRefCount. So this decision is extra call vs repeating code. I prefer the extra call as compiler can optimize that, while we avoid repeating the code.

I am not sure what repeating code or extra call in this context. I just thought to keep this function as it was before since the change can only be done in dismissSds.
I do not see any issue with this change so I approved it. probably not worth the debate :)

Apparently I misunderstood you. I took the change.

poiuj · 2024-11-28T14:30:23Z

The failing test passes for me locally. Talked to @ranshid about it. It's related to another issue.

zuiderkwast · 2024-11-28T15:31:51Z

I've run the benchmark with libc and there is no effect. It doesn't worth to complicate the code with turning off for other allocators.

@poiuj That's great.

While I agree about code complications, as @zuiderkwast correctly mentioned it might be different impact on different platforms. I only think that if we are not going to test it on all common platforms we should atleast state that on the release notes. @zuiderkwast WDYT?

@ranshid I'm fine with just mentioning this change in release notes. We don't test all possible impacts on all possible platforms.

hwware · 2024-11-28T17:37:23Z

@poiuj Can you run a fully daily CI in your repo, we just want to ensure the test can be passed in every platform (This is only concern from my side).

ranshid · 2024-12-01T13:36:53Z

@poiuj Can you run a fully daily CI in your repo, we just want to ensure the test can be passed in every platform (This is only concern from my side).

@hwware We already had the daily runs running on this PR: https://github.com/valkey-io/valkey/actions/runs/12067940597/job/33651977697
The only failed test was related to aknown issue related to the last defrag changes and not new to this PR. I removed the tag in order to save unneeded excutions. I spoke with @zuiderkwast offline and we both agree this is fine to be merged now, given we add a note in the release notes about the fact that the change is optimizing JEMalloc builds and although not tested on all platforms we did not notice any degradation using other allocators.

Co-authored-by: Viktor Söderqvist <[email protected]> Signed-off-by: ranshid <[email protected]>

Signed-off-by: Vadym Khoptynets <[email protected]>

poiuj added 2 commits August 12, 2024 18:25

madolson reviewed Oct 7, 2024

View reviewed changes

Comment thread src/rdb.c

madolson requested a review from ranshid November 22, 2024 03:28

uriyage reviewed Nov 24, 2024

View reviewed changes

Simplify rdbSaveLzfStringObject and move LZF_STATIC_BUFFER_SIZE to rdb.c

c160e1d

Signed-off-by: Vadym Khoptynets <[email protected]>

poiuj force-pushed the unstable branch from 6005959 to c160e1d Compare November 24, 2024 23:14

ranshid reviewed Nov 26, 2024

View reviewed changes

Comment thread src/object.c Outdated

poiuj force-pushed the unstable branch from a1256b6 to 9371f6e Compare November 27, 2024 15:36

ranshid approved these changes Nov 27, 2024

View reviewed changes

enjoy-binbin added the run-extra-tests Run extra tests on this PR (Runs all tests from daily except valgrind and RESP) label Nov 27, 2024

enjoy-binbin approved these changes Nov 27, 2024

View reviewed changes

enjoy-binbin changed the title ~~Free strings during BGSAVE~~ Free strings during BGSAVE/BGAOFRW to reduce copy-on-write Nov 27, 2024

zuiderkwast reviewed Nov 27, 2024

View reviewed changes

Comment thread src/object.c

Dismiss SDS instead of string object

be4a5d7

This will capture more cases. E.g. hashes. Signed-off-by: Vadym Khoptynets <[email protected]>

poiuj force-pushed the unstable branch from 9371f6e to be4a5d7 Compare November 27, 2024 17:01

Merge branch 'valkey-io:unstable' into unstable

8777467

ranshid added the release-notes This issue should get a line item in the release notes label Nov 28, 2024

ranshid removed the run-extra-tests Run extra tests on this PR (Runs all tests from daily except valgrind and RESP) label Nov 28, 2024

ranshid reviewed Nov 28, 2024

View reviewed changes

zuiderkwast reviewed Nov 28, 2024

View reviewed changes

Comment thread src/object.c Outdated

ranshid and others added 2 commits December 1, 2024 15:45

Update src/object.c

ac504ca

Co-authored-by: Viktor Söderqvist <[email protected]> Signed-off-by: ranshid <[email protected]>

Revert the change in dismissStringObject

b4446ec

Signed-off-by: Vadym Khoptynets <[email protected]>

ranshid merged commit 90475af into valkey-io:unstable Dec 1, 2024

YangboLong mentioned this pull request May 25, 2026

Reduce BGSAVE/AOF COW by freeing SDS strings in fork child instead of madvise redis/redis#15260

Open

Uh oh!

Conversation

poiuj commented Aug 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

codecov Bot commented Aug 13, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Codecov Report

Uh oh!

Uh oh!

madolson commented Oct 7, 2024

Uh oh!

ranshid commented Oct 9, 2024

Uh oh!

poiuj commented Oct 10, 2024

Uh oh!

uriyage Nov 24, 2024

Choose a reason for hiding this comment

Uh oh!

uriyage Nov 24, 2024

Choose a reason for hiding this comment

Uh oh!

ranshid left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ranshid left a comment

Choose a reason for hiding this comment

Uh oh!

ranshid commented Nov 27, 2024

Uh oh!

enjoy-binbin left a comment

Choose a reason for hiding this comment

Uh oh!

ranshid commented Nov 27, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ranshid commented Nov 27, 2024

Uh oh!

Uh oh!

poiuj commented Nov 27, 2024

Uh oh!

ranshid commented Nov 27, 2024

Uh oh!

ranshid commented Nov 28, 2024

Uh oh!

zuiderkwast commented Nov 28, 2024

Uh oh!

ranshid commented Nov 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

poiuj commented Nov 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ranshid commented Nov 28, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ranshid commented Nov 28, 2024

Uh oh!

ranshid Nov 28, 2024

Choose a reason for hiding this comment

Uh oh!

ranshid Nov 28, 2024

Choose a reason for hiding this comment

Uh oh!

poiuj Nov 28, 2024

Choose a reason for hiding this comment

Uh oh!

ranshid Dec 1, 2024

Choose a reason for hiding this comment

Uh oh!

poiuj Dec 1, 2024

Choose a reason for hiding this comment

Uh oh!

poiuj commented Nov 28, 2024

Uh oh!

zuiderkwast commented Nov 28, 2024

Uh oh!

Uh oh!

hwware commented Nov 28, 2024

poiuj commented Aug 13, 2024 •

edited

Loading

codecov Bot commented Aug 13, 2024 •

edited

Loading

ranshid commented Nov 27, 2024 •

edited

Loading

ranshid commented Nov 28, 2024 •

edited

Loading

poiuj commented Nov 28, 2024 •

edited

Loading

ranshid commented Nov 28, 2024 •

edited

Loading