Remix.run Logo
▲ Valkey kills the skiplist, cuts sorted set overhead by up to 43%(valkey.io)
55 points by reconditerose 3 days ago | 25 comments
▲tyre 2 hours ago | parent | next [-]

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

▲pastel8739 an hour ago | parent [-]

You really think that LLMs are “very good” at producing useful PR descriptions? I have had a very different experience.

▲stuaxo 23 minutes ago | parent [-]

OMG, I hate the LLM PR descriptions, the comments, the docstrings - anything to be read by a human that isn't code.

▲hinkley an hour ago | parent | prev | next [-]

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)

▲infamouscow an hour ago | parent [-]

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.

▲hinkley an hour ago | parent [-]

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.

▲reconditerose 3 days ago | parent | prev | next [-]

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.

▲hinkley an hour ago | parent | next [-]

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?

▲alfiedotwtf 17 minutes ago | parent | next [-]

B trees are more friendly to being cache oblivious

▲crest an hour ago | parent | prev | next [-]

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).

▲eventualcomp an hour ago | parent [-]

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

▲jjmarr an hour ago | parent [-]

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.

▲wrs an hour ago | parent | prev [-]

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.

▲tyre 2 hours ago | parent | prev [-]

Is this AI? Why do we need a summary of the actual article in a comment?

▲bertonvv 2 hours ago | parent | next [-]

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.

▲hinkley an hour ago | parent [-]

There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...

▲WD-42 2 hours ago | parent | prev [-]

The actual article is AI too so this is just saving you time.

▲hinkley an hour ago | parent [-]

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.

▲dnchdnd an hour ago | parent | prev | next [-]

Is valkey the recommended redis alternative these days ?

▲TkTech an hour ago | parent | next [-]

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.

▲swingboy an hour ago | parent | prev [-]

Yes

▲snissn 2 hours ago | parent | prev | next [-]

Do they provide their benchmark code?

▲WD-42 2 hours ago | parent | prev [-]

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.

▲tyre 2 hours ago | parent [-]

The PR (https://github.com/valkey-io/valkey/pull/4206) is much better.

▲hinkley an hour ago | parent [-]

Can I convince you to post this as a top level?