Background

Single-leader and multi-leader replication are based on the idea that a client sends a write request to one node (the leader), and the database system takes care of copying that write to the other replicas. A leader determines the order in which writes should be processed, and followers apply the leader’s writes in the same order.

Some data storage systems take a different approach, abandoning the concept of a leader and allowing any replica to directly accept writes from clients. Some of the earliest replicated data systems were leaderless, but the idea was mostly forgotten during the era of dominance of relational databases. It once again became a fashionable architecture for databases after Amazon used it for its in-house Dynamo system. Riak, Cassandra, and Voldemort are open source datastores with leaderless replication models inspired by Dynamo, so this kind of database is also known as Dynamo-style.

In some leaderless implementations, the client directly sends its writes to several replicas, while in others, a coordinator node does this on behalf of the client. However, unlike a leader database, that coordinator does not enforce a particular ordering of writes. As we shall see, this difference in design has profound consequences for the way the database is used.

Multi-leader Replication (Master–master or Active/active Replication)

Although replication architectures with only a single leader is a common approach, there are interesting alternatives.

Leader-based replication has one major downside: there is only one leader, and all writes must go through it. If you can’t connect to the leader for any reason, for example due to a network interruption between you and the leader, you can’t write to the database.

A natural extension of the leader-based replication model is to allow more than one node to accept writes. Replication still happens in the same way: each node that processes a write must forward that data change to all the other nodes. We call this a multi-leader configuration (also known as master–master or active/active replication). In this setup, each leader simultaneously acts as a follower to the other leaders.

演化

单机架构

我们从最简单的开始讲起。

假设你的业务处于起步阶段，体量非常小，那你的架构是这样的：

这个架构模型非常简单，客户端请求进来，业务应用读写数据库，返回结果，非常好理解。

但需要注意的是，这里的数据库是「单机」部署的，所以它有一个致命的缺点：一旦遭遇意外，例如磁盘损坏、操作系统异常、误删数据，那这意味着所有数据就全部「丢失」了，这个损失是巨大的。

Vertical Scalability

Vertical scaling, referred to as “scale up”, means the process of adding more power (CPU, RAM, etc.) to your servers. Horizontal scaling, referred to as “scale-out”, allows you to scale by adding more servers into your pool of resources.

When traffic is low, vertical scaling is a great option, and the simplicity of vertical scaling is its main advantage. Unfortunately, it comes with serious limitations.

• Vertical scaling has a hard limit. It is impossible to add unlimited CPU and memory to a single server.
• Vertical scaling does not have failover and redundancy. If one server goes down, the website/app goes down with it completely.

Scope

Title

Bi-Directional Scalable Highly Available ID Mapping

Question Description

The e-commerce platform would like to maintain its own user id space so it can support users from different business / products

Design a highly scalable, highly available bi-directional user id mapping service to bind an external user id to an internal e-commerce platform user id.

• map(external_uid) ==> internal_uid
• reverse_map(internal_uid) ==> external_uid

Describe key components for your design, including database selection and design, cache design, logical flow etc.

Scope

• Candidate: What types of notifications does the system support? Interviewer: Push notification, SMS message, and email.

• Candidate: Is it a real-time system? Interviewer: Let us say it is a soft real-time system. We want a user to receive notifications as soon as possible. However, if the system is under a high workload, a slight delay is acceptable.

• Candidate: What are the supported devices? Interviewer: iOS devices, android devices, and laptop/desktop.

• Candidate: What triggers notifications? Interviewer: Notifications can be triggered by client applications. They can also be scheduled on the server-side.

• Candidate: Will users be able to opt-out? Interviewer: Yes, users who choose to opt-out will no longer receive notifications.

• Candidate: How many notifications are sent out each day? Interviewer: 10 million mobile push notifications, 1 million SMS messages, and 5 million emails.

Scope

1. Candidate: What features are important? Interviewer: Ability to upload a video and watch a video.
2. Candidate: What clients do we need to support? Interviewer: Mobile apps, web browsers, and smart TV.
3. Candidate: How many daily active users do we have? Interviewer: 5 million
4. Candidate: What is the average daily time spent on the product? Interviewer: 30 minutes.
5. Candidate: Do we need to support international users? Interviewer: Yes, a large percentage of users are international users.
6. Candidate: What are the supported video resolutions? Interviewer: The system accepts most of the video resolutions and formats.
7. Candidate: Is encryption required? Interviewer: Yes
8. Candidate: Any file size requirement for videos? Interviewer: Our platform focuses on small and medium-sized videos. The maximum allowed video size is 1GB.
9. Candidate: Can we leverage some of the existing cloud infrastructures provided by Amazon, Google, or Microsoft? Interviewer: That is a great question. Building everything from scratch is unrealistic for most companies, it is recommended to leverage some of the existing cloud services.

Data Warehouse

In computing, a data warehouse (DW or DWH), also known as an enterprise data warehouse (EDW), is a system used for reporting and data analysis and is considered a core component of business intelligence. Data warehouses are central repositories of integrated data from one or more disparate sources. They store current and historical data in one single place that are used for creating analytical reports for workers throughout the enterprise. This is beneficial for companies as it enables them to interrogate and draw insights from their data and make decisions.

The data stored in the warehouse is uploaded from the operational systems (such as marketing or sales). The data may pass through an operational data store and may require data cleansing for additional operations to ensure data quality before it is used in the data warehouse for reporting.

Extract, transform, load (ETL) and extract, load, transform (ELT) are the two main approaches used to build a data warehouse system.

Hadoop distributed file system

The Hadoop distributed file system (HDFS) is a distributed, scalable, and portable file system written in Java for the Hadoop framework. Some consider it to instead be a data store due to its lack of POSIX compliance, but it does provide shell commands and Java application programming interface (API) methods that are similar to other file systems. A Hadoop instance is divided into HDFS and MapReduce. HDFS is used for storing the data and MapReduce is used for processing data.

HBase

HBase is an open-source non-relational distributed database

Use Apache HBase when you need random, realtime read/write access to your Big Data. This project’s goal is the hosting of very large tables – billions of rows X millions of columns – atop clusters of commodity hardware.

Apache HBase is an open-source, NoSQL, distributed big data store. It enables random, strictly consistent, real-time access to petabytes of data.

HBase is a column-oriented, non-relational database. This means that data is stored in individual columns, and indexed by a unique row key.