CAP theorem and its implications

CAP theorem
No distributed system can guarantee "consistency" (C), "availability" (A) and "partition tolerance" (P) at the same time.


Definition of Terms
The words "consistency", "availability" and "partition tolerance" are a common source of confusion as they mean different things to different people. Here is the definition by Gilbert and Lynch in their formal proof of the theorem, followed by my notes.

• Consistency: "There must exist a total order on all operations, such that each operation looks as if it were completed at a single instant." In software engineering parlance, this is equivalent to having the system behave like it is executing requests in a single thread, in some sequence. A system is therefore consistent if each request sees the state of the system as if it were the only request being processed by the system at that time.
• Availability: "For a distributed system to be continuously available, every request received by a non-failing node in the system must result in a response." In other words, the system is available if it is able to respond. The formal proof makes no distinction between arbitrarily long response times and failure to respond.
• Partition Tolerance: "In order to model partition tolerance, the network will be allowed to lose arbitrarily many messages sent from one node to another." A system is partitioned if messages from one component to another are lost. This partitioning could be temporary or permanent, but that doesn't affect the outcome of the proof. In other words, a system is partition-tolerant if it responds correctly in the event of a network or node failure. Also, per the formal proof, "no set of failures less than total network failure is allowed to cause the system to respond incorrectly". As a quick mnemonic, I prefer to think of this property as "fault tolerance".

Implications of the theorem
Large systems need horizontal scale and hence, partition-tolerance. E.g. if one machine becomes unavailable, the system shouldn't fail. This implies that large systems only have "consistency" and "availability" to play with.


Consistency over availability
Some systems just need to be consistent. Banks and financial institutions fall in this category. It is easy to see why.  If money is transferred from account A to account B, you don't want to see it disappear from both A and B (the bank may like it but A and B won't) nor do you want to see it present in both (A and B will like it, but the banks won't!). value consistency over availability (e.g. banks), while others value availability over consistency .


Availability over consistency
This is the choice made by most large systems today (e.g. eBay, Amazon). It turns out that sacrificing consistency isn't as big a deal as it might initially feel if inconsistencies get reconciled within an acceptable time frame. This is the concept of  "eventual consistency", as opposed to total "consistency". If you list an item on eBay, you may be able to search for it only when the search sub-system gets consistent with the listing subsystem; however, both remain available while the system is in an inconsistent state.


Closing remarks
Just as a physical system has inherent limits (e.g. the speed of light or absolute zero temperature), a distributed system has one such limit involving the parameters of consistency, availability and partition tolerance. This limit helps us in making informed decisions when optimizing on the parameters that the system values most.


References

1. Formal Proof by Gilbert and Lynch
2. Availability v/s Partition Tolerance (Canned Platypus)
3. BASE - an ACID alternative

Software Architecture

Large software is not monolithic - an undifferentiated mass of code. It is partitioned into tiers and layers. This partitioning helps in conceptualizing, architecting, designing, implementing, unit testing and maintaining the software with relative ease. This article talks about these partitioning methods, their dependencies and their interactions.

Note that this article does not talk about other types of architectures, like application architecture (partitioning an application into various interacting components), operations architecture (partitioning a system for ease of operational maintenance), etc.

Tiering

Tiering is partitioning software by the level of abstraction. The higher the abstraction, the closer the artifact being modeled resembles our conception and way of thinking (e.g. a car). Conversely, the lower the abstraction, the closer it resembles raw physical entities (e.g. database records or disk storage).

Partitions

• Resource tier holds external services that the software depends on, e.g. database server. Usually, the server does not have access to the state of the objects contained in this tier (e.g. internal object representation of a record in a database).
• Integration tier holds objects that are a local representation of external data, e.g. records stored on a database server. They serve to integrate with external services. At this level of abstraction, there is no business interpretation given to these objects. E.g. there are numbers retrieved from the database, but no meaning imparted to them. E.g. 1=ACTIVE, 2=DEACTIVATED, etc, does not belong here. In other words, this tier holds nothing more than a local representation of external data. This is usually the lowest level of abstraction contained within the server.
• Business (Biz) tier holds objects that have been imparted business interpretation. Additionally, it holds factories for creating those business objects, and associated business logic. Most of the server-side action happens in this level of abstraction.
• Presentation (Prez) tier holds objects and logic related to presentation of the business artifacts. User interfaces (display, validation, etc.) live here. Along with the Biz tier, this is another level of abstraction where the action happens. This is usually the highest level contained within the server.
• Client tier holds client-side objects, e.g. Javascript objects. The server doesn't have direct access to their states. Objects in this tier most closely resemble our way of thinking about them, e.g. a song being played, instead of bytes in an MP3 file.

Variations

• A "Communication" tier can be introduced between the "Integration" and "Resource" tiers, if the server and the resource communicate via a proprietary protocol. If using an open protocol (e.g. HTTP), this tier can be abstracted over and removed from being represented in the stack. 

Interaction between partitions

• To reduce coupling and maintain clean separation of tiers, data that needs to be transferred from one tier to the next can be translated into something that the next tier understands by using tier translator. These translators would reside on the tier boundary and be the only objects that do so.

Layering

Layering is partitioning software by degree of functional specificity or reusability. As the software partition becomes more functionally specific, its reusability goes down.

Partitions

• Kernel holds a basic set of functions and services, common to all functionality provided  by the application suite. There is one kernel per application suite. An application suite is an arbitrary grouping of applications, e.g. Microsoft Office suite.
• Domain holds a common set of functionality, e.g. ability to search a data store, library of WYSIWYG components, etc. This allows for multiple domains in the application stack, one possibly for each set of functionality. The idea behind this partitioning is that the application can pick and choose the domains it needs to do its job, without having to depend on all domains in the stack. This reduces the application's disk/memory footprint.
• Application holds application-specific logic, mostly process orchestration unique to the application, depending on various domains to do its job. E.g. blogging application, that depends on WYSIWYG component domain and search domain to provide the ability to create, edit and search blogs.

Variations

• The above stack can be altered to fit the unique needs of an organization. Here are some examples:
• A "micro kernel" can serve as the foundation of the kernel itself. This allows for multiple kernels, each specific to a particular application suite. E.g. a set of web applications and a set of desktop applications may share a common micro kernel.
• A "domain foundation" or "application foundation" sandwiched between the kernel and the domain can provide. This layer can provide artifacts shareable by all domains. E.g. industry-standard business interfaces or processes.

Conceptualization

• Here is one way to conceptualize the various layers (granted that this is a simple way to understand their purpose and may be hard to find in practice):
• Theoretically, the kernel can be shared by all applications, developed by any organization, in any industry. (In reality, the kernel is rarely shared outside of the organization, but stay with me for a moment.)
• The application foundation can be shared by all applications, in any organization within a specific industry. It may contain definitions for industry-standard business interfaces and business processes.
• The domain can be shared by all applications within an organization needing a common functionality. It is possible that certain applications within an organization don't need the functionality offered by a particular domain. In such cases, the application won't share that domain.
• An application offers a unique set of functionality (hopefully!).

Interaction between partitions

• The application layer can depend on one or more domains. Nothing can depend on an application, including other applications.
• A domain can depend on the kernel. They can also depend on other domains, but there shouldn't be a cyclic dependency - which is usually the result of incorrect dependency assumptions or incorrect partitioning of functionality into domains.
• Kernel cannot depend on the other partitions.

Layers and Tiers

Large software is partitioned along two axes - layers and tiers. This gives rise to interesting combinations, which we look at below. I do not cover resource and client tiers, since they do not reside on the server.

Kernel layer

• Integration tier: this tier is used to integrate with the operating system or other low-level system. This should be efficient, robust, reusable, highly available and high quality (i.e. relatively bug free) code. After all, many, if not all, applications in your application suite depend on this code.
• Biz tier: Having business logic in the kernel is hard to justify. In my opinion, there should be no code here.
• Prez tier: Having presentation logic is even harder to justify in this tier.

Domain layer

• Integration tier: This is a busy tier. Most integration-tier objects (across layers) are in this tier. This provides integration with application-generic, external services, like database servers.
• Biz tier: This is another busy tier. Logic related to a reusable functional area is found here.
• Prez tier: This holds a library of presentation artifacts, that can be shared across multiple applications. This isn't as busy as other tiers in this layer, unless you have high reusability of presentation artifacts.

Application layer

• Integration tier: Application-specific integration is found in this part of the neighborhood. It is hard to justify an integration artifact that cannot be interpreted to be a part of the domain (i.e. base functional area). It is possible, just unlikely.
• Biz tier: This holds application-specific business logic. In other words, this logic is unique to this application.
• Prez tier: This holds presentation logic unique to this application.

In closing, I think that designing and implementing an application suite as layers and tiers helps in creating clean and maintainable software.