aphyr

In a superconducting circuit

A circuit is a loop of something. Probably a solid material, like a metal or carbon, though it could be something more exotic. A superconducting circuit means the electrons in that material move without any resistance. This tells us the circuit is probably very cold--superconductors tend to break down at warm temperatures, like the ones in your house.

conduction electrons

Conductors have electrons in them. Some are "stuck" to atoms, others get to move around. Conduction electrons are the ones that move.

condense into a macroscopic quantum state

Macroscopic means "big", and for QM, "big" means, like, more than a handful of atoms or particles. At least as far as QM is concerned, everything--rocks, electrons, photons, people, etc., has a quantum state, but we use the phrase "quantum state" to mean a state that's, like, WEIRDLY QUANTUM. For instance, a pencil sitting on your desk is normal. A pencil that's like, half on your desk and half on mine is "quantum". Condensing means the electrons are going to change from doing normal individual electron things into acting like some sort of Big But Weirdly Quantum system, likely as a group. Like a crowd becoming a flash mob, they might do some sort of synchronized dance, only except the dance involves, say, every dancer doing two or three or ten dance moves at the same time.

such that currents and voltages behave quantum mechanically [2, 30].

Specifically, we're gonna be able to see quantum effects like superposition in Big Things like "current" and "voltage". The circuit might be in a combination of 3 volts and 5 volts at the same time. Also some of those voltages might be partly real and partly imaginary. Long story.

Our processor uses transmon

What the fuck is a transmon? I had to look this one up; it's a way of making these qubits less sensitive to voltage fluctuations.

qubits [6]

Qubits are quantum bits. A bit can be either 0 or 1. A qubit can be 0 or 1 or (and this is the quantum part) any state in between. Let's call the 0 state |0>, and the 1 state |1>. A qubit can be |1>, but it could also be (1/sqrt(2) |0>) + (1/sqrt(2) |1>). We call that a "cat" state, incidentally, because it's "half 1, half 0"--like Schroedinger's Cat, half alive and half dead. Again, the coefficients here are, in general, complex numbers, but we're gonna gloss over that.

which can be thought of as nonlinear

Nonlinear means they don't respond linearly to some input. Ever had someone do a series of small, mildly annoying things, and at some point you snapped and yelled at them? That's called "going nonlinear".

superconducting resonators

Oscillators are things that vibrate, like strings. Resonators have preferred frequencies to vibrate at. I don't exactly know what this means in this context, though. I'm guessing the circuit has some preferred frequencies it really likes to oscillate at.

at 5 to 7 GHz.

Voltages or currents or whatever are gonna go back and forth 5-7 billion times a second. That's about the same frequency as wifi signals, or microwaves.

The qubit is encoded

A qubit is an abstract thing on a whiteboard. There lots of ways we could actually make a thing that looks like a qubit. "Encoded", here, means "turned into an actual machine you can build in a lab".

as the two lowest quantum eigenstates of the resonant circuit.

An eigenstate, loosely speaking, is a state that has nothing in common with any other eigenstate. For instance, if we wanted to measure a particle's position on a line, we could take x=0 as one eigenstate, x=1 as another, x=2.5 as yet another, etc etc. An infinite number of eigenstates. Quantum systems can be in any (well, normalized) sum of eigenstates. My cat loves being inside and outside at the same time, so they're always trying to occupy 0.2|x=0> + 0.6|x=4> + 0.2|x=5>.

An operator is a thing you can do to a quantum state. Think of operators like functions on values, if you're a programmer, or like matrices that can be applied to state vectors, if you know linear algebra. For instance, I might have a measurement operator, which I use to look at my cat. There's also a special operator called the Hamiltonian, which (loosely) tells you what a state will look like after an infinitely small step in time.

Each operators has associated eigenstates, and those eigenstates have a magic property: if you apply that operator to one of its eigenstates, you get back the exact same state, times some complex number, which we call an eigenvalue. This means eigenstates for the Hamiltonian are, in a sense, stable in time. When we talk about the eigenstates of a system, we usually mean the eigenstates of the Hamiltonian. They could also be talking about measurement eigenstates--I'm not sure.

For the Hamiltonian, eigenvalues are, for Really Fucking Cool Reasons, energies. When we talk about "the two lowest quantum eigenstates", we mean the two states with the lowest energy. So maybe the circuit's eigenstates are, I dunno, 5 Ghz, 6 Ghz, 7 Ghz, etc. We'd take 5 and 6 as our |1> and |0> states.

Each transmon has two controls

A control is a thing we can use to change the transmon.

a microwave drive

Something like the microwave in your kitchen, but very small, and probably expensive.

to excite the qubit

This probably means changing the qubit from |0> to |1>. Microwaves carry energy, right? That's how they heat food. If they microwave the circuit at the right frequency, that microwave energy probably helps it jump from a lower frequency/energy to a higher one.

and a magnetic flux control

This feels like something specific to transmons. Flux has to do with the density of stuff moving through a surface. Magnetic flux probably has to do with how strong and close field lines are in some part of the transmon machinery.

to tune the frequency.

How fast the circuit wobbles depends on a magnetic field, I guess?

Each qubit is connected to a linear resonator

Huh. So we've got nonlinear resonators (the qubits) connected to linear resonators (some sort of measurement device?)

used to read out the qubit state

We need a way to actually look at the qubits, and I guess the linear resonator does that. I assume that the linear resonator is isolated from the qubit during computation, and once the computation is over, it gets connected somehow, and vibrates at the same frequency as the qubit. That process probably "spreads out" the quantum state of the system, pushing it REAL CLOSE to an actual eigenstate of the measurement system, which looks like a probabilistic measurement of the actual qubit state.

Like... my cat could be 3/4 inside and 1/4 outside, so long as the room is really dark. If I turn on the light, suddenly my cat is coupled to a MUCH BIGGER system--the room, and that "quantum" state gets diffused into that larger system, in what looks like a measurement like "cat definitely inside". I don't know a simple way to explain decoherence, haha, but if you like math, try Percival's "Quantum State Diffusion".

Hope this helps, and I also hope I got at least some of this right. Maybe someone with a better/more recent command of QM can step in here.

There might be other ways this could play out in migrations--I haven't had time to look deeply.

I, er, don't mean to be rude, but... both grogers and I have already explained that this idea is somewhat less than correct. The anomaly you're describing is called lost update, and is explicitly prohibited by both snapshot isolation and serializable isolation, the two isolation levels supported by YugaByte DB. Linearizability is not necessary to prevent lost updates. This is not only a theoretical fact, but supported by experimental evidence: we have extensively tested YugaByte DB for lost updates, and have not (yet) observed any.

i didnt say banking per se. can involve a simple billing system of a startup. or any critical data where you need to ensure you are reading accurate, uptodate values. maybe a leaderboard.

While linearizability may be a nice property for these systems to have, it is rarely necessary. Billing systems and leaderboards, like bank ledgers and shopping carts, are often designed as append-only ledgers with eventual consistency, employing sealing windows, compensating transactions, and time-shifting to handle late discovery of events. Others are designed as as reports periodically derived from some underlying datastore via, say, an ETL process; data may be not only milliseconds, but even days or weeks out of date. That's not to say this is a universal pattern, but I can think of a few dozen systems off the top of my head.

I know this because I've worked on several systems like this, including in fintech, and consulted for companies and government organizations building others. I can also offer some anecdotal experience here. For example, I have no fewer than three emails in my inbox from AWS's billing system informing me of missing data or other mistakes in the previous month's bill, accompanied by updated reports providing newer data. Last summer, my bank deferred visibility of some transaction data for over six weeks.

This might feel counter-intuitive, but since money is fungible and addition is commutative, it's one of the easiest things to work with in a stale or even eventually-consistent manner. Where you really want linearizability (or at least sequential consistency) is in domains where operations don't commute. Linearizability is particularly important where those non-commutative operations involve side-channels, but that's a longer discussion for another time.

'most' is not a guarantee

This is true, but there is a qualitative difference between a system which exhibits, say, a 5ms stale read once per thousand transactions during clock skew, and a 10-day stale read one in every two transactions all the time. I mention these numbers to provide a rough characterization of anomaly frequency and severity.

the marketing on yugabyte's page makes it seems it can replace db's like cassandra and give you a consistent view of your data. but if one is seeing stale values, you are back to coding like data is non-consistent

Linearizability is not the only form of consistency model, and many models have no realtime properties whatsoever. You might find https://jepsen.io/consistency informative.

As grogers notes, a stale read is a different phenomenon than the burger problem you describe, which is also called "lost update". We didn't observe any cases of lost updates in YugaByte DB.

As for monetary values, you might find it interesting to ask someone who works in banking or fintech about recency properties of their data systems. Latencies on the order of multiple days are surprisingly common.

I think a bunch of factors are in play here. Sometimes vendors discover bugs with Jepsen, then adjust the test so that it passes, rather than fixing the underlying bug. Consul, IIRC, found errors with Jepsen, and adjusted a timeout parameter to prevent the test from observing concurrent primary nodes, which meant the test passed. The underlying problem was still there--but no longer visible. Sometimes you'll see people turn a workload that does a read-modify-write transaction into a single-statement update transaction, in such a way that the database can execute it atomically. That's still a legal and sensible test, but may not measure the same type of transactional isolation.

Other times, vendors write a custom checker, but haven't tested to make sure that it can catch the anomaly that it's supposed to. Maybe a checker is copy-pasted from another test I wrote for a different system which used different names or data structures to represent histories, so it executes successfully, but in a trivial way--maybe it fails to realize any elements were added to a set, so it assumes every read is legal, since all 0 elements are present!

Other times tests are correctly written, but only run for a short time--maybe the nemesis schedule they designed doesn't actually cause leader elections to take place, so you never observe that phase change in the system. Or the test only performs a handful of operations and sits idle until the end of the test. Or every request fails, and the test passes trivially, since we never observed an illegal result. Some of these mistakes I can address with better analyzers and prompting users with guided error messages. Others you have to qualitatively infer by looking at the graphs and histories. That's something I work on training people to do in my classes, but I haven't written good guides for it online yet.

And of course, there's a familiarity problem: with Jepsen, I've been working on and with this tool for six years, so I'm intimately familiar with its behavior and testing philosophy. So much of that knowledge is implicit and intuitionistic for me, and users who are adopting that tool fresh don't have the benefit of that experience! It's something you can build with time, and I can help transfer with writing and teaching. Working on it! :)

Writing tests is also great! Pick a system you like and dive in. There's a full tutorial (https://github.com/jepsen-io/jepsen/tree/master/doc/tutorial) that walks you through designing and running a test from scratch.

You can use CRDTs, and other commutative data structures, to obtain totally-available replicated objects across wide area networks. Systems like Riak do this. CRDTs can't express some types of computation safely, though! For instance, you can't do something like a minimum-balance constraint, ensuring that an account always contains $25 or more, if you allow both deposits and withdrawals, in a commutative system. Why? Because order matters! Deposit, withdraw is different than withdraw, deposit, in terms of their intermediate states.

For order, you can use a consensus mechanism, like ZAB (Zookeeper), Paxos (Riak SC, Cassandra LWT), or Raft (etcd, consul) to replicate arbitrary state machines without any clock dependence at all. These systems require at least one round trip to establish consensus, and their guarantees only apply within the consensus system itself.

What if you have multiple consensus groups? Say, one per shard? Then you need a protocol to coordinate transactions on top of that. You can execute an atomic commit protocol for cross-shard transactions, perhaps using a consensus system. Or you can use a protocol like Calvin to obtain serializability (or stronger) across shards without relying on clocks. That's what FaunaDB does. That adds a round-trip, but if you're clever, you may only have to pay that round-trip cost between different datacenters once.

Another tactic is to exploit well-synchronized clocks to obtain consistent views across independent consensus groups. You can use this technique to (theoretically) reduce the number of round trips a transaction costs, and there are different ways to balance whether you pay increased latency on read or write transactions. Spanner, CockroachDB, and YugaByte DB all take this approach, with different tradeoffs.

Spanner is backed by custom hardware and carefully designed software, to obtain tight bounds on clock error. CockroachDB and YugaByte DB leave that problem to you, the operator.

Often, a database uses a stronger replication mechanism inside a datacenter, but when it comes to replicating between datacenters, backs off to a weaker strategy which doesn't offer the same safety invariants.

There are still tons of caveats with this idea--Linux and most database software ain't realtime, for starters--but you can imagine a world in which clock errors are sufficiently bounded and infrequent that they no longer represent the most urgent threat to safety. That's ultimately a quantitative risk assessment.

My suspicion is that DB vendors like YugaByte and CockroachDB are making a strategic bet that although clocks right now are pretty terrible, they won't be that way forever. I'd like to see more rigorous measurement on this front, because while I've got plenty of anecdotes, I don't think we have a broad statistical picture of how bad typical clocks are, and whether they're improving.

[1]: https://www.scylladb.com/2016/02/11/jepsen-testing/

[2]: https://github.com/scylladb/scylla/issues?utf8=%E2%9C%93&q=i...

Companies are finding bugs using Jepsen internally, which is great! But when they hire me, I'm usually able to find new behaviors. Some of that is exploring the concurrency and scheduling state space, some of it is reviewing code and looking for places where tests would fail to identify anomalies, some of it is designing new workloads or failure modes, and some is reading the histories and graphs, and using intuition to guide my search. I've been at this for five years now (gosh) and built up a good deal of expertise, and coming at a system with an outsider's perspective, and a different "box of tools", helps me explore the system in a different way.

I do work with my clients to determine what they'd like to focus on, and how much time I can give, but by and large, my clients let me guide the process, and I think the Jepsen analyses I've published are reasonably independent. If there's something I think would be useful to test, and we don't have time or the client isn't interested in exploring it, I note it in the future work section of the writeup.

It's not like clients are saying "please stick ONLY to these tests, we want a positive result." One of the things I love about my job is how much the vendors I work with care about fixing bugs and doing right by their users, and I love that I get to help them with that process. :)

Second, FaunaDB's transactional model precludes interactive transactions, whereas SQL transactions are designed for interactive use. Imagine if every transaction was a stored procedure--that's the query structure you'd be looking at. It's certainly possible to do, but stored procedures are sort of an imperative language grafted on to the relational algebra of SQL, and support isn't as standardized as SQL's core.

Third, FaunaDB is a temporal store--you can ask for the state of any query at any point in time, and even mix temporal scopes in the same query expression. SQL doesn't have a first-class temporal model.

In general, using SQL offers advantages, including user familiarity, code reuse, and easier migration from other SQL stores. None of the things FaunaDB does are impossible to express in SQL, and they have been tackled by various DBs' extensions to SQL, but the familiarity+reuse advantages aren't as applicable once you start thinking about the distinct properties of FaunaDB's data model.

That said, I don't think it's reasonable to infer that because failures occur more often than we'd like, systems based on consensus are always inappropriate for latency and performance sensitive systems. While there are minimum bounds on latency in consensus systems, there are also plenty of human-scale problems for which that bound isn't a dealbreaker. Moreover, some types of computation (e.g. updates in sequentially consistent or snapshot isolated systems) simply can't be performed without paying the same costs as consensus. Consensus can be an appropriate, and in some cases the only possible solution, to some problems.

http://cs.yale.edu/homes/thomson/publications/calvin-sigmod1...

FaunaDB is a unique database: its architecture offers linear scalability for transaction throughput (limited, of course, by contention on common records and predicates). That sets it aside from databases which use a single coordinator for all, or just cross-shard, transactions, like Datomic and VoltDB, respectively.

It's also intended for geographic replication, which is a scenario many databases don't try to handle with the same degree of transactional safety--lots of folks support, say, snapshot isolation or linearizability inside one DC, but between DCs all bets are off.

FaunaDB also does not depend on clocks for safety, which sets it aside from other georeplicated databases that assume clocks are well-synchronized. Theoretically, relying on clocks can make you faster, so those kinds of systems might outperform Fauna--at the potential cost of safety issues when clocks misbehave. In practice, there are lots of factors that affect performance, and it's easy to introduce extra round trips into a protocol which could theoretically be faster. There's a lot of room for optimization! I can't speak very well to performance numbers, because Jepsen isn't designed as a performance benchmark, and its workloads are intentionally pathological, with lots of contention.

One of the things you lose with FaunaDB's architecture is interactive transactions--as in VoltDB, you submit transactions all at once. That means FaunaDB can make some optimizations that interactive session transactions can't do! But it also means you have to fit your transactional logic into FaunaDB's query language. The query language is (IMO) really expressive, but if you needed to do, e.g. a complex string-munging operation inside a transaction to decide what to do, it might not be expressible in a single FaunaDB transaction; you might have to say, read data, make the decision in your application, then execute a second CaS transaction to update state.

FaunaDB's not totally available--it uses unanimous agreement over majority quorums, which means some kinds of crashes or partitions can pause progress. If you're looking for a super low latency CRDT-style database where every node can commit even if totally isolated, it's not the right fit. It is a good fit if you need snapshot isolation to strict serializability, which are strong consistency models!

I'm delighted they have rigorous tests, and I'm glad our tool has been helpful for them! We just can't say anything about those tests, because we haven't looked yet. Maybe someday!