All of our discussion of correctness, integrity, and fault tolerance has been under the assumption that certain things might go wrong, but other things won’t. We call such assumptions our system model (see “System Model and Reality”). For example, we should assume that processes can crash, machines can suddenly lose power, and the network can arbitrarily delay or drop messages. We might also assume that data written to disk is not lost after fsync, that data in memory is not corrupted, and that the multiplication instruction of our CPU always returns the correct result.
These assumptions are quite reasonable, as they are true most of the time, and it would be difficult to get anything done if we had to constantly worry about our computers making mistakes. Traditionally, system models take a binary approach toward faults: we assume that some things can happen and that other things can never happen. In reality, it is more a question of probabilities: some things are more likely, other things less likely. The question is whether violations of our assumptions happen often enough that we may encounter them in practice.
We have seen that data can become corrupted in memory (see “Hardware and Software Faults”), on disk (see “Replication and Durability”), and on the network (see “Weak forms of lying”). Maybe this is something we should be paying more attention to? If you are operating at large enough scale, even very unlikely things do happen.
Maintaining integrity in the face of software bugs
Besides such hardware issues, there is always the risk of software bugs, which would not be caught by lower-level network, memory, or filesystem checksums. Even widely used database software has bugs—for example, past versions of MySQL have failed to correctly maintain uniqueness constraints, and PostgreSQL’s serializable isolation level has exhibited write skew anomalies in the past, even though MySQL and PostgreSQL are robust and well-regarded databases that have been battle-tested by many people for many years. In less mature software, the situation is likely to be much worse.
Despite considerable efforts in careful design, testing, and review, bugs still creep in. Although they are rare, and they eventually get found and fixed, there is still a period during which such bugs can corrupt data.
When it comes to application code, we have to assume many more bugs, since most applications don’t receive anywhere near the amount of review and testing that database code does. Many applications don’t even correctly use the features that databases offer for preserving integrity, such as foreign-key or uniqueness constraints.
Consistency in the sense of ACID is based on the idea that the database starts off in a consistent state, and a transaction transforms it from one consistent state to another consistent state. Thus, we expect the database to always be in a consistent state. However, this notion makes sense only if we assume that the transaction is free from bugs. If the application uses the database incorrectly in some way—for example, using a weak isolation level unsafely—the integrity of the database cannot be guaranteed.
Don’t just blindly trust what they promise
With both hardware and software not always living up to our ideals, data corruption seems inevitable sooner or later. Thus, we should at least have a way of finding out if data has been corrupted so that we can fix it and try to track down the source of the error. Checking the integrity of data is known as auditing.
As discussed in “Advantages of immutable events”, auditing is not just for financial applications. However, auditability is very important in finance precisely because everyone knows that mistakes happen, and we all recognize the need to be able to detect and fix problems.
Mature systems similarly tend to consider the possibility of unlikely things going wrong and manage that risk. For example, large-scale storage systems such as HDFS and Amazon S3 do not fully trust disks. These systems run background processes that continually read back files, compare them to other replicas, and move files from one disk to another, in order to mitigate the risk of silent corruption.
If you want to be sure that your data is still there, you have to read it and check. Most of the time it will still be there, but if it isn’t, you want to find out sooner rather than later. By the same argument, it is important to try restoring from your backups from time to time—otherwise, you may find out that your backup is broken when it is too late and you have already lost data. Don’t just blindly trust that it is all working.
Systems like HDFS and S3 still have to assume that disks work correctly most of the time—which is a reasonable assumption, but not the same as assuming that they always work correctly. However, not many systems currently have this kind of “trust, but verify” approach of continually auditing themselves. Many assume that correctness guarantees are absolute and make no provision for the possibility of rare data corruption. In the future we may see more self-validating or self-auditing systems that continually check their own integrity rather than rely on blind trust.
Designing for auditability
If a transaction mutates several objects in a database, the underlying reason can be difficult to tell after the fact. Even if you capture the transaction logs, the insertions, updates, and deletions in various tables do not necessarily give a clear picture of why those mutations were performed. The invocation of the application logic that decided on those mutations is transient and cannot be reproduced.
By contrast, event-based systems can provide better auditability. In the event sourcing approach, user input to the system is represented as a single immutable event, and any resulting state updates are derived from that event. The derivation can be made deterministic and repeatable, so that running the same log of events through the same version of the derivation code will result in the same state updates.
Being explicit about dataflow makes the provenance of data much clearer, which makes integrity checking much more feasible. For the event log, we can use hashes to check that the event storage has not been corrupted. For any derived state, we can rerun the batch and stream processors that derived it from the event log to check whether we get the same result, or even run a redundant derivation in parallel.
A deterministic and well-defined dataflow also makes it easier to debug and trace the execution of a system to determine why it did something. If something unexpected occurred, it is valuable to have the diagnostic capability to reproduce the exact circumstances that led to the unexpected event—a kind of time-travel debugging capability.
The end-to-end argument again
If we cannot fully trust that every individual component of the system will be free from corruption—that every piece of hardware is fault-free and every piece of software is bug-free—then we must at least periodically check the integrity of our data. If we don’t check, we won’t find out about corruption until it is too late and it has caused some downstream damage, at which point it will be much harder and more expensive to track down the problem.
Checking the integrity of data systems is best done in an end-to-end fashion. The more systems we can include in an integrity check, the fewer opportunities there are for corruption to go unnoticed at some stage of the process. If we can check that an entire derived data pipeline is correct end to end, then any disks, networks, services, and algorithms along the path are implicitly included in the check.
Having continuous end-to-end integrity checks gives you increased confidence about the correctness of your systems, which in turn allows you to move faster. Like automated testing, auditing increases the chances that bugs will be found quickly, and thus reduces the risk that a change to the system or a new storage technology will cause damage. If you are not afraid of making changes, you can much better evolve an application to meet changing requirements.
Tools for auditable data systems
At present, not many data systems make auditability a top-level concern. Some applications implement their own audit mechanisms—for example, by logging all changes to a separate audit table—but guaranteeing the integrity of the audit log and the database state is still difficult. A transaction log can be made tamper-proof by periodically signing it with a hardware security module, but that does not guarantee that the right transactions went into the log in the first place.
Blockchains such as Bitcoin and Ethereum are shared append-only logs with cryptographic consistency checks; the transactions they store are events, and smart contracts are basically stream processors. The consensus protocols they use ensure that all nodes agree on the same sequence of events. The difference from the consensus protocols of the related discussion is that blockchains are Byzantine fault-tolerant—that is, they still work if some of the participating nodes have corrupted data because the replicas continually check one another’s integrity.
For most applications, blockchains have too high an overhead to be useful. However, some of their cryptographic tools can also be used in a lighter-weight context. For example, Merkle trees are trees of hashes that can be used to efficiently prove that a record appears in a dataset (and a few other things). Certificate transparency uses cryptographically verified append-only logs and Merkle trees to check the validity of TLS/SSL certificates; it avoids needing a consensus protocol by having a single leader per log.
Integrity-checking and auditing algorithms, like those of certificate transparency and distributed ledgers, might become more widely used in data systems in general in the future. Some work will be needed to make them as scalable as systems without cryptographic auditing and to keep the performance penalty as low as possible, but they are nevertheless interesting.