18 comments

  • antirez 9 hours ago
    For par condicio: I worked at a similar optimization for Redis using different techniques (when I submitted the PR my colleagues informed me that ValKey and another Redis team was working at it, I was not aware: the amoung the three implementation we picked mine after extensive benchmarks) reaching memory savings that sometimes can be tens of percentage of less RAM compared to this ValKey optimization. So if you are exited for less memory for sorted Sets you should try both the implementations. We also got a lot more speed in many use cases compared to the skiplist.
    • hawk_ 7 hours ago
      Is your implementation also a B+ tree? If so how does it use tens of percentage less memory? less metadata?
      • antirez 6 hours ago
        It uses two techniques: B+ tree instead of sorted sets, but also the hash table side, the dictionary, is specialized for sorted sets and stores several items per allocation. The B+ tree leaves hold all the members and scores (also in clusters of many elements, 96 max or 4k: that's a big part of the win), rank lookup can skip many children because of meta data, which is part of the ability to go as fast or faster than Redis even if the memory is so much smaller. The hash table points to leaves in the B+ tree, does not have elements at all, and is heavily optimized to do just the minimum, a single byte tag is used as a speed optimization to optimized lookups in an optimistic way. Basically it is the sum of many different techniques conceived during the years and never adopted for fear of complexity (today no longer a problem), and newely discovered techniques.

        P.S. I tried several variants with different representations, so this specific implementation is the Pareto frontier in speed/size of many, many attempts.

        • antirez 1 hour ago
          EDIT: "b+ trees instead of skiplists" of course. Sorry, can't edit it anymore.
  • hinkley 14 hours ago
    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)

    • bob1029 5 hours ago
      If cache misses are a huge concern and we have a highly skewed distribution (mostly touching newer records), the splay tree starts to look interesting.

      We don't like the O(n) worst case, but we really like that magical amortization property. There are some simple ways to avoid getting into a linear hot path.

      • hinkley 35 minutes ago
        Timsort and powersort both have O(k) operations which rely on k being approximately a cache line in size.

        One of the last large dev blog entries for V8 was about how they got pointer compression to be performance neutral and that’s down to getting the translation down below the amortized cache hit penalty for 64 bit pointers. IIRC the JVM gets close to that as well.

    • infamouscow 14 hours ago
      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.
      • fpoling 7 hours ago
        The data structure is not a pure B+tree. They also strip common key prefix for node elements and store 4 bytes of remaining key data together with a pointer to the children to avoid key lookup in many cases. Plus they tune node sizes to match jemalloc allocation classes to minimize allocation overhead. I am not sure with such focus on cache friendliness the advantage of skip lists for writes still holds as they will still have more cache misses even on inserts.
      • hinkley 14 hours ago
        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.

      • josephg 7 hours ago
        Yep. I’ve implemented b trees and skip lists a few times. I find skip lists to be a little easier to implement. But b trees seem to perform ~20% faster. I can’t think of any good reasons to use skip lists instead of b trees in high performance code.
    • ignoramous 2 hours ago
      > skiplists are not simple

      Can you please clarify: Simpler in operation or simple in implementation? Or neither/both?

  • zaiyuan_dev 1 hour ago
    Curious how rank queries (ZRANK, ZRANGE by index) perform after the switch. Skiplists made those cheap via span counters; does the B+tree keep per-node subtree counts to match?
  • tyre 14 hours ago
    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

    • plorkyeran 11 hours ago
      This is the standard LLM wall of irrelevant garbage that always makes me groan when I see it. There's a lot of words but it conveys very little useful information. This is exactly the type of thing that LLMs are terrible at and has negative ROI for human reviewers.
      • shiandow 3 hours ago
        Starting with an unnecessary list of touched files before the Reviewing Guide. Talk about burying the lede!

        Not sure about the name reviewing guide, but I do like the contents. Then again I know nothing about code base.

    • monkpit 11 hours ago
      This is an LLM smell and, after having dealt with this sort of thing and realizing it’s usually low-signal high-noise, you end up ignoring this kind of thing outright.
    • catlifeonmars 8 hours ago
      I prefer to go straight to the code when reviewing. I’ll form my own opinion, then read the PR description, then do another, more detailed pass through the code.
    • pastel8739 14 hours ago
      You really think that LLMs are “very good” at producing useful PR descriptions? I have had a very different experience.
      • stuaxo 13 hours ago
        OMG, I hate the LLM PR descriptions, the comments, the docstrings - anything to be read by a human that isn't code.
        • bigstrat2003 8 hours ago
          The code isn't really much better, having reviewed a decent bit of it myself.
        • what 10 hours ago
          Have you read the code though?
      • darig 13 hours ago
        [dead]
    • lelanthran 7 hours ago
      The snr of that file is very very low.
  • dnchdnd 14 hours ago
    Is valkey the recommended redis alternative these days ?
    • TkTech 13 hours ago
      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.
      • graemep 1 hour ago
        Redis is available under the AGPL which is not a headache for most people.
        • load-bearing 55 minutes ago
          Until they close it down again. Why would you trust someone after they've already screwed you over?
      • nurettin 11 hours ago
        I haven't checked the newest additions, there were some updates about adding login and encryption, but the latest innovation I use from redis is xstream, and almost all clones now support it.

        And a moderate LLM subscription can readily generate a useful portion of this project overnight, which makes me concerned about their profitability in the long run.

        • ddorian43 9 hours ago
          what even is `xstream` ? is that a typo for `stream` ?
          • nurettin 7 hours ago
            I seem to remember it was xstream when it was first released. The commands all have a prefix X (XADD, XREAD, XTRIM) perhaps it got rebranded into just stream.
    • ch3nzhao 1 hour ago
      You might also want to try Lavik (https://github.com/eloqdata/lavik). I'm one of the authors. It's an open-source Redis-compatible server that uses NVMe storage while delivering in-memory-class performance. It's particularly fast for strings and hashes, though sorted sets aren't its strong suit yet.
    • unddoch 7 hours ago
      DragonflyDB has had this for years. You might disagree with the licensing choice but the technology is just better IMO.

      (Disclosure, worked for them 3 years ago for a few months)

    • swingboy 13 hours ago
      Yes
  • rsalus 12 hours ago
    I've long since moved to the MultiQueue algorithm for CPQs, seems like SkipList has vanishingly few use cases now...
  • dreamcompiler 10 hours ago
    > Every node carries a backward pointer

    Curious. Skiplists don't need back pointers. You can traverse a skiplist backward almost as fast as forward if you keep the "finger" around. The finger is the set of nodes from level-n down to level-0 that point as close to the goal node as possible without going beyond it. The ideal place to keep these nodes is on the stack. To traverse backwards, you do a conventional search for the starting node but every time you go down a pointer level, you push the last pointer on the stack first. Then back traversal becomes stack pops together with appropriate forward recursive calls when you pop back to a pointer that was too far to the left.

    It's easier to convey the idea with code than english but I'm not typing the algorithm with my thumbs into my phone.

  • snissn 14 hours ago
    Do they provide their benchmark code?
  • reconditerose 3 days ago
    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 14 hours ago
      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?

      • boricj 4 hours ago
        Compute speed has been outpacing memory speed for decades now. So when you spend the cycles to fetch a cache line (64 bytes generally), you want to milk it for all its worth, to minimize time spent waiting on memory.

        On a cold cache, you pay for each level of indirection, so you want to increase fan-out as much as possible. B-trees do that intrinsically.

        • hinkley 43 minutes ago
          Can’t imagine valley is going to have a cold cache. Cache eviction on the other hand…
      • alfiedotwtf 13 hours ago
        B trees are more friendly to being cache oblivious
      • crest 13 hours ago
        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).
        • hinkley 41 minutes ago
          A binary tree would be strictly worse than a skip list for cache line efficiency. Seeing as how skip lists were invented to improve on binary tree cache behavior.
        • eventualcomp 13 hours ago
          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 13 hours ago
            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.
            • entrope 12 hours ago
              Every node in a binary tree needs a value and two child pointers, though. That's asymptotically almost twice as many child pointers per value as a B-tree has.
              • hinkley 12 hours ago
                It’s a good thing this article isn’t about binary trees then.
                • entrope 4 hours ago
                  The comment I replied to claimed that B-trees are "heavyweight" compared to binary trees. I thought it worth pointing out that the claim is only true for quite small trees.
      • wrs 14 hours ago
        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 14 hours ago
      Is this AI? Why do we need a summary of the actual article in a comment?
      • bertonvv 14 hours ago
        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 13 hours ago
          There aren't many commenters at the time you posted this. Which makes this conversation feel even more artificial...
          • bertonvv 12 hours ago
            I meant in general on this site. Dislike the insinuation that I'm generative AI.
      • WD-42 14 hours ago
        The actual article is AI too so this is just saving you time.
  • jauntywundrkind 10 hours ago
    Thanks Bill Pugh for skiplists, worked great for so long. Go terps. https://dl.acm.org/doi/10.1145/78973.78977
  • vivzkestrel 12 hours ago
    - valkey vs redis vs dragonfly 2027?
  • WD-42 14 hours ago
    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.
  • peterliu_dev 1 hour ago
    [flagged]
  • charlie2agent 10 hours ago
    [flagged]
  • yoy0721 12 hours ago
    [flagged]
  • laruss5 8 hours ago
    [flagged]
  • dalisraieb 4 hours ago
    [flagged]
  • dropdropteam 14 hours ago
    [flagged]