Sound approximations
When exactness is too expensive, use a sound approximation.
What it is
The first honest note. Conflict serializability is sufficient but not necessary for correctness. A weaker criterion, view serializability, accepts strictly more schedules, and it is the more faithful definition of "equivalent to a serial run". But testing view serializability is NP-complete (no efficient algorithm is known). Therefore every production system enforces a criterion stricter than correctness requires, because the exact criterion is intractable. Keep this in mind. It comes back several times, and by the end of Multiversion, optimistic and other schemes it will have a name.
From Transactions & Concurrency Control › The serialization graph
Everything that ships is an approximation of MIN, and the approximation ladder has two rungs:
From Memory & Resource Management › The replacement problem
In an asynchronous network you can have completeness always, and accuracy only eventually. The timeout is the dial between them.
From Distributed Systems Coordination › Failure detection
Where it appears
In 13 mechanisms. Each says what the mechanism is about, then how this principle shows up there, in its own words.
- Data Movement
How do records cross between two systems that have independent rates, independent availability and independent lifetimes, and what are you willing to lose when the assumption underneath the crossing breaks?
Every heartbeat timeout is therefore a guess, and the timeout value is a trade-off:
- Transactions & Concurrency Control
What happens when many users change the same data at the same time, and how do we keep the result correct?
Therefore every production system enforces a criterion stricter than correctness requires, because the exact criterion is intractable.
Read it inOne graph, kept free of cyclesLock granularity and intention locksSerializable snapshot isolation (SSI)Begin, commit and abort
- Consistency & Isolation Models
When many users, many objects and many copies exist at once, which histories does the system promise never to show, and who writes the code for the histories it does show?
Truncating version vectors (to bound their size) manufactures false concurrency: two causally ordered writes look concurrent and must be merged or arbitrated.
Read it inCausal consistencyLinearizability and sequential consistencyAn isolation level is a set of forbidden cyclesWrite skew, and the exact boundary of snapshot isolation
- Query Planning & Optimization
How does a system choose a plan for a question when the facts that decide the best plan are unknown until the plan has run?
Every engine implements a restricted, conservative matcher that proves subsumption for a bounded class of patterns, and gives up otherwise.
- Memory & Resource Management
Who is allowed to hold how much memory, for how long, and what happens to the work when the answer is less than it asked for?
Everything that ships is an approximation of MIN, and the approximation ladder has two rungs:
Read it inThe replacement problem, and why every answer is an approximation
- Caching
What happens when we deliberately keep a second copy of data that no protocol forces to be correct?
A cache whose lookup is a search rather than a probe competes with the work it is trying to save.
Read it inCost-aware eviction: the policy family that can be badly wrongSemantic caching: bounded by the cost of deciding a hit
- Distributed Systems Coordination
Who is allowed to decide, and how does everyone else learn the decision without asking?
The objective function is a proxy for the thing you care about, and the residual is systematic rather than random.
Read it inRebalancing: a controller with a loop delay measured in hours
- Fault Tolerance & Delivery Semantics
What is the cheapest thing that can be safely done twice?
Detection is a timeout, and you cannot improve detection speed and detection accuracy at the same time (Failure detection).
Read it inFailover: automatic, manual, fenced
- Cost Mechanics
What is metered, and what is the smallest increment you are charged for?
The denominator is a proxy and carries a systematic residual. $/query falls when people write fewer, larger queries, which may be better or worse. $/GB ingested falls when you ingest junk.
Read it inUnit economicsThe exchange rate between all the other units
- Data Quality & Validation
How do you check that data is right, when "right" is a claim about the world and not about the bytes?
A validation check is decidable only to the extent that its referent is already inside the system.
Read it inWhat makes a check expensive
- Metadata, Catalog & Lineage
What can a system prove about its data without reading the data, and how does it know that proof is still true?
A partition is a predicate (a true/false condition) that is proven true for a set of files, without reading them.
Read it inMetastore mechanismsImpact analysis and deprecation
- Specialized Processing Models
What do you build when a query predicate cannot be reduced to a range over an ordered key?
One line: a global grid converts containment into prefix matching so ordinary indexes can do spatial work.
Read it inSpatial joins and discrete global gridsThe one assumption behind every ordinary indexThe shared template: project, prune, refine
- Measurement & Experimental Method
What would have to be true for this number to mean what I think it means?
An explanation earns belief by predicting a second, different observation.
Read it inBeyond staging: production, cost and explanationMicro versus macro, and benchmarketingRegression to the mean and the stopping rule
Related
Made on the same pages most often.