I have to say I was always on the fence about Bill Pugh (Mr Skiplist).
Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.
It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)
B+tree were designed around optimized IO in the era of magnetic storage, they're inherently cache-friendly. Skiplists are the same thing as a b+tree but the structure is inverted, which makes skiplists more to concurrent writer-friendly than b+trees. Different tradeoffs.
Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years).
I'm guessing their point is unlike binary trees which have two children per node, B trees can have as many children per node is best for cache locality/SIMD/etc. Which despite being "heavyweight" (wasted space if not all children per node are occupied) is faster in practice because it's cheaper to preload large unused blocks to cache rather than only access memory when it is needed.
Yes, that hardware is called "the memory cache". B-trees were invented because disk reads were very expensive. Now, memory cache fills are very expensive.
From what I've seen on here many commenters didn't read the article, only the title (I've been guilty of this too). OP is maybe just adapting to HN culture.
Like all things, it depends. If you don't need the latest and greatest features in upstream redis, and you don't want license headaches, Valkey is probably a good default. It's generally cheaper on hosting providers too - AWS will discount you ~20-35% for Valkey vs Redis.
As a coding exercise I implemented a redis that utilized skiplists. I was excited to read this article. Turns out it's ai slop. Seriously people, stop it. This hurts to read.
Tangentially related, the PR sections for the final PR in this feature is quite nice[0].
There is a reviewing guide with suggested reading order, clear design decisions, and scope boundaries for what is intentionally not included.
This is the type of thing LLMs are very good at and high ROI for human reviewers.
[0]: https://github.com/valkey-io/valkey/pull/4206
You really think that LLMs are “very good” at producing useful PR descriptions? I have had a very different experience.
OMG, I hate the LLM PR descriptions, the comments, the docstrings - anything to be read by a human that isn't code.
I have to say I was always on the fence about Bill Pugh (Mr Skiplist).
Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability.
It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple)
B+tree were designed around optimized IO in the era of magnetic storage, they're inherently cache-friendly. Skiplists are the same thing as a b+tree but the structure is inverted, which makes skiplists more to concurrent writer-friendly than b+trees. Different tradeoffs.
But more cache misses, due to the variable pointer length structure.
That cost varies from chip generation to generation, but it does seem to be the case that b trees win in more generations than they lose.
Redis historically used a skiplist to keep a sorted index. Valkey showed its inefficient and slow on modern hardware, migrating to a B+ tree instead.
It all ends up back at B trees. Why does it always end up back at B trees?
At this point have we optimized hardware to assume B trees in a sort of self-fulfilling prophesy?
Binary trees have worse cache locality. The cost of accessing memory has grown so much compared to computation that supposedly slower "heavy weight" data structures are worth it now (as in the last 10-20 years).
A b-tree isn't a binary tree. B doesn't officially stand for binary either, see History[0].
[0] https://en.wikipedia.org/wiki/B-tree
I'm guessing their point is unlike binary trees which have two children per node, B trees can have as many children per node is best for cache locality/SIMD/etc. Which despite being "heavyweight" (wasted space if not all children per node are occupied) is faster in practice because it's cheaper to preload large unused blocks to cache rather than only access memory when it is needed.
Yes, that hardware is called "the memory cache". B-trees were invented because disk reads were very expensive. Now, memory cache fills are very expensive.
Is this AI? Why do we need a summary of the actual article in a comment?
From what I've seen on here many commenters didn't read the article, only the title (I've been guilty of this too). OP is maybe just adapting to HN culture.
There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...
The actual article is AI too so this is just saving you time.
https://github.com/valkey-io/valkey-io.github.io/pull/665/co...
The PR for the article. I'm not convinced it's AI, but I didn't do a deep dive on the commit tree just poked around a bit.
Is valkey the recommended redis alternative these days ?
Like all things, it depends. If you don't need the latest and greatest features in upstream redis, and you don't want license headaches, Valkey is probably a good default. It's generally cheaper on hosting providers too - AWS will discount you ~20-35% for Valkey vs Redis.
Yes
Do they provide their benchmark code?
As a coding exercise I implemented a redis that utilized skiplists. I was excited to read this article. Turns out it's ai slop. Seriously people, stop it. This hurts to read.
The PR (https://github.com/valkey-io/valkey/pull/4206) is much better.
Can I convince you to post this as a top level?