Обзор книги “System Design Interview: An Insider’s Guide” — Part 1

Рис.1 “Обложка книги”
Рис.2 “Содержание книги”

1. Scale from zero to millions of users

В этой главе автор начинает с рассмотрения размещения системы на одном сервере и рассказывает про

2. Back-of-the-envelope estimation

Эта глава совсем мала, так как в ней автор приводит всего три таблички и один пример приблизительного расчета нагрузки на Twitter в виде query per second и storage, необходимого для хранения твитов и медиа.

3. A framework for system design interviews

В этой главе автор рассказывает про фреймворк для прохождения System Design Interview. Подробнее я рассказывал про него в предыдущей статье, ну а здесь я просто приведу иллюстрацию с четырьмя шагами этого фреймворка.

Рис.3 “Four step process for effective system design interview”

4. Design a rate limiter

В этой главе автор предлагает спроектировать rate limiter. Это система, которая позволяет ограничить количество внешних запросов на ваши системы или наоборот вам ограничить количество исходящих запросов. В любом случае система предназначена для того, чтобы ограничить количество запросов каким-то лимитом. Для решения этой задачи есть целый ряд алгоритмов

Рис.4 “Design of rate limiter”

5. Design consistent hashing

В этой главе автор рассказывает про один из consistent hashing — популярных механизмов для реализации горизонтального масштабирования посредством распределения запросов/данных равномерно по набору серверов. В wikipedia consistent hashing определяется так

Рис.5 “Example of consistent hashing from Datastax Cassandra documentation”

6. Design a key-value store

В этой главе автор разбирает как спроектировать распределенное key-value хранилище, которое поддерживает 2 операции:

Рис.6 “Infamous CAP”
  • CP — система предпочитает не обслуживать часть запросов пользователей, но сохранять консистентность данных
  • AP — система ослабляет требования к консистентности, чтобы продолжать обслуживать запросы пользователей
Рис.7 “Consistency Model”
Рис.8 “Tunable consistency”
Рис.9 “Failure detection”
Рис.10 “Anti-entropy mechanisms”
Рис.11 “LSM component structure”

7. Design a unique id generator in distributed systems

В этой главе автор предлагает спроектировать решение для генерации уникальных идентификаторов. Конкретно автор фиксирует такие требования к решению

Multi-master replication

Используем опцию auto_increment внутри баз данных, но делаем k серверов баз данных и делаем так, чтобы они генерировали ID следующим образом

Universally unique identifier (UUID)

Согласно Wikipedia

Рис.12 “UUID record layout”

Ticket server

Суть этого подхода в том, чтобы централизовать функцию генерации id в одном сервисе, к которому будут обращаться все остальные за получением уникальных идентификаторов.

Twitter snowflake approach

Этот подход к созданию идентификаторов анонсировал Twitter в далеком 2010 году в свое блоге. В Twitter этот подход используется для идентификаторов твитов. Про устройство формата можно прочитать и в Wikipedia — настолько он популярен. Вот как выглядит структура snowflake id

Рис.13 “Components of a snowflake identifier in binary

P.S.

На этом эта статья заканчивается, а в следующей мы рассматриваем вторую часть книги и конкретно те задачи, которые действительно тянут на отдельные задачи в рамках System Design Interview.

--

--

Director of digital ecosystem development department at Tinkoff. Bachelor at applied math, Master at system analysis, Postgraduate studies at economics.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Alexander Polomodov

Alexander Polomodov

Director of digital ecosystem development department at Tinkoff. Bachelor at applied math, Master at system analysis, Postgraduate studies at economics.