Distributed Systems — Episode 6

The chapter opens with the entities we want to find — hosts, printers, disks, files, processes — and with three terms. An address is an access point whose defining property is that it changes: entities move. The book's example is dismissed as dated: switching internet provider used to change your mailbox too. Alexey recalls how in the early internet days a mailbox in the provider's system came with your address; his own first one, from Dolgoprudny, he never opened. A live equivalent turned up at once: your address changes when you change jobs. A true identifier has three properties: it refers to one entity, that entity is bound to exactly one identifier, and it never changes and is never reused. Human-readable names exist because handing identifiers to people is awkward. The rest of the chapter is about turning a name into an address: through a lookup table, as DNS does, or by routing the request itself to the right node.

Flat naming is covered through four approaches. The simplest is broadcast: the request goes to everyone, and the machine recognising its own address answers with its link-layer one; at scale that stops working, so the authors move to multicast, which addresses a group and doubles as a way to replicate. The same approach also covers forwarding pointers: when an entity moves, its old address keeps a link to the new one. The analogies came thick and fast: endless mail forwards, 301 and 302 redirects, the marker on a relocated repository, a garbage collector leaving references where blocks used to be. Chains break and grow, so they are collapsed to a single link, though, the participants note, not always safely. The second approach, home-based, is spelled out in the Mobile IP standard: the home node knows the current location, forwards the request and hands the client the new address in parallel, so the client notices little beyond extra latency, while the home node's availability becomes critical. Alexander, who reads the RFCs alongside the book, showed an austere ASCII diagram of tunnelling from one.

The third approach, distributed hash tables, brings its own properties: autonomy and decentralisation, fault tolerance, scalability. The task is to find the node holding a key, so that a node joining or dropping out does not trigger a full rebalance — hence consistent hashing. The authors present Chord as the simplest system, while one of the most popular DHTs, Alexander says, is torrents; Cassandra shards on the same principles, though its data model is more complex. Locality-aware hashing gets a mention: similar keys land next to each other, so a range scan does not spread across nodes. On the ring a key is served by the node with the nearest larger identifier, and one identifier space covers nodes and keys; passing the request naively around the circle costs a linear search across half the ring, while a finger table with steps in powers of two brings it to a logarithm. Alexander admits he wanted to skip Chord on his first read, but the new edition kept it, and once he worked it through he saw a binary search over a looped key space.

The fourth approach is hierarchical: upper nodes know only that an entity sits somewhere below them, so the search climbs to a node that knows the right branch and then descends. A replicated entity keeps two links, and the arrows fan out through the tree both ways. At this point Alexander's Wi-Fi dropped, Alexey picked the narration up, and on returning Alexander joked that a cable was all he needed to be reliable. Flat naming closes on trust: an identifier tells you nothing about whether the entity returned is the right one. The simple answer is to compute the identifier from the data itself, but that holds only for immutable content; for mutable data the authors propose something more elaborate. What exactly they propose for secure name resolution, Alexander admits he did not follow: the authors point ahead to the chapter on Byzantine failures and hint at a central node that vouches for an answer.

Structured naming starts from a naming graph laid out like a file system, and from the idea that parsing a name rests on implicit knowledge of its structure: recognise a phone number or a path and you know how to take it apart. In Unix the starting node is the superblock, which leads through index nodes to the root directory, and from there hard links and symbolic links carrying a full path inside; one participant recalled rolling out releases ten-odd years ago by flipping such a link — the old version stays beside it, so a rollback is instant. Mounting glues two trees: with NFS you name the protocol, the server and the mounted part, almost as in a URL. DNS is split into three levels: a rarely changing global one with the root nodes, an administrative one inside an organisation's remit, and a bottom one that, the participants agree, is not really DNS. The classification struck Alexander as loosely nailed down: better to look at how often records change and how fast lookups must be answered.

Resolution is either iterative, with the client walking down from the root, or recursive, with the server doing the work; root nodes only work iteratively, while an organisation's own resolver pays for itself through caching. Among the records: A, CNAME as a symbolic link and PTR for reverse lookups. Companies taking a public resolver instead of running their own hand their query history to an outside party and stop getting the nearest server, while DNS over HTTPS hides those queries from prying eyes. Attribute-based naming means RDF triples, which Alexander has never seen in production, and LDAP, crossing a hierarchy with attributes; the chapter's best joke, in his reading, is the authors' remark that the quality of implementations keeps such services from spreading. Searching is proposed through distributed indexes whose answers are intersected, or through a Hilbert curve that puts close values next to each other — which brought back a talk on attribute matching in a dating service. The last topic, named data networking, replaces packet addressing with fetching data by name: the router answers from cache, waits on a table of pending requests, or forwards onward. The participants likened it to IPFS and web 3.0, but have not met it in the wild.