Replace all usage of ziplist with listpack for t_zset by sundb · Pull Request #9366 · redis/redis

sundb · 2021-08-12T11:41:20Z

Part two of implementing #8702 (zset), after #8887.

Description of the feature

Replaced all uses of ziplist with listpack in t_zset, and optimized some of the code to optimize performance.

Rdb format changes

New RDB_TYPE_ZSET_LISTPACK rdb type.

Rdb loading improvements:

Pre-expansion of dict for validation of duplicate data for listpack and ziplist.
Simplifying the release of empty key objects when RDB loading.
Unify ziplist and listpack data verify methods for zset and hash, and move code to rdb.c.

Interface changes

New zset-max-listpack-entries config is an alias for zset-max-ziplist-entries (same with zset-max-listpack-value).
OBJECT ENCODING will return listpack instead of ziplist.

Listpack improvements:

Add lpDeleteRange and lpDeleteRangeWithEntry functions to delete a range of entries from listpack.
Improve the performance of lpCompare, converting from string to integer is faster than converting from integer to string.
Replace snprintf with ll2string to improve performance in converting numbers to strings in lpGet().

Zset improvements:

Improve the performance of zzlFind method, use lpFind instead of lpCompare in a loop.
Use lpDeleteRangeWithEntry instead of lpDelete twice to delete a element of zset.

Tests

Add some unittests for lpDeleteRange and lpDeleteRangeWithEntry function.
Add zset RDB loading test.
Add benchmark test for lpCompare and ziplsitCompare.
Add empty listpack zset corrupt dump test.

oranagra

few minor comments and suggestions..

src/aof.c

oranagra · 2021-08-13T13:24:34Z

src/listpack.c

+        while (i--) {
+            tail = lpNext(lp, tail);
+            assert(p != NULL);
+        }


despite the fact we have a previous check if num is too big, i think we still need to handle a case we reached to the end of the listpack in the middle of that loop (lpLength may be unreliable).
in which case we'll also need to update num since it's used below.
also, why change long to int ?

Ohh, I forgot to corrupt data.
long to int was my mistake.

Done, This piece of code is obsolete.

src/rdb.c

oranagra · 2021-08-13T13:37:33Z

src/rdb.c

                if (deep_integrity_validation) server.stat_dump_payload_sanitizations++;
-                if (!zsetZiplistValidateIntegrity(encoded, encoded_len, deep_integrity_validation)) {
-                    rdbReportCorruptRDB("Zset ziplist integrity check failed.");
+                if (!listpackValidateIntegrity(encoded, encoded_len, deep_integrity_validation)) {


we shouldn't use the plain listpackValidateIntegrity, that one doesn't check for duplicate records.

I think my naming caused your misunderstanding(lpValidateIntegrity is in listpack.c), perhaps it should be changed to hashAndZsetZiplistValidateIntegrity.

yes, i've been mixing lpValidateIntegrity and listpackValidateIntegrity. you must admit that it's confusing 8-)
so you renamed and moved hashListpackValidateIntegrity to serve as common code.
in the past, with ziplists, i've let hash and ziplist have separate integrity validation, just to let them be independent.

our options:

rename your new listpackValidateIntegrity, either to lpPaisValidateIntegrityAndDups or something alike (it's not a generic listpack validation)

move it back to hash and zset to be independently (like before).

i'm ok with option 1.

I prefer 1, because I hate repetitive code.

Done, change to lpPairsValidateIntegrityAndDups.

oranagra · 2021-08-13T13:53:09Z

src/t_zset.c

    /* TODO: add function to ziplist API to delete N elements from offset. */
-    zl = ziplistDelete(zl,&p);
-    zl = ziplistDelete(zl,&p);
+    zl = lpDelete(zl,p,&p);
+    zl = lpDelete(zl,p,&p);


you can now use the new method you created to implement that TODO

I thought about it, but lpDeleteRange uses index for deletion, and I actually wanted to write lpDeleteEntryRange, but I didn't like the name, need help.

Done, Change all similar code for deleting 2 elements.

src/t_zset.c

oranagra · 2021-08-13T14:01:06Z

tests/integration/corrupt-dump.tcl

            verify_log_message 0 "*skipping empty key: zset_ziplist*" 0
-            verify_log_message 0 "*empty keys skipped: 8*" 0
+            verify_log_message 0 "*skipping empty key: zset_listpack*" 0


are there really both types of encoded zsets in the same rdb file? how did you generate it?

I used debug populate to generate it, and modified the saved code.

// zset ziplist robj *o = createObject(OBJ_ZSET,ziplistNew()); o->encoding = OBJ_ENCODING_LISTPACK; dbAdd(c->db,createStringObject("zset_ziplist",12),o); // zset ziplist dbAdd(c->db,createStringObject("zset_listpack",13),createZsetListpackObject());

sundb · 2021-08-16T03:45:12Z

Following are the benchmarking results for loading rdb under different scenarios.
The result is the same as #8887 (comment), i.e. the loading speed depends only on the number of ziplists and is independent of the size of the ziplist entry.

key num	entries num of one element	rdb loading time without convert	rdb loading time with convert
500000	128	6.316s	18.164s
500000	64	3.745s	9.572s
500000	32	2.057s	5.293s
1000000	128	12.498s	32.786s
1000000	64	6.535s	17.399s
1000000	32	3.533s	8.814s

oranagra · 2021-08-16T10:17:02Z

IIRC for hashes the factor was about 1.5x, and here the factor seems like 3x.
am i right? have a clue why such a difference?

sundb · 2021-08-16T10:29:40Z

IIRC for hashes the factor was about 1.5x, and here the factor seems like 3x.
am i right? have a clue why such a difference?

Ohh, My mistake, `entries num of one element` is actually the entry number of zset,
not the ziplist, so I'll have to double check.

sundb · 2021-08-16T10:52:15Z

zset benchmark test. config: `zset-max-ziplist-entries 999999` command: `./src/redis-benchmark -t zadd,zpopmin -n 50000 -r 100000000`
@oranagra I was sceptical about the test results, but I checked the code several times and found no problems, the improvement in the zpopmin test was mainly due to the zzlDelete change, I modified your suggestion to add lpDeleteRangeWithEntry, I wonder if I made a mistake in the code.

listack

zadd:

Summary: throughput summary: 2568.58 requests per second latency summary (msec): avg min p50 p95 p99 max 19.347 0.136 19.167 37.055 44.895 47.871

zpopmin:

Summary: throughput summary: 54406.96 requests per second latency summary (msec): avg min p50 p95 p99 max 0.749 0.064 0.255 1.983 2.263 2.815

ziplist

zadd:

Summary: throughput summary: 1201.63 requests per second latency summary (msec): avg min p50 p95 p99 max 41.463 0.184 34.879 88.575 103.615 167.423

zpopmin:

Summary: throughput summary: 5523.03 requests per second latency summary (msec): avg min p50 p95 p99 max 8.943 0.088 2.183 26.751 37.023 90.431

There is indeed a bug, back to my words.

sundb · 2021-08-16T16:27:11Z

The reason for the error in the previous benchmark (#9366 (comment)) is that when the listpack length exceeds UINT16_MAX, lpDeleteRangeWithEntry method call lpSetNumElements ignores the maximum length of listpack.

zset benchmark test.
config: zset-max-ziplist-entries 999999
command: ./src/redis-benchmark -t zadd,zpopmin -n 30000 -r 100000000

Note: The reason for setting -n 30000 is to avoid exceeding the maximum listpack length(65535), which will result in unrealistic benchmark results.

listack

zadd:

Summary:
  throughput summary: 4033.34 requests per second
  latency summary (msec):
          avg       min       p50       p95       p99       max
       12.276     0.176    12.087    23.535    24.815    26.703

zpopmin:

Summary:
  throughput summary: 58708.42 requests per second
  latency summary (msec):
          avg       min       p50       p95       p99       max
        0.748     0.056     0.751     1.295     1.575     2.439

ziplist

zadd:

Summary:
  throughput summary: 3012.96 requests per second
  latency summary (msec):
          avg       min       p50       p95       p99       max
       16.470     0.152    16.295    30.847    33.983   111.295

zpopmin:

Summary:
  throughput summary: 37593.98 requests per second
  latency summary (msec):
          avg       min       p50       p95       p99       max
        1.229     0.072     1.231     2.223     2.431     3.127

sundb · 2021-08-17T11:29:21Z

@oranagra In #9366 (comment).
The reason for the slow conversion is that we have deep sanitization enabled by default, which causes the hash to be rehashed several times during check dup ziplist.
I modified the ziplist and listpack validation callbacks to use head count for dict expand.
The loading speed dropped from 18s seconds to 14s.

src/listpack.c

src/ziplist.c

oranagra · 2021-08-17T18:04:34Z

src/listpack.c

+    if (numele == LP_HDR_NUMELE_UNKNOWN) {
+        /* If the listpack length cannot be obtained in constant time,
+         * using lpDeleteRangeWithEntry will be much faster. */
+        lp = lpDeleteRangeWithEntry(lp, &p, num);


i don't understand this. it looks like the alternative is doing the same (also using lpDeleteRangeWithEntry)

Yes, but if we do that, we can't use lpGetNumElements, we need to use lpLength, which will traverse the entire listpack when listpack length > UINT16_MAX. Instead, we use lpDeleteRangeWithEntry to delete the length, so it only traverses to the index.

ok, i tihnk i see what you mean.
the code below has an "optimization" to just move the EOF marker, and that optimization can't be used without knowing the real length (which in this case would require calling lpLength).
we rather not use lpLength, so instead in this case we skip the EOF "optimization" and just fall back to the normal path.

the current code and comment is confusing because it mentions we can do something faster, but the thing it's faster from, isn't at all there..
i suggest to refactor that code and improve the comment.

it can be something like:

/* If we know we're gonna delete beyond the end of the listpack, we can just move * the EOF marker, and there's no need to iterate though the entries. * but if we can't be sure how many entries there are, we rather avoid calling lpLength * since that means an additional iteration on all elements. */ if (we know the real length, and we know we're deleting beyond the range) { do the optimal thing and move the EOF } else { lpDeleteRangeWithEntry }

src/rdb.c

oranagra · 2021-08-17T18:11:29Z

@sundb so you're saying that now a loading that used to take 6 seconds takes 14 (and before that fix it used to take 18s)?
so that's about 2.0x?

did that fix also affect (improve) the conversion benchmark we did for hashes?

besides that, i see you also showed an improved performance of zsets that use listpack vs ziplists (not related to any of the commits of recent days, but rather just that listpack is better than ziplist), right?

anything else left before we can merge it? please go over the recent comment that are not yet marked as resolve and make sure they're handled, and please also update the top comment to list all the changes of this PR.

thank you!

oranagra · 2021-08-17T18:14:16Z

ohh, sorry, i see i missed one commit (1c72ad5), so the improvement are a result of a recent change.

src/listpack.c

src/t_zset.c

…nvertAndValidate

sundb · 2021-08-18T03:29:02Z

@sundb so you're saying that now a loading that used to take 6 seconds takes 14 (and before that fix it used to take 18s)?
so that's about 2.0x?

Yeah.

did that fix also affect (improve) the conversion benchmark we did for hashes?

Yes, hashes also pay off, and I'll be benchmarking hash and zset again.

oranagra

ok, so are we done?

anything else left before we can merge it?
please go over the recent comments that are not yet marked as resolve and make sure they're handled, and please also update the top comment to list all the changes of this PR.

oranagra · 2021-08-18T07:43:29Z

src/listpack.c

-        /* Note that index could overflow, but we use the value
-        * after seek, so when we use it no overflow happens. */


you may still wanna keep this comment if you think it's useful (personally i didn't dive into it)

I thought no one would care about this comment, I think it's necessary (I often confusing).

I still need to do the benchmark.

I also need to run "corrupt-dump-fuzzer " for several hours.

…ion-zset

sundb · 2021-08-19T07:49:02Z

Second Rdb loading zset benchmark test after #9366 (comment).
Early expansion of the dict used to validate ziplsit duplicates in lpPairsValidateIntegrityAndDups method(6bac662).

key num	zset length	loading without convert	loading with convert(after optimize)	loading with convert(before optimize)
500000	128	5.352s	13.821s	15.648s
500000	64	2.983s	7.225s	8.443s
500000	32	1.629s	3.835s	4.217s
1000000	128	10.977s	27.026s	31.965s
1000000	64	6.022s	14.280s	16.477s
1000000	32	3.317s	7.522s	8.708s

sundb · 2021-08-19T07:59:32Z

6bac662 also optimises the loading of the listpack with sanitation.

Following is a benchmark test for loading hash listpack.
Half of each hash is strings, and half is numbers.

key num	hash length	with sanitation(before optimize)	with sanitation(after optimize)
1000000	256	39.783s	32.496s
1000000	128	18.372s	15.125s
1000000	64	9.452s	8.029s
1000000	32	5.004s	4.460s

oranagra · 2021-09-09T09:53:44Z

@redis/core-team technically, this is a major decision, but since it follows the footsteps of the same thing we did for hashes, I'll merge this one normally.
So FYI: rdb changes, loading time conversion, etc.

sundb · 2021-09-09T10:17:43Z

@oranagra It's ready to go.
The 'corrupt-dump-fuzzer' test has been run a few times before.

Part three of implementing #8702, following #8887 and #9366 . ## Description of the feature 1. Replace the ziplist container of quicklist with listpack. 2. Convert existing quicklist ziplists on RDB loading time. an O(n) operation. ## Interface changes 1. New `list-max-listpack-size` config is an alias for `list-max-ziplist-size`. 2. Replace `debug ziplist` command with `debug listpack`. ## Internal changes 1. Add `lpMerge` to merge two listpacks . (same as `ziplistMerge`) 2. Add `lpRepr` to print info of listpack which is used in debugCommand and `quicklistRepr`. (same as `ziplistRepr`) 3. Replace `QUICKLIST_NODE_CONTAINER_ZIPLIST` with `QUICKLIST_NODE_CONTAINER_PACKED`(following #9357 ). It represent that a quicklistNode is a packed node, as opposed to a plain node. 4. Remove `createZiplistObject` method, which is never used. 5. Calculate listpack entry size using overhead overestimation in `quicklistAllowInsert`. We prefer an overestimation, which would at worse lead to a few bytes below the lowest limit of 4k. ## Improvements 1. Calling `lpShrinkToFit` after converting Ziplist to listpack, which was missed at #9366. 2. Optimize `quicklistAppendPlainNode` to avoid memcpy data. ## Bugfix 1. Fix crash in `quicklistRepr` when ziplist is compressed, introduced from #9366. ## Test 1. Add unittest for `lpMerge`. 2. Modify the old quicklist ziplist corrupt dump test. Co-authored-by: Oran Agra <[email protected]>

Part three of implementing redis#8702, following redis#8887 and redis#9366 . ## Description of the feature 1. Replace the ziplist container of quicklist with listpack. 2. Convert existing quicklist ziplists on RDB loading time. an O(n) operation. ## Interface changes 1. New `list-max-listpack-size` config is an alias for `list-max-ziplist-size`. 2. Replace `debug ziplist` command with `debug listpack`. ## Internal changes 1. Add `lpMerge` to merge two listpacks . (same as `ziplistMerge`) 2. Add `lpRepr` to print info of listpack which is used in debugCommand and `quicklistRepr`. (same as `ziplistRepr`) 3. Replace `QUICKLIST_NODE_CONTAINER_ZIPLIST` with `QUICKLIST_NODE_CONTAINER_PACKED`(following redis#9357 ). It represent that a quicklistNode is a packed node, as opposed to a plain node. 4. Remove `createZiplistObject` method, which is never used. 5. Calculate listpack entry size using overhead overestimation in `quicklistAllowInsert`. We prefer an overestimation, which would at worse lead to a few bytes below the lowest limit of 4k. ## Improvements 1. Calling `lpShrinkToFit` after converting Ziplist to listpack, which was missed at redis#9366. 2. Optimize `quicklistAppendPlainNode` to avoid memcpy data. ## Bugfix 1. Fix crash in `quicklistRepr` when ziplist is compressed, introduced from redis#9366. ## Test 1. Add unittest for `lpMerge`. 2. Modify the old quicklist ziplist corrupt dump test. Co-authored-by: Oran Agra <[email protected]>

Remove some dead code in object.c, ziplist is no longer used in 7.0 Some backgrounds: zipmap - hash: replaced by ziplist in redis#285 ziplist - hash: replaced by listpack in redis#8887 ziplist - zset: replaced by listpack in redis#9366 ziplist - list: replaced by quicklist (listpack) in redis#2143 / redis#9740

Remove some dead code in object.c, ziplist is no longer used in 7.0 Some backgrounds: zipmap - hash: replaced by ziplist in #285 ziplist - hash: replaced by listpack in #8887 ziplist - zset: replaced by listpack in #9366 ziplist - list: replaced by quicklist (listpack) in #2143 / #9740 Moved the location of ziplist.h in the server.c

Remove some dead code in object.c, ziplist is no longer used in 7.0 Some backgrounds: zipmap - hash: replaced by ziplist in redis#285 ziplist - hash: replaced by listpack in redis#8887 ziplist - zset: replaced by listpack in redis#9366 ziplist - list: replaced by quicklist (listpack) in redis#2143 / redis#9740 Moved the location of ziplist.h in the server.c

sundb force-pushed the listpack-migration-zset branch from d33a9c8 to c77f56e Compare August 12, 2021 12:29

Replace all usage of ziplist with listpack for t_zset

91213f5

sundb force-pushed the listpack-migration-zset branch from c77f56e to 91213f5 Compare August 12, 2021 12:54

oranagra reviewed Aug 13, 2021

View reviewed changes

sundb marked this pull request as draft August 13, 2021 17:27

sundb force-pushed the listpack-migration-zset branch from 3184d20 to 34a9508 Compare August 16, 2021 03:16

Fix CR & Add lpDeleteRangeWithEntry to delete a pair of element

6a45efa

sundb force-pushed the listpack-migration-zset branch from 34a9508 to 6a45efa Compare August 16, 2021 03:20

Speedup lpCompare and zzlFind

1c72ad5

sundb marked this pull request as ready for review August 16, 2021 11:16

Fix wrongly use of lpSetNumElements

8393d42

sundb force-pushed the listpack-migration-zset branch from 089ce2d to 05d6358 Compare August 17, 2021 11:36

Speedup validate dup of ziplist and listpack

6bac662

sundb force-pushed the listpack-migration-zset branch from 05d6358 to 6bac662 Compare August 17, 2021 13:23

oranagra reviewed Aug 17, 2021

View reviewed changes

src/listpack.c Outdated Show resolved Hide resolved

src/ziplist.c Outdated Show resolved Hide resolved

oranagra reviewed Aug 17, 2021

View reviewed changes

src/listpack.c Show resolved Hide resolved

src/t_zset.c Show resolved Hide resolved

Rename _ziplistPairsEntryConvertAndValidation to _ziplistPairsEntryCo…

ea0ed69

…nvertAndValidate

sundb force-pushed the listpack-migration-zset branch from 467ac3a to ea0ed69 Compare August 18, 2021 01:57

sundb force-pushed the listpack-migration-zset branch from ee2956a to 8873fd8 Compare August 18, 2021 06:06

Fix CR & Replace snprintf with ll2string in lpGet

a97a98f

sundb force-pushed the listpack-migration-zset branch from 1f391b9 to b22020d Compare August 18, 2021 07:41

oranagra reviewed Aug 18, 2021

View reviewed changes

sundb added 5 commits August 18, 2021 00:53

Re-add comment

a41a140

Change config & Fix comment, typo

73b62fe

Fix listpack length check in lpDeleteRange & Fix memory leak

9adbefb

Fix typos in ziplsit unittest

852b687

Merge remote-tracking branch 'upstream/unstable' into listpack-migrat…

678a592

…ion-zset

Remove obsolete comment

5572661

oranagra approved these changes Aug 19, 2021

View reviewed changes

Merge branch 'redis:unstable' into listpack-migration-zset

e05a6a7

oranagra added the state:to-be-merged The PR should be merged soon, even if not yet ready, this is used so that it won't be forgotten label Sep 9, 2021

oranagra merged commit 3ca6972 into redis:unstable Sep 9, 2021

sundb deleted the listpack-migration-zset branch September 10, 2021 01:55

oranagra added the state:major-decision Requires core team consensus label Sep 12, 2021

sundb mentioned this pull request Nov 5, 2021

Replace ziplist with listpack in quicklist #9740

Merged

2 tasks

oranagra added the release-notes indication that this issue needs to be mentioned in the release notes label Jan 23, 2022

enjoy-binbin mentioned this pull request May 19, 2022

Remove ziplist dead code in object.c #10751

Merged

DarrenJiang13 mentioned this pull request Jul 29, 2022

fix typo zl to lp as ziplist was replaced by listpack. #11062

Open

oranagra mentioned this pull request Apr 24, 2023

[CRASH] Redis 5.0.9 crash due to ziplistInsert #12099

Closed

srgsanky mentioned this pull request Feb 7, 2024

OBJECT ENCODING - needs an update to use listpack? redis/redis-doc#2658

Closed

artikell mentioned this pull request Feb 18, 2024

Update the listpack object free method #13060

Open

		/* Note that index could overflow, but we use the value
		* after seek, so when we use it no overflow happens. */

Conversation

sundb commented Aug 12, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Description of the feature

Rdb format changes

Rdb loading improvements:

Interface changes

Listpack improvements:

Zset improvements:

Tests

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sundb commented Aug 16, 2021

Uh oh!

oranagra commented Aug 16, 2021

Uh oh!

sundb commented Aug 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sundb commented Aug 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sundb commented Aug 16, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

sundb commented Aug 17, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

oranagra commented Aug 17, 2021

Uh oh!

oranagra commented Aug 17, 2021

sundb commented Aug 12, 2021 •

edited

Loading

sundb Aug 13, 2021 •

edited

Loading

sundb commented Aug 16, 2021 •

edited

Loading

sundb commented Aug 16, 2021 •

edited

Loading

sundb commented Aug 16, 2021 •

edited

Loading

sundb commented Aug 17, 2021 •

edited

Loading