ngbronson

That's a fallback implementation for platforms without SIMD. The real code is lower down.

sparsehash is still more memory efficient, but it is quite slow in comparison. Also, in practice it doesn't reach the ultra-low space overheads claimed by the documentation. It allocates memory blocks of many different sizes, so the dominant space overhead becomes internal fragmentation in the allocator. For sparsehash using JEMalloc's default allocation classes (spaced about a factor of 1.2 apart) the memory used relative to useful data varies from about 1.3 for small values to 1.1 for large values.

F14 supports stateful hashers, so in situations that need to be resilient to hash poisoning we can use a hasher designed for that purpose.

You're right, it's been available for a while now. This is the first time we've made an announcement about it.

Non-SIMD algorithms work better in some cases, for example if you look up the same key over and over (so the control flow is predictable) or when all of the data is in the L1. The SIMD approach tends to be more robust inside a larger program where there's less chance for branch prediction and caching to help you.

Sharding your product so that no cross-shard links are possible is robust and scalable, but it requires you to understand your final product very well at design time. If you start down that path and then bolt on some cross-shard data, the end result is almost always worse then if you had planned for that from the start.

So to get back to Spanner's availability (if you need it), you need the Calvin sequencer Paxos groups to span data centers. Since you're not exploiting the commutativity structure of transactions you need either a leader-based consensus implementation, which will have latency stalls when a leader becomes unavailable (amplified by the all-to-all communication), or you can use old-school 2 RTT Paxos, and your end latency ends up the same as Spanner.

Lest it seem like I'm not actually a fan of the log-based approach, let me point out a way in which Calvin crushes Spanner: write contention. So long as the Calvin transactions can encode the application logic, they can support extremely high write rates on contended objects in the database. Spanner's 2PL, on the other hand, has single-object object update rates visible to the naked eye.

I mistyped, I meant to say that a stalled sequencer stalls all schedulers. It's true that Corfu has impressive per-sequencer throughput (by moving most of the work onto other nodes), but you have to move to multiple sequencers to get to Spanner scale.

The all-to-all dependency step between Calvin's sequencer layer and scheduler layer seems like it will be a problem as things scale, because it means that a single stalled sequencer [edit, orig: scheduler] blocks all writes in the system whether they conflict or not. This is the kind of dependence structure that magnifies outlier latencies and unavailability at scale.

In Spanner's design, on the other hand, a transaction can only be blocked by another one on which it actually conflicts. It will have worse average performance, but better tail latency as things scale.

Perhaps it is just a nit, but the blog post is somewhat inaccurate when it says that Spanner uses the commit timestamp to order transactions. It uses locks to order the transactions, then holds the locks for extra time to ensure that TrueTime order agrees with the lock-based order.

Thank you for publishing the code for your paper. It's an excellent contribution by itself, and should help people understand and evaluate the ideas. Are you going to publish the TLA+ specification as well?