Storage on the Cloud: S3, EFS, EBS, and the Dynamo Legacy

6.1 Storage on the Cloud: The Three Interfaces

6.1.1 Recap: Cloud Foundations

The previous module built the foundation for this one. We looked at what the cloud is — starting with the "three-four-five" model of cloud computing. The phrase is shorthand for the standard cloud picture: three service models (infrastructure as a service, platform as a service, and software as a service), four deployment models (public, private, hybrid, and community), and five essential characteristics (on-demand self-service, broad network access, resource pooling, rapid elasticity, and measured service — the five properties that define a true cloud offering). We asked why organizations and businesses are moving towards the cloud, and we saw the four different kinds of cloud: public, private, hybrid, and community. We went through the benefits of using the cloud, and we covered the first three kinds of services that are offered: infrastructure as a service, platform as a service, and software as a service.

We then talked about what kind of infrastructure you can rent: compute resources (virtual machines that do the work), a network (important because a lot of data transfer happens in cloud systems), and storage (where the data rests). The storage part is where we stopped — we were about to discuss it but ran out of time, so we continue with storage on the cloud today.

This matters because storage is where the big data actually lives. The compute pieces, the network pieces, and now the storage pieces together form the rentable infrastructure of the cloud. A cloud application is really a loop: compute pulls data over the network, processes it, and writes results back to storage — so storage quality and storage choice sit at the heart of every big data system.

6.1.2 Block, File, and Object: The Three Storage Interfaces

AWS offers three different kinds of storage, and the natural way to separate them is by the interface they present. The storage could be a block interface, a file interface, or an object interface. An object interface is an interface along with the metadata — the object carries descriptive data about itself, not just the raw content. In other words, the three interfaces answer the question "how do I ask for my data back?" differently: by raw disk address, by file path, or by key with attached description.

On the AWS map, each interface maps to real services:

• Under block: Amazon Elastic Block Store (EBS) and Amazon EC2 instance storage.
• Under file: Amazon Elastic File System (EFS).
• Under object: S3 buckets and Amazon Glacier.

Under the covers there are also certain data transfer technologies that move data in and out of these storage systems. The transfer can happen from the cloud service providers themselves (Amazon / AWS) or from third-party connections. Named examples offered: AWS Storage Gateway (bridges on-premises storage with AWS), AWS Direct Connect (a dedicated private network link), and a third service whose name was garbled in the source — almost certainly AWS DataSync or AWS File Gateway, both members of the same data-transfer family. These exist to do fast, reliable data transfer between storages, because pushing petabytes over a general internet connection is neither fast nor dependable.

We are not going to cover each and everything on that map — the diagram simply shows what storage on the cloud is. The agenda for this session is: object storage (Amazon S3, the Simple Storage Service), then file storage (Elastic File System), then block storage (Elastic Block Store), and finally DynamoDB. In between, before the DynamoDB model, we will also look briefly at the Dynamo paper, a paper in the public domain that describes how these storage technologies emerged. The session referred to it as "written by Google," but the paper — Dynamo: Amazon's Highly Available Key-value Store, by DeCandia and colleagues at Amazon, published in 2007 — was written by Amazon's engineers; the two tech giants both built similar ideas at the same time, and it is easy to mix them up. The paper is available to read; we will cover the data mentioned in it in brief, not in very detail. It is considered to be the underlying paper for the storage technologies that Amazon developed.

6.1.3 What Each Storage Kind Means

Three quick definitions that anchor everything that follows:

• Object storage is a system that divides the data into separate self-contained units, and stores those units in a flat environment — there is no kind of hierarchy among the objects. Think of a flat namespace where every object is addressable directly, rather than living in a folder tree. Each object bundles the content together with its own metadata, so it carries its own description everywhere it goes.
• File storage organizes data into single files and follows a hierarchical structure: folders, files, directory structures. It is the model you know from ordinary file systems, but offered as a network service — a directory tree you can mount from many machines.
• Block storage splits the data into fixed blocks and stores those blocks separately, each with unique identifiers. The blocks are addressable uniquely. It is a good option when you want to do backup and recovery of your data, because you deal with the raw blocks directly.

Real-world: These three interfaces are the vocabulary of every cloud provider, not just AWS — when you hear about "object storage" or "block storage" from any vendor, these are the same ideas. Object storage powers backup archives, media repositories, and data lakes; file storage powers shared application content; block storage powers the disks behind virtual machines and databases. Choosing storage is the first architectural decision of nearly every cloud application, because it decides how your data can be reached, shared, and charged for.

6.2 Amazon S3: Object Storage

6.2.1 Objects and Buckets

S3 is object storage, which means it stores objects — files with a lot of metadata associated. Metadata is data about the file: information useful for reading or processing the data that is stored in the file. That is the defining difference from raw file storage — the object is shipped together with its description. Metadata covers things like the object's size, its creation date, its content type, its owner, and the permissions on it. A plain file system also keeps a little of this information, but object storage treats the description as a first-class part of the stored unit.

The core organizing unit is the bucket. A bucket is nothing but a container for certain objects. If you are familiar with AWS, you know that typing "S3" in the services search bar takes you there: you create S3 buckets, and inside those buckets you store your objects. The scale is worth noting: an S3 account can have hundreds of buckets, and a bucket can have hundreds of objects. Inside a bucket you can also create folders to organize your objects — so S3 gives you a light hierarchy (folders) even though the object layer itself is flat.

Objects come in any size. You can store a very small object that occupies one byte of storage, and you can also store an object that occupies 5 TB of storage — for example a very large video file, a movie, a very high-definition movie that occupies a lot of storage. Both extremes live in the same bucket model. One byte and 5,000,000,000,000 bytes sit side by side, addressed by the same mechanism.

Objects are uniquely addressable: they are uniquely identified by a developer-defined key and a URL. A developer can identify an object by associating a key and a URL with it. S3 also has an access control system, so anybody — even from within AWS or outside of AWS — can access these objects, subject to the permissions configured. Further, S3 supports versioning, and it offers eventual consistency across multiple reads and writes.

Eventual consistency is a term we discussed earlier. It does not force strict consistency: strict consistency would require updating all the replicas at the same time when a write happens. With eventual consistency we let the write happen, and then the data may not be available everywhere for a while — we may be reading stale data for a certain time — but eventually the system will be consistent, and we will have the consistent data after some time. That caveat aside, this is a deliberate design choice: S3 data, like all distributed-systems data, is partitioned and replicated — partitioning and replication are simply a part of dealing with distributed systems.

6.2.2 Addressing: Keys and URLs

Every bucket gets a URL for access. The first form given is:

\[ \texttt{bucketname.s3.amazonaws.com/objectname} \]

Here the bucket name appears first, then the S3 domain, then the object key — this is the classic (global) endpoint style. The second form, garbled in the source, is the regional endpoint style, which routes through the bucket's home region:

\[ \texttt{s3.}\langle \text{region} \rangle\texttt{.amazonaws.com/bucketname/objectname} \]

For example, with a bucket in the us-east-1 region, the address becomes s3.us-east-1.amazonaws.com/yourbucket/yourfile.txt. The two forms are different spellings of the same idea: a bucket name (unique) plus an object key (unique within the bucket) produces an address that is unique in the whole world.

Bucket names are unique across everything: whenever you create a bucket, AWS asks for a unique bucket name — no two accounts can hold the same bucket name. Within the bucket, the objects are the things you address: you access the bucket, then the object inside it.

6.2.3 S3's Consistency Model: An AP Design

To place S3 in the right spot of the CAP picture, recall the CAP theorem from before the mid-semester discussion: C stands for consistency, A for availability, and P for partition tolerance. When we deal with distributed systems that are geographically apart, partition tolerance is a must — partitions are bound to happen, so we design for them. Out of the remaining two we can choose one, because CAP says we cannot achieve all three in a distributed system; we achieve two, not all three.

S3 follows an AP design: the system is highly available, meaning it will sacrifice consistency. It offers availability and compromises consistency. Concretely: when a user uploads an object into an S3 bucket, the object is replicated, but readers may access an inconsistent replica, because the system wants availability. The write has happened at one place; it may not yet have been replicated to all the replicas. If we read from a replica where the write has not reached, we may read a stale copy of the data. The replicas will become consistent eventually.

There are also various cost options that S3 provides. By default, S3 follows a replication factor of three — three copies — for the purposes of fault tolerance and durability. But you always have an option for reduced redundancy at a lower cost: you can configure "I do not want to maintain many copies; I want to reduce this redundancy as long as it is saving my cost." The trade is honest: if you reduce cost by sacrificing redundancy, you also probably sacrifice a little of the availability as well. That reduced-redundancy storage option is available with S3 buckets.

6.2.4 Eventual Consistency in Action

Because S3 is eventually consistent, certain behaviors can show up for a small period of time. These are the four behaviors listed:

1. An uploaded object may be invisible to a reader. A write has happened, but it may not have been replicated to the replica we are reading from; at that moment the reader can get "the object does not exist". After some time, once the system becomes eventually consistent, the copy appears.
2. An object may not appear in the listing of a bucket immediately. The bucket listing itself can lag the write.
3. Old data may be returned if a write has not propagated to the replica being read.
4. A deleted object may be seen in the listing for some time. The deletion has not yet synced everywhere.

All of these resolve once the systems sync the data. If an operation has happened on certain nodes, this kind of lag can occur; after the sync you will not observe it anymore. The point to internalize: these are features of the availability-first design, not bugs — you get immediate, always-working writes and reads, and you accept brief windows of staleness.

6.2.5 S3 Architecture and Durability

The high-level architecture of S3 is built around regions and availability zones. The cloud has several regions, and within a region there are availability zones (AZs). The numbers given: 20+ regions, 60+ availability zones, and each availability zone can have up to 8 data centers. Data can be stored in at least three physically separated availability zones within a region, and those availability zones are connected by private network connections for low latency. That is the durability story: three physical copies, each in a separate failure-isolated location — a single data center, or even a whole availability zone, can fail without destroying the data.

Inside the system there is a metadata storage — remember, object storage has a lot of metadata — and the blob objects themselves. Organizations often do not expose what the underlying architecture is; at a broad level, the flow works like this: the end user comes through the internet, hits an application load balancer, then goes to the API servers, and the servers access the blob storage as well as the metadata required for processing the request. How the data is mapped to the S3 cluster and all of that is sometimes not exposed — this is the high-level picture of how things happen. The important separation is that metadata (where things are, what they are) and blobs (the raw bytes) are managed by different internal components, which is why object storage scales the way it does.

6.2.6 Storage Tiering

S3 does not give you one single bucket type. There are different tiers of storage, and based on how the application is going to interact with the data — how frequently it will access it — you can choose your S3 storage. The reason is cost: different tiers carry different costs. The three offerings:

• S3 Standard — used when we have very active data and we want synchronous access with millisecond retrieval.
• S3 Standard Infrequent Access — we do not access the data very frequently, but when we do, we still want synchronous access. The cost is lower because the data is accessed infrequently.
• Amazon Glacier — as the name indicates, this is for huge archival data. Historical data — say two-year, three-year, five-year, ten-year-old data — can be placed here. Retrieval takes minutes to hours, and the cost of storage in Amazon Glacier is minimal.

Based on your requirement — how much SLA you want — you choose that storage class. In between, you can use three tiers: frequently accessed data in the active tier, less frequently accessed data in the infrequent tier, and historical data in Glacier. Suppose there is now a requirement for some analysis on the historical data: you can bring that data to a more active state — there is syncing happening between the three tiers — and run certain analytics on top of it. That is the power of having storage classes.

6.2.7 Object Lambda

S3 also offers an Object Lambda service. We saw function as a service in a previous module — the new, serverless kind of thing — and Object Lambda lets you attach a function to the storage itself. When we try to read the data, it is possible that we want to invoke a function. The scenario: data is stored in an S3 bucket; one application needs the data in a certain way, another application needs it in a different way. Say we want to filter the data before it goes to an application — we can write a function that filters the data, or applies a certain transformation, before presenting it to the end user.

The mechanics: create and configure an S3 object lambda access point, and create an AWS Lambda function associated with the S3 object. Whenever a data request comes from a client, we check if there is a Lambda function associated that needs to be invoked: along with the GET request that fetches the data, that function is automatically invoked. The object lambda processes and transforms the object to meet the specific needs of the application — such as masking, filtering, or augmentation — and presents the result on the fly to the end user. The transformation happens per request, per client, without duplicating the stored data.

6.2.8 Use Cases

The S3 use cases given:

• Backup storage — for the cloud as well as for on-premises data you want to move and store in S3 buckets.
• Disaster recovery — with cross-region application data archival.
• Cloud-based applications with scalable storage — if you want to design a cloud-based application that wants scalable storage, accessible from anywhere, S3 buckets serve it.
• Data lakes for data analytics — you can dump any kind of data into one place, and that becomes a data lake; S3 buckets hold every kind of thing you can dump under the bucket you create. The data lake concept is not part of this course, but if you want to read about it there is ample material available.

Real-world: S3 is the storage backbone of a large share of the internet. Backup products write to it, media platforms serve videos from it, analytics teams land raw data in it as a data lake before loading it into warehouses, and AWS's own e-commerce systems lean on it. When a company says "our data lake lives in S3," they mean exactly this: every kind of file — logs, images, JSON, CSVs, Parquet — dumped into buckets, tiered by age, and read back by any tool that can issue an HTTP GET.

6.3 Amazon EFS: File Storage

6.3.1 How File Storage Works

In a file storage, we store one particular data together in a single file, and we maintain the data in a hierarchical structure making use of folders, files, and all the rest — the familiar directory model. Where object storage throws everything into one flat namespace, file storage keeps the tree: a path such as /projects/reports/q3.pdf names the file, the folder, and the whole ancestry of folders above it. The file systems are typically built using SSD storage, and they can be accessed from multiple cloud instances or even from customer premises hosts as well.

Amazon EFS supports the NFS protocol — the network file system protocol — and an application can simply attach the file system to its virtual private cloud (VPC), so there is not much change needed to get the elastic scalability and the input/output operations efficiency. NFS is the same protocol that network-attached storage (NAS) devices have spoken for decades: your operating system treats the remote folder like a local folder, so existing applications keep working almost unchanged.

The performance figures cited: around 10 GB per second of throughput and 500k input output operations per second (500,000 IOPS) — these are the service's peak burst figures, the top end the file system can deliver when there is sustained demand, not a guaranteed minimum at all times. Multiple NFS clients can attach to the file storage, and there are multiple storage classes within EFS as well.

6.3.2 Storage Classes and Lifecycle Policies

Just as S3 has storage tiers, EFS has multiple storage classes. There is EFS Standard, which comes with replication to three-plus availability zones; and there is EFS One Zone, where the application lives within one single zone and replication happens within that one zone, at a lower cost — the storage cost is lower because you are replicating within a single zone. Within each of these classes there are two options: Standard and Infrequent Access. So the full set is: EFS Standard, EFS Standard Infrequent Access, EFS One Zone, and EFS One Zone Infrequent Access.

With the term "infrequent" we are simply telling the cloud: "I can tolerate some delay, or compromise my specifications, as long as I pay less." That trade-off depends on the application needs. Most applications fall into the one-zone replication category; if something is very, very critical, we may go for the Standard class. It is also possible to choose both for different datasets. And we can set up lifecycle policies to move the data based on its age to the infrequent access class — data that is less frequently accessed can be moved down to reduce storage cost — and eventually move historical data to something like Amazon Glacier, as we saw with S3.

6.3.3 Architecture: Mount Targets Across Availability Zones

The standard storage-class architecture picture: we have a virtual private cloud with three availability zones. Each availability zone has a mount target — which is, in effect, an IP address that is exposed — and under the mount target the NFS protocol works. You connect to the mount and then access the files. The three mount targets are connected, and together they form the elastic file system, which offers high scalability to address high traffic. It is also possible to mount the target in one of the subnets within a single availability zone — the one-zone setup: an instance in that zone reaches the file system fast; the file system is replicated within that zone rather than across zones.

Visual intuition: picture three buildings (availability zones) on one campus (the VPC region), each with its own door (the mount target) marked with an address (IP). The buildings are connected by private corridors. An instance inside building 1 walks out of its own door and is home in moments; an instance in building 2 must first cross to building 1's door — or to its own local door, whichever the mount point offers — and every byte it moves across the campus incurs a cost.

There is a cost and latency lesson hidden in the standard setup: if there is an instance in another availability zone that wants to access the file system, it has to connect to the mount first — which incurs latency — and for any data transfer from one AZ to another, the cloud service providers charge. So an instance in another availability zone pays a data-access cost. AWS documentation has plenty of material on this if you want to deep-dive.

Real-world: EFS is the "shared drive in the cloud" — the same NFS mental model that network-attached storage has used for decades, now elastic and managed. Web farms use it to share uploaded content across many web servers; content teams use it as a shared workspace; container platforms mount it into running containers; analytics pipelines use it when multiple processing instances need to read and write a common file tree. Whenever the requirement is "many machines, one familiar folder tree, low change effort," file storage — EFS — is the answer.

6.4 Amazon EBS: Block Storage

6.4.1 What Block Storage Is

Block storage is the fastest of the three kinds, because we have access to the blocks directly — the block is the lowest-level access you can get. You can rent a block storage and attach it to your virtual machine, like an EC2 instance. The good part: in case your EC2 machine dies, your storage still stays — your data still exists on the disk — and because the storage is separate, it can be attached and detached at any time. Storage and compute are independent rentals: kill the virtual machine, keep the disk; replace the machine, reattach the same disk.

One defining constraint of EBS: it can only be accessed by one instance at a time. If an EC2 instance is accessing an EBS volume, no other EC2 instance can access it at the same time. That gives predictable performance for a single-instance use case. The performance parameters cited: on the order of 4 Gbps of throughput, up to 24 terabytes of volume size, up to 60k IOPS, and sub-millisecond latency per volume — the figures describe the top-end provisioned-performance volume family, and the exact numbers in the session were garbled, but the order of magnitude is what matters: this is the fastest, lowest-latency storage interface of the three. Because of that profile, EBS is typically used for I/O-intensive applications such as relational databases, OLTP engines, and transactional databases — workloads where every query waits on a disk read, and a predictable, low-latency block device is the difference between a snappy and a sluggish application.

6.4.2 EBS versus EFS

The comparison is a design decision:

• EBS is a single-instance, predictable-performance block volume — choose it when one machine needs raw, low-latency disk, e.g., a database server.
• EFS is a distributed multi-user network file system — choose it when you want to build scalable distributed services across many users with decent performance, and the file-level sharing model fits.

There is a lot available on all of these Amazon services under the AWS documentation, but that is the essence of the four kinds of storage we have talked about: object, then file, then block.

Real-world: Block storage is the silent engine of the cloud's databases: every managed relational database, every OLTP workload, every transactional engine that a company rents on AWS sits on EBS volumes. When a business says "our core banking database runs in the cloud," the storage layer underneath is almost certainly block storage — the raw, single-owner, low-latency disk that databases demand.

6.5 The Dynamo Paper: What Large-Scale Storage Was Designed For

6.5.1 The Application Study

Before we look at DynamoDB, we step back to the paper that motivated these technologies. The study behind it started from concrete applications: the authors looked at different applications and their requirements, and then came up with this kind of technology. The setting: you build a large-scale distributed application, specifically one you want to be on the cloud — for example, an e-commerce application. The requirements they listed: figuring out the bestseller list, looking into all the shopping carts, customer preferences, session management, sales / product sales rank, and the product catalog. They looked at these various requirements, and also at what kind of queries the end users were firing.

The common thread across all six workloads: each one is a small read or write keyed by something concrete — "give me the cart of user 4412," "update the rank of product X," "store this session for user 8821." None of them is a giant join across tables. That observation, written down honestly from production traffic, is the seed of the whole design.

6.5.2 The Key Findings

The observations from that study:

• No relational queries are being fired on the systems by end users. Largely, the queries are simply key-based object retrievals — "give me the object with this key." The object size is within the size of 1 MB as mentioned in the paper: the vast majority of stored objects are small — on the order of kilobytes to at most a few megabytes — so a single object's data can travel cheaply and quickly.
• Earlier storage systems followed ACID semantics, because storage was used for transaction purposes. The realization: there is no requirement of strict consistency in many of the use cases, so they wanted to come up with systems that should not strictly adhere to ACID semantics. And strict consistency may be the performance bottleneck in the earlier systems — making every write wait for every replica, everywhere, is exactly what makes a system slow at scale.
• Efficiency and scale: the system should be scalable — as the users of an application increase, the system should scale up — and for that they made use of commodity hardware. Ordinary, cheap machines instead of expensive special-purpose servers: the design must tolerate machines failing and still scale out.
• Strict low latency at the 99.9th percentile time. It is a connected system now, and latency must be bounded because if the latency is high, the end-user experience is not good and you lose business. The target: if you take samples of data transfer, 99.9 percent of the transfers should be within the SLA — a low latency. This is actually a very, very hard problem to achieve. The percentile term: 99.9 percentile means 99.9 percent of the samples fall in a certain range; the remaining 0.1 percent may fall outside.

On the right side of that slide there is a high-level diagram: client requests coming in, page rendering components, request routing, aggregator services, then services mapping to the Dynamo instances or other data stores within — a multi-tier design. Requests do not hit the data store directly; they flow through routing and aggregation layers that fan out to the storage tier and assemble the final page.

6.5.3 Design Considerations

From the application requirements, they derived design considerations:

1. The system should be highly available for writes. When you are updating your shopping cart, even if there is a network partition — considering CAP — the write should still go through. What are we going to sacrifice? Consistency: per CAP, a distributed system achieves only two of the three; partition tolerance is a must, so out of C and A we keep availability. These are AP systems: highly available systems. At times you find that a product added to the cart is not there when you look at the cart, or you click a like button and the like is not updated until you refresh — once the systems become eventually consistent, you find it is fine. That is the accepted trade.
2. Complexity of conflict resolution. Now the system is highly available for writes; writes happen at multiple places. When we try to read, which copy should we read — the copy available within that node, or the copy on another node? There could be multiple options, so the question is who resolves the conflicts on reads. Two options: last write wins, or leave it up to the application developer — show the developer the sequence of writes that happened, and the developer chooses which one fits the application.
3. Incremental scalability. As the customer base grows, we should be able to incrementally add nodes, and all nodes should have a symmetric role — there is no kind of master-slave thing happening; it is all peer-to-peer, all are the same. No node is special, so no node is a single point of failure, and growing the cluster means adding more identical peers.
4. Heterogeneous nodes. We could also allow nodes with different capabilities in the system — one may have higher capability, others lower. Then the job of the load balancer becomes a little tough: we have to allocate the work proportional to the capability. If there is heterogeneity, the load-balancing logic becomes a little complex, or maybe challenging.

So the design picture: highly available systems for writes, reads decide what data to read (latest copy, or developer chooses), incremental scaling should be possible, and with heterogeneous nodes we need a good load-balancing logic that allocates work proportional to capability.

6.5.4 Techniques at a Glance

For each problem, the paper picked a technique:

• Partitioning the data → consistent hashing. We will discuss this next — not in too much detail, but the idea.
• High availability for writes → vector clocks with reconciliation during reads. A vector clock is a kind of logical clock maintained to preserve the ordering of events in a distributed system. It is altogether a different topic — typically covered in a distributed computing course — but that is the one-line idea: we have to maintain vector clocks to keep writes highly available and reconcile on reads.
• Handling temporary failures → sloppy quorum and hinted handoff. The advantages it gives: high availability and durability guarantees even when some of the replicas are not available.
• Recovering from permanent failures → first detect whether there is a permanent failure, then use Merkle trees — hash trees that help detect failure and synchronize divergent replicas in the background. The idea: whatever data is on the node, we make hash functions out of the data and keep those hash values. If the replicas are not in sync, the hash values will change; if they differ for a longer period of time, we conclude there is a permanent failure.
• Membership and failure detection → gossip-based membership protocols. In a large distributed system we need to track who the members are, and track failures; gossip-based protocols do that.

The problems are very hard — vector clocks, Merkle trees, and the rest are all comprehensive topics on their own — but this gives the shape of how the systems work. If you know a little bit about hashing from a data structures course — basic hash functions — you already have the seed for the next topic.

Real-world: the Dynamo paper's lineage is everywhere. Amazon turned the design into the DynamoDB service we see next; Apache Cassandra openly describes itself as a Dynamo-inspired system (peer-to-peer nodes, consistent hashing ring, tunable consistency, hinted handoff); Riak and Voldemort follow the same family. When a NoSQL product advertises "Dynamo-style," it means exactly the design considerations listed here: AP, symmetric peers, incremental scaling, and reconciliation on reads.

6.6 Consistent Hashing: Partitioning and Replication

6.6.1 The Circular Address Space

Partitioning and replication was the first problem the paper visualized. The nodes are arranged in a kind of circular setup — a ring — and the challenge is how to partition the data across the nodes. It is not simple like dividing the data into \(n\) number of partitions and allocating them to \(n\) number of nodes; that is not straightforward. Instead they use consistent partitioning — consistent hashing — which offers incremental scalability.

The picture: nodes placed on a circle. Some hash function is applied on the key of the data, and it generates a certain number — a value in the address space. The size of the address space is set by the number of bits: if we use a five-bit address, we can address \(2^5 = 32\) numbers, 0 to 31; two bits address \(2^2 = 4\), zero to three; three bits address \(2^3 = 8\), zero to seven; four bits address 16, zero to fifteen; five bits address 32, zero to thirty-one. The examples in the session use small spaces, but the principle scales.

\[ \text{address space size} = 2^m \quad \text{(the values } 0, 1, 2, \dots, 2^m - 1\text{)} \]

6.6.2 Placement and Replication: Worked Examples

The placement rule is stated with a small ring of seven nodes labeled A, B, C, D, E, F, G in a clockwise circle. We want to store some data: apply the hash function; it indicates a particular node. Then the replicas are stored at the next two nodes following in the clockwise direction:

• If the hash says store in A, the replicas go to the two following nodes — B and C (the source's "P and C" is a transcription garble; clockwise order after A is B, then C).
• If the hash says store in D, the two following nodes hold replicas — E and F (the transcribed "A and F" is inconsistent with the clockwise order A→B→C→D→E→F→G; the deterministic rule gives the next two clockwise from D, which are E and F).
• If it says store in G, the replicas go to A and B — wrapping around the end of the circle back to the start.

The wrap-around behavior is the point: the ring is a circle, so "next clockwise" eventually wraps to the beginning.

Now the numeric example, on a 32-position ring (values 0 to 31) where the positions hold seven nodes — in the diagram, nodes at N5, N10, N17, N20, and N25 are the ones named.

Two student questions test the rule against its tempting mistakes.

A follow-up question pushes the same rule one step further, and adds a trap in the diagram itself.

Three further questions sharpen the edges of the model.

The next question checks that the same mental model covers the copies as well as the original.

One more question asks where the node positions themselves come from.

6.6.3 Incremental Scalability: Adding a Node

Why do we want the nodes placed at chosen positions with spare space between them? Because of incremental scaling. Suppose a node is getting loaded — we detect that it is going to be heavy — so we introduce a new node just before it. Concretely: introduce a new node N15 between N10 and N17. What happens to the data?

6.6.4 Lookup: Linear Search

After the data is organized, we must search it. The naive approach, which the paper considered too costly: linear search through successor links. Given a key, apply the hash function; it says "go to this node." If that node does not have the data, we keep following the successor link of the nodes — each node knows its next neighbor clockwise — and check each one until the object is found.

In the worst case, the data was present somewhere but the search had to go across all the hops to find it. Searching this way is a little costly — the lookup can degenerate to a full walk of the ring: with \(n\) nodes, a lookup may visit all \(n\) of them, one hop at a time. That is \(O(n)\) per lookup — fine for a toy ring, painful for a cluster of thousands.

6.6.5 Efficient Search: Finger Tables

Can we do better? The improvement from the paper: every node maintains a routing table, called a finger table, with a logarithmic number of entries — we skip nodes instead of visiting every one.

For an \(m\)-bit address space there are \(2^m\) key positions (for 7 bits, 128 positions: 0 to 127). Each node \(n\) maintains entries at

\[ n + 2^0,\ n + 2^1,\ n + 2^2,\ n + 2^3,\ \dots,\ n + 2^{m-1} \]

i.e., for node N28 in a 7-bit space: 28+1, 28+2, 28+4, 28+8, 28+16, 28+32, and 28+64 — seven entries, each pointing at the successor node of that value (the first node clockwise from it). We do not maintain each and every entry; the powers of two keep the number of entries small. For a 7-bit address space, seven entries per node. As the finger values grow, the targets grow too — the larger entries of N28 point onward to the bigger nodes in the ring: in the example diagram, once the finger values pass N73, the target becomes N99 (the exact successor targets depend on where the nodes sit in the diagram, but the pattern is always "point to the first node clockwise from the finger value").

An implementation-strategy alternative was mentioned: before forwarding in the clockwise direction, look one step backward — check whether going backward first saves hops. The finger tables help us navigate to the next hop without looking into each and every node.

6.6.6 Finger Table Questions and the Promise of a Full Worked Example

One question settles why the table has exactly the entries it has.

The session ends this topic with a promise: the full lookup walk — how the routing tables end up routing a search to a particular node, and how the routing table is built — was cut short, and the topic will be revisited in the next session with a proper worked example, because it is worth doing properly.

6.7 Versioning, Failure Handling, and Replication Tuning

This session closes the Dynamo story with three supporting systems: logical clocks that order writes, failure handling that keeps the ring alive, and N/R/W knobs that tune consistency, durability, and availability.

6.7.1 Versioning and Vector Clocks

The consistency-using-versioning diagram: as soon as a write is made to a particular data item, it creates a data version, D1. Another write happens — D2 is created. Two writes happen in parallel — D3 and D4 are created. After reconciliation, we may end up with a data version D5.

Vector clocks are associated with every write; every read operation can understand the causal order and reconcile the multiple versions. In the diagram the reconciliation happens at a point whose context values were transcribed as "x = 3, y = 1" — the garbled annotation almost certainly reads as a vector-clock context of the form "node x has seen 3 writes, node y has seen 1": each entry of the clock counts the writes one node has witnessed, and comparing two such vectors tells you whether one write happened before the other (its vector is smaller in every entry) or whether they happened in parallel (each vector has entries the other lacks). Two properties were flagged: vector clocks can grow over time — each new node that writes adds an entry, so the clocks keep growing as the cluster changes — and the system maintains the time span when the item was last updated.

Recall the context: we want high availability for writes. Writes keep happening; when we read, which particular value should we take — the latest update, or something in between? Two options, as in the paper: last write wins, or leave it up to the developer — expose all these writes to the developer and let the application decide which one to pick. Vector clock, one more time: a logical clock maintained to preserve the ordering of events in a distributed system — a comprehensive topic that normally lives in a distributed computing course. Logical clocks exist because wall-clock time on different machines is not trustworthy: two machines' clocks drift, so "2:01 on node A" and "2:01 on node B" cannot be compared. A vector clock replaces wall time with a count of events each node has observed, and "causal order" is the partial order that results — write X precedes write Y only when every node has seen X before Y.

6.7.2 Temporary Failures: Hinted Handoff and Sloppy Quorum

The nodes are connected in a circular fashion and the data is stored on certain nodes. What happens if a node fails — not permanently, but temporarily? Suppose node A was supposed to receive a replica, along with B and C — the data and two replicas. But A is down. What do we do?

6.7.3 Permanent Failures: Merkle Trees

For permanent failures the first step is detection: we have to detect the permanent failure. The tool is Merkle trees — hash trees — used to tag down the subtrees where the replicas have gone out of sync. Instead of comparing data item by data item (which takes much longer), each replica holds a hash value of its data.

The Merkle tree structure is what makes this efficient: the tree pins down which subtree is out of sync, so we do not scan all the data. Compare a Merkle-tree check with the brute-force alternative: checking whether two replicas agree by reading every item costs time proportional to the whole dataset; checking the tree's root hash answers "do they differ at all?" in one comparison, and descending the tree locates the divergent range in steps proportional to the depth of the tree.

6.7.4 Tuning Durability, Consistency, and Availability: N, R, W

The system exposes knobs that tweak durability, consistency, and availability. Three numbers:

• \(N\) — the total number of replicas for a data item (the total number of nodes holding copies).
• \(R\) — the number of replicas that must respond before we return a read request.
• \(W\) — the number of replicas that must be written before we return a write success.

These are the read- and write-concern style knobs — the same consistency configuration we did in the MongoDB material. The extremes:

• \(W = 1\): any single node can ack the write. Write performance is high.
• \(W = N\): highly durable writes — the write is not considered complete unless it has been completed on all the replicas. Highly consistent on the write side.
• \(R = 1\): high-performance reads — read a single node and return that data.
• \(R = N\): highly consistent reads — read all the nodes, and only when all the nodes are in sync and have the same copy of the data do we return.

The number of copies that the distributed-systems designers have come up with as a good default is three. With three replicas, we can use the majority idea: if we have three replicas, read two — if two have the same data, return the read request; and write two — if two nodes are successfully written out of the three, return the write success.

6.7.5 The 99.9th Percentile SLA Problem

The closing note of the paper discussion: a very important and hard challenging problem is to provide a 99.9th percentile SLA on latency — and to accommodate the slowest replicas for the chosen R and W values. Even if 99.9% of requests meet the latency bound, the slow replicas determine the tail; the tail is what breaks the SLA. That is why this remains a hard problem.

The reason is arithmetic: a read with \(R = 2\) waits for the slower of two replicas, and a write with \(W = 2\) waits for the slower of two confirmations. The few machines that are momentarily slow, busy, or unlucky become the pacing item of every request they serve — so the average node may be fast while the tail — the slowest few percent of nodes — drags the 99.9th percentile past the SLA. Fixing the tail is not the same as speeding up the average, which is why the paper treats the 99.9th-percentile target as a genuinely hard design problem.

Real-world: the N, R, W vocabulary is the shared language of real systems. Amazon DynamoDB's read and write settings are exactly these knobs; Apache Cassandra's consistency levels (ONE, QUORUM, ALL, and their local variants) are the same idea named differently — ONE ≈ \(R = 1\) or \(W = 1\), QUORUM ≈ majority, ALL ≈ \(R = N\) or \(W = N\) — and the majority default \(N = 3\), read two, write two, is the same design choice this lecture derives from the paper.

6.8 Amazon DynamoDB

6.8.1 What DynamoDB Is

DynamoDB is a service offered by Amazon as an AWS service: a fully managed NoSQL database service. Fully managed means the user is relieved of the administrative burdens of operating and scaling a distributed database — no hardware provisioning, no setup, no configuration, no worries about application scalability. It is a complete service you simply use from AWS. Compare this with running a database yourself: installing it, tuning it, patching it, adding servers when traffic grows, babysitting it at 3 a.m. when a node fails — DynamoDB removes that entire job and exposes only the parts that matter to the application: tables, items, and queries.

Its headline features: fast performance and seamless scalability. You can store any amount of data in DynamoDB tables, and it can serve any level of request traffic. You can scale up or down without considerable downtime or performance degradation. It also offers backup — in case of, say, an accidental write or delete operation, you can create backups.

6.8.2 Tables, Items, and Attributes

The core components mirror what we have seen in databases before: tables, items, and attributes.

• A table is very similar to a table in an RDBMS.
• An item is similar to a record: a collection of attributes forms one record. We term it an item.
• Each item is a collection of attributes, and an attribute is a key-value pair.

Two differences from an RDBMS are the point:

1. Each record may have a different set of attributes — there is no fixed schema forcing every item to carry the same columns. Item one has phone; item two has address instead.
2. Nesting of attributes is allowed. In the second item, address is nested: address further has street, city, state, zip. Nesting can go up to 32 levels deep — that is the stated property.

So we can create tables, add items to them, and each item is a group of key-value pairs (attributes). The practical effect of nesting: a whole JSON document — a customer profile with contact, address, order history — can be stored as one item, which is why DynamoDB is a natural fit for document-shaped data.

6.8.3 Primary Keys and Secondary Indexes

DynamoDB has the primary key feature we know from RDBMS. For the people table, while creating the table we can specify that person id is the primary key: it has to be unique, and it distinguishes one person from the others. A primary key can be a single attribute, or it can be a multi-attribute key — in that case we call it a composite primary key.

DynamoDB also supports secondary indexing. Every index is built on a base table: from a base table we can create a secondary index, specifying the attributes we want to index — for example, on genre and album title. That secondary index fastens the queries that require genre and album type, and some primary key attributes are also copied into the index. Indexes are maintained automatically: once you have created an index and you modify the base table (add, update, delete), the index is modified accordingly. It is a deeper topic — the AWS documentation on DynamoDB indexing covers it.

6.8.4 DynamoDB Streams and Lambda Triggers

An optional but important feature: DynamoDB Streams, which captures modification events on a table. It is optional — it is not available by default with every table; we need to enable it. An event is something that happens to the data: a new item is added, an item is updated, an item is deleted. When any such event happens, DynamoDB captures it with the help of stream records:

• If a new item is added, the stream captures the image of the entire item, including all the attributes.
• If an item is updated, it maintains before and after images.
• If an item is deleted, it maintains the before image — the image of the item before it was deleted.

The classic combination: DynamoDB Streams + AWS Lambda = triggers. We saw Lambda as function-as-a-service; we can attach functions to this storage. The trigger runs automatically when any event of interest happens: you specify in the Lambda function what should happen, attach it to the DynamoDB Streams; when the event happens in the table, DynamoDB captures it and automatically triggers the function.

6.8.5 Consistency Levels

Consistency matters for distributed databases spread across availability zones, and DynamoDB is available in multiple availability zones. Each region is physically independent and isolated from the other AWS regions: a table in one region and a table in another region are physically separate — they are considered two separate tables in DynamoDB. Within a region, every AWS region consists of multiple distinct locations called availability zones, and each AZ is isolated from failures in the other AZs of the same region. The AZs within the same region are connected via private networks for low latency, and replication of data happens among the AZs within a region for fault tolerance.

DynamoDB offers two levels of consistency:

• Eventual consistency: the response may be very fast, but you may not get the results of a recently completed write operation — a stale copy of the data may be returned. If you repeat the request after a short period of time, the response should return the latest data. The rule of thumb: typically consistent within about one second; for the timings in between you may have stale data. This is for faster reads.
• Strong consistency: reads return the latest write. The downsides: reads may be unavailable on outages — if there is a partition, and the read must read from all the replicas and only return once they are in sync, then with one node unreachable the read request cannot be served; that is low availability. It also means higher latency — reading from multiple nodes and waiting for sync — and it uses more throughput capacity for the read cycle.

So eventual consistency is much faster, but at times we have to compromise with consistency, and strong consistency buys correctness at the price of availability, latency, and throughput.

6.8.6 Capacity Modes and Billing

The last slide: capacity modes. DynamoDB has two read/write capacity modes, and billing depends on which mode is set — it decides how much you will pay:

• On-demand: no capacity planning at all. Set on-demand and auto scaling happens within certain limits, probably within minimal time: if your application scales up, the database adheres to that; if it scales down and not many users are there, the database adheres to that too. It also adheres to a single-digit millisecond SLA on reads and writes — a service level agreement, very important from the business point of view. On-demand is good for unpredictable workloads.
• Provisioned: you do some planning and reserve the capacity for the read and write throughput you need. There is cost predictability in that, and there is also some level of auto scaling in provisioned mode. Provisioned is good where you have some prediction — "this much we can stay within."

Charging works in terms of read request units and write request units consumed:

\[ 1\ \text{read request unit} = 1 \text{ strongly consistent read of } 4\ \text{KB} \]

\[ 1\ \text{read request unit} = 2 \text{ eventually consistent reads of } 4\ \text{KB} \]

\[ 1\ \text{write request unit} = 1\ \text{KB written} \]

Based on how many read request units and write request units are consumed, you pay. The CRUD operations — create, read, update, delete — are simple; any documentation on DynamoDB covers them. And since we have already covered Neo4j and MongoDB, this should be simpler for you now.

Real-world: DynamoDB is the workhorse behind AWS's own e-commerce workloads — the very shopping-cart, bestseller-list, session-management patterns that motivated the Dynamo paper. Outside AWS, the same design runs companies' game leaderboards, IoT device state, ad-tech counters, and any workload that says "give me the object with this key" at web scale. When a startup says "our database just scales," the storage behind that claim is often a key-value service like this one.

Exam Guidance Summary

This session covered storage on the cloud end to end: the three interfaces, three AWS services that implement them, the research paper that shaped them, and the managed database that productized the design. The list below is the exam-relevant core of the session.

• Finger-table lookup and routing-table construction were cut short and are explicitly promised to return — the plan is a full worked example in the next session. Expect this topic again and know the mechanism: node at \(n\) keeps entries \(n + 2^i\) for \(i = 0\) to \(m-1\), and searches skip nodes rather than walking the ring linearly. Practise one full lookup on a small ring before the next session. (Section 6.6.)
• CAP reasoning is assumed knowledge (it appeared "before the mid-semester" discussion): partition tolerance is a must in distributed systems, and each service picks one of C or A — S3 and DynamoDB eventual reads are AP-style choices. Be ready to justify a service's consistency behavior with CAP vocabulary: name the two chosen letters, name the sacrifice, and name the observable symptom (stale reads). (Section 6.2.)
• The N, R, W tuning model echoes the MongoDB consistency configuration done earlier in the course — the same knobs (how many replicas must ack a read/write) come back here; the majority case with \(N = 3\) is read two / write two, and the overlap condition \(R + W > N\) explains why that pairing sees the latest write. (Section 6.7.)
• No mark distribution was given in this session. The material covered spans: the three storage interfaces, S3 features (tiering, Object Lambda) and use cases, EFS, EBS, the Dynamo paper's requirements/design considerations/techniques, consistent hashing placement and lookup, failure handling, and DynamoDB core components. These are the likely exam topics — the storage-interfaces vocabulary and the problem-to-technique mapping of the paper are the two most likely question families.
• DynamoDB CRUD is easier after Neo4j and MongoDB — if CRUD appears, the pattern from those systems carries over; the AWS documentation is the reference. Consistency-level questions, request-unit arithmetic, and capacity modes are the parts specific to this session.

Key Industry Applications

• Amazon S3 — backup storage (cloud and on-premises), disaster recovery with cross-region archival, scalable cloud applications, and data lakes for analytics; objects from 1 byte to 5 TB, three AZ copies by default, tiered into Standard / Standard-IA / Glacier. In industry this is the landing zone for raw data in most analytics pipelines: logs, exports, and archives all land in buckets first.
• Amazon Glacier — archival and historical data at minimal cost with minutes-to-hours retrieval; the home for compliance records that must be kept for years but rarely read — the "coldest" tier of the storage lifecycle.
• S3 Object Lambda — per-request transformation of stored objects (masking, filtering, augmentation) without duplicating data; the pattern used to serve the same stored object to different consumers with different views (compliance-masked, filtered, or transformed) from one bucket.
• Amazon EFS — shared, NFS-based file storage across many instances and VPCs, with one-zone (cheap) and multi-AZ (highly available) classes plus lifecycle policies; the "shared drive in the cloud" for web farms, content teams, and container platforms that need many machines on one folder tree.
• Amazon EBS — low-latency block storage for I/O-intensive workloads: relational and transactional databases, OLTP engines; the raw, single-owner disk that database servers sit on, portable across zones only through snapshots.
• Amazon DynamoDB — fully managed NoSQL for e-commerce (shopping carts, bestseller lists, session management), any-scale traffic, on-demand scaling, streams + Lambda for event-driven flows (e.g., welcome emails via Amazon Simple Email Service); the managed face of the Dynamo design for web-scale key-value workloads.
• Consistent hashing and finger tables — the partitioning and routing ideas behind the Dynamo paper; the ISP hop-by-hop lookup analogy shows why hop efficiency matters at internet scale — the same ring idea appears in Cassandra's partitioner, in distributed caches, and in content delivery networks.