Tufts CS 117 (Fall 2023):
Internet-scale Distributed Systems

Cross-cutting Issues*:
Principles, Guidelines and Bits of Wisdom

The fundamental goal of CS 117 is to uncover and explore a variety of principles, guidelines, and other useful insights relating to computer systems in general, and to large-scale distributed systems in particular. As we encounter each one, a brief entry will be recorded here. The entries below will be grouped into major themes, but in many cases the most important principles are indeed cross-cutting, in that they impact many facets of system architecture simultaneously.

Some of the items listed below are well understood fundamentals of good system design. Others are controversial and remain the subject of debate in the system design community.

* The term cross-cutting issues is lifted from one of the best textbooks ever written on computer hardware architecture: Computer Architecture: A Quantitative Approach, by John Hennessy and David Patterson. That book has sections throughout discussing cross-cutting issues relating to hardware design. For anyone who wants to do some self-study on hardware architecture, the book is highly recommended!

We will fill in this page as the term progresses.


KISS — Keep It Simple Stupid!

When in doubt, choose the simplest approach to solving a problem. Keep interfaces simple and straightforward. As the designers of UNIX advised: have each component of the system do one thing well.

Adding features or options to a system tends to create complexity that is out of proportion to the individual function that's added. Such complexity makes systems slower to develop and harder to maintain, and it often results in worse runtime performance as well. Even small additions to a system can have far-reaching ramifications.

Example: Unicode allows the Ö (O with Umlaut) character to be represented as either the single value U+00D6 or the two combining characters U+004F (O) and U+0308 ( ̈ ). Allowing such alternative representations in documents can facilitate integration with certain systems (on some old typewriters, the two were typed separately), but it greatly complicates the comparison of otherwise similar strings from two documents. This has been a major headache in many Unicode-based systems, including the Web. Extra code is needed in the comparison routines, and the pathlengths when doing comparisons may be longer. Such overhead is typically incurred for all comparisons, as it's usually hard to tell in advance which strings actually contain combining characters. Furthermore, the added comparison code can fill up processor caches, causing other parts of the system to run slower too. Similar complications arise if combining characters are allowed in filenames or variable names.

History: The KISS principle was first articulated (according to Wikipedia) by the legendary aircraft designer Kelly Johnson. According to the same source, the word "stupid" was not referring to those making the design decisions. Rather, the goal was to build a system that you didn't have to be very smart to understand and maintain. So, the principle is "Keep it simple (and) stupid", not "Keep it simple, stupid".

Tradeoffs: Sometimes a complex solution is needed to achieve the required result. In such situations, trying to make things overly simple can actually result in unnecessary complication or a poor design (as an example, the optimizers in programming language compilers often perform quite tricky transformations that result in code that is difficult to understand and debug, but that runs very fast.) There is a related principle attributed to Albert Einstein that "everything should be as simple as it can be, but not simpler".



Almost every decision in the design of a system involves compromises. Even when applying the most fundamental of good practices, there are usually tradeoffs. A well layered system maybe easier to understand, evolve and maintain, but it might be slower than one in which layers are integrated. Clean abstractions are essential to good system design, but such abstraction often prevents control of specifics that may be important. Be alert for tradeoffs and compromises when applying the principles and guidelines described here.

Example: A filesystem provides many useful facilities for storing, organizing and retrieving information using hard disk, but access through a filesystem prevents the use of certain low-level optimizations that may be important in unusual cases (that's why many high-performance databases directly control the hard disk, rather than working through a filesystem).


The term idempotent describes an operation that produces the same results regardless of how many times it is executed. Setting someone's bank account balance to $100 is an idempotent operation; adding $10 to their account is not. The second deposit will add to the first.

In many cases, idempotent operations can be supported more efficiently, and by simpler protocols, than otherwise similar operations that are not idempotent. For example, if the (idempotent) balance setting operation above fails, it can be retried until the desired result is retrieved. If the (non-idempotent) bank deposit operation is sent through a network and clear confirmation is not received, then any retry must be labeled as a duplicate so the receiving system will know to perform the update exactly once. In order to do this, the receiving system will normally have to keep a record of operations that have already been performed, and all requests must be checked against that record.

Not all operations can be designed to be idempotent, but when practical, idempotent operations are usually simpler to implement and incur less overhead than others. Not always, but sometimes, a choice is available: if we know that the bank account has $90 before the deposit, then either an "add $10" or a "set balance to $100" operation will yield the same final result. The latter is idempotent, but the former is not.


Metcalfe's Law and Network Effects

Metcalfe's Law states that for many networks, there is value in each connection that can be made. The number of such connections grows as the square of the number of things that can be connected, so the value of the network grows quickly as nodes or resources are added. Because growth is much faster than linear, a single large network tends to be much more valuable than multiple smaller networks, even though the smaller networks are often easier to build and maintain. The term network effects is often used to refer to the super-linear gain in value from integrating a node or resource into an existing network.

Example: the telephone system became more valuable when international direct dialing became possible. Phones in Europe could be used to directly call the United States, something that had not been possible when the networks were separate.

Example: Metcalfe's law is often used to explain why there "can be only one World Wide Web". A new page added to the Web potentially adds value to the many other pages that can now link it. Similarly, the new page itself may be more valuable as part of a Web in which it too can link to many other things. For example, an airline page can link to weather reports for the cities to which it flies, and the weather site can offer links to flights. Neither could be done if the weather reports and flights were in separate networks.

Implications: Metcalfe's law gives useful perspective on a surprising range of issues relating to the Web, including:

  • A single Web should connect users world wide
  • A single Web should support the broadest possible range of devices and operating systems
  • It should be possible to publish existing content using Web technologies
  • All scaling limits should be avoided if possible
  • Decentralized control and extensibility tends to be necessary if such a broad range of users and content is to be supported.
  • If content is "locked up" in proprietary systems, then that content neither contributes to nor benefits from the Web
  • Creating walled gardens, I.e. parts of the Web that can be accessed only by some users tends to undermine the benefits of network effects (a movie review that can be accessed only by logged in Facebook users contributes less to network effects than one that can be accessed by everyone).
  • Etc.

Tradeoffs: building and maintaining large networks may be more difficult than building multiple smaller ones.

History and references: this law is attributed to Ethernet inventor Bob Metcalfe, who supposedly made the point in a talk in 1980. His focus at the time was more on the value of a network of compatibly connected devices than on users (of a phone system) or Web pages, but the essence of the argument applies broadly. George Guilder has also apparently contributed to the formulation of the law, but everone calls it Metcalfe's law. Boston-area entrepreneur Sim Simeonov offers some clarification of the history in a 2006 blog posting.

Simplicity supports scalability

Having noted Metcalfe's law, we must observe that building very large systems is inherently difficult. Many of the challenges are obvious: it's hard to design algorithms that work at global scale, hard to manage a large system running under control of many separate organizations, hard to keep the software running as updates are incrementally installed in different locations, etc., etc.

One might therefore be tempted to assume that the largest systems are the most complex in their design and interfaces, but often the opposite is true. If the interface required for a system to join a network is simple, then the barriers to connecting are much lower. Thus, among the reasons that the Web's key architectural elements (URIs, HTTP, and HTML) are quite simple to learn and implement is to reduce the barrier to connecting a wide range of systems to the Web. We all know that many large organizations run Web servers, but simple Web servers are also now found in printers, home appliances, and even traffic lights! Building a simple but completely standards-compliant Web server is quite easy to do.

Tradeoffs: as noted above under KISS, some things just can't be properly implemented using simple techniques. One could argue, for example, that public key cryptography is conceptually complex and also difficult to implement properly. Nonetheless, this form of crypto is the best way we've found to implement (relatively) secure communication and identification checking on a global scale.

Related to: KISS principle and Metcalfe's Law.


The End-to-End Principle

One of the most famous and influential papers relating to the design of distributed systems is End to End Arguments in System Design by Jerry Salzer, David Reed, and David Clark. The Association for Computing Machinery's (ACMs) SIGOPS group voted this paper to its hall of fame, stating:

"This paper gave system designers, and especially Internet designers, an elegant framework for making sound decisions. A paper that launched a revolution and, ultimately, a religion."

Maybe not a religion, but this paper has helped a lot of designers to think clearly about tradeoffs in organizing distributed systems, and it neatly explains some of the tradeoffs embodied in the architecture of the Internet. This is a surprisingly easy paper to read and understand.

Stated informally, the principle says:

If you don't check the entire function of a multistep process from end to end, making sure that the overall operation completed successfully, then there are almost surely steps that are unchecked. Errors in those steps are likely to go undetected. Therefore, end to end checking is typically required to ensure that a system operates successfully!

Additional checking and recovery for particular steps within the system (e.g. on some particular network link) is therefore at best an optimization, because the end-to-end checks are both necessary and sufficient to ensure correctness. However, such incremental error recovery is often required to achieve practical performance; end-to-end recovery tends to result in repeating large operations in bulk (e.g. retransmitting an entire file), while incremental recovery of particular errors (e.g. a dropped or corrupted packet) can often be done very efficiently.

The principle also applies to systems in which end-to-end checking is not done, correctly predicting that those systems are at risk of having undetected errors.

From the paper:

"This paper discusses one class of function placement argument that has been used for many years with neither explicit recognition nor much conviction. However, the emergence of the data communication network as a computer system component has sharpened this line of function placement argument by making more apparent the situations in which and reasons why it applies. This paper articulates the argument explicitly, so as to examine its nature and to see how general it really is. The argument appeals to application requirements, and provides a rationale for moving function upward in a layered system, closer to the application that uses the function."

In short, the principle encourages clear thinking as to which functions or guarantees must be provided at the endpoints of a system, and which might be handled by interior layers or communication nodes.

Not only is this a wonderfully visionary paper on how to think about reliability and error recovery in a wide variety of computer data manipulation systems, it forms the key philosophical underpinning for the Internet as we know it. These were the "arguments" used to justify building a reliable system out of unreliable datagrams, and crucially, to justify putting the smarts at the periphery of the Internet vs. in the network itself (traditional AT&T phone systems). Thus, indirectly, this paper justifies building networks in which you can innovate by providing new functions (e.g. the Web, BitTorrent, VOIP, etc.) without necessarily rearchitecting or redeploying the infrastructure that implements the network fabric.

Thus, end-to-end arguments are closely related to the principle of network neutrality, I.e. that providers of network infrastructure should carry packets indiscriminately for any application, and should provide qualities of service based only on what's paid for and the underlying capabilities of the system. Tim Berners-Lee cites network neutrality as key to his ability to create and deploy the Web at a time when few others believed such a system was necessary or even possible (video)

Stateless Protocols

It's often necessary to build protocols in which each message is interpreted in the context of the ones that came before: for example, an initial message might authenticate a customer of a bank so that a subsequent "getBalance" message will implicitly return the balance for the intended user. To implement such protocols, runtimes must maintain state between the processing of successive messages. In the example, the system must maintain for each connection the identity of an authenticated user. If the connection is lost and re-established, then either some way must be found to correlate the new connection with the old, or the state must be re-created.

A different class of so-called stateless protocols avoids such complexity by transmitting in each message the information necessary for its independent processing. One way to adapt the example above would be to include user authentication information with all balance requests and other such operations. Each message can then be processed completely independently.

Stateless protocols are not always practical, but they when they are, they tend to have many benefits. They tend to be easier to implement and test. Although performance of individual requests is not necessarily improved, the flexibility in processing requests often makes it easier to gain performance in other ways, e.g. by dynamically allocating workload across multiple servers (that's harder to do if session state has to be moved.) In the example above, the individual stateless messages are larger and more complex to process, but fewer round trips are involved if only a single query is to be done.

Examples: The Internet and the Web use a mix of stateless and stateful protocols. IP itself can be implemented in a stateless manner (if IP-level fragmentation is ignored); each IP packet can be routed and delivered completely independently of others. TCP is a highly stateful protocol: as a TCP session operates, the two endpoints maintain coordinated information about how many packets are "in flight", which packets have been successfully received, etc. If a connection is "lost", then equivalent state must be established for a new session.

Stateless protocols are often used to support stateful protocols and vice versa. IP (which is mostly stateless) is used to support UDP and TCP. TCP, which is stateful, is used to support HTTP (stateless, if we ignore cookies, etc.), which in turn is often used to build stateful applications (Amazon remembers what you've put in your cart between HTTP requests.)


Global Names lead to Network Effects

A global name is one that resolves the same way everywhere. Although there are exceptions, most URIs are global in this sense, and this location independence is fundamental to the success of the Web: URI's can be passed from person to person, copied from e-mails or even billboards into HTML links, all with reasonable confidence that the right resource will be located if the link is dereferenced.

Examples: In addition to URIs, widely used examples of global names include telephone numbers (assuming country code is included), postal addresses (if the country is included), and ISBN numbers for books.

Counterexamples: The file: URI scheme is not global in this sense: the same URI resolves differently according to the machine on which it is used. Unix filenames are in a sense global within a single system, but not truly global (I.e. worldwide), because they typically resolve to different files on each Unix system. Relative URIs are not themselves global, but once resolved to an absolute URI, the result is typically a global name.

Related to: Metcalfe's Law because, as stated in the Archtecture of the World Wide Web: Global naming leads to global network effects.

Name Everything

Things with names tend to be usable in more powerful ways than things that can be found only indirectly. Thus, in this document, it's easy to create references to this section, but much harder to reference the 9th character of this paragraph. The section has an id attribute, which results in it being identified by a URI, and that URI can be used in hyperlinks, in Semantic Web RDF statements, or even for reference in textual documents such as books. As Tim Berners-Lee states in his Axioms of Web Architecture

An information object is "on the web" if it has a URI. Objects which have URIs are sometimes known as "First Class Objects" (FCOs). The Web works best when any information object of value and identity is a first class object. If something does not have a URI, you can't refer to it, and the power of the Web is the less for that.

Related to: Metcalfe's Law

One Name for Each Thing

When possible, give each thing one name, not more. When a system allows for a given thing to have more than one name, complications result. For example, cache management becomes more difficult: an update made using one name may require invalidation of the cache for entries under all names. Even the possibility of such aliasing tends to complicate code and to slow systems down.

Even in systems where aliases are allowed, their use should generally be minimized. If a particular thing is given only one name, then it's always straightforward to determine that multiple references are indeed to that same thing.

In practice, aliasing can be difficult to avoid. For example, some systems have a history of treating names in a case-independent manner. Partly to facilitate interoperation with such systems, certain components of a URI are compared independent of case.

Example: http://example.com/ and HTTP://example.com/ always identify the same Web resource, because scheme names are case-independent (though lowercase is preferred; having a preferred form increases the chance that the same URI will in fact be used in all cases.)

Related to: Metcalfe's Law; KISS

Avoid Collisions: Use Different Names for Different Things

Sometimes we are too lazy to implement names for everything, or in some cases it's impractical. Often the result is that some things have no names, but there are also cases where the result is naming collisions, that is when the same name refers to more than one thing. When there are collisions, we can't use the name to distinguish one thing from another.

Example: giving distinct names to each version of a page or document that changes over time. Without such names, we lose the ability to access or discuss problems in a particular version.

Example: Using the same URI for the mobile and full size version of a Web page. Having a link that gets you either according to where you are is typically very valuable, but there are occasions where you want to refer to, e.g. specifically the mobile version. For that you need a distinct URI referring just to that.

Related to: Name Everything

Uniform Names Support Uniform Interfaces

Uniform naming systems support uniform manipulation of a broad range of resources. For example: Unix and Linux use uniform, slash-deliminated names (/a/b/c/d) not just for files, but also for devices, pipes, processes and other resources. In many cases, the same operations (e.g. sort) can be applied to all of them, using common code.

URIs provide uniform naming not just for Web documents, but also for mailboxes (mailto scheme), telephone numbers (tel scheme) etc. Links to any of these can be created using the same <a href=...> construct in HTML. Though details vary for accessing such resources, most modern browsers will follow links to any of them, I.e. by retrieving the Web page, preparing mail to the mailbox, or dialing the specified phone number. Furthermore, the same semantic Web constructs allow statements to be made about all these classes of resource (for example, one could state that a phone number, a mailbox, or a document is "owned by" Mary Smith).

Related to: Metcalfe's Law

Opaque names support flexible allocation and processing

Many names are defined as opaque: all that is significant is that each name can be distinguished from every other name, and that each name has (or might have) a referent.

Other naming systems convey additional information in the name itself. For example, on some operating systems a filename someprog.exe is presumed or even required to be an executable file, because the filename extension says it is. All absolute URIs convey at least the name of a scheme, and many schemes define URIs that provide additional information, such as hierarchical paths and query parameters. In some cases, users will document URI assignment policies that convey yet more information, such as that:


is in all cases the weather for the named city.

Providing such "metadata" in URIs or other names can be very handy, but it has drawbacks. Let's say you are building a system about historical figures, and you get the idea to use three letter name suffixes derived from the subjects' initials. You therefore, perhaps without thinking, try to use the extension "jpg" for files relating to historical figure J. Paul Getty. On many operating systems, those files will mistakenly be assumed to be JPEG images. Opaque names can typically be allocated and processed in a uniform way. Furthermore, if one encodes into a name a characteristic that may change (e.g. an author's name for a document that later gets amended by someone else), then it may be necessary to rename an item, and thus to break references to its original name.

Related to: KISS

Reference: W3C TAG Finding Metadata in URIs

Layering and Separation of Concerns

Modularity, Layering and Separation of Concerns

Separation of concerns is the principle that, where practical, one should try to avoid unnecessarily tangling together the solutions to problems that are separable. By enforcing such separation, the chances increase that the solution to each problem can be clearly reasoned about, and modified when necessary.

A common way to achieve separation of concerns is to produce specifications and/or code that is modular, that is, in which each piece is devoted to a specific function and has clean interfaces to the other data, specifications or services with which it interacts.

Tradeoffs: The advantages of achieving modularity are reasonably obvious. Implementations and specifications tend to be cleaner, and testing is often easier as well. Modular systems tend to be easier to maintain and modify over time. There can however be drawbacks to modularity: in many cases optimization for best performance requires optimization across layers of the system. For example, in almost all high-performance networking systems, optimization requires sharing of buffers not just among layers of the networking protocol, but often with file systems or databases as well. This is necessary to avoid unnecessary memory-to-memory copying of data, which on modern hardware tends to be very slow. Similarly, many popular compiler optimizations involve integration and transformation of code for a variety of source level constructs, and indeed from source that may be scattered throughout the users program. For example, it is very common to combine the optimization of loop control code with array access code within the loop being optimized.

Also, abstractions leak in ways that can be surprising or even dangerous. Many of the most serious security problems in the systems we build relate to leaky abstractions that were not noticed by the designers.

Example: In his autobiography Just for Fun: The Story of an Accidental Revolutionary Linux OS creator Linus Torvalds criticizes the layered architecture of microkernel operationg systems including Minix (page 98ff) and later the Mach Operating System (pp149-151). Mach was developed by a research group at Carnegie Mellon Univserity, but was then adopted as and is still the basis for modern versions of the Macintosh OS.

With microkernels such as Mach and Minix, the core protected part of the OS is very small; many of the OS features that would in a larger kernel (like Linux) be integrated together run as separate processes outside the kernel, much as user code does. In short, microkernels have a more heavily layered architecture, which does bring a number of advantages. For example: things like filesystems and graphics subsystems that would otherwise be in trusted kernel code are moved to a process environment, with clean interfaces to the other parts of the system. These user level processes are relatively easy to start and stop and to replace. Also, a very small microkernel named L4 was the basis for one of the first operating systems to be formally proven correct.

Linus raises at least two criticisms of microkernal architecture:

  1. Performance: crossing all those interface boundaries is expensive (processor context switches), prevents data sharing and makes many other optimizations difficult. One can make the case that it also compromises locality, and thus presents a more challenging load to processor caches, etc.
  2. Complexity: although microkernel advocates claim that their layered designs are cleaner, Linus argues that the interfaces required between those components are themselves another level of complication to be carefully architected and tuned. In the Linux kernel, a component that needs access to some other data or service can typically get at it quite directly. Quoting Linus (p99):
    In the micro-kernel approah, you're supposed to split up the problem space so much that none of it is complex. I thought this was stupid. Yes, it makes every single piece simple. But the interaction makes it far more complex than it would be if many of the services were included in the kernel itself, as they are in Linux.

It's interesting to note that, all these years later, both the MacOS (based on Mach) and Linux continue to be widely used; Minix, which was basically a university project, is not. A Wikipedia summary is available of the debate between Linus Torvalds and Minix creator Andy Tanenbaum.

Leaky Abstractions

Joel Spolsky, who is the person behind Stack Overflow, is often credited with highlighting the problem that abstractions leak. In other words, most abstractions represent an ideal that is too simple to describe what's actually happening. Abstraction is still a very, very important goal: you just have to watch for its limits. In practice, troublesome details will often leak through from lower layers in the system, complicating the simple view promised by a clean abstraction.

Example: Most computers provide a program with the illusion of a flat data space in which any word or byte can be accessed equally well. One way in which this abstraction tends to leak on modern computers has to do with locality: in practice, a load instruction for a word that has recently been accessed, or even for a word near one that has recently been accessed will often yield results many times more quickly than would otherwise be typical. This, of course, is because computers use hierarchical memories in which recent data is cached. We might try to clarify the model, by saying that the memory is one which is flat, but in which references near to recent references will be satisfied more quickly. Unfortunately, this too is an oversimplification: if the first reference is to a word at the beginning of a cache line, then a reference to a word immediately before that is still likely to be slow. Conversely, if the first reference is to the second word in a cache line, then a reference to the word immediately before is likely to be quick. In short, to completely understand the performance characteristics of the memory you need to understand the exact organization of the cache, along with the complete trace of prior references not just from the program in question, but from all programs run on the machine since it was booted (since in principle, any of them could have caused a line to be loaded into or evicted from the cache, thus affecting subsequent decisions about cashing other data). The simple abstraction of a flat memory "leaks" quite badly when performance is considered.

Example: In 2018 the computing community was shaken by news that the majority of CPUs deployed over a period of perhaps 20 years have serious vulnerabilities that allow untrusted code to access data that should be protected. The details of the so called Spectre and Meltdown vulnerabilities are complex and subtle, but interactions among a number of leaky abstractions are the essence of the problem. These processors do a number of tricky things all designed to work around the delays involved in accessing main memory. Specifically: caches cause recently accessed data to be available more quickly; speculative execution can run code that follows a conditional branch even before the direction of the branch is known. Of course, if it's later determined that such a code path is not to be executed after all, the results are never exposed, except... if such speculatively executed code has caused changes to the cache, then those changes remain, and can be observed by timing access to data that goes into the same lines. Crucially, security checks are not done on speculatively executed code, so malicious code can cause the line number of the cache lines affected to depend on the values of supposedly inaccessible data. Remember that most of the mechanisms discussed above (caching, speculative execution, etc.) are not visible in the programming model exposed to the application.

Example: UNIX and Linux file I/O provides the famous open, close, read, write, ioctl(seek) operations. Unstated, typically, is that the performance of sequential versus random access will depend to a very significant degree on the underlying hardware: a traditional rotating magnetic disk, accessed through a typical, reasonably well-maintained filesystem, will almost surely provide an order of magnitude better performance for sequential access when compared to random accesses to the same file. This is due to the physical characteristics of the underlying disk, which can transfer data quite rapidly from a given track once the disk head is properly positioned, but which moves the head itself relatively slowly. Furthermore, to maximize overlap between computing and file I/O, and to minimize the risk of unnecessarily losing extra rotations, many file systems detect sequential access and read one or more blocks ahead of what a program has actually requested. This optimization cannot be used when the program makes less predictable access to a file. The story changes completely with modern "solid state drives" (SSDs): on these devices, performance is likely to be much less sensitive to access patterns. To predict the performance of Unix file operations, you need to understand the characteristics of the device being used, the buffering strategy of the chosen filesystem, as well as the access pattern not just from the program in question, but from any other system activity that might be moving the disk arm or contending for access to the drive and its buffers.

Documents, Data Formats, Data Management

Text vs. Binary Formats

One of the most important tradeoffs in designing a data or message format is the choice of text or binary representation. By text representation we mean one in which the bits of the format are interpreted as encodings of characters that are suitable for presentation to users: ASCII or Unicode are the most common choices. Any information to be conveyed is first represented as characters, and then those are encoded as bits for storage or transmission. For example, the number 321 would be represented either as:

Text:     321     (e.g. the 3 ascii characters 0x33 0x32 0x31)
Binary:   0x0141  (i.e. the two bytes with the decimal values 1 and 65)

Actually, in the case of binary, the order of the bytes may vary according to whether the machine is big-endian or little-endian. I.e. they may be stored in memory or transmitted as either [0x01,0x41] or [0x41,0x01]. Indeed, this incompatibility results in one of the important tradeoffs favoring the use of text: widely used text encodings such as ASCII and Unicode tend to be stored and transmitted the same way by all systems; binary formats have multiple incompatible representations.

In the early days of computing, when memory was scarce, binary formats were almost always preferred when practical, as they tend to be more compact. To a striking degree, the application-level protocols used on the Internet, including those for e-mail (RFC 2822), Web HTTP (RFC 2616) and Web HTML (HTML) tend to be text-based.

History: This tradeoff has existed since the early days of computing. As noted above, the rapid drop in the price of computer memory and processing power has facilitated the widespread use of text-based formats.

Tradeoffs: As noted above, binary formats tend to be more compact. When all systems involved use the same binary formats (word size, endianness, etc.), then binary can be much faster as well. In such cases, in-memory data structures can often be written and read directly to or from a disk or network.

Text formats have many important advantages, including:

  • Machine-independent format eases transmission between incompatible systems
  • Easy to process using widely available tools, including text editors, programming language print statements, regular expression processors, or even spreadsheets
  • Easy for humans to debug
  • Easy to teach and learn: text-based formats are much more easily expained in books or Web pages. The View Source effect in systems like the Web means that users can easily inspect a file or message to see what it looks like, and thus to learn more about how a system works.

Related to:

Mixed Content

One interesting characteristic of a document, data format, or programming language is its ability or lack of ability to easily handle what SGML and XML call mixed content, I.e. text strings that contain structured markup. The most familiar example for most users is HTML, which allows markup like this:

<p>This is a <em>really</em> important point!</p>

In the example above, the <em>really</em> markup turns the string into mixed content, because there is markup within the text. Mixed content is particularly important in HTML because it enables links like this one to be embedded directly within text like this sentence, using markup like this!

...because it enables <a href="https://en.wikipedia.org/wiki/Hyperlink">links 
like this one</a> to be embedded directly within text...

Mixed content tends to be important for the machine-processable representation of highly structured documents. Systems that lack mixed content are fine for simple text documents (e.g. plain text e-mail), but tend not to represent with fidelity the logical structure of a more complex document. For example, both XML and JSON are useful for storing simple typed key/value pairs, but XML (which supports mixed content) is better able to convey the structure of, an insurance policy document that has many nested sections, specific fields with the customer's name and amount of coverage, etc. JSON is, however, simpler to implement and use for the cases it does handle well.

History: as far as I know, mixed content was first popularized in the (precursors of) SGML. Specifically: Charles Goldfarb developed a series of document formats at IBM in the 1970s; these evolved into SGML, which was widely used outside of IBM, and is indeed the precursor of XML. Tim Berners-Lee chose to make HTML a variant of SGML, in part to leverage the skills, expertise, and expectations of those who already knew SGML, and to avoid "reinventing the wheel"

Tradeoffs: Mixed content is powerful and useful, but it greatly complicates the handling of text strings in a programming language. Almost all popular languages have built in support for ASCII or Unicode strings; the only ones that handle mixed content really well tend to be languages like XQuery and XSLT that were designed with systems like XML in mind.

References: mixed content in the XML Recommendation

Model / View Separation

When designing a document or data representation format, the content (sometimes referred to as the model) should, to the extent practical, be stored separately from the presentation formatting instructions (the view). A number of benefits result from this approach, including:

  • Content tends to be easier to extract, search and update, both for machines and for people
  • The same content can more easily be re-styled, for presentation on different devices or purposes
  • This approach tends to facilitate making information accessible to those with perceptual deficiences or other disabilities: e.g. to process with screen readers for the blind
  • In many cases, the resulting encodings are more compact, because presentation information is shared across multiple documents

Many systems include not just model and presentation information, but also logic for managing interactions with a user and transitions between program states. There are benefits to separating such control logic from both the model and the view. The resulting architecture is known as Model/View/Controller (MVC). For example, in a user interface framework that's used to fill out data forms, the stored data (the model) should be separate from the form layout (the view), and both should be separate from the logic that decides which form to present next after the first is filled in.

Examples: The separation of CSS stylesheets from HTML is the most obvious example on the Web. It should be noted that this separation was incompletely realized for many years. For a long time, the preferred way of styling HTML content was with attributes in the HTML; only over time did CSS emerge and become sufficiently capable to cover most styling needs. Other examples include XSLT for styling XML (though in practice, XSLT is often used to produce HTML, that in turn uses CSS!). To see great examples of Model/View separation with HTML and CSS, check out the CSS Zen Garden.

Many presentation tools such as PowerPoint provide ways of changing the "Design" of a document after it has been created. As noted above, the User Interface frameworks for many languages including Smalltalk embody an MV or MVC layering.

History: Model / view / controller separation was first seriously explored during development of the famous Smalltalk language, which was created at Xerox PARC in the 1970s.

Related to: Layering and separation of concerns; tradeoffs

Tradeoffs: Tradeoffs in supporting MV or MVC include

  • Layering can result in complexity or performance problems
  • Separating content from presentation can be inconvenient or a bad choice when:
    • Users need to repeatedly update content and formatting together. This is a common case, e.g. when formatting word processor documents, slide presentations, etc. When updating Web pages using CSS, it is often necessary to update the HTML and the CSS separately
    • There will be only one document of a given style, so formatting information is never shared across documents anyway

The Rule of Least Power

Turing-complete languages are the most powerful, and thus for many purposes the most useful. Nonetheless, the Rule of Least Power highlights the drawbacks to using such powerful languages for information publishing: it is typically much easier to extract and interpret information published using a less flexible declarative language. The detailed reasons are set out in the W3C Technical Architecture Group (TAG) Finding: The Rule of Least Power, which in turn is based on an earlier analysis by Tim Berners-Lee.

The rule suggests that, where practical, Web pages should rely on technologies like HTML and CSS to convey information, using JavaScript only where those declarative technologies are not sufficient. Note that search engines like Google and Bing could probably not have been deployed if all Web page content were encoded in JavaScript as opposed to HTML. With HTML and CSS, it is easy for Web crawlers to extract information about links and styling, as well as page content.

Errors and Error Handling

Design for error handling

The overall architecture of a system tends to affect the options available for reporting on and recovering from errors. Indeed, providing robust error handling may significantly constrain or in some cases complicate the design of a system. For all of these reasons, the requirements for dealing with errors should be set out early in the design process, and where appropriate the architecture should be chosen to support clean handling of the necessary reporting and recovery.

Example: Many programming languages provide a syntax for character string literals. A design choice that has a significant effect on error reporting is whether such literals can extend beyond one line of source, for example:

str = "Hello

One subtlety when such continuations are allowed is determining whether the newline is part of the string, whether it becomes a blank space, etc. There is, however, a more serious problem relating to error reporting. Consider the following example:

str = "Hello World; <— Note missing quote mark

if (a > B) {
  printf("It's a beautiful day");
} else {
  printf("The weather is bad");

Note the missing " character after World. Because strings may extend beyond one line, the literal being assigned to str starts with Hello as intended, but it extends to the characters printf(, and everything to that point is legal syntax. The compiler will therefore report an error not on the assignment to str, but instead on the first printf It may go on to claim that there is an else clause with no corresponding if, since the latter was included in the string literal. This is confusing in the example above, but in a real program there may be hundreds of lines of code before the next quote character; the error report may indicate a line far from the true source of trouble, and it will likely say nothing about unterminated strings.

In a language where strings cannot extend beyond one line, or as in C and C++ where an explicit line contuation marker is required, the compiler can localize such errors to the line in which the problem occurs, and can provide a more helpful message, such as "Unterminated string literal on line xxx". Furthermore, the compiler may be able to go on and provide meaningful error reports for the remainder of the program.

Example: Robust error handling must typically be anticipated as code is organized and as invariants are established. Very often exceptions provide a structured framework for doing this, especially in networked and interactive systems. Consider a server system that maintains multiple connections supporting multiple remote users. A typical recovery architecture might have the following general features:

  • Invariant: each remote user is served by a single process.
  • Invariant: the exception handling code associated with that process will, when invoked, cleanly terminate the connection to the associated remote user, without affecting communication with any other user
  • Invariant: whenever a non-recoverable error or timeout occurs while communicating with a user, an exception is thrown in the associated process

By constraining the design of the system in this way, it becomes relatively easy to write code that will terminate the connection to one user without affecting work done by others. It also becomes easy to reason about the system's response to error conditions.

Tradeoffs: The choices described above constrain the design of a system. Often they make the system simpler and more powerful, but in other cases designing for robust error handling can compromise performance, convenience for users, or clarity of the program source code.

Clean abstractions for error handling

When designing a system of significant size, one of the key principles all good designers learn is: create clean abstractions, and where practical, use clean interfaces that are easy to reason about. The same good advice applies when planning to handle errors and failures. Clean abstractions are often the key to a robust and scalable approach to handling errors.

Example: one surprisingly effective approach to dealing with errors is to just stop. Do nothing! Although it's tempting to assume that some elaborate approach to recovering errors might be more effective (as sometimes it is!), guaranteeing that some component or part of a system will just stop rather than proceeding in the face of errors yields a very powerful guarantee: the system will never do anything incorrect!

Of course, it is often undesirable for an entire system to stop, so the "fail stop" architecture is very often applied to components or subsystems. In cloud-scale computing system with thousands of connected computers, each one that fails may stop, but the others will rapidly notice and arrange for the computation to either restart or be cleanly terminated. The power of this approach comes from the fact that it applies in uniform way to a very broad class of errors, and that the consequences are easy to reason about rigorously. If the system is running, then no unrecoverable errors have been detected and the computation is believed to be correct; higher-level error recovery is reduce to one challenge, I.e. dealing with components that have stopped.

Versioning and Evolution

Plan for Evolution

Any system that is used for an extended time is likely to require changes. Implementing such modifications would be straightforward if new versions completely replaced the old, and especially if no data sharing were required across versions. Unfortunately, such interoperation across versions is often important. Versioning of deployed software tends to be one of the harder problems in computer science, and unfortunately it tends not to be carefully studied.

Almost always, robust interoperation across software versions is much easier if the necessary mechanisms are provided in the first version. A variety of approaches can be taken, but questions to be considered include:

  • What sorts of changes are anticipated?
  • Will additional information be stored and managed by later versions of the software? If so, what provisions are made in the original formats and APIs to allow for such extensibility?
  • What are the constraints on extensibility? What may change in future versions, and is there anything that's guaranteed never to change?
  • Will data or features that were suppored in early versions ever be unsupported in later versions?
  • What information from newer versions can be safely ignored if read by older versions? Can information stored by newer versions change the interpretation of older data (e.g. by adding a "units" field for numbers)?

Backwards compatibility refers to the ability of newer software release to correctly handle older data or APIs. Usually, backwards compatibility is straightforward to achieve if suitable care is employed, though in some cases duplicate data and logic may be involved (it was said that some versions of Lotus Notes used up to four simultaneous ways for storing the color of a run of text: as the system evolved, newer and richer color spaces were supported, but the old ones were retained for compatibility with earlier releases.) Such duplication is suprisingly common in commercial software.

Forwards compatibility can be equally important, but is usually a much more challenging problem. Forwards compatibility is the ability of an old version of a program to properly process, or at least tolerate, data fields or other features that were introduced by subsequent releases. Usually, some general or generic rules are used to decide which such data can be ignored completely, which can be processed in some generic way (e.g. stored or printed), and which must be signaled as an unrecoverable error (some new features may not be safe to ignore.)

Related to: Partial understanding

Tradeoffs: Mechanisms for versioning tend to complicate software, limit the ways that information is stored, and to greatly slow the design of the initial version of a system. If versioning is not anticipated, evolution may be difficult or impossible to achieve.

Postel's Law (the Robustness Principle)

Postel's Law, also known as the Robustness Principle was set down by Jon Postel in RFC 760. Postel's law is often stated as:

"Be liberal in what you accept, and conservative in what you send".

The rule is intended to be applicable to large scale systems like the Internet, in which interoperation is required even as the same protocols are re-implemented in different code bases and by different organization. The "law" suggests that systems attempt to process incoming messages even if those messages have minor deviations from the specified protocol. So, receivers should be "liberal" in what they accept. This tends to make systems less brittle, because minor errors don't prevent the system from continuing to operate.

The problem with this first half of Postel's law is that it removes some of the pressure to fix bugs. Thus, Postel's Law's second part mandates that senders be diligent about sending only correct content, I.e. they should be conservative, and should fix bugs, even if many receivers are tolerating their errors..

Tradeoffs: Postel's Law is widely believed to be fundamental to the growth of the Interent, but one can also make the case that it has led to significant trouble. In many cases, the temptation to be liberal is much stronger than the mandate to fix problems. Buggy content is tolerated by receiving software, to the point where users come to expect the buggy content to work.

Several important examples of these tradeoffs can be found in the handling of HTTP responses by Web user agents. The pertinent specifications are clear that the type of an HTTP response is to be determined from the Content-type header. Unfortunately, those responsible for configuring servers weren't always careful. In some cases out of laziness, but in other cases because the users creating content did not in fact have control over the Content-type header, it became common to find JPEGs and other non-text content served as Content-type text/plain. Consistent with Postel's Law, many browsers rendered this content not as text (which would have been gibberish), but as a photo. Similar "sniffing" was done to detect other formats such as XML.

The Web sites operated as users expected, but several significant problems resulted: one is that it is in some cases now impossible to successfully serve on the Web a plain text document that happens to begin with charactes like <?xml, because browsers assume that the document is XML, and then fail if in fact the text is not legal XML after all. Furthermore, the expectation that such incorrect content would be processed led to a decision to document in the HTML5 specification rules for processing the incorrect content in an interoperable manner. The resulting specification is significantly larger, more complex, and arguably less architecturally clean than would have been the case if early browsers had insisted on correct content.

Partial Understanding

As discussed above, it's important to architect robust mechanisms for sharing information across versions of a given piece of software. There is a tendency to assume that any given file or data item is either properly understood, or not, but that view is often too simple. Often, particularly when designing for forward compatibility, it's better to embrace a model in which it's understood that agreement on the interpretation may be partial.

Example: it may be acceptable for a Web user agent to completely understand the content of an HTTP response, but to not understand a new header indicating that the response is cacheable. An older version of an application might correctly understand that it has received a purchase order, but not understand a new field requesting priority shipping.

Example: HTML's treatment of nonconforming tags such as <bogus>: although technically in error, such a tag will be accepted, added to the DOM tree, and thus available for access by scripts. By default, the tag has no effect on rendering for the screen or printing, but data contained within the tag is displayed.

Tradeoffs: Whether it's appropriate to proceed in the face of such partial misunderstanding typically depends on the requirements of the application. Usually there is a tradeoff, and it's one that should be considered early in the design of a system: if content that must be understood can be distinguished from content that can be ignored or partially understood, there tend to be more flexible options for incrementally enhancing and redeploying software later. Conversely, processing data that isn't fully understood can lead to errors. It can be very tricky to anticipate all the situations that may result when multiple fields of a message or document are simultaneously processed based on partial underestanding: for example, if early versions of a document format included a field for price, it's essential that a field added in later versions to convey units of currency (dollars vs. pesos) not be ignored.


Plan for Security

One of the main guidelines you will hear repeatedly from security experts is: architect a system for required security from the start. Achieving good security in a distributed system usually requires attention in the core abstractions, data structures, and protocols that comprise the system. Often, it's important to establish invariants that will be true in all cases (e.g. user information will never appear on disk unencrypted). It's much easier to maintain such invariants from the start, and to reason about the security characteristics of a system, if the required characteristics are designed in, subject to design and code inspection, and tested from day 1.

Tradeoff: planning early for required security is important, but it's not easy to do well. Features introduced to enhance security tend to require time to design and verify, and they may also slow or complicate the operation of a system once deployed. Security requirements and threats (security experts speak of a "threat matrix") are sometimes misunderstood, raising the risk that a system will be delayed or made more complicated by features that do not ultimately deliver the required system security. Getting security right is important but difficult. Usually, it is an ongoing process of adapting a system as new threats emerge. Such adaptation tends to facilitated if the underlying system is cleanly organized and as simple as possible.

Related to: KISS

Related to: The Rule of Least Power

Related to: Partial Understanding

Related to: Mobile Code

Mobile code tends to cause security problems

One of the most powerful ways to build a distributed system is to use mobile code, I.e. to send messages containing executable programs. To be useful at the receiving end, such code must to some degree be trusted. There are several pitfalls that can easily arise, including:

  • Code may inadvertently be granted inappropriate permissions
  • Code may inadvertently be accepted from the wrong sources
  • Even correct code may execute for extended periods before producing results, and correct code is hard to distinguish from incorrect (the halting problem)

The Web uses mobile code in the form of JavaScript and indeed, many of the Web's most serious security problems relate to use of JavaScript. If you are designing systems using mobile code, pay careful attention to the risks involved.

Related to: The Rule of Least Power

Beware of Code that Manipulates Other Code

Ken Thompson's legendary paper Reflections on Trusting Trust showed how extraordinarily difficult it can be to detect malicious code that's been well hidden in a compiler. Indeed, the compiler can plant viruses in other programs that the compiler compiles and can cause the malicious code to appear in subsequent versions of the compiler itself, even if both the compiler source and the user's source code are completely free of malicious constructs.

Thompson's work illustrates a deeper point: any code that manipulates other code can make malicious changes. Thus, code that manipulates code must be trustworthy, and for the reasons Thompons points out, it's very hard to be sure that code is trustworthy, unless you know and trust the people who wrote it, and likewise who wrote the tools used to build it. Code that manipulates other code includes: compilers, linkers, editors, filesystems (if used to store code), networks (if used to transmit code), and even the CPU's on which code is run.

In practice, we typically do an imperfect job of ensuring that code is trustworthy. Nonetheless, it is particularly important to pay attention to the integrity of compilers and other tools that are specifically designed to manipulate, store, or run code.

Copyright 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 & 2022 — Noah Mendelsohn & Tufts University