§48.1–48.2Communication Basics and Unreliable Communication Layers

Distributed systems distributed system A system built from many cooperating machines that, despite regular failures of machines, disks, networks, and software, is engineered to appear to clients as if it rarely fails. Collecting unreliable components into a reliably-appearing whole is the central value of distributed systems, and underlies virtually every modern web service (Google, Facebook, and so on). defined in ch. 48 — open in glossary run across many machines — thousands, for a service like Google or Facebook — that cooperate to look, to you, like one always-available whole. The new problem they all share is failure: machines, disks, networks, and software all fail from time to time, and we don’t know how to build perfect parts.

Failure is also the opportunity: a machine failing doesn’t have to mean the system fails. Pool enough machines and you can build something that rarely seems to fail even though its parts fail constantly. We start with the one genuinely new ingredient — communication — and its central, humbling truth.

48.1 Communication Basics

Packet loss packet loss The fundamental fact of networking that packets sometimes never reach their destination. Causes include bit corruption in transit, down or severed links and non-working machines, and — most fundamentally — a switch, router, or host running out of buffer space and having no choice but to drop arriving packets. defined in ch. 48 — open in glossary has several causes, and the most fundamental one is subtle:

That last cause is the deep one. Even if every link and machine worked perfectly, a packet arriving at a router must be stored in memory to be processed. If packets arrive faster than they leave, that memory fills, and the router simply drops what it can’t hold. The same happens at a busy end host. So loss isn’t an anomaly — it’s built into networking. The question is how to cope.

48.2 Unreliable Communication Layers

The simplest answer is: don’t cope — expose a raw, best-effort layer and let applications that already know how to tolerate loss handle it themselves. (That’s a preview of the end-to-end argument, at the end of the chapter.) The canonical unreliable communication layer unreliable communication layer A messaging layer that makes no guarantee of delivery — packets may be silently lost, with the sender never informed — leaving applications that can tolerate loss to cope themselves. UDP is the canonical example, and using such a layer is an instance of the end-to-end argument. defined in ch. 48 — open in glossary is UDP/IP udp The User Datagram Protocol (UDP/IP), the ubiquitous unreliable communication layer. A process uses the sockets API to create an endpoint and exchange fixed-size datagrams; UDP includes a checksum to detect some corruption but provides no protection against, or notification of, packet loss. defined in ch. 48 — open in glossary : a process uses the sockets API to make an endpoint, and machines exchange datagrams datagram A fixed-size message (up to some maximum) sent over an unreliable layer such as UDP. Delivery is best-effort: datagrams may be lost, duplicated, or arrive out of order, with no guarantees from the layer itself. defined in ch. 48 — open in glossary — fixed-size, best-effort messages.

A tiny client and server are all you need to start (Figure 48.1):

// client.c — send one message, await a reply
int main(int argc, char *argv[]) {
  int sd = UDP_Open(20000);
  struct sockaddr_in addrSnd, addrRcv;
  int rc = UDP_FillSockAddr(&addrSnd, "cs.wisc.edu", 10000);
  char message[BUFFER_SIZE];
  sprintf(message, "hello world");
  rc = UDP_Write(sd, &addrSnd, message, BUFFER_SIZE);
  if (rc > 0)
    rc = UDP_Read(sd, &addrRcv, message, BUFFER_SIZE);
  return 0;
}

// server.c — receive, then reply
int main(int argc, char *argv[]) {
  int sd = UDP_Open(10000);
  assert(sd > -1);
  while (1) {
    struct sockaddr_in addr;
    char message[BUFFER_SIZE];
    int rc = UDP_Read(sd, &addr, message, BUFFER_SIZE);
    if (rc > 0) {
      char reply[BUFFER_SIZE];
      sprintf(reply, "goodbye world");
      rc = UDP_Write(sd, &addr, reply, BUFFER_SIZE);
    }
  }
  return 0;
}

Those UDP_* calls are a thin wrapper over the sockets API (Figure 48.2) — the essentials:

int UDP_Open(int port) {                       // make a socket, bind to a port
  int sd = socket(AF_INET, SOCK_DGRAM, 0);
  struct sockaddr_in myaddr;
  bzero(&myaddr, sizeof(myaddr));
  myaddr.sin_family      = AF_INET;
  myaddr.sin_port        = htons(port);
  myaddr.sin_addr.s_addr = INADDR_ANY;
  bind(sd, (struct sockaddr *) &myaddr, sizeof(myaddr));
  return sd;
}
int UDP_Write(int sd, struct sockaddr_in *addr, char *buffer, int n) {
  int addr_len = sizeof(struct sockaddr_in);   // sendto() — fire off a datagram
  return sendto(sd, buffer, n, 0, (struct sockaddr *) addr, addr_len);
}
int UDP_Read(int sd, struct sockaddr_in *addr, char *buffer, int n) {
  int len = sizeof(struct sockaddr_in);        // recvfrom() — receive a datagram
  return recvfrom(sd, buffer, n, 0, (struct sockaddr *) addr, (socklen_t *) &len);
}

The exchange looks like this:

UDP isn’t entirely defenseless: it carries a checksum to catch some corrupted packets.

But a checksum only catches corruption — it does nothing about loss, and when a datagram is dropped the sender is never told. Since most applications just want their data to arrive, we need more: reliable communication built on top of this unreliable network — the subject of the next section.