A senior engineer’s perspective on building highly available distributed systems Таблица контента Введение: Почему Dynamo изменил все Теорема о торговле CAP Core Architecture Components Consistent Hashing for Partitioning Replication Strategy (N, R, W) Vector Clocks for Versioning Sloppy Quorum and Hinted Handoff Решение конфликтов: проблема корзины покупок Читать и писать Flow Меркель деревья для антиэнтропии Членство и обнаружение неудач Характеристики: Реальные цифры Разделение стратегии эволюции Сравнение Dynamo с современными системами Что вам не даст Динамо Пример практической реализации Ключевые уроки системного дизайна Когда нельзя использовать системы Dynamo-Style Заключение Приложение: Проблемы и подходы к проектированию Это долгосрочная ссылка — каждый раздел стоит сам по себе, поэтому не стесняйтесь перепрыгивать прямо к тому, что наиболее актуально для вас. Это долгосрочная ссылка — каждый раздел стоит сам по себе, поэтому не стесняйтесь перепрыгивать прямо к тому, что наиболее актуально для вас. Введение: Почему Dynamo изменил все Когда Amazon опубликовал статью Dynamo в 2007 году, это было не просто еще одним академическим упражнением. Это было проверенным решением реальных проблем в огромном масштабе.Я помню, когда я впервые прочитал эту статью — это фундаментально изменило то, как я думал о распределенных системах. Он был разработан для поддержки услуг Amazon с высоким уровнем трафика, таких как системы управления корзиной покупок и сеансами. Нет вторичных индексов, нет связей, нет семантики отношений — только ключи и ценности, с крайним акцентом на доступность и масштабируемость. Он не обеспечивает линейность или глобальные гарантии заказа, даже при самых высоких настройках кворума. Dynamo is a distributed key-value storage system. Основная проблема, с которой сталкивался Amazon, была простой в заявлении, но жестокой в решении: Когда кто-то пытается добавить товар в свою корзину покупок во время сетевого раздела или сбоя сервера, отказ от этого письма недопустим. How do you build a storage system that never says “no” to customers? Теорема согласования CAP: почему Dynamo выбирает доступность Перед тем, как погрузиться в то, как работает Dynamo, вам нужно понять фундаментальные ограничения, вокруг которых он разработан. Что такое теорема CAP? Теорема CAP описывает фундаментальный компромисс в распределенных системах: когда происходит сетевой раздел, вы должны выбрать между последовательностью и доступностью. Консистенция (C): все узлы видят одни и те же данные одновременно Доступность (A): каждый запрос получает ответ (успех или неудача) Толерантность разделов (P): система продолжает работать, несмотря на сетевые сбои Распространенная аббревиатура - «выберите 2 из 3», но это чрезмерное упрощение.На практике сетевые разделы неизбежны по масштабу, поэтому реальное решение: Это и есть реальный выбор дизайна. when partitions occur (and they will), do you sacrifice consistency or availability? : Сетевые разделы произойдут. Кабели отрезаются, переключатели не удаются, центры обработки данных теряют подключение. Вы не можете избежать их, поэтому вы должны выбрать: последовательность или доступность? The harsh reality Традиционные базы данных выбирают последовательность : Traditional approach Database: "I can't guarantee all replicas are consistent, so I'll reject your write to be safe." Result: Customer sees error, cart is empty Impact: Lost revenue, poor experience Dynamo выбирает доступность : Dynamo’s approach Dynamo: "I'll accept your write with the replicas I can reach. The unreachable replica will catch up later." Result: Customer sees success, item in cart Impact: Sale continues, happy customer Торговля визуализирована When a partition occurs: Traditional Database: Choose C over A → Sacrifice Availability - ✓ All replicas always have same data - ✓ No conflicts to resolve - ❌ Rejects writes during failures - ❌ Poor customer experience - ❌ Lost revenue Dynamo: Choose A over C → Sacrifice Strong Consistency - ✓ Accepts writes even during failures - ✓ Excellent customer experience - ✓ No lost revenue - ❌ Replicas might temporarily disagree - ❌ Application must handle conflicts Реальный пример Amazon: торговая корзина Черной пятницы Представьте, что это Чёрная пятница. Миллионы клиентов совершают покупки. : With traditional database Time: 10:00 AM - Network partition occurs Result: - All shopping cart writes fail - "Service Unavailable" errors - Customers can't checkout - Twitter explodes with complaints - Estimated lost revenue: $100,000+ per minute : With Dynamo Time: 10:00 AM - Network partition occurs Result: - Shopping cart writes continue - Customers see success - Some carts might have conflicts (rare) - Application merges conflicting versions - Estimated lost revenue: $0 - A few edge cases need conflict resolution (acceptable) Почему этот выбор имеет смысл для электронной коммерции Amazon сделал математику: Стоимость отклонения письма: немедленная потеря продаж ($50-200) Стоимость принятия противоречивого письма: Время от времени приходится сливать корзины для покупок (редко случается, легко фиксируется) Бизнес-решение: принимайте письма, справляйтесь с редкими конфликтами : Types of data where Availability > Consistency Торговые корзины (слияние противоречивых дополнений) Данные сеанса (последняя запись-победа в порядке) Пользовательские предпочтения (возможное соответствие приемлемо) Списки лучших продавцов (приблизительно хорошо) : Types of data where Consistency > Availability Балансы банковских счетов (не могут иметь противоречивых балансов) Счет инвентаризации (не может быть перепродан) Дневник транзакций (должен быть заказан) Вот почему Dynamo не для всех, но для случаев использования электронной коммерции Amazon выбор доступности над сильной последовательностью был правильным компромиссом. Важный нюанс: Хотя Dynamo часто описывается как система AP, точнее называть ее системой регулируемой консистенции.В зависимости от вашей конфигурации кворума R и W, она может вести себя ближе к CP. Этикетка AP относится к ее по умолчанию / рекомендуемой конфигурации, оптимизированной для рабочих нагрузок электронной коммерции. В то время как Dynamo часто описывается как система AP, точнее называть ее В зависимости от вашей конфигурации кворума R и W он может вести себя ближе к CP. Этикетка AP применяется к его по умолчанию/рекомендуемой конфигурации, оптимизированной для рабочих нагрузок электронной коммерции. Important nuance tunable consistency system Основные архитектурные компоненты 1. последовательное хаширование для разделения Позвольте мне объяснить это конкретным примером, потому что последовательное хаширование является одним из тех понятий, которые кажутся магическими, пока вы не увидите его в действии. Проблема: традиционное хаширование на основе хаширования Представьте, что у вас есть 3 сервера и вы хотите распространять данные по ним. # Traditional approach - DON'T DO THIS def get_server(key, num_servers): hash_value = hash(key) return hash_value % num_servers # Modulo operation # With 3 servers: get_server("user_123", 3) # Returns server 0 get_server("user_456", 3) # Returns server 1 get_server("user_789", 3) # Returns server 2 Это работает... пока вы не добавите или не удалите сервер. Посмотрим, что происходит, когда мы переходим от 3 до 4 серверов: # Before (3 servers): "user_123" → hash % 3 = 0 → Server 0 "user_456" → hash % 3 = 1 → Server 1 "user_789" → hash % 3 = 2 → Server 2 # After (4 servers): "user_123" → hash % 4 = 0 → Server 0 ✓ (stayed) "user_456" → hash % 4 = 1 → Server 1 ✓ (stayed) "user_789" → hash % 4 = 2 → Server 2 ✓ (stayed) # But wait - this is lucky! In reality, most keys MOVE: "product_ABC" → hash % 3 = 2 → Server 2 "product_ABC" → hash % 4 = 3 → Server 3 ✗ (MOVED!) : Когда вы меняете количество серверов, почти все ваши данные должны быть перераспределены. The disaster Решение: последовательный хашинг Последовательное хаширование решает эту проблему, обращаясь к хашируемому пространству как к кругу (от 0 до 2^32 – 1, оборачивая вокруг). Step 1: Place servers on the ring Каждому серверу присваивается случайная позиция на кольце (называемая «токеном»). Step 2: Place data on the ring Когда вы хотите хранить данные, вы: Хеш ключ, чтобы получить позицию на кольце Ходить по часовой дорожке с этого положения Хранить данные на первом сервере, с которым вы сталкиваетесь Визуальный пример: полное кольцо Вот кольцо, выложенное в порядке.Ключи ходят по часовой стрелке к следующему серверу: Ключ движется по часовой стрелке, пока не ударит по серверу. Simple rule : Examples user_123 при 30° → ходит до 45° → Server A владеет ею user_456 при 150° → ходит до 200° → Server C владеет им cart_789 при 250° → ходит до 280° → Сервер D владеет им product_ABC при 300° → проходит через 360°, обворачивается до 0°, продолжается до 45° → Сервер А владеет им Who owns what range? Сервер A (45°): владеет всем от 281° до 45° (окружается) Сервер B (120°): владеет всем от 46° до 120° Сервер C (200°): владеет всем от 121° до 200° Сервер D (280°): владеет всем от 201° до 280° Магия: добавление сервера Теперь давайте посмотрим, почему это блестяще. Мы добавляем сервер E на позиции 160°: BEFORE: Server A (45°) → owns 281°-45° Server B (120°) → owns 46°-120° Server C (200°) → owns 121°-200° ← THIS RANGE WILL SPLIT Server D (280°) → owns 201°-280° AFTER: Server A (45°) → owns 281°-45° ← NO CHANGE Server B (120°) → owns 46°-120° ← NO CHANGE Server E (160°) → owns 121°-160° ← NEW! Takes part of C's range Server C (200°) → owns 161°-200° ← SMALLER range Server D (280°) → owns 201°-280° ← NO CHANGE : Перемещать нужно только ключи в диапазоне 121°-160° (от C до E).Серверы A, B и D полностью не затронуты! Result Оптимизация виртуальных узлов Существует критическая проблема с базовым последовательным хашированием: . random distribution can be extremely uneven The Problem in Detail: Когда вы случайно назначаете одну позицию на сервер, вы, по сути, бросаете дартсы на круглую доску.Иногда дартсы скопируются вместе, иногда они распространяются. Позвольте показать вам конкретный пример: Scenario: 4 servers with single random tokens Server A: 10° } Server B: 25° } ← Only 75° apart! Tiny ranges Server C: 100° } Server D: 280° ← 180° away from C! Huge range Range sizes: - Server A owns: 281° to 10° = 89° (25% of ring) - Server B owns: 11° to 25° = 14° (4% of ring) ← Underutilized! - Server C owns: 26° to 100° = 74° (21% of ring) - Server D owns: 101° to 280° = 179° (50% of ring) ← Overloaded! Real-world consequences: Неравномерная нагрузка: сервер D обрабатывает 50% всех данных, в то время как сервер B обрабатывает только 4%. Процессор, диск и сеть сервера D максимально удалены Сервер B в основном не работает (трата мощности) Ваша 99.9-я процентильная задержка доминирует из-за перегрузки сервера D Каскад Hotspot: Когда сервер D становится медленным или не работает: Все его 50% загрузки переходят на сервер А (следующий в часовом направлении) Сервер A становится перегруженным Производительность системы катастрофически ухудшается Неэффективное масштабирование: добавление серверов не помогает равномерно, потому что новые серверы могут приземляться в уже небольших диапазонах Visualizing the problem: Каждый физический сервер получает несколько виртуальных позиций (токены). Dynamo’s solution Instead of one dart throw per server, throw many darts. The more throws, the more even the distribution becomes (law of large numbers). How Virtual Nodes Fix the Problem: Let’s take the same 4 servers, but now each server gets 3 virtual nodes (tokens) instead of 1: Physical Server A gets 3 tokens: 10°, 95°, 270° Physical Server B gets 3 tokens: 25°, 180°, 310° Physical Server C gets 3 tokens: 55°, 150°, 320° Physical Server D gets 3 tokens: 75°, 200°, 340° Now the ring looks like: 10° A, 25° B, 55° C, 75° D, 95° A, 150° C, 180° B, 200° D, 270° A, 310° B, 320° C, 340° D Range sizes (approximately): - Server A total: 15° + 55° + 40° = 110° (31% of ring) - Server B total: 30° + 20° + 30° = 80° (22% of ring) - Server C total: 20° + 30° + 20° = 70° (19% of ring) - Server D total: 20° + 70° + 20° = 110° (31% of ring) Load ranges from 19% to 31% instead of 4% to 50%. Much better! Why this works: : With more samples (tokens), the random distribution averages out. This is the law of large numbers in action. Statistics : When a server fails, its load is distributed across many servers, not just one neighbor: Granular load distribution Server A fails: - Its token at 10° → load shifts to Server B's token at 25° - Its token at 95° → load shifts to Server C's token at 150° - Its token at 270° → load shifts to Server B's token at 310° Result: The load is spread across multiple servers! : When adding a new server with 3 tokens, it steals small amounts from many servers instead of a huge chunk from one server. Smooth scaling Real Dynamo configurations: The paper mentions different strategies evolved over time. In production: Early versions: 100-200 virtual nodes per physical server Later optimized to: Q/S tokens per node (where Q = total partitions, S = number of servers) Типичная настройка: каждый физический сервер может иметь 128-256 виртуальных узлов The Trade-off: Balance vs Overhead More virtual nodes means better load distribution, but there’s a cost. What you gain with more virtual nodes: With 1 token per server (4 servers): Load variance: 4% to 50% (±46% difference) ❌ With 3 tokens per server (12 virtual nodes): Load variance: 19% to 31% (±12% difference) ✓ With 128 tokens per server (512 virtual nodes): Load variance: 24% to 26% (±2% difference) ✓✓ What it costs: Размер метаданных: каждый узел поддерживает информацию о маршрутизации 1 токен на сервер: отслеживайте 4 записи 128 tokens per server: Track 512 entries Gossip overhead: Nodes периодически обмениваются информацией о членстве More tokens = more data to sync between nodes Каждую секунду узлы шутят о своем взгляде на кольцо Сложность ребалансирования: когда узлы присоединяются/выходят Больше виртуальных узлов = больше переносов разделов для координации Но каждая передача меньше (что на самом деле хорошо для загрузки) Dynamo’s evolution: The paper describes how Amazon optimized this over time: Strategy 1 (Initial): - 100-200 random tokens per server - Problem: Huge metadata (multiple MB per node) - Problem: Slow bootstrapping (had to scan for specific key ranges) Strategy 3 (Current): - Q/S tokens per server (Q=total partitions, S=number of servers) - Equal-sized partitions - Example: 1024 partitions / 8 servers = 128 tokens per server - Benefit: Metadata reduced to KB - Benefit: Fast bootstrapping (transfer whole partition files) Real production sweet spot: Most Dynamo deployments use 128-256 virtual nodes per physical server. This achieves: Распределение нагрузки в пределах 10-15% вариации (достаточно хорошо) Объем метаданных менее 100 КБ на узел (незначительный) Быстрое восстановление неисправностей (загрузка распространяется по многим узлам) Diminishing returns. Going from 128 to 512 tokens only improves load balance by 2-3%, but doubles metadata size and gossip traffic. Why not more? : Physical servers (top) map to multiple virtual positions (bottom) on the ring. This distributes each server’s load across different parts of the hash space. Key concept : Benefits More even load distribution When a server fails, its load is distributed across many servers (not just one neighbor) Когда сервер присоединяется, он крадет небольшое количество с многих серверов Real-World Impact Comparison Let’s see the difference with real numbers: Traditional Hashing (3 servers → 4 servers): - Keys that need to move: ~75% (3 out of 4) - Example: 1 million keys → 750,000 keys must migrate Consistent Hashing (3 servers → 4 servers): - Keys that need to move: ~25% (1 out of 4) - Example: 1 million keys → 250,000 keys must migrate With Virtual Nodes (150 vnodes total → 200 vnodes): - Keys that need to move: ~12.5% (spread evenly) - Example: 1 million keys → 125,000 keys must migrate - Load is balanced across all servers The “Aha!” Moment The key insight is this: Consistent hashing decouples the hash space from the number of servers. Traditional: ← num_servers is in the formula! server = hash(key) % num_servers Consistent: ← num_servers isn’t in the formula! server = ring.findNextClockwise(hash(key)) Именно поэтому добавление/удаление серверов влияет только на небольшую часть данных.Хеш-значения не изменяются — только тот сервер, который «владеет», который диапазон изменяется, и только локально. Think of it like a circular running track with water stations (servers). If you add a new water station, runners only change stations if they’re between the old nearest station and the new one. Everyone else keeps going to their same station. Стратегия репликации (N, R, W) The Problem: Availability vs Consistency Trade-off Представьте, что вы строите корзину покупок Amazon. Клиент добавляет товар в свою корзину, но в этот момент: One server is being rebooted for maintenance Другой сервер имеет сетевой хиккуп Третий сервер идеально подходит (с высокой степенью консистенции): Traditional database approach Client: "Add this item to my cart" Database: "I need ALL replicas to confirm before I say yes" Server 1: ✗ (rebooting) Server 2: ✗ (network issue) Server 3: ✓ (healthy) Result: "Sorry, service unavailable. Try again later." : 😡 “I can’t add items to my cart during Black Friday?!” Customer experience This is unacceptable for e-commerce. Every rejected write is lost revenue. Решение Dynamo: Tunable Quorums Dynamo gives you three knobs to tune the exact trade-off you want: N: Количество копий (количество копий данных) Кворум чтения (колько реплик нужно ответить для успешного чтения) : Write quorum (how many replicas must acknowledge for a successful write) W : когда , вы гарантируете перекрытие кворума — это означает, что хотя бы один узел, который получил запись, будет запрошен во время любого чтения. Это перекрытие позволяет обнаружить последнюю версию, при условии, что логика примирения правильно идентифицирует самые высокие векторные часы. The magic formula R + W > N Позвольте мне показать вам, почему это важно с реальными сценариями: Scenario 1: Shopping Cart (Prioritize Availability) N = 3 # Three replicas for durability R = 1 # Read from any single healthy node W = 1 # Write to any single healthy node # Trade-off analysis: # ✓ Writes succeed even if 2 out of 3 nodes are down # ✓ Reads succeed even if 2 out of 3 nodes are down # ✓ Maximum availability - never reject customer actions # ✗ Might read stale data # ✗ Higher chance of conflicts (but we can merge shopping carts) What happens during failure: Client: "Add item to cart" Coordinator tries N=3 nodes: - Node 1: ✗ Down - Node 2: ✓ ACK (W=1 satisfied!) - Node 3: Still waiting... Result: SUCCESS returned to client immediately Node 3 eventually gets the update (eventual consistency) Scenario 2: Session State (Balanced Approach) N = 3 R = 2 # Must read from 2 nodes W = 2 # Must write to 2 nodes # Trade-off analysis: # ✓ R + W = 4 > N = 3 → Read-your-writes guaranteed # ✓ Tolerates 1 node failure # ✓ Good balance of consistency and availability # ✗ Write fails if 2 nodes are down # ✗ Read fails if 2 nodes are down Why R + W > N enables read-your-writes: Write to W=2 nodes: [A, B] Later, read from R=2 nodes: [B, C] Because W + R = 4 > N = 3, there's guaranteed overlap! At least one node (B in this case) will have the latest data. The coordinator detects the newest version by comparing vector clocks. This guarantees seeing the latest write as long as reconciliation picks the causally most-recent version correctly. Scenario 3: Financial Data (Prioritize Consistency) N = 3 R = 3 # Must read from ALL nodes W = 3 # Must write to ALL nodes # Trade-off analysis: # ✓ Full replica quorum — reduces likelihood of divergent versions # ✓ Any read will overlap every write quorum # ✗ Write fails if ANY node is down # ✗ Read fails if ANY node is down # ✗ Poor availability during failures Системы, требующие строгих транзакционных гарантий, обычно выбирают системы CP. Эта конфигурация технически поддерживается Dynamo, но жертвует свойствами доступности, которые мотивируют его использование в первую очередь. Конфигурация таблицы сравнения Config N R W Availability Consistency Use Case High Availability 3 1 1 ⭐⭐⭐⭐⭐ ⭐⭐ Shopping cart, wish list Balanced 3 2 2 ⭐⭐⭐⭐ ⭐⭐⭐⭐ Session state, user preferences Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ High-stakes reads (not linearizable) Read-Heavy 3 1 3 ⭐⭐⭐ (reads) ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ (writes) ⭐⭐⭐ Click tracking, metrics High Availability 3 1 1 ⭐⭐⭐⭐⭐ ⭐⭐ Торговая корзина, список желаний Balanced 3 2 2 ⭐⭐⭐⭐ ⭐⭐⭐⭐ Состояние сеанса, предпочтения пользователя Full Quorum 3 3 3 ⭐⭐ ⭐⭐⭐⭐⭐ Высокие ставки (не линейные) Read-Heavy 3 1 3 ⭐⭐⭐⭐ Product catalog, CDN metadata Write-Heavy 3 3 1 ⭐⭐⭐ Click tracking, metrics Примечание о финансовых системах: Системы, требующие сильных транзакционных гарантий (например, балансы банковских счетов), обычно не должны использовать Dynamo. : Systems requiring strong transactional guarantees (e.g., bank account balances) typically shouldn’t use Dynamo. That said, some financial systems do build on Dynamo-style storage for their persistence layer while enforcing stronger semantics at the application or business logic layer. Note on financial systems Ключевое понимание Большинство систем используют Потому что: N=3, R=2, W=2 : Can tolerate up to 2 replica failures before permanent data loss (assuming independent failures and no correlated outages). Durability Доступность: допускает 1 сбой узла для чтения и написания Консистенция: R + W > N гарантирует, что кворумы чтения и письма перекрываются, позволяя читать-писать поведение при отсутствии одновременных записей. : Don’t wait for the slowest node (only need 2 out of 3) Performance Real production numbers from the paper: Amazon’s shopping cart service during peak (holiday season): Configuration: N=3, R=2, W=2 Handled tens of millions of requests Более 3 миллионов чеков за один день No downtime, even with server failures Этот настраиваемый подход сделал Dynamo революционным. Вы не застряли в одноразмерном подходе — вы настраиваете его на основе ваших реальных потребностей в бизнесе. Векторные часы для версий The Problem: Detecting Causality in Distributed Systems Когда несколько узлов могут принимать письма самостоятельно, нужно ответить на критический вопрос: Are these two versions of the same data related, or were they created concurrently? Why timestamps don’t work: Scenario: Two users edit the same shopping cart simultaneously User 1 at 10:00:01.500 AM: Adds item A → Writes to Node X User 2 at 10:00:01.501 AM: Adds item B → Writes to Node Y Physical timestamp says: User 2's version is "newer" Reality: These are concurrent! Both should be kept! Problem: - Clocks on different servers are NEVER perfectly synchronized - Clock skew can be seconds or even minutes - Network delays are unpredictable - Physical time doesn't capture causality What we really need to know: Version A happened before Version B? → B can overwrite A Version A and B are concurrent? → Keep both, merge later Version A came from reading Version B? → We can track this! The Solution: Vector Clocks A vector clock is a simple data structure: a list of pairs that tracks which nodes have seen which versions. (node_id, counter) The rules: When a node writes data, it increments its own counter Когда узел читает данные, он получает векторные часы When comparing two vector clocks: Если все счетчики в A ≤ счетчики в B → A является предком B (B является новейшим) If some counters in A > B and some B > A → A and B are concurrent (conflict!) Step-by-Step Example Let’s trace a shopping cart through multiple updates: Breaking down the conflict: D3: [Sx:2, Sy:1] vs D4: [Sx:2, Sz:1] Comparing: - Sx: 2 == 2 ✓ (equal) - Sy: 1 vs missing in D4 → D3 has something D4 doesn't - Sz: missing in D3 vs 1 → D4 has something D3 doesn't Conclusion: CONCURRENT! Neither is an ancestor of the other. Both versions must be kept and merged. Real-World Characteristics Эти цифры отражают конкретную нагрузку Amazon — высокое соотношение чтения и письма, в основном однопользовательские сеансы — и не следует считать обобщенными для всех развертываний Dynamo: 99.94% - Single version (no conflict) 0.00057% - 2 versions 0.00047% - 3 versions 0.00009% - 4 versions Конфликты на практике встречаются редко! Key insight Why conflicts happen: Not usually from network failures В основном от одновременных авторов (часто автоматизированные процессы / боты) Люди редко создают конфликты, потому что они медленны по сравнению со скоростью сети. The Size Problem Vector clocks can grow unbounded if many nodes coordinate writes. Dynamo’s solution: once the clock exceeds a size threshold. truncate the oldest entries // When vector clock exceeds threshold (e.g., 10 entries) // Remove the oldest entry based on wall-clock timestamp vectorClock = { 'Sx': {counter: 5, timestamp: 1609459200}, 'Sy': {counter: 3, timestamp: 1609459800}, 'Sz': {counter: 2, timestamp: 1609460400}, // ... 10 more entries } // If size > 10, remove entry with oldest timestamp // ⚠ Risk: Dropping an entry collapses causality information. // Two versions that were causally related may now appear // concurrent, forcing the application to resolve a conflict // that didn't actually exist. In practice, Amazon reports // this has not been a significant problem — but it is a // real theoretical risk in high-churn write environments // with many distinct coordinators. Sloppy Quorum и Hinted Handoff Проблема: строгие кворумы убивают доступность Traditional quorum systems are rigid and unforgiving. Traditional strict quorum: Your data is stored on nodes: A, B, C (preference list) Write requirement: W = 2 Scenario: Node B is down for maintenance Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✓ Result: SUCCESS (got 2 out of 3) Scenario: Nodes B AND C are down Coordinator: "I need to write to 2 nodes from {A, B, C}" Tries: A ✓, B ✗ (down), C ✗ (down) Result: FAILURE (only got 1 out of 3) Customer: "Why can't I add items to my cart?!" 😡 The problem: . If those specific nodes are down, the system becomes unavailable. Strict quorums require specific nodes Real scenario at Amazon: Black Friday, 2:00 PM - Datacenter 1: 20% of nodes being rebooted (rolling deployment) - Datacenter 2: Network hiccup (1-2% packet loss) - Traffic: 10x normal load With strict quorum: - 15% of write requests fail - Customer support phones explode - Revenue impact: Millions per hour Название: Sloppy Quorum Dynamo расслабляет требование кворума: “Write to the first N healthy nodes in the preference list, walking further down the ring if needed.” Preference list for key K: A, B, C But B is down... Sloppy Quorum says: "Don't give up! Walk further down the ring: A, B, C, D, E, F, ..." Coordinator walks until N=3 healthy nodes are found: A, C, D (D is a temporary substitute for B) Как работает Handoff Когда узел временно заменяет неудачный узел, он сохраняет «наводку» с данными. Подробный процесс Handoff Step 1: Detect failure and substitute def write_with_hinted_handoff(key, value, N, W): preference_list = get_preference_list(key) # [A, B, C] healthy_nodes = [] for node in preference_list: if is_healthy(node): healthy_nodes.append((node, is_hint=False)) # If we don't have N healthy nodes, expand the list if len(healthy_nodes) < N: extended_list = get_extended_preference_list(key) for node in extended_list: if node not in preference_list and is_healthy(node): healthy_nodes.append((node, is_hint=True)) if len(healthy_nodes) >= N: break # Write to first N healthy nodes acks = 0 for node, is_hint in healthy_nodes[:N]: if is_hint: # Store with hint metadata intended_node = find_intended_node(preference_list, node) success = node.write_hinted(key, value, hint=intended_node) else: success = node.write(key, value) if success: acks += 1 if acks >= W: return SUCCESS return FAILURE Step 2: Background hint transfer # Runs periodically on each node (e.g., every 10 seconds) def transfer_hints(): hints_db = get_hinted_replicas() for hint in hints_db: intended_node = hint.intended_for if is_healthy(intended_node): try: intended_node.write(hint.key, hint.value) hints_db.delete(hint) log(f"Successfully transferred hint to {intended_node}") except: log(f"Will retry later for {intended_node}") Why This Is Brilliant Durability maintained: Even though B is down: - We still have N=3 copies: A, C, D - Data won't be lost even if another node fails - System maintains durability guarantee Availability maximized: Client perspective: - Write succeeds immediately - No error message - No retry needed - Customer happy Traditional quorum would have failed: - Only 2 nodes available (A, C) - Need 3 for N=3 - Write rejected - Customer sees error Eventual consistency: Timeline: T=0: Write succeeds (A, C, D with hint) T=0-5min: B is down, but system works fine T=5min: B recovers T=5min+10sec: D detects B is back, transfers hint T=5min+11sec: B has the data, D deletes hint Result: Eventually, all correct replicas have the data Configuration Example // High availability configuration const config = { N: 3, // Want 3 replicas W: 2, // Only need 2 ACKs to succeed R: 2, // Read from 2 nodes // Sloppy quorum allows expanding preference list sloppy_quorum: true, // How far to expand when looking for healthy nodes max_extended_preference_list: 10, // How often to check for hint transfers hint_transfer_interval: 10_seconds, // How long to keep trying to transfer hints hint_retention: 7_days }; Реальный мировой эффект Из опыта производства Amazon: During normal operation: Hinted handoff rarely triggered Most writes go to preferred nodes Hints database is mostly empty During failures: Scenario: 5% of nodes failing at any time (normal at Amazon's scale) Without hinted handoff: - Write success rate: 85% - Customer impact: 15% of cart additions fail With hinted handoff: - Write success rate: 99.9%+ - Customer impact: Nearly zero During datacenter failure: Scenario: Entire datacenter unreachable (33% of nodes) Without hinted handoff: - Many keys would lose entire preference list - Massive write failures - System effectively down With hinted handoff: - Writes redirect to other datacenters - Hints accumulate temporarily - When datacenter recovers, hints transfer - Zero customer-visible failures The Trade-off Benefits: Максимальная письменная доступность ✓ Durability maintained during failures ✓ Automatic recovery when nodes come back ✓ No manual intervention required Costs: Временное несоответствие (данные не на «правильных» узлах) Дополнительное хранилище для базы данных Hints Пропускная способность фонового диапазона для передачи указаний Немного более сложный код Hinted handoff обеспечивает временную долговечность, а не постоянное воспроизведение.Если замещающий узел (например, D) потерпит неудачу, прежде чем он сможет передать свой намек обратно в B, число истинных реплик упадет ниже N, пока ситуация не будет решена. Преимущества доступности значительно превышают затраты на рабочие нагрузки электронной коммерции. Amazon’s verdict: Conflict Resolution: The Shopping Cart Problem Let’s talk about the most famous example from the paper: the shopping cart. This is where rubber meets road. What Is a Conflict (and Why Does It Happen)? A occurs when two writes happen to the same key on different nodes, without either write “knowing about” the other. This is only possible because Dynamo accepts writes even when nodes can’t communicate—which is the whole point! conflict Вот конкретная последовательность событий, которые создают конфликт: Timeline: T=0: Customer logs in. Cart has {shoes} on all 3 nodes. T=1: Network partition: Node1 can't talk to Node2. T=2: Customer adds {jacket} on their laptop → goes to Node1. Cart on Node1: {shoes, jacket} ← Vector clock: [N1:2] T=3: Customer adds {hat} on their phone → goes to Node2. Cart on Node2: {shoes, hat} ← Vector clock: [N2:2] T=4: Network heals. Node1 and Node2 compare notes. Node1 says: "I have version [N1:2]" Node2 says: "I have version [N2:2]" Neither clock dominates the other → CONFLICT! Neither version is “wrong”—both represent real actions the customer took. Dynamo’s job is to detect this situation (via vector clocks) and surface к заявлению, чтобы заявление могло решить, что делать. both versions What Does the Application Do With a Conflict? Вот ключевая часть, которую документ делегирует вам: . Dynamo gives you all the concurrent versions; your code decides how to merge them. the application must resolve conflicts using business logic Для корзины покупок Amazon выбрала : keep all items from all concurrent versions. The rationale is simple—losing an item from a customer’s cart (missing a sale) is worse than occasionally showing a stale item they already deleted. union merge Conflict versions: Version A (from Node1): {shoes, jacket} Version B (from Node2): {shoes, hat} Merge strategy: union Merged cart: {shoes, jacket, hat} ← All items preserved Вот настоящий код примирения: from __future__ import annotations from dataclasses import dataclass, field class VectorClock: def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def merge(self, other: "VectorClock") -> "VectorClock": """Merged clock = max of each node's counter across both versions.""" all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" @dataclass class ShoppingCart: items: list[str] = field(default_factory=list) vector_clock: VectorClock = field(default_factory=VectorClock) @staticmethod def reconcile(carts: list["ShoppingCart"]) -> "ShoppingCart": if len(carts) == 1: return carts[0] # No conflict, nothing to do # Merge strategy: union of all items (never lose additions). # This is Amazon's choice for shopping carts. # A different application might choose last-write-wins or something else. all_items: set[str] = set() merged_clock = VectorClock() for cart in carts: all_items.update(cart.items) # Union: keep everything merged_clock = merged_clock.merge(cart.vector_clock) return ShoppingCart(items=sorted(all_items), vector_clock=merged_clock) # Example conflict scenario cart1 = ShoppingCart(items=["shoes", "jacket"], vector_clock=VectorClock({"N1": 2})) cart2 = ShoppingCart(items=["shoes", "hat"], vector_clock=VectorClock({"N2": 2})) # Dynamo detected a conflict and passes both versions to our reconcile() reconciled = ShoppingCart.reconcile([cart1, cart2]) print(reconciled.items) # ['hat', 'jacket', 'shoes'] — union! The Deletion Problem (Why This Gets Tricky) The union strategy has a nasty edge case: . deleted items can come back from the dead T=0: Cart: {shoes, hat} T=1: Customer removes hat → Cart: {shoes} Clock: [N1:3] T=2: Network partition — Node2 still has old state T=3: Some concurrent write to Node2 Clock: [N2:3] T=4: Network heals → conflict detected T=5: Union merge: {shoes} ∪ {shoes, hat} = {shoes, hat} Result: Hat is BACK! Customer removed it, but it reappeared. Amazon explicitly accepts this trade-off. A “ghost” item in a cart is a minor annoyance. Losing a cart addition during a Black Friday sale is lost revenue. Инженерная глубина: Логика слияния должна быть специфичной для домена и тщательно спроектирована. Добавление элементов является коммутативным (порядок не имеет значения) и легко слиять. Удаление элементов не является — удаление в одном одновременном филиале может молча игнорироваться во время слияния на основе союза. Это преднамеренный компромисс в дизайне Dynamo, но это означает, что приложение должно тщательно рассуждать о добавлении против удаления семантики. Если ваши данные естественно не поддерживают слияния союза (например, счетчик, адрес пользователя), вам нужна другая стратегия — например CRDT, последняя запись-победа с временными отметками или просто отказ от совместных записей для этого типа данных Инженерная глубина: Логика слияния должна быть специфичной для домена и тщательно спроектирована. Добавление элементов является коммутативным (порядок не имеет значения) и легко слиять. Удаление элементов не является — удаление в одном одновременном филиале может молча игнорироваться во время слияния на основе союза. Это преднамеренный компромисс в дизайне Dynamo, но это означает, что приложение должно тщательно рассуждать о добавлении против удаления семантики. Если ваши данные естественно не поддерживают слияния союза (например, счетчик, адрес пользователя), вам нужна другая стратегия — например CRDT, последняя запись-победа с временными отметками или просто отказ от совместных записей для этого типа данных Read and Write Flow Вышеперечисленные диаграммы показывают поток высокого уровня, но давайте посмотрим, что на самом деле происходит шаг за шагом во время чтения и письма. Write Path Step-by-step narration of a PUT request: to any node (via a load balancer) or directly to the coordinator. Client sends the request — this is the first node in the preference list for the key’s hash position on the ring. The coordinator is determined Векторные часы обновляются — координатор увеличивает свой счетчик в векторных часах, создавая новую версию. , then fans out the write to the other N-1 nodes in the preference list simultaneously. The coordinator writes locally It does NOT wait for all N — just the first W to respond. The remaining nodes that haven’t responded yet will get the write eventually (or via hinted handoff if they’re down). The coordinator waits for W acknowledgments. Как только W ACKs прибывают, координатор возвращает 200 OK клиенту. : The client gets a success response as soon as W nodes confirm. The other (N – W) nodes will receive the write asynchronously. This is why the system is “eventually consistent”—all nodes данные, но не обязательно одновременно. Key insight about the write path Воль Читать дорогу Step-by-step narration of a GET request: Клиент отправляет запрос координатору для этого ключа. in the preference list simultaneously (not just R). This is important — it contacts all N, but only needs R to respond. The coordinator sends read requests to all N nodes The coordinator returns as soon as R nodes have replied, without waiting for the slower ones. Wait for R responses. The coordinator checks all the vector clocks: Compare the versions returned. If all versions are identical → return the single version immediately. If one version’s clock dominates the others (it’s causally “newer”) → return that version. If versions are concurrent (neither clock dominates) → return to the client, which must merge them. all versions happens in the background: if the coordinator noticed any node returned a stale version, it sends the latest version to that node to bring it up to date. Read repair Because Dynamo is a general-purpose storage engine. It doesn’t know whether you’re storing a shopping cart, a user profile, or a session token. Only знает, как объединить две противоречащие друг другу версии таким образом, что это имеет деловой смысл.Координатор передает вам сырые одновременные версии вместе с контекстом векторных часов, и вы делаете правильное для вашего случая использования. Why does the client receive the conflict instead of the coordinator resolving it? Ваше применение : когда клиент пишет объединенную версию обратно, она должна включать контекст (совместные векторные часы). Это говорит Динамо, что новая запись "видела" все одновременные версии, поэтому конфликт решен. Конкуренты пишут над еще не разрешенным конфликтом. The vector clock context is the key to closing the loop another Меркель деревья для антиэнтропии Проблема: как вы знаете, когда реплики выходят из синхронизации? После того, как узел восстанавливается от сбоя, он может пропустить некоторые записи. После того, как сетевой раздел исцеляется, две реплики могут расходиться. The brute-force approach would be: “Every hour, compare every key on Node A against Node B, and sync anything that’s different.” But at Amazon’s scale, a single node might store hundreds of millions of keys. Comparing them all one by one would be so slow and bandwidth-intensive that it would interfere with normal traffic. The core idea: instead of comparing individual keys, compare Если хеш совпадает, вся эта группа идентична — перемещайте его. Dynamo uses Merkle trees to solve this efficiently. hashes of groups of keys : Merkle tree sync is a mechanism. It’s not on the hot read/write path. Normal reads and writes use vector clocks and quorums for versioning. Merkle trees are for the repair process that runs periodically in the background to catch any inconsistencies that slipped through. Important background anti-entropy : Merkle tree sync is a mechanism. It’s not on the hot read/write path. Normal reads and writes use vector clocks and quorums for versioning. Merkle trees are for the repair process that runs periodically in the background to catch any inconsistencies that slipped through. Important background anti-entropy How a Merkle Tree Is Built Each node builds a Merkle tree over its data, organized by key ranges: contain the hash of a small range of actual data keys (e.g., hash of all values for keys k1, k2, k3). Leaf nodes Внутренние узлы содержат хаш их детей. is a single hash representing the data on the node. The root all Как два узла синхронизируются с помощью деревьев Merkle Когда Node A и Node B хотят проверить, синхронизированы ли они: : Compare root hashes. If they’re the same, everything is identical. Done! (No network traffic for the data itself.) Step 1 : If roots differ, compare their left children. Same? Skip that entire half of the key space. Step 2 : Keep descending only into subtrees where hashes differ, until you reach the leaf nodes. Step 3 : Sync only the specific keys in the differing leaf nodes. Step 4 Example: Comparing two nodes Node A root: abc789 ← differs from Node B! Node B root: abc788 Compare left subtrees: Node A left: xyz123 Node B left: xyz123 ← same! Skip entire left half. Compare right subtrees: Node A right: def456 Node B right: def457 ← differs! Go deeper. Compare right-left subtree: Node A right-left: ghi111 Node B right-left: ghi111 ← same! Skip. Compare right-right subtree: Node A right-right: jkl222 Node B right-right: jkl333 ← differs! These are leaves. → Sync only the keys in the right-right leaf range (e.g., k10, k11, k12) Instead of comparing all 1 million keys, we compared 6 hashes and synced only 3 keys! : Synchronization process in code def sync_replicas(node_a, node_b, key_range): """ Efficiently sync two nodes using Merkle trees. Instead of comparing all keys, we compare hashes top-down. Only the ranges where hashes differ need actual key-level sync. """ tree_a = node_a.get_merkle_tree(key_range) tree_b = node_b.get_merkle_tree(key_range) # Step 1: Compare root hashes first. # If they match, every key in this range is identical — nothing to do! if tree_a.root_hash == tree_b.root_hash: return # Zero data transferred — full match! # Step 2: Recursively find differences by traversing top-down. # Only descend into subtrees where hashes differ. differences = [] stack = [(tree_a.root, tree_b.root)] while stack: node_a_subtree, node_b_subtree = stack.pop() if node_a_subtree.hash == node_b_subtree.hash: continue # This whole subtree matches — skip it! if node_a_subtree.is_leaf: # Found a differing leaf — these keys need syncing differences.extend(node_a_subtree.keys) else: # Not a leaf yet — recurse into children for child_a, child_b in zip(node_a_subtree.children, node_b_subtree.children): stack.append((child_a, child_b)) # Step 3: Sync only the specific keys that differed at leaf level. # This might be a handful of keys, not millions. for key in differences: sync_key(node_a, node_b, key) Why This Is Efficient The power of Merkle trees is that the number of hash comparisons you need scales with the (Логарифмический в количестве ключей), а не в количестве самих ключей. Глубина дерева Node with 1,000,000 keys: Naive approach: Compare 1,000,000 keys individually Cost: 1,000,000 comparisons Merkle tree: Compare O(log N) hashes top-down Tree depth ≈ 20 levels Cost: 20 comparisons to find differences Then sync only the differing leaves (~few keys) Speedup: ~50,000x fewer comparisons! И критически, если два узла (which is almost always true in a healthy cluster), the root hashes often match entirely and zero data needs to be transferred. The anti-entropy process is very cheap in the common case. mostly in sync Membership and Failure Detection Dynamo использует слуховой протокол для управления членством. Каждый узел периодически обменивается информацией о членстве с случайными коллегами. Нет главного узела — вся координация полностью децентрализована. Госпитализация на основе членства Key Design Points : Каждый узел поддерживает свой собственный вид членства в кластере. Нет центрального реестра, поэтому нет единой точки сбоя для данных членства. No single coordinator : Dynamo uses an accrual-based failure detector (similar to Phi Accrual). Rather than a binary “alive/dead” judgment, nodes maintain a that rises the longer a peer is unresponsive. This avoids false positives from transient network hiccups. Failure suspicion vs. detection Уровень подозрений Node A's view of Node B: - Last heartbeat: 3 seconds ago → Suspicion low → Healthy - Last heartbeat: 15 seconds ago → Suspicion rising → Likely slow/degraded - Last heartbeat: 60 seconds ago → Suspicion high → Treat as failed : New nodes contact a seed node to join, then gossip spreads their presence to the rest of the cluster. Ring membership is eventually consistent—different nodes may have slightly different views of the ring momentarily, which is acceptable. Decentralized bootstrapping Характеристики: Реальные цифры The paper provides fascinating performance data. Let me break it down: Латентное распределение Metric | Average | 99.9th Percentile --------------------|---------|------------------ Read latency | ~10ms | ~200ms Write latency | ~15ms | ~200ms Key insight: 99.9th percentile is ~20x the average! На 99,9 процентиле влияет: Why the huge gap? Garbage collection pauses Диск I/O вариации Network jitter Неравновесие нагрузки This is why Amazon SLAs are specified at 99.9th percentile, not average. Конфликтные версии From 24 hours of Amazon’s production shopping cart traffic (per the Dynamo paper). Note these reflect Amazon’s specific workload characteristics, not a universal baseline: 99.94% - Saw exactly one version (no conflict) 0.00057% - Saw 2 versions 0.00047% - Saw 3 versions 0.00009% - Saw 4 versions Конфликты редки на практике! Чаще всего вызываются одновременными писателями (роботами), а не неудачами. Takeaway Разделение стратегии эволюции Dynamo развивался через три стратегии разделения.Эта эволюция учит нас важным урокам: Стратегия 1: Случайные токены (Inicial) Problem: Random token assignment → uneven load Problem: Adding nodes → expensive data scans Problem: Can't easily snapshot the system : Случайное назначение токенов звучит элегантно, но на практике это кошмар.Каждый узел получает случайное положение на кольце, что означает дико разные диапазоны владения данными и неравномерное распределение нагрузки. Operational lesson Стратегия 2: равные размеры разделов + случайные токены Improvement: Decouples partitioning from placement Problem: Still has load balancing issues Стратегия 3: Токены Q/S на узел — равные размеры разделов + детерминистическое размещение (текущее) What Q and S mean: = the total number of fixed partitions the ring is divided into (e.g. 1024). Think of these as equally-sized, pre-cut slices of the hash space that never change shape. Q = the number of physical servers currently in the cluster (e.g. 8). S = how many of those fixed slices each server is responsible for (e.g. 1024 / 8 = ). Q/S 128 partitions per server Ключевой сдвиг от предыдущих стратегий: кольцо теперь разделено на Q фиксированные, равные размеры разделов , and then those partitions are assigned evenly to servers. Servers no longer get random positions — they each own exactly Q/S partitions, distributed evenly around the ring. Первым Example: Q=12 partitions, S=3 servers Ring divided into 12 equal slices (each covers 30° of the 360° ring): Partition 1: 0°– 30° → Server A Partition 2: 30°– 60° → Server B Partition 3: 60°– 90° → Server C Partition 4: 90°–120° → Server A Partition 5: 120°–150° → Server B Partition 6: 150°–180° → Server C ...and so on, round-robin Each server owns exactly Q/S = 12/3 = 4 partitions → perfectly balanced. When a 4th server joins (S becomes 4): New Q/S = 12/4 = 3 partitions per server. Each existing server hands off 1 partition to the new server. Only 3 out of 12 partitions move — the rest are untouched. This evolution — from random tokens to fixed, equal-sized partitions with balanced ownership — is one of the most instructive operational learnings from Dynamo. The early approach prioritized simplicity of implementation; the later approach prioritized operational simplicity and predictability. Сравнение Dynamo с современными системами System Consistency Model Use Case Dynamo Influence Cassandra Tunable (N, R, W) Time-series, analytics Direct descendant — heavily inspired by Dynamo, uses same consistent hashing and quorum concepts Riak Tunable, vector clocks Key-value store Closest faithful Dynamo implementation Amazon DynamoDB Eventually consistent by default Managed NoSQL DynamoDB is a completely different system internally, with no vector clocks and much simpler conflict resolution. Shares the name and high-level inspiration only. ⚠️ Not the same as Dynamo! Voldemort Tunable LinkedIn's data store Open-source Dynamo implementation Google Spanner Linearizable Global SQL Opposite choice to Dynamo — prioritizes CP via TrueTime clock synchronization Redis Cluster Eventually consistent Caching, sessions Uses consistent hashing; much simpler conflict resolution Cassandra Tunable (N, R, W) Временные серии, аналитики Прямой преемник — сильно вдохновленный Dynamo, использует те же последовательные концепции хаширования и кворума Riak Векторные часы, векторные часы Key-value store Closest faithful Dynamo implementation Amazon DynamoDB В конечном счете последовательно по умолчанию Управление NoSQL DynamoDB is a completely different system internally, with no vector clocks and much simpler conflict resolution. Shares the name and high-level inspiration only. ⚠️ Not the same as Dynamo! Voldemort Тунинг Магазин данных LinkedIn Открытый исходный код Dynamo Google Spanner Линейный Глобальный SQL Opposite choice to Dynamo — prioritizes CP via TrueTime clock synchronization Redis Cluster Eventually consistent Caching, sessions Использует последовательное хаширование; гораздо более простое разрешение конфликтов : Many engineers conflate Amazon DynamoDB with the Dynamo paper. They are very different. DynamoDB is a managed service optimized for operational simplicity. It does not expose vector clocks, does not use the same partitioning scheme, and uses a proprietary consistency model. The paper is about the internal Dynamo storage engine that predates DynamoDB. The DynamoDB confusion : Многие инженеры путают Amazon DynamoDB с бумагой Dynamo. Они очень отличаются. DynamoDB - это управляемая услуга, оптимизированная для простоты работы. Она не раскрывает векторные часы, не использует одну и ту же схему разделения и использует собственную модель консистенции. The DynamoDB confusion What Dynamo Does NOT Give You Каждый блог старшего инженера должен быть честным относительно ограничений. Нет транзакций: операции выполняются только с одним ключом. Вы не можете атомно обновлять несколько ключей. Нет вторичных индексов: Вы можете искать данные только по их первичному ключу (по крайней мере, в первоначальном дизайне). : It’s a key-value store. There is no query language. No joins : Events across different keys have no guaranteed ordering. No global ordering Нет линейности: Даже при R=W=N, Dynamo не обеспечивает линейные показания. : The system detects conflicts and surfaces them to the application. The must resolve them. If your engineers don’t understand this, you will have subtle data bugs. No automatic conflict resolution application Стоимость ремонта в масштабе: Процесс антиэнтропии (примирение дерева Меркле) не бесплатный. Рост векторных часов: В средах с большим количеством координат, векторные часы могут вырастать достаточно крупными, чтобы требовать отрезания, что вводит потенциальную потерю причинности. Понимание этих ограничений имеет решающее значение для успешной эксплуатации систем в стиле Dynamo в производстве. Пример практической реализации Below is a self-contained Python implementation of the core Dynamo concepts. It’s intentionally simplified—no actual networking, no persistence—but it faithfully models how vector clocks, the consistent hash ring, quorum reads/writes, and conflict detection interact. Each component is explained before its code. Часть 1: Векторные часы ТЭ class - это основа отслеживания версий. это просто словарь Две ключевые операции: VectorClock node_id → counter — bump our own counter when we write increment(node) — check if one clock is causally “after” another; if neither dominates, the writes were concurrent (conflict) dominates(other) from __future__ import annotations from dataclasses import dataclass, field from typing import Optional class VectorClock: """ Tracks causality across distributed writes. A clock like {"nodeA": 2, "nodeB": 1} means: - nodeA has coordinated 2 writes - nodeB has coordinated 1 write - Any version with these counters has "seen" those writes """ def __init__(self, clock: dict[str, int] | None = None): self.clock: dict[str, int] = clock.copy() if clock else {} def increment(self, node_id: str) -> "VectorClock": """Return a new clock with node_id's counter bumped by 1.""" new_clock = self.clock.copy() new_clock[node_id] = new_clock.get(node_id, 0) + 1 return VectorClock(new_clock) def dominates(self, other: "VectorClock") -> bool: """ Returns True if self is causally AFTER other. self dominates other when: - Every counter in self is >= the same counter in other, AND - At least one counter in self is strictly greater. Meaning: self has seen everything other has seen, plus more. """ all_keys = set(self.clock) | set(other.clock) at_least_one_greater = False for key in all_keys: self_val = self.clock.get(key, 0) other_val = other.clock.get(key, 0) if self_val < other_val: return False # self is missing something other has seen if self_val > other_val: at_least_one_greater = True return at_least_one_greater def merge(self, other: "VectorClock") -> "VectorClock": """ Merge two clocks by taking the max of each counter. Used after resolving a conflict to produce a new clock that has "seen" everything both conflicting versions saw. """ all_keys = set(self.clock) | set(other.clock) merged = {k: max(self.clock.get(k, 0), other.clock.get(k, 0)) for k in all_keys} return VectorClock(merged) def __repr__(self): return f"VectorClock({self.clock})" Part 2: Versioned Value Каждое значение, хранящееся в Dynamo, обернуто его векторными часами.Это сочетание позволяет координатору сравнивать версии во время чтения и обнаруживать конфликты. @dataclass class VersionedValue: """ A value paired with its causal history (vector clock). When a client reads, they get back a VersionedValue. When they write an update, they must include the context (the vector clock they read) so Dynamo knows what version they're building on top of. """ value: object vector_clock: VectorClock def __repr__(self): return f"VersionedValue(value={self.value!r}, clock={self.vector_clock})" Часть 3: Симулированный узел In real Dynamo each node is a separate process. Here we simulate them as in-memory objects. The key detail: each node has its own local Ноды могут быть обозначены как Для симуляции неудач. storage down class DynamoNode: """ Simulates a single Dynamo storage node. In production this would be a separate server with disk storage. Here it's an in-memory dict so we can demo the logic without networking. """ def __init__(self, node_id: str, token: int): self.node_id = node_id self.token = token # Position on the consistent hash ring self.storage: dict[str, list[VersionedValue]] = {} self.down = False # Toggle to simulate node failures def write(self, key: str, versioned_value: VersionedValue) -> bool: """ Store a versioned value. Returns False if the node is down. We store a LIST of versions per key, because a node might hold multiple concurrent (conflicting) versions until they are resolved by the application. """ if self.down: return False # In a real node this would be written to disk (e.g. BerkeleyDB) self.storage[key] = [versioned_value] return True def read(self, key: str) -> list[VersionedValue] | None: """ Return all versions of a key. Returns None if the node is down. A healthy node with no data for the key returns an empty list. """ if self.down: return None return self.storage.get(key, []) def __repr__(self): status = "DOWN" if self.down else f"token={self.token}" return f"DynamoNode({self.node_id}, {status})" Part 4: Consistent Hash Ring Мы сортируем узлы по их токену (позиции) и используем часовой ход, чтобы найти координатор и список предпочтений для любого ключа. import hashlib class ConsistentHashRing: """ Maps any key to an ordered list of N nodes (the preference list). Nodes are placed at fixed positions (tokens) on a conceptual ring from 0 to 2^32. A key hashes to a position, then walks clockwise to find its nodes. This means adding/removing one node only rebalances ~1/N of keys, rather than reshuffling everything like modulo hashing would. """ def __init__(self, nodes: list[DynamoNode]): # Sort nodes by token so we can do clockwise lookup efficiently self.nodes = sorted(nodes, key=lambda n: n.token) def _hash(self, key: str) -> int: """Consistent hash of a key into the ring's token space.""" # Use MD5 for a simple, evenly distributed hash. # Real Dynamo uses a more sophisticated hash (e.g., SHA-1). digest = hashlib.md5(key.encode()).hexdigest() return int(digest, 16) % (2**32) def get_preference_list(self, key: str, n: int) -> list[DynamoNode]: """ Return the first N nodes clockwise from key's hash position. These are the nodes responsible for storing this key. The first node in the list is the coordinator — it receives the client request and fans out to the others. """ if not self.nodes: return [] key_hash = self._hash(key) # Find the first node whose token is >= key's hash (clockwise) start_idx = 0 for i, node in enumerate(self.nodes): if node.token >= key_hash: start_idx = i break # If key_hash is greater than all tokens, wrap around to node 0 else: start_idx = 0 # Walk clockwise, collecting N unique nodes preference_list = [] for i in range(len(self.nodes)): idx = (start_idx + i) % len(self.nodes) preference_list.append(self.nodes[idx]) if len(preference_list) == n: break return preference_list Часть 5: Координатор Dynamo Это сердце системы — логика, которая обрабатывает запросы клиентов, фанатов в репликах, ждет кворума и обнаруживает конфликты. class SimplifiedDynamo: """ Coordinates reads and writes across a cluster of DynamoNodes. Any node can act as coordinator for any request — there's no dedicated master. The coordinator is simply whichever node receives the client request (or the first node in the preference list, if using partition-aware routing). Configuration: N = total replicas per key R = minimum nodes that must respond to a read (read quorum) W = minimum nodes that must acknowledge a write (write quorum) """ def __init__(self, nodes: list[DynamoNode], N: int = 3, R: int = 2, W: int = 2): self.N = N self.R = R self.W = W self.ring = ConsistentHashRing(nodes) # ------------------------------------------------------------------ # # WRITE # # ------------------------------------------------------------------ # def put(self, key: str, value: object, context: VectorClock | None = None) -> VectorClock: """ Write a key-value pair to N replicas, wait for W ACKs. The 'context' is the vector clock from a previous read. Always pass context when updating an existing key — it tells Dynamo which version you're building on top of, so it can detect whether your write is concurrent with anything else. Returns the new vector clock, which the caller should store and pass back on future writes to this key. Raises: RuntimeError if fewer than W nodes acknowledged. """ preference_list = self.ring.get_preference_list(key, self.N) if not preference_list: raise RuntimeError("No nodes available") # The coordinator is always the first node in the preference list. coordinator = preference_list[0] # Increment the coordinator's counter in the vector clock. # If no context was provided (brand new key), start a fresh clock. base_clock = context if context is not None else VectorClock() new_clock = base_clock.increment(coordinator.node_id) versioned = VersionedValue(value=value, vector_clock=new_clock) # Fan out to all N replicas. # In a real system these would be concurrent RPC calls. # Here we call them sequentially for simplicity. ack_count = 0 for node in preference_list: success = node.write(key, versioned) if success: ack_count += 1 # Only need W ACKs to declare success. # The remaining replicas are updated asynchronously (or via # hinted handoff if they were down). if ack_count < self.W: raise RuntimeError( f"Write quorum not met: got {ack_count} ACKs, needed {self.W}" ) print(f"[PUT] key={key!r} value={value!r} clock={new_clock} " f"({ack_count}/{self.N} nodes wrote)") return new_clock # ------------------------------------------------------------------ # # READ # # ------------------------------------------------------------------ # def get(self, key: str) -> list[VersionedValue]: """ Read a key from N replicas, wait for R responses, reconcile. Returns a LIST of VersionedValues: - Length 1 → clean read, no conflict - Length >1 → concurrent versions detected; application must merge After reading, the caller should: 1. If no conflict: use the single value normally. 2. If conflict: merge the values using application logic, then call put() with the merged value and the merged vector clock as context. This "closes" the conflict. Read repair happens in the background: any replica that returned a stale version is silently updated with the latest version. """ preference_list = self.ring.get_preference_list(key, self.N) # Collect responses from all N nodes all_versions: list[VersionedValue] = [] responding_nodes: list[tuple[DynamoNode, list[VersionedValue]]] = [] for node in preference_list: result = node.read(key) if result is not None: # None means the node is down all_versions.extend(result) responding_nodes.append((node, result)) if len(responding_nodes) < self.R: raise RuntimeError( f"Read quorum not met: got {len(responding_nodes)} responses, needed {self.R}" ) # Reconcile: discard any version that is strictly dominated # (i.e., is a causal ancestor of) another version. # What remains is the set of concurrent versions. reconciled = self._reconcile(all_versions) # Background read repair: if any node returned something older # than the reconciled result, send it the latest version. # (Simplified: only meaningful when there's a single winner.) if len(reconciled) == 1: latest = reconciled[0] for node, versions in responding_nodes: if not versions or versions[0].vector_clock != latest.vector_clock: node.write(key, latest) # Repair silently in background status = "clean" if len(reconciled) == 1 else f"CONFLICT ({len(reconciled)} versions)" print(f"[GET] key={key!r} status={status} " f"({len(responding_nodes)}/{self.N} nodes responded)") return reconciled # ------------------------------------------------------------------ # # INTERNAL: VERSION RECONCILIATION # # ------------------------------------------------------------------ # def _reconcile(self, versions: list[VersionedValue]) -> list[VersionedValue]: """ Remove any version that is a causal ancestor of another version. If version A's clock is dominated by version B's clock, then B is strictly newer — A adds no new information and can be dropped. Whatever remains after pruning are CONCURRENT versions: writes that happened without either "knowing about" the other. The application must merge these using domain-specific logic. Example: versions = [clock={A:1}, clock={A:2}, clock={B:1}] {A:2} dominates {A:1} → drop {A:1} {A:2} and {B:1} are concurrent → both survive result = [{A:2}, {B:1}] ← conflict! application must merge """ dominated = set() for i, v1 in enumerate(versions): for j, v2 in enumerate(versions): if i != j and v2.vector_clock.dominates(v1.vector_clock): dominated.add(i) # v1 is an ancestor of v2, discard v1 survivors = [v for i, v in enumerate(versions) if i not in dominated] # De-duplicate: identical clocks from different replicas are the same version seen_clocks: list[VectorClock] = [] unique: list[VersionedValue] = [] for v in survivors: if not any(v.vector_clock.clock == s.clock for s in seen_clocks): unique.append(v) seen_clocks.append(v.vector_clock) return unique if unique else versions Часть 6: Поставьте все вместе - Демо Давайте пройдем через полный сценарий: нормальное письмо/читание, затем симулированный конфликт, где два узла расходятся, и приложение должно объединить их. def demo(): # ── Setup ────────────────────────────────────────────────────────── # # Five nodes placed at evenly spaced positions on the hash ring. # In a real cluster these would span multiple datacenters. nodes = [ DynamoNode("node-A", token=100), DynamoNode("node-B", token=300), DynamoNode("node-C", token=500), DynamoNode("node-D", token=700), DynamoNode("node-E", token=900), ] dynamo = SimplifiedDynamo(nodes, N=3, R=2, W=2) print("=" * 55) print("SCENARIO 1: Normal write and read (no conflict)") print("=" * 55) # Write the initial shopping cart ctx = dynamo.put("cart:user-42", {"items": ["shoes"]}) # Read it back — should be a clean single version versions = dynamo.get("cart:user-42") print(f"Read result: {versions[0].value}\n") # Update the cart, passing the context from our earlier read. # The context tells Dynamo "this write builds on top of clock ctx". ctx = dynamo.put("cart:user-42", {"items": ["shoes", "jacket"]}, context=ctx) versions = dynamo.get("cart:user-42") print(f"After update: {versions[0].value}\n") print("=" * 55) print("SCENARIO 2: Simulated conflict — two concurrent writes") print("=" * 55) # Write the base version base_ctx = dynamo.put("cart:user-99", {"items": ["hat"]}) # Now simulate a network partition: # node-A and node-B can't talk to each other. # We model this by writing directly to individual nodes. pref_list = dynamo.ring.get_preference_list("cart:user-99", 3) node_1, node_2, node_3 = pref_list[0], pref_list[1], pref_list[2] # Write 1: customer adds "scarf" via node_1 (e.g., their laptop) clock_1 = base_ctx.increment(node_1.node_id) node_1.write("cart:user-99", VersionedValue({"items": ["hat", "scarf"]}, clock_1)) # Write 2: customer adds "gloves" via node_2 (e.g., their phone) # This write also descends from base_ctx, not from clock_1. # Neither write knows about the other → they are concurrent. clock_2 = base_ctx.increment(node_2.node_id) node_2.write("cart:user-99", VersionedValue({"items": ["hat", "gloves"]}, clock_2)) # Read — coordinator sees two concurrent versions and surfaces the conflict versions = dynamo.get("cart:user-99") if len(versions) > 1: print(f"\nConflict detected! {len(versions)} concurrent versions:") for i, v in enumerate(versions): print(f" Version {i+1}: {v.value} clock={v.vector_clock}") # Application-level resolution: union merge (Amazon's shopping cart strategy) # Merge items: take the union so no addition is lost all_items = set() merged_clock = versions[0].vector_clock for v in versions: all_items.update(v.value["items"]) merged_clock = merged_clock.merge(v.vector_clock) merged_value = {"items": sorted(all_items)} print(f"\nMerged result: {merged_value}") # Write the resolved version back with the merged clock as context. # This "closes" the conflict — future reads will see a single version. final_ctx = dynamo.put("cart:user-99", merged_value, context=merged_clock) versions = dynamo.get("cart:user-99") print(f"\nAfter resolution: {versions[0].value}") assert len(versions) == 1, "Should be a single version after merge" if __name__ == "__main__": demo() Expected output: ======================================================= SCENARIO 1: Normal write and read (no conflict) ======================================================= [PUT] key='cart:user-42' value={'items': ['shoes']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) Read result: {'items': ['shoes']} [PUT] key='cart:user-42' value={'items': ['shoes', 'jacket']} clock=VectorClock({'node-A': 2}) (3/3 nodes wrote) [GET] key='cart:user-42' status=clean (3/3 nodes responded) After update: {'items': ['shoes', 'jacket']} ======================================================= SCENARIO 2: Simulated conflict — two concurrent writes ======================================================= [PUT] key='cart:user-99' value={'items': ['hat']} clock=VectorClock({'node-A': 1}) (3/3 nodes wrote) [GET] key='cart:user-99' status=CONFLICT (2 versions) (3/3 nodes responded) Conflict detected! 2 concurrent versions: Version 1: {'items': ['hat', 'scarf']} clock=VectorClock({'node-A': 2}) Version 2: {'items': ['hat', 'gloves']} clock=VectorClock({'node-A': 1, 'node-B': 1}) Merged result: {'items': ['gloves', 'hat', 'scarf']} [PUT] key='cart:user-99' value={'items': ['gloves', 'hat', 'scarf']} ... (3/3 nodes wrote) [GET] key='cart:user-99' status=clean (3/3 nodes responded) After resolution: {'items': ['gloves', 'hat', 'scarf']} В сценарии 2 координатор правильно определяет, что и Они не являются ни равными, ни в доминирующих отношениях - ни один из них не является предком другого, поэтому оба они выходят на поверхность как одновременные.Приложение затем берет на себя ответственность за их слияние и переписывает разрешенную версию с объединенными часами. What to notice: {'node-A': 2} {'node-A': 1, 'node-B': 1} Ключевые уроки системного дизайна После многолетней работы с системами, вдохновленными Dynamo, вот мои ключевые идеи: 1. Always-On Beats Strongly-Consistent Для приложений, ориентированных на пользователя, почти всегда выигрывает доступность.Пользователи будут терпеть видение слегка застойных данных.Они не будут терпеть "Услуга недоступна". 2. Application-Level Reconciliation is Powerful Приложение понимает бизнес-логику и может принимать более умные решения, чем база данных когда-либо могла. 3. Tunable Consistency is Essential Добавки в корзину требуют высокой доступности (W = 1).Финансовые транзакции нуждаются в более сильных гарантиях (W = N).Умение настроить эту операцию невероятно ценно. 4. The 99.9th Percentile Matters More Than Average Сосредоточьте свои усилия по оптимизации на задержках хвоста.Это то, что пользователи на самом деле испытывают во время пиковых времен. 5. Gossip Protocols Scale Beautifully Децентрализованная координация через сплетни устраняет единичные точки неудачи и масштабы до тысяч узлов. Когда нельзя использовать системы Dynamo-Style Будьте честны о компромиссах.Не используйте этот подход, когда: Требуется сильная последовательность (финансовые операции, управление запасами) Необходимы сложные запросы (отчеты, аналитики, соединения) Транзакции охватывают несколько элементов (Dynamo только операции с одним ключом) Ваша команда не может справиться с возможной последовательностью (если разработчики не понимают векторные часы и разрешение конфликтов, у вас будут проблемы) Conclusion Dynamo represents a fundamental shift in how we think about distributed systems. By embracing eventual consistency and providing tunable trade-offs, it enables building systems that scale to massive sizes while maintaining high availability. The paper’s lessons have influenced an entire generation of distributed databases. Whether you’re using Cassandra, Riak, or DynamoDB, you’re benefiting from the insights first published in this paper. Как инженеры, наша работа заключается в том, чтобы глубоко понять эти компромиссы и применить их соответствующим образом. Dynamo дает нам мощный инструмент, но как и любой инструмент, он только так хорош, как наше понимание того, когда и как его использовать. дальнейшее чтение Оригинал Dynamo Paper: SOSP 2007 Блог Вернера Вогельса: Все вещи распределены Документация Кассандра: понимание того, как реализуются эти концепции «Проектирование данных-интенсивных приложений» Мартина Клеппманна — глава 5 о репликации Приложение: Проблемы и подходы к проектированию Три открытых проблемы, которые возникают в интервью системного дизайна и реальной инженерной работы. Проблема 1: Решение конфликтов для совместного редактора документов : Вы строите что-то вроде Google Docs, поддерживаемого магазином в стиле Dynamo. Два пользователя редактируют один и тот же абзац одновременно. The problem Стратегия корзины покупок (объединение всех элементов) безопасна только потому, что добавление элементов является коммутативным. Если Пользователь А удаляет предложение, а Пользователь Б редактирует его середину, объединение их изменений является бессмысленным или противоречивым. Why shopping cart union doesn’t work here {A} ∪ {B} = {B} ∪ {A} The right approach: Operational Transformation (OT) or CRDTs Решение отрасли заключается в том, чтобы представить документ не в виде блока текста, а как последовательность операций, и преобразовать одновременные операции, чтобы они могли быть применены без конфликта: User A's operation: delete(position=50, length=20) User B's operation: insert(position=60, text="new sentence") Without OT: B's insert position (60) is now wrong because A deleted 20 chars. With OT: Transform B's operation against A's: B's insert position shifts to 40 (60 - 20). Both operations now apply cleanly. Стратегией разрешения конфликтов для слоя Dynamo будет: Хранить операции (не полные кадры документа) как значение для каждого ключа. При конфликте соберите все списки одновременных операций из каждой версии. Используйте OT, чтобы объединить их в единый последовательный журнал операций. Напишите слитый дневник обратно с слиянием векторных часов в контексте. Лог операции по сегменту документа, а не рендерированный текст.Это делает слияния детерминистскими и без потерь. What to store in Dynamo Их слои хранения используют либо OT, либо вариант CRDT (Conflict-free Replicated Data Types), которые являются структурами данных, математически гарантированными для слияния без конфликтов независимо от порядка операции. Real-world reference Проблема 2: Выбор N, R, W для различных случаев использования : Какую конфигурацию вы бы выбрали для (а) магазина сеансов, (б) каталога продуктов, (в) профилей пользователей? The problem Правильный способ подумать об этом: определите режим неудачи, который стоит больше — пропущенный запись (потеря данных) или отклоненный запись (недоступность). Session store — prioritize availability Сеансы являются временными и специфическими для пользователя.Если сессия пользователя на короткое время остановилась или потеряна, они выходят и снова войдут.Это досадно, но не катастрофично.Вы никогда не хотите отказаться от записи сессии. N=3, R=1, W=1 Rationale: - W=1: Accept session writes even during heavy failures. A user can't log in if their session write is rejected. - R=1: Read from any single node. Stale session data is harmless. - N=3: Still replicate to 3 nodes for basic durability. Trade-off accepted: Stale session reads are possible but inconsequential. Product catalog — prioritize read performance and consistency Данные о продуктах пишутся редко (опс-командами), но читаются миллионы раз в день.Стальные цены или описания являются проблематичными. N=3, R=2, W=3 Rationale: - W=3: All replicas must confirm a catalog update before it's live. A price change half-published is worse than a brief write delay. - R=2: Read quorum overlap with W=3 guarantees fresh data. Acceptable: catalog writes are rare, so write latency doesn't matter. - N=3: Standard replication for durability. Trade-off accepted: Writes are slow and fail if any node is down. Acceptable because catalog updates are infrequent. User profiles — balanced Данные профиля (имя, адрес электронной почты, предпочтения) умеренно важны. Застойный профиль является раздражающим, но не опасным. Отклоненное обновление (например, пользователь не может обновить свою электронную почту) является реальной проблемой. N=3, R=2, W=2 Rationale: - The classic balanced configuration. - R + W = 4 > N = 3, so quorums overlap: reads will see the latest write. - Tolerates 1 node failure for both reads and writes. - Appropriate for data that matters but doesn't require strict consistency. Trade-off accepted: A second simultaneous node failure will cause errors. Acceptable for non-critical user data. Decision framework summary: Priority R W When to use Max availability 1 1 Sessions, ephemeral state, click tracking Balanced 2 2 User profiles, preferences, soft state Consistent reads 2 3 Catalogs, config, rarely-written reference data Highest consistency 3 3 Anywhere you need R+W > N with zero tolerance for stale reads (still not linearizable) Макс Доступность 1 1 Сеансы, эффектное состояние, отслеживание кликов сбалансированный 2 2 Пользовательские профили, предпочтения, мягкое состояние Постоянное чтение 2 3 Каталоги, конфиг, редко записанные справочные данные Высочайшая последовательность 3 3 Где бы вы ни нуждались в R+W > N с нулевой толерантностью для непостоянных отчетов (все еще не линейные) Проблема 3: Испытание системы Dynamo-Style по сценариям разделения Как вы проверяете, что ваша система действительно ведет себя правильно, когда узлы не удаляются и происходит разделение? The problem Это одна из самых сложных проблем в тестировании распределенных систем, потому что ошибки появляются только в конкретных промежутках одновременных событий, которые трудно воспроизвести детерминистически. Layer 1: Unit tests for the logic in isolation Прежде чем тестировать распределенное поведение, проверьте строительные блоки самостоятельно.Логика сравнения векторных часов, обнаружение конфликтов и функции примирения могут быть протестированы с помощью чисто единичных тестов — сетевое подключение не требуется. def test_concurrent_clocks_detected_as_conflict(): clock_a = VectorClock({"node-A": 2}) clock_b = VectorClock({"node-B": 2}) assert not clock_a.dominates(clock_b) assert not clock_b.dominates(clock_a) # Both survive reconciliation → conflict correctly detected def test_ancestor_clock_is_discarded(): old_clock = VectorClock({"node-A": 1}) new_clock = VectorClock({"node-A": 3}) assert new_clock.dominates(old_clock) # old_clock should be pruned during reconciliation Layer 2: Deterministic fault injection Вместо того чтобы надеяться, что неудачи произойдут в нужном порядке во время тестирования нагрузки, впрыскивайте их преднамеренно и неоднократно. является простой версией этого. В производственных системах библиотеки, такие как или Делайте это на уровне инфраструктуры. node.down = True Джейсон Хаос обезьяны Ключевые сценарии для тестирования: Scenario A: Write succeeds with W=2, third replica is down. → Verify: the data is readable after the down node recovers. → Verify: no data loss occurred. Scenario B: Two nodes accept concurrent writes to the same key. → Verify: the next read surfaces exactly 2 conflicting versions. → Verify: after the application writes a merged version, the next read is clean. Scenario C: Node goes down mid-write (wrote to W-1 nodes). → Verify: the write is correctly rejected (RuntimeError). → Verify: no partial writes are visible to readers. Scenario D: All N nodes recover after a full partition. → Verify: no data was lost across the cluster. → Verify: vector clocks are still meaningful (no spurious conflicts). Layer 3: Property-based testing Вместо того чтобы писать отдельные тесты, определите которые всегда должны держать и генерировать тысячи последовательностей случайных операций, чтобы попытаться нарушить их: Неизменные # Invariant: after any sequence of writes and merges, a final get() # should always return exactly one version (no unresolved conflicts). # Invariant: a value written with a context derived from a previous read # should never produce a conflict with that read's version # (it should dominate it). # Invariant: if R + W > N, a value written successfully should always # be visible in the next read (read-your-writes, absent concurrent writes). Такие инструменты как (Python) позволяет вам выразить эти инварианты и автоматически находить контрпримеры. Гипотеза Layer 4: Linearizability checkers Для максимальной уверенности записывайте время начала, время окончания и результат каждой операции во время теста на впрыскивание дефектов, а затем подавайте историю в проверку линейности, например: Он расскажет вам, согласуется ли какая-либо наблюдаемая история с правильным последовательным выполнением — даже для системы, которая в конечном итоге работает в рамках заявленных гарантий. Кносы Написано из трещин распределенных систем. Проверенные в боях знания, нулевая ручная волна. Ноутбук Линк Ноутбук Линк
