Availability is the ability of a system to respond to requests successfully (availability = (1 - (n_requests - n_error) / n_requests) * 100)

Consistency is related to the following question: Is a client guaranteed to see the most recent value for a given key when it issues a GET? (also known as read-after-write consistency).

In a dynamo-like database, Availability is always prioritized over consistency, making it an eventually-consistent database.

The way dynamo increases write (and get) availability is by using a technique called leaderless replication in conjunction with sloppy quorums and hinted hand-offs (sloppy quorum and hinted hand-off will be explained in future posts).

In leaderless replicated systems, multiple nodes in the cluster can accept writes (as opposed to leader-based replication) and consistency guarantees can be configured (to some extent) by leveraging Quorum. To describe Quorum, let's go through an example in which the Quorum Configuration is: replicas: 3, reads: 2, writes: 2

To detect conflicts, dynamo databases use techniques like vector clocks (or version vectors). Vector clocks will be explained in great detail in future posts.

If a conflict is detected, both conflicting values are stored and a conflict resolution process needs to happen at a later stage. In the dynamo case, conflicts are handled by clients during read. When a client issues a GET for a key which has conflicting values, both values are sent as part of the response and the client has to issue a subsequent PUT to resolve to conflict with whatever value it wants to store. Again, more details on conflict resolution will be part of future posts on Get and Put API implementations.

2.2.2. System Scalability

Quoting Designing Data-Intensive applications - chapter 1

"Scalability is the term used to describe a system's ability to cope with increased load".

For the dynamo paper, this means that when the number of read/write operations increase, the database should

be able to still operate on the same availability and performance levels.

To achieve scalability, dynamo-like databases rely on several different techniques:

• Replication
  
  
  
  
  • scales reads
  
  
  • as mentioned in the previous section, replication is implemented via leaderless-replication with version vectors for conflict detection and resolution
  
  
  
  
  
  



• Partitioning - spreading the dataset amongst multiple nodes
  
  
  
  
  • scales writes
  
  
  • Dynamo relies on a technique called consistent-hashing to decide which nodes should own which keys. Consistent hashing and its pros and cons will be explained in future posts.
  
  
  
  
  
  

2.2.3. Data Durability

"Durability is the ability of stored data to remain intact, complete, and uncorrupted over time, ensuring long-term accessibility." (.

For GCP, durability is guaranteed at 11 nines - ie: GCP won't lose any more than 0.000000001 percent of your data in a year. We won't be calculating how many nines of durability our database will be able to provide, but we will apply many different techniques that increase data durability in multiple different components.

Most relevant durability techniques that we will go over are:

1. Replication -> Adds redundancy to the data stored


2. Checksum and checksum bracketing -> guarantees that no corruptions (either network or memory) can lead to data loss


3. Anti entry / read repair -> whenever a node doesn't have data that it should have (eg: maybe it was offline for deployment while writes were happening), our system has to be able to back-fill it.

2.2.4. Node discovery and failure detection

Dynamo databases rely on ) for this.

2.3. Dynamo-like database summary

The dynamo-like database key characteristics are:

• Eventually consistent storage system (but with tunnable consistency guarantees via Quorum configuration)


• Relies on leaderless-replication + sloppy quorums and hinted handoffs to maximize PUT availability


• Relies on Vector clocks for conflict detection


• Confliction resolution is handled by the client during reads


• Data is partitioned using Consistent-Hashing


• Durability is guaranteed by multiple techniques with anti-entropy and read-repair being the most relevant ones


• Node discovery and failure detection are implemented via Gossip Protocol

Next steps

Based on the concepts introduced in this post and the use case of the dynamo paper, the next posts on this series will walk through each component of the dynamo architecture, explain how it fits into the overall design, discuss alternate solutions and tradeoffs and then dive into specific implementations of the chosen solutions.

Below I include a (non-comprehensive) list of topics/components that will be covered in the next posts:

• Part 1 - Handling requests - a minimal TCP server


• Part 2 - Introducing PUT and GET for single node


• Part 3 - Bootstrapping our cluster: Node discovery and failure detection


• Part 4 - Partitioning with consistent-hashing


• Part 5 - Replication - the leaderless approach


• Part 6 - Versioning - How can we detect conflicts in a distributed system?


• Part 7 - Quorum based PUTs and GETs


• Part 8 - Sloppy quorums and hinted handoffs


• Part 9 - Re-balancing/re-sharding after cluster changes


• Part 10 - Guaranteeing integrity - the usage of checksums


• Part 11 - Read repair


• 
  Part 12 - Active anti-entropy (will likely have to be broken down into multiple posts since we will have to discuss merkle trees)

In order for me to focus on what you actually care about, please leave comments, complains and whatever else you might think while going through these posts. It's definitely going to be more useful the more people engage.

Cheers,