System Design Interview – An insider's guide - Alex Xu
Refs:
CHAPTER 1: SCALE FROM ZERO TO MILLIONS OF USERS
Single server setup
Database
Which databases to use?
Vertical scaling vs horizontal scaling
Load balancer
Database replication
Cache
Cache tier
Considerations for using cache
Вот несколько соображений касательно использования систем кеширования.
- Decide when to use cache (Определитесь с тем, когда будет использоваться кэш)
Это лучше делать в ситуациях, когда чтение данных происходит часто, а изменение — редко. Поскольку кэшированные данные хранятся в энергозависимой памяти, сервер кеширования не подходит для постоянного хранения. Например, если он перезапустится, все данные, хранившиеся в памяти, будут утрачены. В связи с этим данные необходимо записывать в постоянные хранилища. - Expiration policy (Выбор срока действия)
Рекомендуется реализовать механизм, ограничивающий срок действия кэша. Просроченные данные немедленно удаляются. Если такого механизма нет, данные будут храниться в памяти постоянно. Срок действия лучше не делать слишком коротким, иначе система будет слишком часто обновлять данные, загружая их из БД. С другой стороны, из-за слишком длинного срока действия данные могут оказаться неактуальными. - Consistency (Согласованность)
Это подразумевает синхронизацию данных в хранилище и кэше. Несогласованность может возникнуть из-за того, что операции изменения данных в хранилище и кэше выполняются не за одну транзакцию. При масштабировании системы в пределах нескольких регионов может быть непросто поддерживать согласованность. Подробнее об этом можно почитать в документе Scaling Memcache at Facebook, опубликованном Facebook [7]. - Mitigating failures (Предотвращение сбоев)
Наличие лишь одного сервера кэширования может оказаться потенциальной единой точкой отказа (single point of failure, SPOF), которая, согласно английской Википедии, имеет следующее определение: «Единая точка отказа — это компонент, выход из строя которого приводит к прекращению работы всей системы» [8]. В связи с этим, чтобы избежать SPOF, рекомендуется использовать несколько серверов кэширования, размещенных в разных центрах обработки данных (ЦОД). А еще можно выделить какой-нибудь дополнительный объем памяти: это создаст буфер на случай, если память начнет использоваться более активно. - Eviction Policy (Политика вытеснения)
Когда кэш полностью заполнен, любой запрос на добавление новых элементов может привести к удалению существующих. Это называют вытеснением кэша. Самой популярной политикой считается вытеснение давно неиспользуемых данных (least-recently-used, LRU). Для разных ситуаций могут также подойти вытеснение наименее часто используемых данных (least-frequently-used, LFU) или метод «первым пришел, первым ушел» (FIFO, first-in-first-out).
Content delivery network (CDN)
Considerations of using a CDN
Stateless web tier
Now it is time to consider scaling the web tier horizontally. For this, we need to move state (for instance user session data) out of the web tier. A good practice is to store session data in the persistent storage such as relational database or NoSQL. Each web server in the cluster can access state data from databases. This is called stateless web tier.
Stateful architecture
The issue is that every request from the same client must be routed to the same server. This can be done with sticky sessions in most load balancers [10]; however, this adds the overhead. Adding or removing servers is much more difficult with this approach. It is also challenging to handle server failures.
Data centers
Для реализации архитектуры с несколькими центрами обработки данных необходимо решить несколько технических вопросов.
- Traffic redirection (Перенаправление трафика)
Необходимы эффективные инструменты для направления трафика к подходящему ЦОД. GeoDNS позволяет выбирать центр обработки данных, который находится ближе всего к пользователю. - Data synchronization (Синхронизация данных)
Пользователи могут работать с разными локальными базами данных и кэшами в зависимости от региона. В случае сбоя трафик может быть перенаправлен к ЦОД, в котором нет запрашиваемых данных. Распространенным решением является репликация данных между несколькими ЦОД. В одном из исследований показано, как Netflix реализует асинхронную репликацию между разными центрами обработки данных [11]. - Test and deployment (Тесты и развертывание)
В конфигурации с несколькими ЦОД тестирование веб-сайта/приложения необходимо проводить в разных местах. Автоматические средства развертывания.
Message queue
Logging, metrics, automation
Adding message queues and different tools
Database scaling
Vertical scaling
Horizontal scaling
Sharding (Шардинг) позволяет разделить крупные наборы данных на более мелкие и простые в использовании части, которые называют shards (шардами). Все шарды имеют одну и ту же схему, но каждый из них хранит уникальные данные.
При реализации стратегии сегментирования самый важный фактор — это выбор ключа. Sharding key (partition key, ключ шардинга, ключ раздела) состоит из одного или нескольких столбцов, на основе которых происходит распределение данных.
Шардинг отлично подходит для масштабирования баз данных, но это далеко не идеальное решение. Оно усложняет систему и создает дополнительные трудности.
- Resharding data (Повторное сегментирование данных)
Это может понадобиться, когда 1) отдельный шард полностью заполняется из-за стремительного развития системы или 2) некоторые шарды заполняются быстрее других из-за неравномерного распределения данных. В такой ситуации необходимо обновить функцию сегментирования и переместить имеющиеся данные. Для решения этой проблемы зачастую применяют согласованное хеширование, которое описано в главе 5. Масштабирование от нуля до миллионов пользователей - Celebrity problem (Проблема знаменитостей)
Слишком частое обращение к определенному шарду может вызвать перегрузку сервера. Представьте, что информация о Кэтти Перри, Джастине Бибере и Леди Гаге очутилась в одном и том же сегменте. Если речь идет о социальных приложениях, этот сегмент будет перегружен операциями чтения. Для решения этой проблемы, возможно, придется выделить по отдельному шарду для каждой знаменитости. Может случиться так, что каждый сегмент потребует дальнейшего разделения. - Join and de-normalization (Соединение и денормализация)
После сегментирования базы данных между несколькими серверами становится сложно выполнять операции соединения, охватывающие несколько шардов. Распространенное решение состоит в денормализации базы данных таким образом, чтобы запросы могли выполняться в рамках одной таблицы.
Millions of users and beyond
Summary of how we scale our system to support millions of users:
- Keep web tier stateless
- Build redundancy at every tier
- Cache data as much as you can
- Support multiple data centers
- Host static assets in CDN
- Scale your data tier by sharding
- Split tiers into individual services
- Monitor your system and use automation tools
CHAPTER 2: BACK-OF-THE-ENVELOPE ESTIMATION
The following concepts should be well understood:
- power of two [2]
- latency numbers
- availability numbers
Power of two
Latency numbers every programmer should know
Availability numbers
Example: Estimate Twitter QPS and storage requirements
Tips
CHAPTER 3: A FRAMEWORK FOR SYSTEM DESIGN INTERVIEWS
Step 1 - Understand the problem and establish design scope
Step 2 - Propose high-level design and get buy-in
Step 3 - Design deep dive
Step 4 - Wrap up
Time allocation on each step
CHAPTER 4: DESIGN A RATE LIMITER
Step 1 - Understand the problem and establish design scope
Here is a summary of the requirements for the system:
- Accurately limit excessive requests.
- Low latency. The rate limiter should not slow down HTTP response time.
- Use as little memory as possible.
- Distributed rate limiting. The rate limiter can be shared across multiple servers or processes.
- Exception handling. Show clear exceptions to users when their requests are throttled.
- High fault tolerance. If there are any problems with the rate limiter (for example, a cache server goes offline), it does not affect the entire system.
Step 2 - Propose high-level design and get buy-in
Algorithms for rate limiting
Ограничение трафика может быть реализовано с помощью разных алгоритмов, у каждого из которых есть определенные преимущества и недостатки. Эта глава посвящена другим темам, но чтобы выбрать алгоритм или сочетание алгоритмов, которые подходят для ваших задач, не помешает иметь о них общее представление. Вот список популярных вариантов:
- token bucket (алгоритм маркерной корзины);
- leaking bucket (алгоритм дырявого ведра);
- fixed window counter (счетчик фиксированных интервалов);
- sliding window log (журнал скользящих интервалов);
- sliding window counter (счетчик скользящих интервалов).
Step 3 - Design deep dive
Rate limiter in a distributed environment
Building a rate limiter that works in a single server environment is not difficult. However, scaling the system to support multiple servers and concurrent threads is a different story. There are two challenges:
- Race condition
- Synchronization issue
Performance optimization
Monitoring
Step 4 - Wrap up
CHAPTER 5: DESIGN CONSISTENT HASHING
The rehashing problem
Consistent hashing
- Hash scope
- Hash ring
- Hash servers
- Virtual hash servers
CHAPTER 6: DESIGN A KEY-VALUE STORE
Understand the problem and establish design scope
key-value store that comprises of the following characteristics:
- The size of a key-value pair is small: less than 10 KB.
- Ability to store big data.
- High availability: The system responds quickly, even during failures.
- High scalability: The system can be scaled to support large data set.
- Automatic scaling: The addition/deletion of servers should be automatic based on traffic.
- Tunable consistency.
- Low latency.
Single server key-value store
Distributed key-value store
CAP theorem
Теорема CAP гласит, что распределенная система может обеспечивать не больше двух из следующих трех свойств: согласованность, доступность и устойчивость к секционированию. Дадим несколько определений.
- Consistency (Согласованность)
Означает, что все клиенты одновременно видят одни и те же данные, к какому бы узлу они ни подключились. - Availability (Доступность)
Означает, что любой клиент, запрашивающий данные, получает ответ, даже если некоторые из узлов недоступны. - Partition Tolerance (Устойчивость к секционированию)
Секционирование свидетельствует о нарушении связи между двумя узлами. Устойчивость к секционированию означает, что система продолжает работать вопреки нарушению связи в сети.
System components
Core components and techniques used to build a key-value store:
- Data partition
- Data replication
- Consistency
- Inconsistency resolution
- Handling failures
- System architecture diagram
- Write path
- Read path
Data partition
- Automatic scaling (Автоматическое масштабирование)
Серверы можно добавлять и удалять автоматически в зависимости от загрузки. - Heterogeneity (Гетерогенность)
Количество виртуальных узлов сервера пропорционально его емкости. Например, серверам с большей емкостью назначают больше виртуальных узлов.
Consistency models
Модель согласованности — еще один важный фактор, который следует учитывать при проектировании хранилища типа «ключ–значение». Она определяет степень согласованности данных и имеет широкий спектр разновидностей.
- Strong consistency (Строгая согласованность)
Любая операция чтения возвращает значение, соответствующее результату самой последней операции записи. Клиент всегда получает актуальные данные. - Weak consistency (Слабая согласованность)
Последующие операции чтения могут и не вернуть самое последнее значение. - Eventual consistency (Согласованность в конечном счете)
Это разновидность слабой согласованности. Рано или поздно все обновления распространятся.
CHAPTER 7: DESIGN A UNIQUE ID GENERATOR IN DISTRIBUTED SYSTEMS
Step 1 - Understand the problem and establish design scope
Multi-master replication
However, this strategy has some major drawbacks:
- Hard to scale with multiple data centers
- IDs do not go up with time across multiple servers.
- It does not scale well when a server is added or removed.
UUID
Pros:
- Generating UUID is simple. No coordination between servers is needed so there will not be any synchronization issues.
- The system is easy to scale because each web server is responsible for generating IDs they consume. ID generator can easily scale with web servers.
Cons:
- IDs are 128 bits long, but our requirement is 64 bits.
- IDs do not go up with time.
- IDs could be non-numeric.
Ticket Server
Pros:
- Numeric IDs.
- It is easy to implement, and it works for small to medium-scale applications.
Cons:
- Single point of failure. Single ticket server means if the ticket server goes down, all systems that depend on it will face issues. To avoid a single point of failure, we can set up multiple ticket servers. However, this will introduce new challenges such as data synchronization.
Step 2 - Propose high-level design and get buy-in
Multiple options can be used to generate unique IDs in distributed systems. The options we considered are:
- Multi-master replication
- Universally unique identifier (UUID)
- Ticket server
- Twitter snowflake approach
Step 3 - Design deep dive
Step 4 - Wrap up
NTP - Network Time Protocol
CHAPTER 8: DESIGN A URL SHORTENER
Step 1 - Understand the problem and establish design scope
Step 2 - Propose high-level design and get buy-in
Step 3 - Design deep dive
We will explore two types of hash functions for a URL shortener. The first one is hash + collision resolution, and the second one is base 62 conversion.
Comparison of the two approaches
| Хеш + разрешение конфликтов | Преобразование base62 |
|---|---|
| Фиксированная длина сокращенного URL-адреса | Сокращенный URL-адрес имеет переменную длину, которая увеличивается вместе с ID |
| Не требует генератора уникальных ID | Этот подход использует генератор уникальных ID |
| Возможны конфликты, которые нужно разрешать | Конфликты исключены, так как ID уникальные |
| Невозможно определить, каким будет следующий сокращенный URL-адрес, так как он не зависит от ID | Если ID всегда инкрементируется на 1, можно легко определить следующий доступный URL-адрес. Это может стать угрозой безопасности |