ключевых вывода
1. Масштабирование систем от нуля до миллионов пользователей
Создать систему, способную обслуживать миллионы пользователей — задача непростая, требующая постоянной доработки и бесконечного совершенствования.
Начинайте с малого, масштабируйтесь постепенно. Построение системы для миллионов пользователей начинается с простой архитектуры на одном сервере, где размещаются все компоненты — веб-приложение, база данных и кэш. По мере роста аудитории система эволюционирует, применяя продуманные методы масштабирования.
Основные техники масштабирования. Переход от одного сервера к крупномасштабной системе включает несколько ключевых этапов:
- разделение веб-слоя и слоя данных для независимого масштабирования;
- горизонтальное масштабирование за счёт добавления серверов в пул ресурсов;
- внедрение балансировщиков нагрузки для равномерного распределения трафика;
- репликация базы данных для отказоустойчивости и резервирования;
- добавление слоя кэша для ускорения отклика и снижения нагрузки на базу;
- использование CDN для эффективной доставки статического контента.
Отсутствие состояния и мультидатацентры. Горизонтальное масштабирование требует, чтобы веб-слой был без состояния — данные сессий пользователей хранятся в постоянном хранилище. Поддержка нескольких датацентров повышает доступность и улучшает опыт пользователей в разных регионах. Очереди сообщений отделяют компоненты системы, позволяя им масштабироваться независимо и повышая устойчивость к сбоям.
2. Прикидочные оценки для проектирования систем
Прикидочные расчёты — это оценки, основанные на мысленных экспериментах и типичных показателях производительности, которые помогают понять, какие решения удовлетворят ваши требования.
Значение оценок. На интервью по проектированию систем прикидочные оценки играют ключевую роль для оценки ёмкости и производительности. Они помогают определить, насколько реализуемы разные варианты дизайна и выявить узкие места. Важно владеть базовыми понятиями масштабируемости: степенями двойки, показателями задержек и уровнем доступности.
Ключевые понятия и цифры. Необходимо знать:
- единицы измерения объёмов данных с использованием степеней двойки (КБ, МБ, ГБ, ТБ, ПБ);
- типичные показатели задержек операций (доступ к памяти, поиск на диске, передача по сети);
- показатели доступности и соответствующее время простоя (99%, 99.9%, 99.99%).
Советы и методы оценки. Эффективные прикидочные расчёты включают:
- округление и упрощение для удобства вычислений;
- запись предположений для ясности и последующего анализа;
- обозначение единиц измерения, чтобы избежать путаницы;
- практику типичных оценок, таких как QPS, пиковый QPS, требования к хранилищу и кэшу.
3. Структурированный подход к интервью по проектированию систем
Интервью по проектированию систем моделирует реальную работу, где два коллеги совместно решают неоднозначную задачу и находят решение, соответствующее их целям.
Суть совместной работы. Интервью не сводится к поиску «правильного» ответа, а демонстрирует навыки решения проблем, коммуникации и умение работать в команде. Процесс включает анализ расплывчатой задачи, предложение решений, обоснование выбора и конструктивное реагирование на обратную связь.
Четырёхэтапный процесс. Структурированный подход состоит из:
- Понимания задачи и определения рамок дизайна.
- Предложения высокоуровневого решения и согласования с интервьюером.
- Глубокого погружения в отдельные компоненты.
- Завершения с обсуждением вопросов и возможных улучшений.
Ключевые навыки и моменты. Для успеха важно:
- задавать уточняющие вопросы для понимания требований;
- работать с интервьюером как с партнёром;
- предлагать несколько вариантов и оценивать компромиссы;
- выявлять узкие места и предлагать улучшения;
- чётко и понятно излагать ход мыслей.
4. Проектирование надёжного ограничителя скорости
В сетевой системе ограничитель скорости контролирует интенсивность трафика, отправляемого клиентом или сервисом.
Зачем нужен ограничитель скорости. Он необходим для контроля трафика, предотвращения истощения ресурсов, снижения затрат и защиты серверов от перегрузок. Ограничитель лимитирует число запросов клиента за определённый период, блокируя избыточные вызовы.
Способы реализации. Ограничители могут работать на стороне клиента, сервера или как промежуточный компонент. Серверные и промежуточные решения надёжнее, так как клиентские можно обойти злоумышленникам. API-шлюзы часто включают функции ограничения скорости в свой набор сервисов.
Алгоритмы ограничения скорости. Распространённые алгоритмы:
- «ведро с токенами»: допускает всплески трафика при сохранении среднего уровня;
- «протекающее ведро»: обрабатывает запросы с фиксированной скоростью, подходит для стабильного потока;
- счётчик фиксированного окна: простой, но может пропускать больше запросов на границах окна;
- журнал скользящего окна: точный, но требует много памяти;
- счётчик скользящего окна: гибридный подход, балансирующий точность и использование памяти.
5. Консистентное хеширование для распределённых систем
Консистентное хеширование — особый вид хеширования, при котором при изменении размера хеш-таблицы в среднем требуется переназначить лишь k/n ключей, где k — число ключей, а n — число слотов.
Решение проблемы перераспределения. Традиционные методы хеширования приводят к значительной перераспределённости при добавлении или удалении серверов, что вызывает промахи кэша и ухудшение производительности. Консистентное хеширование минимизирует этот эффект, переназначая лишь небольшую часть ключей.
Хеш-пространство и кольцо. Консистентное хеширование отображает серверы и ключи на кольце с равномерно распределённой хеш-функцией. Чтобы определить сервер для ключа, движутся по часовой стрелке от позиции ключа до ближайшего сервера.
Виртуальные узлы и улучшенное распределение. Для решения проблем неравномерного распределения и разного размера партиций применяются виртуальные узлы (реплики). Каждый сервер представлен несколькими виртуальными узлами на кольце, что обеспечивает более сбалансированное распределение ключей и снижает стандартное отклонение.
6. Создание масштабируемого хранилища ключ-значение
Хранилище ключ-значение, или key-value база данных, — это нереляционная база данных.
Основы хранилища ключ-значение. Такие базы хранят данные в виде пар ключ-значение, обеспечивая высокую масштабируемость и низкую задержку. Они подходят для приложений, требующих быстрого доступа к данным без сложных связей.
Теорема CAP и модели согласованности. При проектировании распределённого хранилища важно понимать теорему CAP, которая утверждает, что система может одновременно гарантировать только две из трёх характеристик: согласованность, доступность и устойчивость к разделению. Модели согласованности (сильная, слабая, конечная) определяют степень согласованности данных.
Ключевые компоненты и методы. Важные элементы и техники:
- партиционирование данных с помощью консистентного хеширования;
- репликация для высокой доступности и надёжности;
- консенсус кворума для обеспечения согласованности при чтении и записи;
- версионирование и векторные часы для разрешения конфликтов;
- обнаружение и устранение сбоев с помощью протокола сплетен и отложенной передачи.
7. Генерация уникальных идентификаторов в распределённых системах
В этой главе рассматривается задача проектирования генератора уникальных ID в распределённых системах.
Сложности генерации ID. Традиционные автоинкременты в базах данных не подходят для распределённых систем из-за проблем масштабируемости и упорядочивания по времени. Требования к уникальным ID включают уникальность, сортируемость, числовой формат и укладку в 64-битное представление.
Подходы к генерации уникальных ID. Существуют разные методы:
- мульти-мастер репликация: использует автоинкремент, но страдает от проблем масштабируемости и порядка;
- UUID: простой, но генерирует 128-битные нечисловые идентификаторы;
- сервер билетов: централизованный автоинкремент, но создаёт единую точку отказа;
- подход Twitter Snowflake: делит ID на части для временной метки, ID датацентра, машины и последовательности.
Подход Twitter Snowflake. 64-битный ID разбивается на 41 бит для временной метки, 5 бит для ID датацентра, 5 бит для ID машины и 12 бит для последовательного номера. Такой дизайн обеспечивает уникальность, сортируемость и масштабируемость.
8. Проектирование и реализация сервиса сокращения URL
В этой главе мы рассмотрим классическую задачу интервью по проектированию систем: создание сервиса сокращения URL, подобного tinyurl.
Основные функции и дизайн API. Сервис сокращения URL преобразует длинные ссылки в короткие алиасы для удобного обмена и отслеживания. Основные API:
- сокращение URL: принимает длинный URL и возвращает короткий;
- перенаправление URL: принимает короткий URL и перенаправляет на исходный.
Перенаправление и HTTP-коды. Перенаправление реализуется с помощью кодов 301 (постоянное) или 302 (временное). 301 снижает нагрузку на сервер за счёт кэширования в браузере, 302 позволяет отслеживать клики и источники.
Дизайн хеш-функции. Хеш-функция отображает длинный URL в короткий алиас. Два распространённых подхода:
- хеш + разрешение коллизий: используется CRC32, MD5 или SHA-1, при коллизиях добавляется дополнительная строка;
- конвертация в систему счисления с основанием 62: преобразование уникального ID в строку из символов [0-9, a-z, A-Z].
9. Архитектура и методы веб-краулера
В этой главе мы сосредоточимся на проектировании веб-краулера — интересной и классической задаче интервью по системному дизайну.
Основы веб-краулера. Веб-краулер (паук) находит новый или обновлённый контент в интернете, переходя по ссылкам на страницах. Он используется для индексирования поисковыми системами, архивирования, веб-майнинга и мониторинга.
Ключевые компоненты и рабочий процесс. Веб-краулер обычно включает:
- стартовые URL (seed URLs) для начала обхода;
- очередь URL для загрузки;
- загрузчик HTML-страниц;
- DNS-резолвер для преобразования URL в IP;
- парсер контента для анализа и проверки HTML;
- модуль обнаружения дубликатов;
- извлекатель URL из страниц;
- фильтр URL для исключения нежелательного контента;
- трекер посещённых URL;
- хранилище посещённых URL.
Вежливость и приоритизация URL. Хорошо спроектированный краулер должен быть вежливым — не перегружать сайты частыми запросами, и приоритизировать URL по полезности. Очередь URL управляет вежливостью, распределяя загрузочные потоки по хостам и приоритизируя URL на основе PageRank, трафика и частоты обновлений.
10. Проектирование масштабируемой системы уведомлений
Система уведомлений стала важной функцией для многих приложений в последние годы.
Обзор системы уведомлений. Система оповещает пользователей важной информацией через push-уведомления на мобильные устройства, SMS и электронную почту. Для многих приложений это критически важная функция, требующая масштабируемости и надёжности.
Типы уведомлений и сторонние сервисы. Разные типы уведомлений используют разные сервисы:
- push-уведомления iOS: Apple Push Notification Service (APNS);
- push-уведомления Android: Firebase Cloud Messaging (FCM);
- SMS: сторонние сервисы, например Twilio или Nexmo;
- email: коммерческие сервисы, такие как Sendgrid или Mailchimp.
Архитектура и компоненты системы. Масштабируемая система уведомлений включает:
- API-серверы для приёма запросов на отправку уведомлений;
- кэш для хранения информации о пользователях, устройствах и шаблонах уведомлений;
- базу данных для хранения данных о пользователях, уведомлениях и настройках;
- очереди сообщений для разделения компонентов и буферизации событий;
- воркеры, которые извлекают события из очередей и отправляют их в сторонние сервисы.
11. Архитектура и дизайн системы новостной ленты
В этой главе вам предстоит спроектировать систему новостной ленты.
Основы системы новостной ленты. Система агрегирует и отображает контент от друзей, страниц и групп, на которые подписан пользователь. Ключевые функции — публикация ленты и построение новостной ленты.
Модели публикации и распространения. Публикация ленты включает запись данных в кэш и базу, а также наполнение новостной ленты. Модели распространения:
- push-модель (fanout on write): лента формируется при записи, обеспечивает быструю выдачу, но может создавать «горячие» ключи;
- pull-модель (fanout on read): лента формируется при чтении, экономит ресурсы для неактивных пользователей, но замедляет выдачу.
Гибридный подход и получение ленты. Гибридный метод сочетает push и pull: push для большинства пользователей, pull — для знаменитостей и пользователей с большим числом подписчиков. Получение ленты включает извлечение ID новостей из кэша и формирование полной ленты с объектами пользователей и постов.
12. Проектирование системы чата в реальном времени
В этой главе мы рассмотрим проектирование системы чата.
Основы системы чата. Система обеспечивает общение пользователей в реальном времени, поддерживая личные и групповые чаты. Важные функции — индикаторы онлайн-статуса, поддержка нескольких устройств и push-уведомления.
Протоколы связи и основные компоненты. Связь между клиентами и серверами может реализовываться разными протоколами:
- опрос (polling): клиент периодически запрашивает новые сообщения;
- длинный опрос (long polling): клиент держит соединение открытым до появления новых сообщений или таймаута;
- WebSocket: обеспечивает двунаправленное и постоянное соединение.
Архитектура и хранение данных. Система чата обычно включает:
- бессостояные сервисы для управления входом, регистрацией и профилями;
- состояные сервисы для обработки сообщений в реальном времени и поддержания соединений;
- интеграцию с третьими сторонами для push-уведомлений;
- хранилища ключ-значение для истории чата.
Последнее обновление:
FAQ
What's "System Design Interview – An Insider's Guide" about?
- Comprehensive Guide: The book by Alex Xu is a detailed guide to mastering system design interviews, which are a crucial part of technical interviews for software engineering roles.
- Interview Preparation: It provides strategies, frameworks, and examples to help candidates prepare for and excel in system design interviews.
- Real-World Applications: The book covers real-world system design problems, offering insights into how large-scale systems are built and scaled.
- Step-by-Step Approach: It includes a step-by-step framework for tackling system design questions, making it accessible for both beginners and experienced engineers.
Why should I read "System Design Interview – An Insider's Guide"?
- Improve Interview Skills: The book is essential for anyone looking to improve their performance in system design interviews, which are common in tech companies.
- Gain Practical Knowledge: It offers practical knowledge and examples that can be applied to real-world system design challenges.
- Learn from an Expert: Written by Alex Xu, an experienced software engineer, the book provides insider insights into the system design process.
- Structured Learning: The book's structured approach helps readers systematically build their understanding and skills in system design.
What are the key takeaways of "System Design Interview – An Insider's Guide"?
- Framework for Interviews: The book provides a reliable framework for approaching system design questions, emphasizing the importance of understanding requirements and constraints.
- Scalability and Reliability: It highlights techniques for building scalable and reliable systems, such as load balancing, caching, and database sharding.
- Real-World Examples: Readers gain insights from real-world examples, such as designing a URL shortener, a chat system, and a notification system.
- Continuous Learning: The book encourages continuous learning and practice, emphasizing that mastering system design is an ongoing process.
What are the best quotes from "System Design Interview – An Insider's Guide" and what do they mean?
- "Designing a system that supports millions of users is challenging, and it is a journey that requires continuous refinement and endless improvement." This quote emphasizes the iterative nature of system design and the need for ongoing optimization.
- "The system design interview simulates real-life problem solving where two co-workers collaborate on an ambiguous problem and come up with a solution that meets their goals." It highlights the collaborative and open-ended nature of system design interviews.
- "There is neither the right answer nor the best answer." This quote underscores the idea that system design is about trade-offs and finding a solution that best fits the given constraints and requirements.
How does Alex Xu suggest approaching system design interviews?
- Understand the Problem: Start by thoroughly understanding the problem and clarifying requirements and constraints with the interviewer.
- High-Level Design: Propose a high-level design and get buy-in from the interviewer, focusing on key components and their interactions.
- Deep Dive: Dive deeper into specific components, discussing trade-offs, optimizations, and potential bottlenecks.
- Wrap Up: Conclude by discussing potential improvements, error handling, and scalability considerations.
What is the "Scale from Zero to Millions of Users" chapter about?
- Scaling Journey: This chapter guides readers through the process of scaling a system from a single user to millions, highlighting key techniques and considerations.
- Single Server Setup: It starts with a simple single server setup and gradually introduces concepts like load balancing, caching, and database replication.
- Horizontal vs. Vertical Scaling: The chapter explains the differences between vertical and horizontal scaling and why horizontal scaling is often preferred for large-scale systems.
- Redundancy and Failover: It emphasizes the importance of building redundancy and failover mechanisms to ensure high availability and reliability.
What is the "Back-of-the-Envelope Estimation" chapter about?
- Estimation Techniques: This chapter teaches readers how to perform quick, rough estimations of system capacity and performance requirements.
- Scalability Basics: It covers essential concepts like the power of two, latency numbers, and availability percentages to help with estimations.
- Practical Examples: The chapter includes practical examples, such as estimating Twitter's QPS and storage requirements, to illustrate the estimation process.
- Problem-Solving Focus: It emphasizes that the estimation process is more about problem-solving and understanding trade-offs than obtaining precise results.
What is the "A Framework for System Design Interviews" chapter about?
- 4-Step Process: The chapter introduces a 4-step process for effective system design interviews: understanding the problem, proposing a high-level design, diving deep into specifics, and wrapping up.
- Collaboration and Communication: It highlights the importance of collaboration and communication with the interviewer throughout the process.
- Avoiding Pitfalls: The chapter warns against common pitfalls like over-engineering and jumping to solutions without understanding the problem.
- Time Management: It provides guidance on managing time effectively during the interview to cover all necessary aspects of the design.
What is the "Design a Rate Limiter" chapter about?
- Rate Limiting Basics: This chapter explains the concept of rate limiting, which is used to control the rate of traffic sent by a client or service.
- Algorithms: It covers different algorithms for implementing rate limiting, such as token bucket, leaking bucket, and sliding window.
- High-Level Architecture: The chapter provides a high-level architecture for a rate limiter, including considerations for distributed environments.
- Practical Applications: It discusses practical applications of rate limiting, such as preventing DoS attacks and reducing server load.
What is the "Design Consistent Hashing" chapter about?
- Consistent Hashing Concept: This chapter introduces consistent hashing, a technique used to distribute requests/data efficiently across servers.
- Rehashing Problem: It explains the rehashing problem and how consistent hashing mitigates it by minimizing key redistribution when servers are added or removed.
- Virtual Nodes: The chapter discusses the use of virtual nodes to achieve balanced data distribution and improve scalability.
- Real-World Use Cases: It highlights real-world use cases of consistent hashing, such as in Amazon's Dynamo database and Apache Cassandra.
What is the "Design a Key-Value Store" chapter about?
- Key-Value Store Basics: This chapter covers the design of a key-value store, a non-relational database that stores data as key-value pairs.
- CAP Theorem: It explains the CAP theorem and its implications for distributed systems, focusing on consistency, availability, and partition tolerance.
- System Components: The chapter discusses key components of a distributed key-value store, such as data partitioning, replication, and consistency models.
- Inconsistency Resolution: It covers techniques for resolving inconsistencies, such as versioning and vector clocks, to ensure data integrity.
What is the "Design a Unique ID Generator in Distributed Systems" chapter about?
- Unique ID Requirements: This chapter addresses the challenge of generating unique IDs in distributed systems, focusing on uniqueness, order, and scalability.
- Approaches: It explores different approaches, such as multi-master replication, UUIDs, ticket servers, and Twitter's Snowflake.
- Snowflake Approach: The chapter provides a detailed explanation of the Snowflake approach, which divides IDs into sections for timestamp, datacenter ID, machine ID, and sequence number.
- Design Considerations: It discusses design considerations like clock synchronization, section length tuning, and high availability.
Отзывы
«System Design Interview – An insider's guide» вызывает смешанные отзывы. Многие хвалят книгу за практические примеры и системный подход к задачам проектирования систем, отмечая её полезность при подготовке к собеседованиям. Читатели ценят ясные объяснения и реальные сценарии из жизни. Однако некоторые критикуют недостаток глубины, упрощение сложных тем и редкие опечатки. В целом, книга воспринимается как хороший старт для знакомства с концепциями проектирования систем, но часто советуют дополнять её более подробными источниками для полного понимания.
Similar Books
