Distributed data: replication, the CAP theorem, NoSQL and data warehouses

Large information systems do not sit on a single server: data is copied to several machines so as not to stop when one fails, distributed over many nodes to handle huge volumes, and reorganised into separate stores for analysis. In this lesson we look at replication and the quorum condition with its proof, the CAP theorem with proof, eventual consistency and NoSQL databases, data warehouses with the star schema and OLAP analysis, and the protection of personal data.

Replication

Keeping several copies of the same data on different servers increases availability (lesson on architectures) and makes it possible to spread reads. The problem is keeping them aligned. In synchronous replication a write is acknowledged only when all copies have received it: the copies are always identical, but every write waits for the slowest node and blocks if one does not answer. In asynchronous replication the write is acknowledged at once and propagated later: fast, but for a moment a copy may return old data, and if the primary node fails before propagating, the last writes are lost.

Quorums

A middle way: with copies, a write is acknowledged when copies have received it, and a read queries copies and takes the most recent value (every value carries a version number).

Theorem. If , every read sees the last acknowledged write.

Proof. The last acknowledged write is on a set of at least copies; the read queries a set of copies. If the two sets were disjoint, together they would contain distinct copies, more than exist: impossible. So at least one queried copy has the latest version, and the read, taking the most recent version, returns it. ∎

With , the typical choice tolerates the failure of one copy for both reads and writes; makes reads fast and writes slow.

The CAP theorem

In a distributed system one would like three properties:

• consistency (C): every read returns the latest write, as if there were a single copy;
• availability (A): every request to a working node receives a response;
• partition tolerance (P): the system keeps working even if the network splits into parts that cannot communicate.

Theorem (CAP, Brewer, proved by Gilbert and Lynch). During a network partition a system cannot be both consistent and available.

Proof. Consider two nodes each with a copy of data item , initially 0, separated by a partition: no message passes between them. A client writes to the first node; if the system is available, the write receives a response. Then another client reads from the second node; if the system is available, the read also receives a response. But the second node could not receive anything from the first, so it answers 0: consistency is violated. To be consistent the system must refuse or indefinitely delay the write or the read, giving up availability. ∎

Partitions do happen in real networks, so the real choice is between C and A when there is a partition: banks and booking systems choose consistency (better to refuse an operation than to sell the same seat twice), social networks and shopping carts choose availability.

Eventual consistency and NoSQL

Systems that favour availability offer eventual consistency: if no new writes arrive, sooner or later all copies converge to the same value. Many NoSQL databases, designed to spread data over hundreds of nodes, are based on this model:

• key-value (as in a distributed hash table), for sessions and caches;
• document stores, holding JSON objects with a flexible structure;
• column-family stores, for huge sparse tables;
• graph databases, for complex relationships such as social networks.

They partly give up joins and multi-object transactions in exchange for scalability. In recent years NewSQL and distributed databases (with consensus protocols such as Raft and Paxos) again offer ACID transactions across many nodes, paying for consistency with some latency.

The data warehouse

Operational systems are optimised for many small transactions; executive analyses (“sales by region and quarter over the last five years”) read millions of rows and would slow everything down. So a data warehouse is built: a separate store, fed periodically by an extract, transform and load (ETL) process that cleans and integrates the data from the various sources.

The typical schema is a star: a fact table with the measures (amounts, quantities) and the keys to the dimension tables (time, product, customer, place), deliberately not normalised so as to require few joins (lesson on normalisation). OLAP analysis navigates this data cube: rolling up (from months to years), drilling down into detail, slicing by a region. Modern systems store data by columns rather than by rows: a query that sums a single column of a billion rows reads only that column, compressed. Data lakes instead keep raw data, even unstructured, for future analyses and for machine learning.

Protection of personal data

An information system that handles people’s data must comply with data protection rules, in Europe the GDPR: collect only the data needed for a declared purpose (minimisation), keep it only as long as necessary, protect it with adequate measures (encryption, access control, logging of operations), allow people to consult it, correct it and ask for its erasure, and notify breaches. Protection must be designed in from the start (privacy by design), not added at the end: the database schema itself, separating identifying data from usage data and pseudonymising where possible, is part of it.