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

That's precisely the point: if threads never block or yield the CPU, you can guarantee system-wide progress.

If you have an algorithm which might deadlock, 'progress' isn't really well defined.

The whole point of a non-blocking algorithm is system-wide forward progress. Yes, this is much harder to do if a thread can suspend for an unbounded amount of time, but that's kind of the point of the article: being in the kernel allows you to pull the kind of trick that makes that behaviour a non-issue.

(edit: s/per-thread/system-wide, since we're talking about lock-freedom).

Here's one paper on the intersection of Byzantine fault tolerance, altruiusm and rational behaviour from UT Austin: https://www.cs.utexas.edu/lasr/download.php?uid=63

I think it's rather clear that he's talking about high availability in the CAP sense, which is precisely the kind of availability FoundationDB (rightly) doesn't claim to achieve (http://foundationdb.com/#CAP).

BTW, the images are failing to load on that page for me.

You're right, it doesn't really. When I started building this list it was more carefully given over to graduate-level courses. It evolved into a bit of a repository of courses that aligned with my interests and thought were good.

You're mixing up 'premature optimisation' and 'unnecessary optimisation'. The first is making code faster that isn't the bottleneck, or dominating performance factor. The second is making something faster than it needs to be. Profiling helps avoid the first, benchmarking helps avoid the second. Both require working (toy) systems, which is hard when you are evaluating which language to begin work in.

Writing a library in C (for reasons of performance) where performance would have been 'good enough' in Python is unnecessary optimisation. Writing your own GC implementation layer in Python because you think that's the bottleneck would be premature optimisation.

EDIT: typo

That was the introductory blog post to which I referred - note the similar discussion in the comments.

Extremely familiar - see my articles at

http://the-paper-trail.org/blog/?p=173

and http://the-paper-trail.org/blog/?p=190

for some tutorials I wrote on the subject.

You're correct that failure detection and consensus are very deeply related, in that a strong failure detector is 'sufficient' for consensus.

But my point is about client failure detection, not failure detection between servers (which must have some kind of timeout system; that's ok - you just sacrifice liveness in a few pathological cases rather than sacrificing correctness). If I am to implement leader election with Doozer, does Doozer provide any tools to help us with deciding when to elect a new leader? There's no reason it should, but ZooKeeper, for example, does have that in its arsenal.

Doozer doesn't, AFAIK, expose consensus as a primitive; that's not its model. So the fact that it uses Paxos, or ZAB, or 2PC or whatever doesn't make a difference to its clients.

It's not clear to me how, or if, failure detection is to be integrated with Doozer. Keith has said on the thread accompanying the announcement blog post that Doozer doesn't have the 'baggage' of sessions (which are used in ZooKeeper to manage timeout failure and the removal of certain kinds of data which can be used to model lock revocation).

Without some way of knowing if a process fails, it's hard to do leader election, locks, other synchronisation patterns. It would be a reasonable design choice to do failure detection completely out of band with the sequentially consistent store, but I'd like to understand their architecture better.

I think your definitions are good, although thread-centric - to be really precise you have to talk a bit about 'steps' in the operational semantics of the program, but it's not helpful usually to do so.

Right, but if you make assumptions about the scheduler, you are tied to that scheduler's implementation, which introduces a significant coupling between OS implementation and language runtime that doesn't win you much and commits you to an implementation that, honestly, can and will change over time.

As you say, from the perspective of the program any scheduling interleaving is possible. The OS can substitute a new scheduling algorithm any time it likes. Otherwise we could know that the possible set of executions is much smaller than the set of all interleavings, and could write our concurrent code based upon that assumption. Then we'd be SOL when anyone tweaked the scheduler.

These are tricky waters, but here's what I see as the difference:

Two separate threads that can run completely independently without any synchronisation are concurrent because it doesn't matter what order you run them in. Therefore there are many, many 'sequentially equivalent' computations that are correct per the language semantics. From the perspective of the user it can seem like you ran Thread A to completion followed by Thread B, or Thread B then Thread A, or any interleaving of the two.

Threads are one way of expressing concurrency. Actors, to pick at random, are another. So I don't believe that threads <=> concurrency, but that threads usually express concurrency unless they have pathological synchronisation behaviour.

Which they would have, in your final example - there is no concurrency because there's only a single ordering of events that is correct.

Multiple threads of control aren't necessarily parallelisable. Consider a language runtime for which every thread takes the same global lock on the interpreter, and therefore prevents two threads running 'simultaneously'. You have concurrency but no parallelism. Such things happen in the real world.

So you might argue that concurrency is necessary for parallelism, but it's not sufficient.

Concurrency, to me, is about expanding the set of sequentially-equivalent executions of the program which are considered 'correct' according to the operational semantics of the programming language. If you just have one correct sequential execution, then there isn't any concurrency because you would have to execute sequentially to enforce the one correct ordering.

For example, consider this snippet:

1. a = 1 2. b = 2 3. print a to file1 4. print b to file2

For most realistic language semantics there's no dependency between lines 3, and 4, so it's ok to execute in the following orders:

1, 2, 3, 4 1, 3, 2, 4 2, 1, 3, 4 2, 1, 4, 3

and others. There is concurrency there, and if the runtime cannot detect or leverage it quite often the processor will with out-of-order-execution and pipelining.

However, the simpler snippet:

1. a = 2 2. b = a * 2 3. print a + b

Doesn't have any obvious concurrency (ignoring that in this case the compiler could optimise away the assignments and additions into a single statement). 1 must happen before 2, which must happen before 3. There is only one 'correct' sequential execution, and therefore there is no obvious parallelisation achievable.