Chapter 4: Scalable and Fault-Tolerant Applications

Question 1

Name and describe the two principle methods to scale.

Answer 1

Vertical Scalability (Scaling Up)
Idea: Increase performance of a single node (more CPUs, memory, …)
Pro: Good speed-up up to a particular point
Con: Beyond that point, speed-up becomes very expensive
Horizontal Scalability (Scaling Out)
Idea: Increase number of nodes
Pro: Cheap to grow total amount of resources
Con: Standard software is often not able to leverage resources, special software needed

Question 2

What is the Difference between Stateless and Stateful components?

Answer 2

a stateless component maintains no internal state beyond a request e.g DNS server, web server with static pages, …
a stateful component maintains state beyond request required to process next request
e.g SMTP server, stateful WS, DBMS, …

Question 3

Name three possible Levels of Stateless Load Balancing.

Answer 3

Load balancing on IP level
Load balancing on DNS
Load balancing by distinct load balancer
(Load balancing on different levels can be combined)

Question 4

How does Load balancing on IP level work?

Answer 4

Balancing is implemented by IP routers
- Multiple devices share one IP address (IP anycast)
- Routers route packet to different locations
Requirements for applicability
- Request must fit in one IP packet
- Control over routers
Examples: DNS root server (mostly for reliability)

Question 5

How does Load balancing on DNS level work?

Answer 5

Balancing is implemented by DNS servers
- DNS servers resolve DNS name to different IP addresses
Requirements for applicability
- Control over DNS server
- Stable load characteristics (think of DNS caching)
Examples: Various big websites, e.g. www.google.com

Question 6

How does Load balancing by distinct load balancer work?

Answer 6

Explicitly distributes request among available machines
- Clients send requests to load balancer
Requirements for applicability
- No network bottleneck
Examples: Various websites, Amazon Elastic LB

Question 7

What are the three Different strategies for the actual load balancing?

Answer 7

1. Round robin LB
   - Simple, good if all request cause roughly the same load
2. Feedback-based LB
   - Servers report actual load back to load balancer
3. Client-based LB
   - Choose server with smallest network latency for client

Question 8

Explain the Idea of Partitioning.

Answer 8

Divide data into distinct independent parts
- Each server is responsible of one or more parts
Pure partitioning improve scalability but not availability
- Each data item is only stored in one partition!

Question 9

Name and explain three Popular Partitioning Schemes.

Answer 9

Partitioning per tenant
- Put different tenant on different machines
- Pro: In PaaS clouds, tenants are expected to be isolated No network traffic between machines, good scalability Con: Tenant cannot scale beyond one machine
Horizontal partitioning (relational databases)
- Split table by rows
- Put different rows on different machines
- Reduced number of rows, reduced indices
- Done by Google BigTable, MongoDB
Vertical partitioning (relational databases)
- Split table by columns
- Not very common to improve scalability
-> Just mentioned here for the sake of completeness

Question 10

Which two Classes of Partition Functions exist and what are the pro and cons?

Answer 10

Hash partitioning

• Desired property: Uniform distribution
• Pro: Good load balancing characteristics
• Con: Inefficient for range queries, typically requires data reorganization when number of partitions changes

Range partitioning

• Pro: Efficient for range queries and partition scaling
• Con: Poor load balancing properties

Question 11

Where to Place the Replicas?

Answer 11

Within a cloud data center, replica placement is often done with respect to the network hierarchy
- One replica on another machine
- Guards against individual node failures
- One replica on another rack
- Guards against outages of the rack switch
On a global scale, replicas are often distributed with regard to the client locations

Question 12

Who can create the copies for Replication?

Answer 12

Server-initiated replication
- Copies are created by server when popularity of data
item increases
- Mainly used to reduce server load
- Server decides among a set of replica servers
Client-initiated replication
- Also known as client caches
- Replica is created as result of client‘s response
- Server has no control of cached copy anymore
- Stale replicas handled by expiration date
- Traditional examples: Web proxies

Question 13

What Happens at Replication when the Data Changes? steps 1. - 3.

Answer 13

1. Invalidation protocols
   - Inform replica servers that their replica is now invalid
   - Good when many updates and few reads
2. Transferring the modified data among the servers
   - Each server immediately receives latest version
   - Good when few updates and many reads
3. Don‘t send modified data, but modification commands
   - Good when commands substantially smaller than data
   - Assumes that servers are able to apply commands
   - Beneficial when network bandwidth the scarce

Question 14

Explain Push- and Pull- based updates

Answer 14

Push-based updates (server-based protocols)
- Server pushes updates to replica servers
- Mostly used in server-initiated replica setups
- Used when high degree of consistency is needed
Pull-based updates (client-based protocols)
- Clients request updates from server
- Often used by client caches
- Good when read-to-update ratio is low

Question 15

What are Issues of Push- and Pull- based updates

Answer 15

State of server
Messages sent
Response time at client

Question 16

Which two Views On Consistency exist?

Answer 16

Data-centric consistency models
- Talk about consistency from a global perspective
- Provides guarantees how a sequence of read/write operations are perceived by multiple clients
Client-centric consistency models
- Talk about consistency from the client‘s perspective
- Provides guarantees how a single client perceives the state of a replicated data item

Question 17

Two groups of Data-Centric Consistency Models

Answer 17

Strong consistency models
- Operations on shared data is synchronized
- Strict consistency (related to time)
- Sequential consistency (what we are used to)
- Causal consistency (maintains only causal relations)
Weak consistency models
- Synchronization only when data is locked/unlocked
- General weak consistency
- Release consistency
- Entry consistency

Question 18

5 Client-Centric Consistency Models (Client-Centric)

Answer 18

1. Eventual Consistency
2. Monotonic Reads
3. Monotonic Writes
4. Read Your Writes
5. Writes Follow Reads

Question 19

Characteristics of Eventual Consistency (Client-Centric)

Answer 19

• all replicas will reach the most recent state at some point of time
• client can read from everywhere
• most common used by big cloud providers

Question 20

Characteristics of Monotonic Reads (Client-Centric)

Answer 20

The client reads always from the servers which has all writes that the cllient previously read.

Question 21

Characteristics of Monotonic Writes (Client-Centric)

Answer 21

The client can only write on servers where his previous writes have been completed.

Question 22

Characteristics of Read Your Writes (Client-Centric)

Answer 22

All write operations of a client will always be seen by a successive read operation of the same client.

Question 23

Characteristics of Writes Follow Reads (Client-Centric)

Answer 23

A write operation after a read operation can only be performed after all preceding writes have been performed.

Question 24

General Remark on Consistency

Answer 24

In general, the stricter the consistency model, the more it impacts the scalability of a system
- More consistency requires more synchronization
- While the data is synchronized, some client requests
may be answered
- Databases of the 80s and 90s put strong emphasis on consistency, lived with limited scalability/availability
- Today‘s cloud databases often sacrifice consistency in favor of scalability and availability

Question 25

Explain the Brewer’s CAP Theorem

Answer 25

In a distributed system, it is impossible to provide all three of the following guarantees at the same time:
- Consistency: Write to one node, read from another node will return something no older than what was written
- Availability: Non-failing node will send proper response (no error or timeout)
- Partition tolerance: Keep promise of either consistency
or availability in case of network partition

Question 26

Why Replication and not only Partitioning?

Answer 26

Partitioning helps with scalability but not availability
- Data is only stored in one location
- If machine goes down, data is gone
Replication can improve both scalability and availability!

Question 27

Characteristics of Strict Consistency (Data-Centric)

Answer 27

Any read operation returns the value stored by the most recent write operation.

Question 28

Characteristics of Sequential Consistency (Data-Centric)

Answer 28

Any reads in a sequence return the last writes in sequence.

Question 29

Characteristics of Causal Consistency (Data-Centric)

Answer 29

As long as the writes were not potentially depending, a different read order of concurrent writes is ok.

Question 30

Fundamental Cloud Architectures.

Answer 30

• Workload distribution
• Resource pooling
• Dynamic scaling and elastic capacities

Question 31

Goal of every partitioning scheme.

Answer 31

Reduce network communication.

Question 32

Consistency Models impact on Scalability.

Answer 32

The stricter the CL, the less scalability is possible.