Encoding and Evolution

Designing Data-Intensive Applications · Chapter 4 · Recall lab

Chapter 3 was about how one process stores data. Chapter 4 is about what happens when two versions of your code exist at the same time — because in a large application, code changes cannot happen instantaneously. That single fact generates the whole chapter: two directions of compatibility, a handful of encoding formats judged by how well they hold those directions, and three modes of dataflow in which the question keeps recurring.

The data models of chapter 2 cope with that differently. Relational databases generally assume all data conforms to one schema: it can be changed through migrations, ALTER statements, but there is exactly one schema in force at any point in time. Schema-on-read databases don’t enforce one, so the database can contain a mixture of older and newer data formats written at different times.

When the format changes, application code usually has to change too. But code changes can’t happen instantaneously either.

Both definitions name an old thing and a new thing, which is exactly why they are so easy to get the wrong way round. Choosing the two ends is more reliable than parsing the sentence.

Encoding is the translation from the in-memory representation to a byte sequence — also known as serialization or marshalling. Decoding is the reverse: parsing, deserialization, unmarshalling.

Language-specific formats, convenient and a bad idea

Many languages ship built-in support for encoding in-memory objects: Java has java.io.Serializable, Ruby has Marshal, Python has pickle. Third-party libraries exist too, such as Kryo for Java. They’re very convenient — in-memory objects saved and restored with minimal extra code — and they have a number of deep problems.

All three are textual and thus somewhat human-readable, though the syntax is a popular topic of debate. Beyond the superficial syntactic issues, they have subtle problems.

Despite these flaws, JSON, XML and CSV are good enough for many purposes, and will likely remain popular, especially as data interchange formats — sending data from one organization to another. In those situations, as long as people agree on what the format is, it often doesn’t matter how pretty or efficient it is: the difficulty of getting different organizations to agree on anything outweighs most other concerns.

Binary encodings of JSON, and why they barely help

For data used only internally there’s less pressure to use a lowest-common-denominator format, so you could pick something more compact or faster to parse. For a small dataset the gains are negligible, but once you get into the terabytes, the choice of data format can have a big impact. That observation led to a profusion of binary encodings for JSON — MessagePack, BSON, BJSON, UBJSON, BISON, Smile — and for XML, such as WBXML and Fast Infoset. None is as widely adopted as the textual versions.

Some extend the set of datatypes, for instance distinguishing integers from floats or adding binary strings, but they otherwise keep the JSON data model unchanged. Crucially, since they don’t prescribe a schema, they need to include all the object field names within the encoded data.

{
  "userName": "Martin",
  "favoriteNumber": 1337,
  "interests": ["daydreaming", "hacking"]
}

Three colours, and they are the whole argument of this half of the chapter. Amber is what the encoding spends saying which field this is — the name spelled out, or the tag that stands in for it. Accent is the values, the payload you actually wanted. Grey is framing: type markers, lengths, delimiters, union branches, stop bytes.

Read the scoreboard by those bands rather than by the totals, and the chapter’s central claim stops being an assertion. Every encoding here carries the same record, and four of the six spend exactly 26 bytes on its values.

struct Person {
  1: required string       userName,
  2: optional i64          favoriteNumber,
  3: optional list<string> interests
}

message Person {
    required string user_name      = 1;
    optional int64 favorite_number = 2;
    repeated string interests      = 3;
}

record Person {
    string               userName;
    union { null, long } favoriteNumber = null;
    array<string>        interests;
}

// note: no tag numbers anywhere

Confusingly, Thrift has two different binary encoding formats — BinaryProtocol and CompactProtocol. Actually three: DenseProtocol exists but is only supported by the C++ implementation, so it doesn’t count as cross-language. Plus two different JSON-based encoding formats. What fun. Protocol Buffers has only one binary encoding format, and it does the bit packing slightly differently from Thrift’s CompactProtocol but is otherwise very similar.

Both savings between BinaryProtocol’s 59 bytes and CompactProtocol’s 34 are visible in the strips above: the field header becomes one byte carrying tag and type together, and every integer becomes variable-length. The second is worth a dial of its own, because the chapter states its boundaries as a table and a table makes them look arbitrary.

Field tags and schema evolution

An encoded record is just the concatenation of its encoded fields. Each field is identified by its tag number and annotated with a datatype, and if a field value is not set it is simply omitted from the encoded record. From which it follows that field tags are critical to the meaning of the encoded data — and that a reader meeting a tag it does not recognise has everything it needs to carry on anyway.

record Person {
    string               userName;
    union { null, long } favoriteNumber = null;
    array<string>        interests;
}

{
  "type": "record",
  "name": "Person",
  "fields": [
    {"name": "userName",
     "type": "string"},
    {"name": "favoriteNumber",
     "type": ["null", "long"],
     "default": null},
    {"name": "interests",
     "type": {"type": "array",
              "items": "string"}}
  ]
}

The writer’s schema and the reader’s schema

When an application encodes data it uses whatever version of the schema it knows about, perhaps compiled into the application. That is the writer’s schema. When an application decodes data it expects some schema, which is the reader’s schema — the one the application code relies on, possibly the one its code was generated from at build time.

The key idea: the writer’s schema and the reader’s schema don’t have to be the same. They only need to be compatible. When data is decoded, the Avro library resolves the differences by looking at the two schemas side by side and translating the data from the writer’s schema into the reader’s schema. The Avro specification defines exactly how this resolution works.

Schema evolution rules

But what is the writer’s schema?

How does the reader know which schema a particular piece of data was encoded with? You can’t include the entire schema with every record — the schema would likely be much bigger than the encoded data, making all the space savings from the binary encoding futile. Look at the Avro strip above: the record is 32 bytes and the JSON form of its schema is several hundred. The answer depends on the context.

Dynamically generated schemas

Why does it matter that Avro’s schema has no tag numbers? Because Avro is friendlier to dynamically generated schemas. Say you want to dump a relational database’s contents to a file in a binary format, avoiding the problems with textual formats. With Avro you can fairly easily generate a schema from the relational schema — a record schema per table, each column becoming a field, the column name mapping to the field name — and dump it all into an Avro object container file.

Code generation and dynamically typed languages

Thrift and Protocol Buffers rely on code generation. That’s useful in statically typed languages such as Java, C++ or C#, because it allows efficient in-memory structures for decoded data, plus type checking and autocompletion in IDEs. In dynamically typed languages such as JavaScript, Ruby or Python there’s not much point, since there is no compile-time type checker to satisfy — and code generation is often frowned upon in those languages, which otherwise avoid an explicit compilation step. Worse, with a dynamically generated schema, code generation is an unnecessary obstacle to getting to the data.

In a database, the writer encodes and the reader decodes. There may be just a single process, in which case the reader is simply a later version of the same process — storing something in the database is like sending a message to your future self. Backward compatibility is clearly necessary there, or your future self won’t be able to decode what you previously wrote.

But it’s common for several processes to access a database at the same time: different applications or services, or several instances of the same service running in parallel for scalability or fault tolerance. Either way, in a changing application it’s likely that some processes are running newer code and some older — for instance because a new version is mid-rolling-upgrade. So a value may be written by a newer version and subsequently read by an older version that is still running: forward compatibility is also often required for databases.

That much the byte walk above already showed. Here is the part it didn’t.

Different values written at different times

A database generally allows any value to be updated at any time, so within a single database you may have values written five milliseconds ago and values written five years ago. When you deploy a new version of a server-side application you may replace the old version entirely within a few minutes. The same is not true of database contents: the five-year-old data will still be there, in the original encoding, unless you have explicitly rewritten it.

Which yields a nice way to state the payoff: schema evolution allows the entire database to appear as if it was encoded with a single schema, even though the underlying storage may contain records encoded with various historical versions of the schema.

The web works this way: browsers make GET requests to download HTML, CSS, JavaScript and images, and POST requests to submit data. That API is a standardized set of protocols and data formats — HTTP, URLs, SSL/TLS, HTML — and because browsers, servers and website authors mostly agree on these standards, you can use any browser to access any website. At least in theory.

Browsers aren’t the only clients. A native app on a mobile device or desktop can make requests, and a client-side JavaScript application in a browser can use XMLHttpRequest to become an HTTP client, a technique known as Ajax. Then the server’s response is typically not HTML for a human but data in an encoding convenient for further processing by client-side code, such as JSON. HTTP may be the transport, but the API on top is application-specific, and client and server must agree on its details.

A server can itself be a client to another service — a typical web app server acts as client to a database. That’s how a large application gets decomposed into smaller services by area of functionality, an approach traditionally called service-oriented architecture (SOA), more recently refined and rebranded as microservices architecture.

And the design goal that makes this chapter relevant: SOA and microservices aim to make the application easier to change and maintain by making services independently deployable and evolvable. Each service should be owned by one team, and that team should be able to release new versions frequently without having to coordinate with other teams. In other words, we should expect old and new versions of servers and clients to be running at the same time, so the encoding used must be compatible across versions of the service API.

Web services, three contexts and two philosophies

When HTTP is the underlying protocol for talking to a service, it’s called a web service — a slight misnomer, since web services aren’t only used on the web.

The problems with remote procedure calls

Web services are merely the latest incarnation of a long line of technologies for making API requests over a network, many of which received a lot of hype but have serious problems. Enterprise JavaBeans (EJB) and Java’s Remote Method Invocation (RMI) are limited to Java. The Distributed Component Object Model (DCOM) is limited to Microsoft platforms. The Common Object Request Broker Architecture (CORBA) is excessively complex, and does not provide backward or forward compatibility.

All are based on the idea of a remote procedure call (RPC), around since the 1970s. The RPC model tries to make a request to a remote network service look the same as calling a function or method in your programming language, within the same process — an abstraction called location transparency. It seems convenient at first, but the approach is fundamentally flawed, because a network request is very different from a local function call.

The conclusion: there’s no point trying to make a remote service look too much like a local object in your programming language, because it’s a fundamentally different thing. Part of the appeal of REST is that it doesn’t try to hide the fact that it’s a network protocol — although that doesn’t seem to stop people building RPC libraries on top of REST.

Current directions for RPC

Despite the problems, RPC isn’t going away. Frameworks have been built on top of all the encodings in this chapter: Thrift and Avro come with RPC support included, gRPC is an RPC implementation using Protocol Buffers, Finagle also uses Thrift, and Rest.li uses JSON over HTTP.

This new generation is more explicit about the fact that a remote request is different from a local function call. Finagle and Rest.li use futures, or promises, to encapsulate asynchronous actions that may fail — futures also simplify making requests to multiple services in parallel and combining their results. gRPC supports streams, where a call consists not of one request and one response but a series of both over time. Some frameworks also provide service discovery, letting a client find out at which IP address and port a particular service can be found.

Hence the split in practice: REST seems to be the predominant style for public APIs, while the main focus of RPC frameworks is on requests between services owned by the same organization, typically within the same datacenter.

Data encoding and evolution for RPC

The compatibility properties of an RPC scheme are inherited from whatever encoding it uses: Thrift, gRPC over Protocol Buffers, and Avro RPC all evolve according to the rules of their respective formats. In SOAP, requests and responses are specified with XML schemas, which can be evolved, but there are some subtle pitfalls. RESTful APIs most commonly use JSON without a formally specified schema for responses, and JSON or URI-encoded or form-encoded parameters for requests; adding optional request parameters and adding new fields to response objects are usually considered changes that maintain compatibility.

The difference from RPC is that message-passing communication is usually one-way: a sender normally doesn’t expect a reply to its messages. A process can send a response, but that would usually be done on a separate channel. The pattern is asynchronous: the sender doesn’t wait for the message to be delivered, but simply sends it and then forgets about it.

Message brokers

The landscape used to be dominated by commercial enterprise software from companies such as TIBCO, IBM WebSphere and webMethods. More recently open source implementations have become popular: RabbitMQ, ActiveMQ, HornetQ, NATS and Apache Kafka.

Distributed actor frameworks

The actor model is a programming model for concurrency in a single process. Rather than dealing directly with threads, and the associated problems of race conditions, locking and deadlock, logic is encapsulated in actors. Each actor typically represents one client or entity, may have some local state that is not shared with any other actor, and communicates with other actors by sending and receiving asynchronous messages. Message delivery is not guaranteed: in certain error scenarios, messages will be lost. Since each actor processes only one message at a time it needn’t worry about threads, and each can be scheduled independently by the framework.

In distributed actor frameworks the model is used to scale an application across multiple nodes. The same message-passing mechanism is used whether sender and recipient are on the same node or different nodes; if different, the message is transparently encoded into a byte sequence, sent over the network, and decoded on the other side.

Chapter 4 in one breath. Encoding details affect not only efficiency but, more importantly, the architecture of applications and your options for deploying them. Many services need rolling upgrades, where a new version is gradually deployed to a few nodes at a time rather than everywhere at once — allowing releases without downtime, which encourages frequent small releases over rare big ones, and making deployments less risky by letting faulty releases be detected and rolled back before they affect many users. Hugely beneficial for evolvability. During a rolling upgrade we must assume different nodes run different versions of the code, so all data flowing around the system must provide backward compatibility, where new code can read old data, and forward compatibility, where old code can read new data.

The formats: language-specific encodings are restricted to one language and often fail to provide either direction. Textual formats — JSON, XML, CSV — are widespread, their compatibility depends on how you use them, their optional schema languages are sometimes helpful and sometimes a hindrance, and they’re vague about datatypes, so be careful with numbers and binary strings. Binary schema-driven formats — Thrift, Protocol Buffers, Avro — allow compact, efficient encoding with clearly defined compatibility semantics, and their schemas are useful for documentation and code generation, at the cost that data needs to be decoded before it is human-readable. The 81 bytes at the top of the inspector and the 32 at the bottom are the same record; the 49 bytes of difference are almost entirely names and punctuation.

The modes: databases, where the writing process encodes and the reading process decodes; RPC and REST APIs, where the client encodes a request, the server decodes it and encodes a response, and the client finally decodes the response; and asynchronous message passing via brokers or actors, where nodes communicate by messages encoded by the sender and decoded by the recipient. The conclusion: with a bit of care, backward and forward compatibility and rolling upgrades are quite achievable. May your application’s evolution be rapid and your deployments be frequent.