System design: Distributed locks | Leader election topic | My 20 minutes study

May 19, 2021

I like to read the article and also highlight things I like to learn next 20 minutes. 

Here are highlights:

1. The DynamoDB Lock Client is a Java Library widely used inside Amazon, which enables you to solve distributed computing problems like leader election and distributed locking with client-only code and a DynamoDB table
2. client-only code and a DynamoDB table
3. 
   

AWS Database Blog

Building Distributed Locks with the DynamoDB Lock Client

by Alexander Patrikalakis and Sasha Slutsker | on 15 AUG 2017 | in Amazon DynamoDB, Database | Permalink |  Comments |  Share

Alexander Patrikalakis and Sasha Slutsker are senior software development engineers with Amazon.

TL;DR
At Amazon, teams all across the company build upon AWS services just like AWS’s external customers. Here we have a contribution from Alex and Sasha, who work on teams supporting Amazon.com about a new client library that they developed to make their applications better – hopefully you’ll find it useful too. The DynamoDB Lock Client is a Java Library widely used inside Amazon, which enables you to solve distributed computing problems like leader election and distributed locking with client-only code and a DynamoDB table.

DynamoDB supports mechanisms, like conditional writes, that are necessary for distributed locks. However, the AWS SDK doesn’t include the logic needed to actually implement distributed locks. The DynamoDB Lock Client wraps up the necessary client logic for distributed advisory locks in an easy-to-use client interface. The protocol in the lock client Java library is widely applicable, and we encourage you to apply it in other languages.

Background
Distributed locking can be a complicated challenge to solve, because you need to atomically ensure only one actor is modifying a stateful resource at any given time. For example, perhaps you have a database that serves as the central source of truth for your application. To ensure data is always accurate, you need to ensure that only one application server in your application server fleet is modifying a particular record in your database.

In AWS, the many moving parts of Amazon EC2 also need to agree on what their configuration should be so that they can survive many different failure modes. A primitive that enables this consensus must also be highly available, consistent, and partition-tolerant. Ideally, this primitive is unaffected by clock skew across large fleets of machines.

Systems like Raft and Paxos were designed to address these challenges, but they are notoriously difficult to implement and operate. What if you just want to easily implement a lock for a simple distributed application you’re writing? Amazon EC2 does just this with DynamoDB. We’re happy to present the DynamoDB Lock Client, a Java client library that uses locks to coordinate cluster configuration independently of system time, with baked-in DynamoDB primitives like consistent reads and conditional writes. We baked so you can have your cake too…

A practical example
Let’s suppose that you are a retail bank that wants to ensure that at most one customer service representative changes customer details at a time. From a fraud prevention perspective and from a consistency perspective, temporarily locking customer records during an update makes a lot of sense. In this case, each customer has a unique identifier. The bank stores customer information like account balances, transactions, addresses, contact information, and relationship history in many different tables. To make their system scale horizontally, this bank doesn’t embed foreign key relationships in any of their tables. Each table is isolated from all others. The bank uses their application layer to coordinate changes to each customer in a distributed fashion.

The tables are independent, so you can’t just wrap the changes you need in a relational transaction. Instead, you can lock the customer’s unique identifier at a high level. Alternatively, you can lock the unique identifiers of customer details (addresses and telephone numbers) at a finer-grained level. You’d do so with a locking API action for a certain duration in your application before making any changes.

The DynamoDB Lock Client implements a protocol allowing similar applications to take advisory locks on any part of your problem domain, big or small. This protocol ensures your players “stay in possession of the ball” for a certain period of time.

The locking protocol
For a new lock, the lock client stores a lock item in the lock table. With the item, it stores the host name of the owner, the lease duration in milliseconds, a UUID unique to the host, and the host system clock time when the lock was initially created. The lock table looks something like this in the AWS Management Console.

The sequence and architecture diagram following shows the locking protocol. The protocol architecture includes an EC2 Auto Scaling group. The group spans two subnets in two Availability Zones of a single AWS Region and two EC2 instances with a Java application running in each subnet. Each of the instances is trying to acquire a lock on Moe.

1. Host A acquires a lock on Moe by writing an item to the lock table on the condition that no item keyed at “Moe” exists yet. Host A acquires the lock with a revision version number (RVN) of UUID1.
2. Host B tries to get a lock on Moe with a RVN UUID2.
3. Host B checks to see if a lock already exists with a GetItem call.
4. In this case, host B finds that host A holds a lock on Moe with a record version number (RVN) of UUID1. The same application runs on hosts A and B. That being so, host B expects host A to heartbeat and renew the lock on Moe in less than 10 seconds, if host A intends to keep the lock on Moe. Host A heartbeats once, and uses a conditional update on the lock keyed at Moe to update the RVN of the lock to UUID3.
5. Host B checks 10 seconds after the first AcquireLock call to see if the RVN in A’s lock on Moe changed with a conditional UpdateItem call and a RVN of UUID4.
6. Host A successfully updates the lock. Thus, host B finds the new RVN equal to UUID3 and waited 10 more seconds. Host A died after the first heartbeat, so it never changes the RVN past UUID3. When host B calls tries to acquire a lock on Moe for the third time, it finds that the RVN was still UUID3, the same RVN retrieved on the second lock attempt.
7. In this case, hosts A and B run the same application. Because host B expects host A to heartbeat if host A is healthy and intends to keep the lock, host B considers the lock on Moe expired. Host B’s conditional update to acquire the lock on Moe succeeds, and your application makes progress!

Sample code
The following is a code sample that attempts to take a lock on Moe with 10-second leases and heart beating, as described in the preceding example.

import java.io.IOException;
import java.util.Optional;
import java.util.concurrent.TimeUnit;
import org.junit.Test;
import com.amazonaws.auth.DefaultAWSCredentialsProviderChain;
import com.amazonaws.client.builder.AwsClientBuilder;

public class LockClientExample {
    private static final AwsClientBuilder.EndpointConfiguration DYNAMODB_LOCAL_ENDPOINT =
            new AwsClientBuilder.EndpointConfiguration("http://localhost:4567",
                    "us-west-2");
    @Test
    public void usageExample() throws InterruptedException, IOException {
        // Inject client configuration to the builder like the endpoint and signing region
        final AmazonDynamoDB dynamoDB = AmazonDynamoDBClientBuilder.standard()
                .withEndpointConfiguration(DYNAMODB_LOCAL_ENDPOINT)
                .withCredentials(new DefaultAWSCredentialsProviderChain())
                .build();
        // Whether or not to create a heartbeating background thread
        final boolean createHeartbeatBackgroundThread = true;
        //build the lock client
        final AmazonDynamoDBLockClient client = new AmazonDynamoDBLockClient(
            AmazonDynamoDBLockClientOptions.builder(dynamoDB, "lockTable")
                    .withTimeUnit(TimeUnit.SECONDS)
                    .withLeaseDuration(10L)
                    .withHeartbeatPeriod(3L)
                    .withCreateHeartbeatBackgroundThread(createHeartbeatBackgroundThread)
                    .build());
        //try to acquire a lock on the partition key "Moe"
        final Optional<LockItem> lockItem =
                client.tryAcquireLock(AcquireLockOptions.builder("Moe").build());
        if (lockItem.isPresent()) {
            System.out.println("Acquired lock! If I die, my lock will expire in 10 seconds.");
            System.out.println("Otherwise, I will hold it until I stop heartbeating.");
            client.releaseLock(lockItem.get());
        } else {
            System.out.println("Failed to acquire lock!");
        }
        client.close();
    }
}

Before running the code listing preceding, create a dependency on the DynamoDB Lock Client in your POM as shown following.

<dependency>
    <groupId>com.amazonaws</groupId>
    <artifactId>dynamodb-lock-client</artifactId>
    <version>1.0.0</version>
</dependency>

Features
The DynamoDB Lock Client uses the DynamoDB UpdateItem API to heartbeat and extend locks each host owns. Additionally, the lock client uses client-side TTL to expire locks. The lock client uses a recent version of the AWS SDK for Java. The locking protocol employs conditional updates extensively and throughout the lifecycle of a lock (creation, renewal by heartbeat, and expiration by deletion). The lock client is an excellent example of how to use condition and update expressions when updating items in a DynamoDB table. Finally, the lock client POM demonstrates best practices that developers can use to integration-test their applications with DynamoDB Local and the Maven failsafe plugin.

Scaling your locks
Application developers using the lock client can scale their locking use in a few dimensions. First, by varying the granularity of locks taken, you can reduce contention to the smallest possible surface area necessary for a logical operation to succeed. Second, you can configure the heartbeat and TTL intervals of the entity locks based on the read and write latency of the persistence layer where you store your business entities. By doing so, you can reduce contention by taking locks only for the amount of time you need.

A lock table schema with a workload equally distributed among the partition and sort key space helps you use all the throughput that you allocate to the lock table. Use composite partition keys when possible. You can usually use them when you don’t need to read a range of locks associated with the same primary entity—for example, when one customer has multiple orders on an e-commerce platform. Finally, you can scale the backing DynamoDB lock table to arbitrary levels of reads and writes per second (provisioned capacity).

Future directions
One way we might expand on this work is to implement client support for other SDKs and platforms. JavaScript, iOS, and Android are all likely candidates. When AWS SDK for Java 2.0 is generally available, you can update the lock library to take advantage of the new Java SDK. Another thing we might add is support for server-side TTL, a recently released DynamoDB feature. Finally, we might later embed this library in other applications that require coordination. As always, pull requests are welcome.

Summary
We are excited to share the DynamoDB Lock Client with you. We look forward to helping you use it to iterate on your own distributed platforms. Happy tinkering!

TAGS: Amazon DynamoDB, DynamoDB, DynamoDB Lock Client

System design: Roberto Vitillo | Leader election best practices | My 20 minutes study

 May 19, 2021

I do think that it is important to read technical articles daily. I like to enjoy learning and prepare myself to be a good system designer. I like to start from the small thing, read very well a technical article daily. 

Here is the blog. 

Here are highlights what I should do: 

1. Look into key value store - etcd
2. Leader election - ZooKeeper or etcd
3. Distributed concepts: basic primitives like compare-and-swap to fully-fledged distributed mutexes
4. Ideally, the external store needs to offer atomic compare-and-swap and expiration times (TTL) for keys
5. Ideally, the external store needs to offer atomic compare-and-swap and expiration times (TTL) for keys. A compare-and-swap operation updates the value of a key if and only if the value matches the expected one, while an expiration time defines the time to live for a key, after which the key expires and is removed from the store if the lease hasn’t been extended
6. Concepts in the above statements: TTL - expiration time (TTL) for keys, compare-and-swap operation, the lease, key expires
7. Spend 5 minutes to read about locking library, DynamoDB

Leader election best practices

December 26, 2020

Sometimes a single process in a system needs to have special powers, like being the only one that can access a shared resource or assign work to others. To grant a process these powers, the system needs to elect a leader among a set of candidate processes, which remains in charge until it crashes or becomes otherwise unavailable. When that happens, the remaining processes detect that the leader is no longer available and elect a new one.

Leader election can be implemented without any external dependency like the Raft algorithm does. Doing so is far from trivial, though, and it’s best avoided unless you have a very good reason to.

In practice, you can leverage an external linearizable key-value store, like etcd or Zookeeper, which offer abstractions that make it easy to implement leader election. The abstractions span from basic primitives like compare-and-swap to fully-fledged distributed mutexes.

Ideally, the external store needs to offer atomic compare-and-swap and expiration times (TTL) for keys. A compare-and-swap operation updates the value of a key if and only if the value matches the expected one, while an expiration time defines the time to live for a key, after which the key expires and is removed from the store if the lease hasn’t been extended. Each process tries to acquire a “lease” by creating a new key with a specific TTL using compare-and-swap. The first process to succeed becomes the leader and remains such until it stops renewing the lease, after which another process can become the leader.

The TTL expiry logic can also be implemented on the client-side, like this locking library for DynamoDB does, but the implementation is more complex, and it still requires the data store to offer a compare-and-swap operation.

You might think that’s enough to guarantee there can’t be more than one leader in your application. Unfortunately, that’s not the case.

To see why, suppose there are multiple processes that need to update a file on a shared blob store, and you want to guarantee that only a single process at a time can do so to avoid race conditions. To achieve that, you decide to use a distributed mutex - a form of leader election. Each process tries to acquire the lock, and the one that does so successfully reads the file, updates it in memory, and writes it back to the store:

if lock.acquire():
    try:
        content = store.read(blob_name)
        new_content = update(content)
        store.write(blob_name, new_content)
    except:
        lock.release()

The problem here is that by the time the process writes the content to the store, it might no longer be the leader - a lot might have happened since it was elected. For example, the operating system might have preempted and stopped the process, and several seconds will have passed by the time it’s running again. So how can the process ensure that it’s still the leader then? It could check one more time before writing to the store, but that doesn’t eliminate the race condition, it just makes it less likely.

To avoid this issue, the data store downstream needs to verify that the request has been sent by the current leader. One way to do that is by using a fencing token. A fencing token is a number that increases every time that a distributed lock is acquired - in other words, it’s a logical clock. When the leader writes to the store, it passes down the fencing token to it. The store remembers the value of the last token and accepts only writes with a greater value:

success, token = lock.acquire()
if success:
    try:
        content = store.read(blob_name)
        new_content = update(content)
        store.write(blob_name, new_content, token)
    except:
        lock.release()

This approach adds complexity as the downstream consumer - in our case, the blob store - needs to support fencing tokens. If it doesn’t, you are out of luck, and you will have to design your system around the fact that occasionally there will be more than one leader. For example, if there are momentarily two leaders and they both perform the same idempotent operation, no harm is done.

Although having a leader election can simplify the design of a system as it eliminates concurrency, it can become a scaling bottleneck if the number of operations performed by the leader increase to the point where it can no longer keep up. When that happens, you might be forced to re-design the whole system.

Also, having a leader introduces a single point of failure with a large blast radius - if the election process stops working or the leader isn’t working as expected, it can bring down the entire system with it.

You can mitigate some of these downsides by introducing partitions and assigning a different leader per partition, but that comes with additional complexity. This is the solution many distributed data stores use.

Before considering the use of a leader, check whether there other are ways of achieving the desired functionality without it. For example, optimistic locking is one way to guarantee mutual exclusion at the cost of wasting some computing power. Or perhaps high availability is not a requirement for your application, in which case having just a single process that occasionally is restarted after failure is not a big deal.

As a rule of thumb, if you must use leader election, you have to minimize the work it performs and be prepared to occasionally have more than one leader if you can’t support fencing tokens end-to-end.

GTE stock: GTE is one of the BEST

 

System design: How do you prepare for the system design interview? | Robert Vertillo

Here is the link.  

How do you prepare for the system design interview?

I get asked this question a lot. I lost track of people I know that spend all their time brushing up on algorithmic puzzles and barely prepare for the system design round. I can’t blame them; it’s easy to find comfort reversing lists, finding shortest paths, and whatnot. The solutions of those problems can be checked for correctness or efficiency. But you can’t automatically check how good your mock designs are. It turns out system design is hard! There is no fail-proof recipe for it, there are no perfect solutions, and it’s all about trade-offs.

If you are a junior engineer, then you might be able to wing the design round and still get an offer. 

If you are a senior engineer, then you need to be able to design complex systems and dive deep in any vertical. You can be a world champion in balancing trees, but if you fail the design round, you are out. If you just meet the bar, then don’t be surprised when your offer is well below what you were expecting.

I know what you are thinking. “How the heck am I supposed to get better at nailing design interviews if there is no recipe for it?” The best way to breeze through a system design round is to learn how to design actual real systems. Who would have thought, right? Unlike algorithmic puzzles, it’s not an “interview-only” skill. It requires hard work and experience. But if you approach it the right way, then you will add a powerful tool to your tool belt. One that will make you stand out from the crowd.

When I say system design, I mean the distributed kind. It used to be that large scale system design questions were only asked by the likes of Amazon, Google, and Microsoft. But that’s no longer true. The reality is that nowadays we are all distributed systems engineers. And we need to understand the implications of building complex systems out of a networked mesh of simpler ones.

So how do you design real-world distributed systems? I recall how hard it was to find the right information when I first started. Some books on distributed systems were too theoretical to build real stuff. Some felt like marketing material for a technology stack that was going to be obsolete in a few years. All I wanted was something pragmatic like a timeless classic. Only whitepapers of real systems satisfied me. But without a solid grasp of the fundamentals, I spent hours trying to connect all the missing dots.  

This is why I decided to write a book to teach the fundamentals of large scale distributed systems design. The book contains knowledge I have used over the years to solve concrete problems, the kind that needs to scale to millions of requests per second, and billions of devices. But no matter what scale you are working on today, the core principles are universal.

After reading the book, you are not going to look at network calls the same way. And you will start applying that knowledge from day one at your job and on personal projects. Armed with the core fundamentals, you will have the tools to understand technical whitepapers, build systems of your own, and nail interviews.

Roberto Vitillo's Blog: Three hours reading time | Excited to read blog

May 18, 2021

Introduction

I choose not to purchase the book right away, instead I like to spend time to read Roberto Vitillo's blog and spend time to learn a few things from his blog. 

Blog - I found the blog after more than 20 minutes search

Blog link is here. 

Roberto Vitillo: Understanding Distributed Systems: What every developer should know about large distributed applications

 Learning to build distributed systems is hard, especially if they are large scale. It's not that there is a lack of information out there. You can find academic papers, engineering blogs, and even books on the subject. The problem is that the available information is spread out all over the place, and if you were to put it on a spectrum from theory to practice, you would find a lot of material at the two ends, but not much in the middle.

That is why I decided to write a book to teach the fundamentals of distributed systems so that you don’t have to spend countless hours scratching your head to understand how everything fits together. This is the guide I wished existed when I first started out, and it's based on my experience building large distributed systems that scale to millions of requests per second and billions of devices.

If you develop the back-end of web or mobile applications (or would like to!), this book is for you. When building distributed systems, you need to be familiar with the network stack, data consistency models, scalability and reliability patterns, and much more. Although you can build applications without knowing any of that, you will end up spending hours debugging and re-designing their architecture, learning lessons that you could have acquired in a much faster and less painful way.

Table of contents

1 Introduction
1.1 Communication
1.2 Coordination
1.3 Scalability
1.4 Resiliency
1.5 Operations
1.6 Anatomy of a distributed system

Communication
2 Reliable links
2.1 Reliability
2.2 Connection lifecycle
2.3 Flow control
2.4 Congestion control
2.5 Custom protocols
3 Secure links
3.1 Encryption
3.2 Authentication
3.3 Integrity
3.4 Handshake
4 Discovery
5 APIs
5.1 HTTP
5.2 Resources
5.3 Request methods
5.4 Response status codes
5.5 OpenAPI
5.6 Evolution

Coordination
6 System models
7 Failure detection
8 Time
8.1 Physical clocks
8.2 Logical clocks
8.3 Vector clocks
9 Leader election
9.1 Raft leader election
9.2 Practical considerations
10 Replication
10.1 State machine replication
10.2 Consensus
10.3 Consistency models
10.4 Chain replication
10.5 Solving the CAP theorem
10.6 Coordination avoidance
11 Transactions
11.1 ACID
11.2 Isolation
11.3 Atomicity
11.4 Asynchronous transactions

Scalability
12 Functional decomposition
12.1 Microservices
12.2 API gateway
12.3 CQRS
12.4 Messaging
13 Partitioning
13.1 Sharding strategies
13.2 Rebalancing
14 Duplication
14.1 Network load balancing
14.2 Replication
14.3 Caching

Resiliency
15 Common failure causes
15.1 Single point of failure
15.2 Unreliable network
15.3 Slow processes
15.4 Unexpected load
15.5 Cascading failures
15.6 Risk management
16 Downstream resiliency
16.1 Timeout
16.2 Retry
16.3 Circuit breaker
17 Upstream resiliency
17.1 Load shedding
17.2 Load leveling
17.3 Rate-limiting
17.4 Bulkhead
17.5 Health endpoint
17.6 Watchdog

Testing and operations
18 Testing
18.1 Scope
18.2 Size
18.3 Practical considerations
19 Continuous delivery and deployment
19.1 Review and build
19.2 Pre-production
19.3 Production
19.4 Rollbacks
20 Monitoring
20.1 Metrics
20.2 Service-level indicators
20.3 Service-level objectives
20.4 Alerts
20.5 Dashboards
20.6 On-call
21 Observability
21.1 Logs
21.2 Traces
21.3 Putting it all together
22 Final words

The book webpage is here.