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.

I haven't seen those discussions, but is it possible that they were trying to rehash the results of Object.hashCode rather than pass all of the bytes of the original value through a new hash algorithm?

If you haven't seen it before you will appreciate https://accidentallyquadratic.tumblr.com/post/153545455987/r...

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

It would be nice to have a deeper understanding of how/why this works, but in practice it seems fine. Under a continuous insert and erase workload the number of chunks with an overflow fluctuates a bit but stays low enough to keep probe lengths short, so F14 never needs to rehash to clean them up. Batched adds and then removes might let you bias a bit toward having longer probes for the remaining keys, but it never gets too bad. A truly adversarial workload could make things pretty bad, but they could also just insert lots of keys that all have the same hash code.

See the steady_state_stats test at https://github.com/facebook/folly/blob/master/folly/containe...

https://github.com/rust-lang/hashbrown is a port of Google's SwissTable algorithm (abseil flat_hash_map). It also uses SIMD filtering and has the potential to be quite good.

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.

I'm one of the authors. Seeing the Google presentation at CPPCon convinced us that the potential wins were worth the effort to productionize, but the similarity in the designs is a case of convergent evolution. Since then Google and Facebook have collaborated on a microbenchmark (https://github.com/google/hashtable-benchmarks/), which shows that the algorithms have slightly different tradeoffs but neither dominates the other.

If there is metadata available at every slot then you can track overflows rather than tombstones. These let you terminate the search earlier (you don't need to find an empty) and can be cleaned up on erase, because they are a property of the keys in the map rather than the keys that are no longer in the map.

folly's F14 maps use this strategy, and handle erase + insert workloads fine with no rehashing needed. https://github.com/facebook/folly/blob/master/folly/containe...

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?

One option for compatibility on non-futex platforms is to write your own futex emulation using striped std::mutex or pthread_mutex_t. The emulated futex API still has the same slow-path-only goodness as a real futex, but is fully portable.

For an example of this technique, check out https://github.com/facebook/folly/blob/master/folly/detail/F... . That code only implements wake and wait, but it would be straightforward to extend it to the other futex operations.

Metastability comes in when you think about the problem that originally triggered congestion. A normal network overload caused by a bulk transfer, for example, can be fixed by canceling the transfer. Once you add the feedback loop, however, you need to both cancel the transfer and remove lots of other load. I use the term metastable because although it is fully stable (that's the problem!) it isn't the "ground state". Another way to say it is that the metastable states are only local attractors.

When the pool was originally coded, MySQL had one thread per open connection. That made the auto-sizing MRU pool a pretty big win, because it kept the connection counts as low as possible while using the warmest database threads. MySQL has matured since then, so this optimization is no longer important.

Out-of-order delivery causes TCP to shrink the congestion windows, which cuts throughput. Connection pools help here (in addition to their reduction in setup and teardown work), because they let the windows widen and stay open. We disable tcp_slow_start_after_idle to take advantage of this.

One of the reasons this took a long time to figure out is that it was a failure amplifier, so there was always a more typical network problem preceding it. Network failures in a data center cause lots of changes to the packets, because of retries, failover, and automatic load balancing, so there were a lot of trees to look at.

I coded the fix. We considered some options that had a bias away from the slow links, but we thought it was safer to avoid bias completely. It was fine in my tests, but I couldn't prove that biasing toward the faster link in a 2 link setup wouldn't set up an oscillation.