Data: A Free and Easy Wandering
Is the sky’s deep blue its true color? Or is it only that it lies so far away that it has no limit? When it looks down, it must be the same. — Free and Easy Wandering (Zhuangzi)
To a programmer, data is the thing we deal with at every moment. Our code is a machine that transforms or maps incoming data into outgoing data. Mathematically, it is nothing more than y = f(x). Data is like the fish in Zhuangzi’s tale: under the work of code it now takes the form of a file, “sinking” into the file system; now it becomes a variable, “floating” in memory; and then it rises on the wind and becomes a byte stream, “soaring” across the network.
The Book of Changes speaks of the simple, the changing, and the unchanging. However varied, complex, and abstruse data may be, once we clarify its concepts and understand its temperament, we can control it and master it; and from its endless transformations we can extract fixed patterns and become its owner. Unable to sleep because of jet lag, this topic suddenly came to mind, and I wanted to talk it over with you.
Concepts
Concepts are the essence of things. Muddy concepts produce muddy relationships, which drag thinking into a muddy swamp. To do a job well, one must first get the names right. Let’s look at what concepts surround data.
Identity
An identity is the only “name” that can represent the data itself. There are two implications here: 1) uniqueness, 2) representation. We often conflate identity with name. My WeChat account is called “A Programmer’s Life,” but that name does not represent the account—any account can be named “A Programmer’s Life.” An identity must be unique. In daily work, though, we tend to notice only uniqueness and ignore representativeness. Think about it: is an ID an identity? 99.999% of the time we would say an ID is equivalent to an identity. Through Wang Xiao’er’s national ID number we can find precisely the person Wang Xiao’er, but the link between the number and the person is a fragile, one-way connection. I can find Wang Xiao’er; but from Wang Xiao’er alone I cannot derive his ID number. Those born in the 1980s probably remember that roughly fifteen years ago our ID numbers went from 15 digits to 18. The old numbers remained unique, but they lost the data bound to them. If an identity can represent the data, then the data should also be able to deterministically derive its identity with some algorithm; likewise, the identity of data cannot change, and should not change.
For a human being, the identities meeting this condition are the iris, the fingerprint, the DNA: even if Wang Xiao’er becomes Wang Xiao San, even if the ID becomes Thai instead of Chinese, she is still him. For data, the identities meeting this condition are md5, sha1, sha2, sha3, and so on.
Note that an identity uniquely represents the data, but data may have more than one identity. There is no contradiction here.
Address
Having unwound the thread and separated identity from the many concepts it is entangled with, we are in a better position to explain what follows. Once identity is clear, address is much easier. An address locates and finds data; it is one-way and unique. In that sense, address is a superset of identity, and identity a subset of address. The ID number mentioned above is an address. Other common addresses: the ID of a record in a database—or more precisely, hostname + database name + table name + ID is the address of that record; a filename with a full path is the address of the file’s content; a five-tuple containing IP addresses and ports (src ip, src port, dest ip, dest port, protocol) is the address of a socket connection.
An address and the content it maps to constitute a logical key-value store. So a file system is essentially a KV store: give me a filename (key), and I will find and hand you its content (value).
We said identity is a subset of address. So what if we address data by its identity? That opens a wondrous world—the identity points to the data, and the data itself derives the identity, thereby proving that the content I am addressing really is the content I am addressing. Savor the power of that sentence. For example: late at night, in the quiet, you furtively put on your headphones, and with a trembling right hand you double-click Aoi_Sora.avi—and out comes the Heart Sutra…
Reference
Once you understand addresses, what is a reference? Why do we need references? A reference is a middleware that ties the address of data to the context in which that data is handled. A person’s name is the most important reference. With names, people need not labor to remember 9527; they say “Hua An” to refer to 9527. Within the context of the Hua mansion, 9527 is Hua An; outside of it, he is Tang Bohu. So we say that a reference connects the address of data with a context. In this sense, a reference is a form of indirection: it lets the two layers it isolates remain ignorant of each other’s existence. There is a famous saying in computing: Any problem in computer science can be solved with another layer of indirection. Hence the enormous power of references. Rich Hickey, the father of Clojure, said in his talk Simple Made Easy that references let us avoid the dreadful PLOP—PLace Oriented Programming.
With references, you can use a variable name to stand for a variable’s memory address, reading and writing data through it, and thus avoid hard-wiring your code to a particular memory-address mapping; you can use git reset HEAD~1 without caring whether the current HEAD points at this thing or that; you can use a symbolic link to make current.log point to the system’s current log file, so that programs need not care where the current log file actually lives.
Properties
Having distinguished identity, address, and reference, let’s talk about the properties data ought to have.
Immutability
The most important property of data is this: data is, in essence, immutable. This claim runs against intuition, but add the dimension of time and space and it becomes easier. Suppose we have data D0; at time t1, event E1 occurs, causing the data to migrate to D1. That is the basic pattern of data change. Our current practice is in-place update—write D1’s content directly into the memory address or file location pointed to by D0. D0 becomes D1, so we consider it mutable. Yet at time t0, the data was still D0, and that fact cannot be changed. If we recognize this and avoid in-place update, we can greatly simplify how we handle problems.
For example, in a multithreaded context, threads alice, bob, and tyr all hold a reference to the data D0 as of t0. Alice uses her reference to migrate D0 into D1, which does not affect bob’s and tyr’s use of D0; in their respective worlds they still see D0. Thus bob and tyr need not worry that alice’s writes will crash their code, and there is no need for critical-section protection or locking—which means that although alice, bob, and tyr act on the same data, they need not know of one another’s existence. In this sense, immutability greatly reduces the context dependencies of code.
Ported to git, the multithreading example becomes: alice, bob, and tyr are branches forked from the same master. They can complete their work independently, without interfering with one another. Only when alice wants to merge her work into master does she need to see what has happened to master between the moment she forked and the present, and whether she can adapt: rebase, merge, or resolve conflicts.
Treating data as immutable—this way of looking at data has precious value.
Data immutability in memory solves concurrency problems efficiently. Most functional programming languages use this property, making concise, concurrency-safe code a matter of course. Immutability does not mean data cannot be modified; it means the state after modification does not affect the state before. The most obvious way to achieve this is to copy memory on every modification, but that is inefficient. The invention and use of persistent data structures make immutability practical in both performance and efficiency.
Data immutability in persistent storage (a hard disk, say) allows us to track version changes. Git uses this to build a most unusual file system, unrivaled in the VCS (Version Control System) world.
Immutability means data can be addressed by its identity, so data becomes location-independent and can live anywhere: on a remote server you don’t own, or in some corner of your local machine. It can be cached, verified, efficiently stored (lossless compression), and used to derive new data whose derivation can be tracked and verified.
Let me explain derivation. Take a 3200x1800 photo; we derive an 800x450 thumbnail from it. The photo is addressed by sha2, and the derived thumbnail carries the original’s sha2 along with the algorithm used for derivation. Suppose the original’s sha2 address is abcd and the thumbnail’s is efgh. Then from the derived thumbnail we can find the original’s address abcd and thereby fetch the original’s content. We then apply the same algorithm to compute the thumbnail and its address; if it is efgh, we have proved that this thumbnail derives from that original.
A few more words on git.
Git describes itself as a content-addressable file system. VCS is only one manifestation of git’s capabilities (and code management is only one application of VCS—look how we squander the gift). Content-addressable means, as we said above, that data can be addressed by its own identity. The precondition for addressing data by identity is necessarily that the data is immutable; the two reinforce each other. Only if the data is immutable is its identity immutable, and only then can the identity serve as a means of addressing. Git uses this approach to organize files into a tree, and then generates a commit pointing at that tree. Later, changes in content produce new trees, eventually forming a vast DAG (directed acyclic graph):
Yet, as we know, addresses alone cannot make data convenient to use—we need references. Hence head / tag / branch, which let us give names to dry, unreadable sha1 addresses: the default master branch, the tag for some release, all of them references to commit addresses:
IPFS (InterPlanetary File System) goes further, combining the DAG git uses to describe files and directory trees with a p2p network to build a decentralized file system. Setting aside the p2p part, what are the benefits of describing an entire file system in a content-addressable way? First, the file you address can prove itself: the QmarHSr9 you wanted (the content-address of Aoi_Sora.avi) is the avi you wanted, not one frame more, not one frame less. Second, you can wander through the different versions of a file. Since every change produces a new identity and thus a new tree, changes at any moment in time can be found with ease.
Compared with today’s file systems, you might worry about the extra resource cost. True, there is a good deal more of it, but it is worth it—just as persistent data structures in functional languages waste some memory, while the benefits far outweigh the waste. Files now have versions and can be restored to any state; they can self-verify—the address really does represent the content; and because this kind of addressing is independent of physical location, we can scatter different parts of a file across different machines—since each part can prove itself, we need not fear malicious machines tampering with content. File access becomes independent of whether the file sits on the Internet or the LAN, and the same content exists, logically, only once across the whole network (physically there will still be redundancy) because the address is the same, which can drastically reduce storage (think how many copies of “Gangnam Style” exist worldwide) while improving access efficiency—imagine the 5G era, when network speed exceeds disk access speed, and different parts of a file living in different places can be fetched faster.
The 5G era will greatly change the way we obtain data: 1) network speed exceeds disk access speed, so reading data locally and reading it over the network are nearly indistinguishable; 2) local storage capacity will be filled by network data in a very short time (assuming 5G reaches 10Gbps, your 1TB disk holds only about 20 minutes’ worth of traffic). In such an environment, distributed storage of data is the only option. So the technology behind IPFS has very broad prospects once 5G arrives.
Connection
Grain by grain a mound is made; piece by piece a robe is sewn. When data connects with data, quantity turns into quality. A single byte of data holds only 256 states, while 1GB of data can hold Honor of Kings. One file depicts a scene of life on the banks of the Volga; a set of files can constitute the magnificent War and Peace. The World Wide Web’s great contribution to the human world is that data has a unique address through URIs, and those addresses are then connected through hypertext links. Files that once lay scattered across FTP servers are reorganized into a mesh structure—information no longer sits alone at home but, in some order, forms living organisms.
The connection of data vastly expands the boundaries and meaning of data. Yet the web’s biggest problem also comes from the way it organizes things: the URI. The URI is a textbook PLOP in Rich’s sense—it conflates address and identity. The site behind a URI may vanish; the content a URI maps to may be corrupted. So consuming a URI is an uncertain affair: it may 404, it may 500, it may return something completely different two hours later than it did two hours earlier. This uncertainty forces us to spend a great deal of extra effort handling exceptions whenever we follow a link.
We said earlier that git manages content through an immutable tree. If content changes, a new tree is produced. If a website is a small grove made of git repos, then the web is an Amazon woven from tens of thousands of such groves. When site A links to site B’s data, the link does not break because site B modifies that data, because in the git world a reference to a commit hash is always valid (assuming git push -f is forbidden).
In the near future, our web will connect in the manner of git. Once that connection forms, the web will no longer be merely a connection in “space” but also a connection in “time.” By then there will be nothing left for the Internet Archive to do, because everything—past, present, and future—will be recorded and connected in an immutable way.
