HenryR

You might not be aware that this is one of, if not the, seminal paper in distributed systems.

Lamport clocks, described briefly in the review, are an answer to the general problem of establishing an order between events that happen on different machines that respects causality. They’re still practical to this day, over 50 years after this paper was published.

There are lots of in-depth descriptions of the paper and its contributions elsewhere. I’d totally recommend finding them - it’s a great paper and not a hard read at all.

This might be useful: https://web.stanford.edu/class/ee384m/Handouts/HowtoReadPape...

If you find there is just too much unfamiliar technical language, it’s a good idea to pause and look up a definition. You might need to follow that chain several steps, but that will help you get to an understanding of new terms.

Companies usually provide the space and will sponsor pizza and drinks, at least in SF. That’s about all the costs beyond the time of the organizers which is offered for free.

Where Wizards Stay Up Late (https://www.amazon.com/Where-Wizards-Stay-Up-Late/dp/0684832...)

Authors try to compare their work against hash tables because, usually, HT represent an upper bound on the performance of point-lookups; we don't know how to do much better in general.

So if your data structure supports range queries _and_ point lookups, you should measure against hash tables to understand how far off the ideal you are. If it's not far, and your data structure is strictly more general, that's compelling.

Should be fixed now! (But I've been wrong with css before)

Oh yeah that's no good. I'll fix that when I'm back at my computer. Thanks for pointing that out!

Yeah, Masstree has settled into the standard set of comparator systems for most research since it was published - and not as a strawman "this system was crap, so let's pretend we've done good work by beating it!" but as a real challenge to do better than.

Anna is on my list of systems to include in this review (see https://www.the-paper-trail.org/reading-list/). Looking forward to it!

I could either figure out how Judy works, or review another three papers :)

I don't know of one, but it's such a natural idea that I'd guess it's been studied. There are standard implementations of LRU caches that use e.g. a hash map and a linked list to get both fast lookup and ordering, but for real performance I think you'd want to try and minimise the number of data structures to avoid having competing cache behaviours.

Author here - if you like this you might also like another paper summary of mine in the same vein:

https://news.ycombinator.com/item?id=18132730

Here's a recent comparison of Masstree to ART: https://twitter.com/andy_pavlo/status/986647389820747776?s=2...

ART looks to be better in most cases. It's on my list of K-V stores to review: https://www.the-paper-trail.org/page/reading-list/

I am surprised that anyone is trying to differentiate on storage at this time, precisely when that's the part of the stack that's being cannibalized by the cloud vendors (look at the rate of innovation in HDFS over time; the effort is going elsewhere). Are you just targeting on-premise clusters, or is there some differentiation planned for the cloud as well?

Unfortunately not (my blog is http://the-paper-trail.org but tends to be more theoretical than practical). That would make a good post though!

That’s totally a fair point. I could have given a more concrete talk about how I’ve done these things in real systems (and the original version of this talk, presented internally to my company, had more real details and spoke very candidly about mistakes that I’d made along the way). Here I wanted to give more of a “here’s how you might want to structure your thinking, along with some basic design principles” kind of talk - I wish I’d had time to give more detail!

What does the columnar format look like? Particularly, is the group by column compressed with RLE? That’s kind of a pre-computed group-by + count that would make this kind of query very very fast :)