Replace ziplist with listpack in quicklist by sundb · Pull Request #9740 · redis/redis

sundb · 2021-11-05T06:11:41Z

Part three of implementing #8702, following #8887 and #9366 .

Description of the feature

Replace the ziplist container of quicklist with listpack.
Convert existing quicklist ziplists on RDB loading time. an O(n) operation.

Interface changes

New list-max-listpack-size config is an alias for list-max-ziplist-size.
Replace debug ziplist command with debug listpack.

Internal changes

Add lpMerge to merge two listpacks . (same as ziplistMerge)
Add lpRepr to print info of listpack which is used in debugCommand and quicklistRepr. (same as ziplistRepr)
Replace QUICKLIST_NODE_CONTAINER_ZIPLIST with QUICKLIST_NODE_CONTAINER_PACKED(following Add support for list type to store elements larger than 4GB #9357 ).
It represent that a quicklistNode is a packed node, as opposed to a plain node.
Remove createZiplistObject method, which is never used.
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

Calling lpShrinkToFit after converting Ziplist to listpack, which was missed at Replace all usage of ziplist with listpack for t_zset #9366.
Optimize quicklistAppendPlainNode to avoid memcpy data.

Bugfix

Fix crash in quicklistRepr when ziplist is compressed, introduced from Replace all usage of ziplist with listpack for t_zset #9366.

Test

Add unittest for lpMerge.
Modify the old quicklist ziplist corrupt dump test.

TODO

Comment typos.
Benchmark.

oranagra

@sundb thank you,
i guess we wanna see some benchmarks.
rdb loading to make sure we know the price
and commands to make sure there's no big regression.

i see rdb file format conversion test wasn't added, it is because the one added in #9357 covers it?

p.s. edited your top comment a bit (no need for backwards compatibility for DEBUG command).

src/rdb.c

src/listpack.c

src/quicklist.c

1. Modify the timing of the call to lpShrinkToFit. 2. Remove the listpack overhead calculation in quicklistAllowInsert, and remove the `new_sz` assertion, since listpack will never be large than 1GB, and `sz` is also smalloc than `packed_threshold`(1GB). 3. Change type of `lpBytes` to `unsigned long long` to avoid overflow in 32bit.

sundb · 2021-11-08T13:04:23Z

@sundb thank you, i guess we wanna see some benchmarks. rdb loading to make sure we know the price and commands to make sure there's no big regression.

It's still on the way.

i see rdb file format conversion test wasn't added, it is because the one added in #9357 covers it?

Yes.

src/quicklist.c

Co-authored-by: Oran Agra <[email protected]>

sundb · 2021-11-09T13:44:20Z

From the results, we can see that the performance of l/rpush and l/rpop operations is basically unchanged, but the performance of lrange for quicklist listpack is a little bit degraded.
The main reason is that the performance of lpNext/lpGet is not as good as ziplistNext/ziplistGet, which use a lot of ifs to fetch data.

  1000000 requests
  50 parallel clients
  3 bytes payload
  keep alive: 1
  host configuration "save": 
  host configuration "appendonly": no
  multi-thread: no

quicklist info

count: 1000000
len: 612
fill: -2
compress: 0
listpack items per node: 8182

command	quicklist listpack(rps)	quicklist ziplist(rps)	percentage(positive: performance enhancement, negative: performance degradation)
LPUSH	106929 rps, p50=0.223	103535.75 rps, p50=0.223	3.2%
LRANGE_100	65737.58 rps, p50=0.375	67333.27 rps, p50=0.375	-2.3%
LRANGE_300	30900.44 rps, p50=0.839	31346.00 rps, p50=0.823	-1.4%
LRANGE_500	22126.59 rps, p50=1.175	22689.63 rps, p50=1.159	-1.4%
LRANGE_600	19443.90 rps, p50=1.343	19690.08 rps, p50=1.327	-1.2%
RPUSH	109075.04 rps, p50=0.223	108283.71 rps, p50=0.223	0.7%
LPOP	108636.61 rps, p50=0.223	110778.77 rps, p50=0.223	1.9%
RPOP	109757.44 rps, p50=0.223	109206.08 rps, p50=0.223	0.5%

src/quicklist.c

sundb · 2021-11-10T13:00:28Z

Following is the RDB load time test of quicklist ziplist convert to quicklist listpack.
From the results, we can see that the speed of converting quicklist ziplist to quicklist listpackis faster than hash and zset,
which I think is reasonable because loading list key does not need to check duplication.
See #8887 (comment), #9366 (comment).

Config:

list-max-listpack-size: -2
list-compress-depth 0

Test other info:

list entry size: 32 bytes(rand string)

Due to the physical memory limitation, when the list size and quicklist length are 250000/512 and 500000/256, the loading speed drops significantly, we can ignore their loading speed degradation percentage.

list size	quicklist length per list	quicklist ziplist loading time(second)	quicklist listpack loading and convert time(second)	convert cost time(second)	degradation percentage	rdb size
250000	512	9.053	13.468	4.415	48.7%(memory limit reach)	3.7G
250000	256	4.752	6.850	2.098	44.1%	1.9G
250000	128	2.555	3.722	1.167	45.6%	946M
250000	64	1.385	1.999	0.614	44.3%	486M
500000	256	9.214	13.847	4.633	50.2%(memory limit reach)	3.7G
500000	128	4.990	7.170	2.18	43.6%	1.9G
500000	64	2.868	3.961	1.093	38.1%	971M
500000	32	1.703	2.365	0.662	38.8%	505M

oranagra · 2021-11-11T10:38:47Z

@redis/core-team this is the final step in getting rid of ziplists, it's basically more of the same of what we did for hashes and listpacks.
please take a quick look at the top comment, and also at the benchmarks at the bottom, specifically this one:

yossigo

Approving the change, did not code review.

madolson

Approve at a high level.

soloestoy

Approve the change, did not code review line by line.

src/config.c

…n-quicklist-1

…ze to list_max_listpack_size

zuiderkwast · 2021-11-23T21:22:21Z

Good job @sundb!

If this is the last usage of ziplist, can we now remove almost all of ziplist.c? It seems that only ziplistGet is used in the conversion.

sundb · 2021-11-24T01:31:38Z

@zuiderkwast Only ziplsitGet and ziplistValidateIntegrity are still being used.
But internally they depend on other methods, and removing ziplist.c completely means we need to move the rest of the code elsewhere, which doesn't feel good.
Similarly with zipmap.c, which has been left in place.

…n-quicklist-1

zuiderkwast · 2021-11-24T11:15:51Z

OK. I was thinking about deleting the dead code (ziplistInsert, etc. which is at least half of ziplist.c). I suppose instead we will delete ziplist.c in Redis 8 or 9(?) when we no longer support conversion from ziplist.

sundb · 2021-11-24T11:24:50Z

@zuiderkwast It could be a long, long time, and I hate to see them at lcov with such low coverage.

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

Replace ziplist with listpack in quicklist

2335e65

oranagra linked an issue Nov 7, 2021 that may be closed by this pull request

[NEW] listpack migration - replace all usage of ziplist with listpack #8702

Closed

oranagra reviewed Nov 7, 2021

View reviewed changes

src/rdb.c Show resolved Hide resolved

src/rdb.c Outdated Show resolved Hide resolved

src/listpack.c Outdated Show resolved Hide resolved

src/quicklist.c Outdated Show resolved Hide resolved

src/quicklist.c Show resolved Hide resolved

src/quicklist.c Outdated Show resolved Hide resolved

sundb added 3 commits November 7, 2021 21:57

Optimize quicklistAppendPlainNode to avoid memcpy data

0fb9850

Move the ziplist to quicklist conversion code to rdb.c

2723bc6

sundb marked this pull request as draft November 8, 2021 12:30

Fix crash in quicklistRepr when ziplist is compressed

7987b9b

oranagra reviewed Nov 8, 2021

View reviewed changes

src/quicklist.c Outdated Show resolved Hide resolved

Add SIZE_ESTIMATE_OVERHEAD and add some comments

6206d13

sundb force-pushed the listpack-migration-quicklist-1 branch from 4b82a0f to 6206d13 Compare November 9, 2021 08:36

sundb marked this pull request as ready for review November 9, 2021 09:34

oranagra reviewed Nov 9, 2021

View reviewed changes

src/quicklist.c Outdated Show resolved Hide resolved

src/quicklist.c Outdated Show resolved Hide resolved

sundb and others added 3 commits November 9, 2021 18:13

Update src/quicklist.c

34983d4

Co-authored-by: Oran Agra <[email protected]>

Update src/quicklist.c

0b93add

Co-authored-by: Oran Agra <[email protected]>

Fix typo

59df7c2

zuiderkwast reviewed Nov 9, 2021

View reviewed changes

src/quicklist.c Show resolved Hide resolved

Fix comment about SIZE_ESTIMATE_OVERHEAD

201e227

oranagra added approval-needed Waiting for core team approval to be merged release-notes indication that this issue needs to be mentioned in the release notes state:major-decision Requires core team consensus labels Nov 11, 2021

sundb mentioned this pull request Nov 17, 2021

Fix crashes when list-compress-depth is used. #9779

Merged

yossigo approved these changes Nov 18, 2021

View reviewed changes

madolson approved these changes Nov 23, 2021

View reviewed changes

soloestoy approved these changes Nov 23, 2021

View reviewed changes

src/config.c Outdated Show resolved Hide resolved

Merge remote-tracking branch 'origin/unstable' into listpack-migratio…

6495589

…n-quicklist-1

sundb added 2 commits November 23, 2021 02:05

Fix unittest compile error

85c37f6

Rename ziplist to listpack in comments and rename list_max_ziplist_si…

562f31e

…ze to list_max_listpack_size

sundb force-pushed the listpack-migration-quicklist-1 branch from 506cb6c to 562f31e Compare November 23, 2021 12:23

sundb added 2 commits November 23, 2021 23:59

Merge remote-tracking branch 'origin/unstable' into listpack-migratio…

5a4a878

…n-quicklist-1

Change test added by redis#9831

b6764c1

oranagra merged commit 4512905 into redis:unstable Nov 24, 2021

sundb deleted the listpack-migration-quicklist-1 branch November 24, 2021 11:36

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

sundb mentioned this pull request Apr 2, 2025

Fix a couple of compiler warnings #13911

Merged

Conversation

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

Uh oh!

Description of the feature

Interface changes

Internal changes

Improvements

Bugfix

Test

TODO

Uh oh!

oranagra left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

sundb commented Nov 8, 2021

Uh oh!

Uh oh!

Uh oh!

Uh oh!

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

Uh oh!

Uh oh!

Uh oh!

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

Uh oh!

Uh oh!

oranagra commented Nov 11, 2021

Uh oh!

yossigo left a comment

Choose a reason for hiding this comment

Uh oh!

madolson left a comment

Choose a reason for hiding this comment

Uh oh!

soloestoy left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

zuiderkwast commented Nov 23, 2021

Uh oh!

sundb commented Nov 24, 2021

Uh oh!

zuiderkwast commented Nov 24, 2021

Uh oh!

sundb commented Nov 24, 2021

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

6 participants

sundb commented Nov 5, 2021 •

edited

Loading

sundb commented Nov 9, 2021 •

edited

Loading

sundb commented Nov 10, 2021 •

edited

Loading