New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Fix several bugs in quicklist: #12568
Conversation
imchuncai
commented
Sep 11, 2023
- As is disscussed in Minor comment bug #12548: Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit.
- As is disscussed in [BUG] quicklist compress bug #12563: A node will not be compressed if it is not compress small enough. So node's member recompress will stay 0 after calling function quicklistDecompressNodeForUse(). If that node's entry is changed later, call function quicklistRecompressOnly() will not make that node compressed. In this situation, we should call function quicklistCompress() instead, I will take this approach in this commit, obviously it's not efficient. We should redesign 'recompress' to fundamentally solve the problem.
- struct quicklistNode's member dont_compress is removed.
- As is disscussed in #12548: Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. - As is disscussed in #12563: A node will not be compressed if it is not compress small enough. So node's member recompress will stay 0 after calling function quicklistDecompressNodeForUse(). If that node's entry is changed later, call function quicklistRecompressOnly() will not make that node compressed. In this situation, we should call function quicklistCompress() instead, I will take this approach in this commit, obviously it's not efficient. We should redesign 'recompress' to fundamentally solve the problem. - struct quicklistNode's member dont_compress is removed.
node->entry = lpReplace(node->entry, &entry->zi, data, sz); | ||
quicklistNodeUpdateSz(node); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We should avoid these changes for a better review.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's related to #12548.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I mean that we can revert unrelated changes.
It's like these two lines that don't need to be changed.
entry->node->entry = lpReplace(entry->node->entry, &entry->zi, data, sz);
quicklistNodeUpdateSz(entry->node);
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
No, I don't think so. Don't you think ‘entry->node->entry’ is kind of weird? And 'entry->node' is used everywhere in function quicklistReplaceEntry(), take it out can improve readability of the code.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I agree with your idea, but for the sake of better review, we can avoid so many changes, maybe you can make these changes at the end instead of now!
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Please also handle this and run ./runtest
once.
I see that the runtest is also failed.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Failed runtest is fixed.
_quicklistListpackMerge(quicklist, target, target->next); | ||
} | ||
unsigned int newCount = a->count + b->count; | ||
lpMerge(&a->entry, &b->entry); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can you describe why this changes was made?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
/* else, the merge returned NULL and nothing changed. */
This comment is wrong, something is changed which is a and b is decompressed.
This else is not unnecessary or we should recompress a and b.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Function _quicklistMergeNodes() is deleted, don't used it now.
src/quicklist.c
Outdated
@@ -1171,7 +1147,7 @@ int quicklistDelRange(quicklist *quicklist, const long start, | |||
quicklist->count -= del; | |||
quicklistDeleteIfEmpty(quicklist, node); | |||
if (node) | |||
quicklistRecompressOnly(node); | |||
quicklistCompress(quicklist, node); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Why are you using quicklistCompress
here and in other places? Because node->recompress
is 0 and can't compress?
This change may hide other bugs where node is not compressed.
btw: quicklistCompress is more expensive than quicklistRecompressOnly.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This is mentioned in commit log, This change can fix #12563, for more efficient experience, quicklistNode->recompress should be redesigned.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Do you mean that quicklistDelRange
also can cause uncompress nodes?
Could you provide the smoke test and others?
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
No, this means I can't say that quicklistDelRange() won't cause uncompressed nodes. If anyone can prove that, should leave a comment here and keep using quicklistRecompressOnly().
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Note that the uncompressed node is only created because we reset iter->node
early before quicklistReleaseIterator()
, not because of the uncompression caused by quicklistRecompressOnly
.
I'd prefer to fix the problem of creating uncompressed nodes, rather than using quicklistRecompressOnly
for all potentially uncompressed nodes.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
The first scenario, I don't know if it's possible that a uncompressed node can be compressed after deleted part of the data.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
if so we should find out why this node wasn't compressed correctly.
at any time we should assume that a node is compressed correctly.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This node is compressed correctly, but it is not compress small enough, so it remains uncompressed. What I don't know is if it's possible to compress it small enough after deleted part of the data.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Compression algorithms are usually unlikely to do this, when a piece of data has a low compression ratio, it means that there are too few duplicate blocks, and when some of the blocks are removed, its compression ratio should become lower.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
OK, Then I will roll back this change.
quicklistNodeUpdateSz(new_node); | ||
__quicklistInsertNode(quicklist, node, new_node, after); | ||
_quicklistMergeNodes(quicklist, node); | ||
_quicklistInsertIntoFullNode(quicklist, entry, value, sz, after); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Can you explain why adding this method?
It seems that it doesn't relate to #12563.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's related to #12548.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Append value to new_node without check can make listpack too big.
@imchuncai Thanks, Can you also add some unit tests at the bottom of quicklist.c? |
Please also use
|
- fix test bug - add unit tests for listpack limit test - roll back changes for function quicklistDelRange()
Added. |
Fixed |
src/quicklist.c
Outdated
iter->offset--; | ||
quicklistNext(iter, entry); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I don't think we should engage in these dangerous behaviors.
quicklistNext()
should be the responsibility of the caller of the iterator, and should not be used internally.
All we can do is update the iterator to the correct position when it changes or reset it to prevent it from being used again.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
It's removed, it causes bug anyway.
@@ -1017,14 +1000,14 @@ REDIS_STATIC void _quicklistInsert(quicklistIter *iter, quicklistEntry *entry, | |||
node->entry = lpInsertString(node->entry, value, sz, entry->zi, LP_AFTER, NULL); | |||
node->count++; | |||
quicklistNodeUpdateSz(node); | |||
quicklistRecompressOnly(node); | |||
quicklistCompress(quicklist, node); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Similar changes in this file should be handled as we discussed in #12568 (comment).
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Similar but not same, I've added a new unit test: TEST("small listpack compress"). Try this.
- fix test bug - add new unit test for small listpack compress - fix another issue in function _quicklistInsert() whitch not update node's sz
@imchuncai I see that you changed the positions of |
@imchuncai IMHO, we can fix #12563 simply by using following patch: diff --git a/src/quicklist.c b/src/quicklist.c
index 301a2166..8bd15d60 100644
--- a/src/quicklist.c
+++ b/src/quicklist.c
@@ -1071,12 +1071,14 @@ REDIS_STATIC void _quicklistInsert(quicklistIter *iter, quicklistEntry *entry,
quicklistNodeUpdateSz(new_node);
__quicklistInsertNode(quicklist, node, new_node, after);
_quicklistMergeNodes(quicklist, node);
+ node = NULL;
}
quicklist->count++;
/* In any case, we reset iterator to forbid use of iterator after insert.
* Notice: iter->current has been compressed in _quicklistInsert(). */
+ if (node) quicklistCompress(quicklist, node);
resetIterator(iter);
} The reason why this node doesn't compress is that we forgot to compress the iterator node before resetting the iterator. |
The reason is we changed node->entry, that makes node->recompress no longer reliable. Poor design of node->recompress is the fundamental problem. |
@imchuncai But we recompress node by using |
So I replaced quicklistRecompressOnly() with quicklistCompress(), what's the problem? |
@imchuncai Yeah, you are right, this is exactly how it's handled in |
We should redesign node->recompress, if we only changed node->entry, quicklistRecompressOnly() should always work. |
Replace quicklistRecompressOnly() with quicklistCompress() is just a quick fix not efficient。 |
@imchuncai Thanks, I finally understand the desing problem you mentioned about recompress. |
quicklistCompress(quicklist, new_node); | ||
quicklistRecompressOnly(node); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
quicklistCompress(quicklist, new_node); | |
quicklistRecompressOnly(node); | |
quicklistCompressNode(new_node); | |
quicklistCompress(node); |
Maybe it's more appropriate.
Since the newnode has data added to it, we'll recompress it anyway.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
No, new_node may not in the compress depth. And node->entry is not changed, node->recompress is reliable.
@imchuncai I think we can fix both bugs in separate PRs, to avoid too many changes. |
src/quicklist.c
Outdated
/* node->count > 1, node will not be removed */ | ||
quicklistDelEntry(iter, entry); | ||
if (quicklistNext(iter, entry)) { | ||
_quicklistInsert(iter, entry, data, sz, iter->direction == AL_START_HEAD); | ||
} else { | ||
int direction = iter->direction == AL_START_HEAD | ||
? AL_START_TAIL : AL_START_HEAD; | ||
quicklistIter *rev_iter = quicklistGetIterator(quicklist, direction); | ||
quicklistNext(rev_iter, entry); | ||
_quicklistInsert(rev_iter, entry, data, sz, direction == AL_START_HEAD); | ||
quicklistReleaseIterator(rev_iter); |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
I wouldn't say I like this way that nested use of iterators.
Can you explain why we have to do as this.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
We can't insert first now, because entry->node have a chance be freed due to merge.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
In that case I'd prefer an implementation like _quicklistInsert to reimplement the replacement, rather than nested iterators.
But that would introduce a lot of duplicate code and more complexity.
What's your suggestion? Move it back and add declaration of function _quicklistInsert() above it? |
Move them back to their original position for better review. |
done |
This PR fix actually equates I was thinking that maybe we could fix it in some other way.
I'm not sure which way is better. |
It's not related to this PR. This PR fixed a packed node violate size limit, what the limitation is nor which node should be treated as a large element is not concerned. |
@imchuncai The scenarios I propose are only meant to avoid the implementations mentioned in #12568 (comment).
|
disclaimer: i'm not certain i understand everything, as i only took a quick look at the code, and only read the top comment and last 3 at the top. i understand that there's an overlapping between the threshold for PLAIN nodes, and the threshold of packed nodes with just one element (in case nodes are limited by count rather than size). as far as i remember, SIZE_SAFETY_LIMIT is actually not about safety but an optimization, i.e. we on't want memmoves and reallocs when we're dealing with large items. that said, this mechanism was created before PLAIN nodes existed, and i think that now that we have them, maybe we can reduce the default i do think that we should take this opportunity to clean that code and simplify it (not just fix the bug), since this PR looks quite large anyway. while on that subject, considering the amount of changes, and the fact the bugs aren't critical ones (don't really affect redis's behavior, right?), i don't think we should backport this fix to any existing release. |
I don't think we need to backport this which doesn't do any harm. |
I'm not able to contributing code anymore. |
@imchuncai Still appreciate the effort you put into it. |
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Why: I tried to solve the issue I found earlier, but found myself stuck in a quagmire because the issues kept coming up while I fix the old one, so I finally decided to rewrite it. Issues with the old one: - A node which should be compressed stays raw This is due to by poor design of quicklist->recompress, the design forgot the situation that a node could stay uncompressed if it can not compress small enough. And if we changed the node, wo should perform compress on it again. See issue redis#12563. - Iterator don't behave like iterator Iterator will be reset and not avaliable for further use after replace or insert, see marcro resetIterator(). The only operation that athe iterator does not get reset is quicklistDelEntry(), and it has a commment about it, but the comment is wrong, the iterator may not behave like the comment says. See issue redis#12614. - Packed node violate size limit Certen call to function quicklistReplaceEntry(), quicklistInsertBefore() and quicklistInsertAfter() will cause a packed node violate size limit. See issue redis#12548. - Merge operation only performed in insert There is no merging in delete nor replace, which can make the quicklist contain adjacent small nodes. See issue redis#12856. - Algorithms that maintain compress depth are not efficient the algorithm to maintain compress depth after add or delete is to check nodes on both sides of the list, time complexity is O(n), where n is the uncompressed depth on both sides of the list. All the changes: - Partition the node Divide the node into three partitions: head, middle and tail. The head and tail partitions hold uncompressed nodes, and the middle partition holds compressed nodes. Therefore,the time complexity of maintaining compress depth after adding or deleting a node will drop to O(1), moving at most one node from one partition to another. - Removed annoying members recompress, attempted_compress and dont_compress from quicklist node structure - Merge structure quicklistIter and quicklistEntry - The historical parameter packed_threshold has been removed This is mentioned by @sundb and @oranagra in pull request redis#12568. - Merge strategy is added That is that any adjacent node in quicklist can not be merged.
Following #12568 In issue #9357, when inserting an element larger than 1GB, we currently store it in a plain node instead of a listpack. Presently, when we insert an element that exceeds the maximum size of a packed node, it cannot be accommodated in any other nodes, thus ending up isolated like a large element. I.e. it's a node with only one element, but it's listpack encoded rather than a plain buffer. This PR lowers the threshold for considering an element as 'large' from 1GB to the maximum size of a node. While this change doesn't completely resolve the bug mentioned in the previous PR, it does mitigate its potential impact. As a result of this change, we can now only use LSET to replace an element with another element that falls below the maximum size threshold. In the worst-case scenario, with a fill of -5, the largest packed node we can create is 2GB (32k * 64k): * 32k: The smallest element in a listpack is 2 bytes, which allows us to store up to 32k elements. * 64k: This is the maximum size for a single quicklist node. ## Others To fully fix #9357, we need more work, as discussed in #12568, when we insert an element into a quicklistNode, it may be created in a new node, put into another node, or merged, and we can't correctly delete the node that was supposed to be deleted. I'm not sure it's worth it, since it involves a lot of modifications.