1. 5

  2. 1

    Seems similar to a hierarchical timing wheel?

    1. 3

      (one of the authors here)

      You could say that, the coarse TTL (binning), index, and efficient scanning all resemble timing wheel.

      But obviously events in a timing wheel are indexed by the actual TTL timestamp into a “row”, and laid out into a table of many rows based on how soon they expire, and the hierarchical aspect comes in as multiple such tables. Within each row in the timing wheel there is no order, this is also why sometimes a red/black tree is more suitable for implementing expiration with strict ordering requirements. While Segcache packs segments of different timestamps into the same row and keep them sorted in a row.

      Coincidentally I’m a huge fan of the timing wheel paper (though this design was mostly Juncheng’s idea) and I implemented a (non-hierarchical) version of it which Pelikan uses :D https://github.com/twitter/ccommon/blob/master/src/time/cc_wheel.c