Системный дизайн облачного хранилища файлов: чанкинг, дедупликация и синхронизация
Dropbox или Google Drive на system design интервью: оценка нагрузки, разбиение файлов на блоки, дедупликация по SHA-256, метаданные отдельно от блобов, синхронизация, конфликты, presigned URL.
Коротко
| Вопрос | Решение в этом разборе |
|---|---|
| Главная идея | файл — это список хешей блоков; байты и метаданные живут в разных системах |
| Блоки | content-defined chunking, в среднем 4 МБ, ключ блока — его SHA-256 |
| Дедупликация | клиент сначала спрашивает «каких хешей у вас нет» и грузит только их |
| Метаданные | реляционная база, шардированная по пространству имён (пользователь, папка) |
| Байты | объектное хранилище, клиент пишет и читает напрямую по presigned URL |
| Синхронизация | журнал изменений с курсором, уведомление через long polling или WebSocket |
| Конфликты | оптимистичная проверка ревизии, проигравшая версия становится «конфликтной копией» |
На этой задаче проверяют одно умение: разделить систему на части с очень разными профилями нагрузки. Байтов петабайты, но они почти не меняются. Метаданных в тысячи раз меньше, зато каждая операция пользователя — это транзакция над ними. Кто проектирует их одной базой, проваливается на первой же оценке.
Общий порядок секции описан в статье про подходы к проектированию систем. Здесь он применён к одной задаче от начала до конца.
Как распределить время
| Этап | Минуты | Что должно остаться на доске |
|---|---|---|
| Требования | 5 | список «делаем» и «не делаем» |
| Оценка нагрузки | 5 | объём, загрузки в секунду, размер метаданных |
| Высокоуровневая схема | 8 | клиент, API, метаданные, блоки, уведомления |
| Загрузка: блоки и дедупликация | 10 | протокол из двух шагов |
| Синхронизация и конфликты | 10 | курсор, журнал, правило для конфликта |
| Узкие места и вопросы вглубь | 7 | что ломается первым |
Типичный провал — начать с выбора облака для файлов и полчаса обсуждать репликацию дисков. Интервьюеру интереснее, как два ноутбука договорятся о версии одного файла.
Шаг 1. Требования
Задайте вопросы, каждый из которых меняет дизайн.
| Вопрос | Типичный ответ | Что это меняет |
|---|---|---|
| Есть десктоп-клиент с синхронизацией? | да, плюс веб и мобильные | нужен журнал изменений и локальная база |
| Максимальный размер файла? | десятки гигабайт | обязательно разбиение и докачка |
| Совместное редактирование в реальном времени? | нет, только синхронизация файлов | не нужны OT/CRDT, хватит ревизий |
| Общие папки? | да, с правами чтения и записи | шардирование не просто по пользователю |
| История версий? | 30 дней | блоки нельзя удалять сразу |
| Файлы могут быть одинаковыми у разных людей? | да, вложения, дистрибутивы, фото | межпользовательская дедупликация — с оговорками |
Нефункциональные требования предложите сами:
- Надёжность: загруженный файл не теряется никогда. Это важнее доступности. Пусть синхронизация остановится на час, но данные останутся целы.
- Согласованность метаданных строгая в пределах одного пространства имён: два устройства не должны увидеть разные «последние» версии одного файла навсегда.
- Синхронизация в пределах нескольких секунд, когда оба устройства онлайн.
- Экономия трафика: изменение одного абзаца в файле на 200 МБ не должно гонять 200 МБ.
Не делаем: поиск по содержимому, превью документов, антивирус. Упомяните, что они цепляются к той же ленте событий, и двигайтесь дальше.
Шаг 2. Оценка нагрузки
Возьмём круглые числа и проговорим их вслух. Техника подробно разобрана в статье про оценку на салфетке.
users = 500_000_000 dau = 100_000_000 avg_used_gb = 5 uploads_per_day = 2 # новых или изменённых файлов на активного пользователя avg_file_mb = 2 logical_pb = users * avg_used_gb / 1_000_000 print(f'логический объём: {logical_pb:.0f} ПБ') writes_per_sec = dau * uploads_per_day / 86_400 print(f'загрузок в секунду: {writes_per_sec:,.0f}, в пике x3: {writes_per_sec * 3:,.0f}') ingress_gbps = writes_per_sec * avg_file_mb * 8 / 1000 print(f'входящий трафик: {ingress_gbps:,.0f} Гбит/с в среднем') daily_new_tb = dau * uploads_per_day * avg_file_mb / 1_000_000 print(f'новых данных в день: {daily_new_tb:,.0f} ТБ') files_per_user = 200 row_bytes = 500 meta_tb = users * files_per_user * row_bytes / 1e12 print(f'строк метаданных: {users * files_per_user / 1e9:.0f} млрд, объём: {meta_tb:.0f} ТБ') # логический объём: 2500 ПБ # загрузок в секунду: 2,315, в пике x3: 6,944 # входящий трафик: 37 Гбит/с в среднем # новых данных в день: 400 ТБ # строк метаданных: 100 млрд, объём: 50 ТБ
Что из этого следует:
- 2,5 эксабайта логических данных. Никакая база столько не держит; байты уходят в объектное хранилище, а реплики или erasure coding умножают физический объём ещё в 1,5–3 раза.
- Метаданные — 50 ТБ. Много для одной машины, но вполне по силам шардированному кластеру реляционной базы.
- Несколько тысяч загрузок в секунду — для метаданных это умеренно. Байтовый трафик в десятки гигабит нельзя пропускать через свои API-серверы, отсюда presigned URL.
- Пользователь хранит 5 ГБ, а меняет за день мегабайты. Профиль «пишем один раз, читаем изредка» — значит, холодные данные можно уводить на дешёвые классы хранения.
Шаг 3. Высокоуровневая схема
┌──────────────┐ 1. какие блоки нужны? ┌────────────────────┐
│ Клиент │ ───────────────────────▶ │ API / Metadata │
│ (локальная │ ◀─────────────────────── │ service │
│ база, CDC) │ 2. presigned URL └─────────┬──────────┘
└──┬───────┬───┘ │ транзакции
│ │ 3. PUT блоков напрямую ▼
│ ▼ ┌────────────────────┐
│ ┌──────────────────┐ │ Metadata DB │
│ │ Блоб-хранилище │ │ (шарды по │
│ │ (S3 и подобные) │ │ namespace) │
│ └──────────────────┘ └─────────┬──────────┘
│ │ журнал изменений
│ 5. «есть изменения» ┌──────────────────┐ │
└◀────────────────────── │ Notification │ ◀────┘
│ service │ 4. событие commit
└──────────────────┘
Четыре компонента с разными требованиями:
- Клиент — полноценная часть системы, а не тонкий UI. Он следит за папкой, режет файлы на блоки, считает хеши, держит локальную базу с последним известным состоянием и курсором.
- Metadata service — знает дерево папок, ревизии файлов и списки блоков. Это сердце системы, здесь нужны транзакции.
- Блоб-хранилище — неизменяемые блоки по ключу «хеш содержимого». Никакой логики, только надёжность и пропускная способность.
- Notification service — держит открытые соединения с клиентами и толкает «в пространстве X есть изменения». Сами изменения клиент забирает у metadata service.
Шаг 4. Метаданные и блобы — почему раздельно
Можно хранить файлы в базе как BLOB. Для прототипа сойдёт, на интервью это сигнал, что кандидат не считал.
| Свойство | Метаданные | Блоки |
|---|---|---|
| Объём | десятки ТБ | эксабайты |
| Размер записи | сотни байт | мегабайты |
| Изменяемость | постоянно: переименования, ревизии | никогда: блок с хешем H всегда одинаков |
| Нужны транзакции | да | нет |
| Кэшируемость | плохо, часто меняются | идеально: ключ однозначно задаёт содержимое |
Минимальная схема метаданных:
CREATE TABLE files ( namespace_id BIGINT, -- пользователь или общая папка path TEXT, rev BIGINT, -- растёт при каждом изменении size BIGINT, blocks TEXT[], -- упорядоченный список SHA-256 is_deleted BOOLEAN, PRIMARY KEY (namespace_id, path) ); CREATE TABLE journal ( namespace_id BIGINT, seq BIGINT, -- монотонный номер внутри namespace path TEXT, rev BIGINT, PRIMARY KEY (namespace_id, seq) );
В реальной системе путь хранят не строкой, а через file_id и parent_id, иначе переименование папки с миллионом файлов превращается в миллион обновлений. Но на доске так проще, и это стоит сказать вслух.
Шардирование по namespace_id. Все файлы пространства имён и его журнал лежат на одном шарде, поэтому коммит файла и запись в журнал — одна локальная транзакция. Общая папка — отдельное пространство имён, которое монтируется в дерево нескольких пользователей. Это ответ на вопрос «как шардировать, если папка общая»: шардируем не по пользователю, а по папке. Детали — в статье про шардирование и репликацию.
Горячий ключ — огромная общая папка компании, куда пишут тысячи людей. Её шард становится узким местом; это стоит назвать и предложить делить такие пространства на поддеревья.
Шаг 5. Чанкинг: почему не файлами целиком
Загружать файл целиком плохо по трём причинам: обрыв на 9-м гигабайте из 10 означает начать заново, правка одного байта гонит весь файл, а одинаковые куски разных файлов хранятся многократно. Решение — резать файл на блоки и адресовать каждый его хешем.
Dropbox исторически использовал блоки по 4 МБ. Меньше блок — лучше дедупликация, но больше строк метаданных и накладных расходов на запрос. 1–8 МБ — разумный диапазон для интервью.
Фиксированный размер ломается на вставке
Самое простое — резать по смещениям 0, 4 МБ, 8 МБ. Проверим, что будет, если вставить один байт в начало.
import hashlib import random def fixed_chunks(data: bytes, size: int) -> list[bytes]: return [data[i:i + size] for i in range(0, len(data), size)] def sha(chunk: bytes) -> str: return hashlib.sha256(chunk).hexdigest() random.seed(1) original = random.randbytes(1_000_000) edited = b'X' + original # вставили один байт в начало old = {sha(c) for c in fixed_chunks(original, 64 * 1024)} new = [sha(c) for c in fixed_chunks(edited, 64 * 1024)] reused = sum(h in old for h in new) print(f'блоков в новой версии: {len(new)}, совпало со старой: {reused}') # блоков в новой версии: 16, совпало со старой: 0
Ни одного совпадения: все границы сдвинулись на байт, и каждый блок стал новым. Для дописывания в конец (логи) фиксированные блоки работают отлично, для правки документов — нет.
Content-defined chunking
Идея: границу блока определяет содержимое, а не смещение. Считаем скользящий хеш по последним байтам и режем там, где его старшие биты равны нулю. После вставки байта граница сдвигается вместе с данными, и следующие блоки совпадают. Тот же приём лежит в основе rsync и алгоритма Рабина — Карпа.
import hashlib import random random.seed(42) GEAR = [random.getrandbits(64) for _ in range(256)] # случайное число на каждый байт MASK64 = (1 << 64) - 1 def cdc_chunks(data: bytes, avg_bits=16, min_size=16 * 1024, max_size=256 * 1024): """Content-defined chunking на gear-хеше: средний блок около 2**avg_bits байт.""" mask = ((1 << avg_bits) - 1) << (64 - avg_bits) # смотрим на старшие биты chunks, start, h = [], 0, 0 for i, byte in enumerate(data): h = ((h << 1) + GEAR[byte]) & MASK64 size = i - start + 1 if size < min_size: continue if (h & mask) == 0 or size >= max_size: chunks.append(data[start:i + 1]) start, h = i + 1, 0 if start < len(data): chunks.append(data[start:]) return chunks def sha(chunk: bytes) -> str: return hashlib.sha256(chunk).hexdigest() random.seed(1) original = random.randbytes(1_000_000) edited = b'X' + original old = {sha(c) for c in cdc_chunks(original)} new = [sha(c) for c in cdc_chunks(edited)] reused = sum(h in old for h in new) print(f'блоков в новой версии: {len(new)}, совпало со старой: {reused}') # блоков в новой версии: 9, совпало со старой: 8
Изменился только первый блок, остальные восемь клиент не грузит. Это gear-хеш, как в FastCDC: сдвиг влево за 64 шага «забывает» старые байты, поэтому окно получается неявным и очень дешёвым. Ограничения min_size и max_size не дают блокам вырождаться в крошечные или гигантские.
На интервью код не нужен, достаточно фразы «режем по скользящему хешу, а не по смещению, чтобы вставка не сдвигала все границы». Если интервьюер копнёт глубже — у вас есть объяснение.
Шаг 6. Загрузка и дедупликация
Ключ блока — SHA-256 его содержимого. Отсюда протокол из трёх шагов:
- Клиент режет файл, считает хеши и отправляет список:
POST /files/commit_prepare {path, base_rev, blocks: [h1, h2, ...]}. - Сервер отвечает, каких хешей у него нет, и выдаёт на каждый presigned URL для загрузки.
- Клиент заливает недостающие блоки напрямую в хранилище и вызывает
commit— атомарную запись новой ревизии со списком блоков.
Проверка «есть ли такой хеш» — та же операция, что в задаче про дубликаты в массиве, только множество размером в сотни миллиардов элементов. Её держат в индексе блоков, а перед ним можно поставить фильтр Блума, чтобы большинство новых блоков отсекать без похода в базу.
Почему коммит после загрузки, а не до. Если сначала записать метаданные, другое устройство увидит ревизию и пойдёт за блоками, которых ещё нет. Правило: метаданные ссылаются только на уже существующие блоки. Обратная ситуация — блок загружен, а коммит не случился — безопасна: осиротевший блок удалит сборщик мусора.
Коммит должен быть идемпотентным. Клиент повторяет запрос после таймаута, и второй коммит не должен создать вторую ревизию. Помогает ключ идемпотентности или та же проверка base_rev. Подробнее — в статье про идемпотентность.
Межпользовательская дедупликация: осторожно
Соблазнительно делить блоки между всеми пользователями: один популярный дистрибутив хранится один раз. Но если сервер отвечает «этот блок у нас уже есть» на хеш, который клиент прислал без загрузки, появляются две проблемы:
- Утечка информации. Злоумышленник может проверить, хранит ли кто-то конкретный файл, просто предложив его хеш.
- Получение чужих данных. Если знать хеш достаточно, чтобы «загрузить» файл к себе, хеш превращается в ключ доступа. Именно такой обход дедупликации Dropbox публично разбирали исследователи в начале 2010-х.
Варианты ответа: дедуплицировать только внутри пространства имён, требовать доказательство владения (например, хеш случайного фрагмента по запросу сервера) или для межпользовательской дедупликации всё равно принимать байты и сравнивать на сервере. Назвать этот компромисс — сильный ход на интервью.
Удаление и сборка мусора
Блок может входить в десятки файлов и ревизий, поэтому удалять его при удалении файла нельзя. Два подхода:
- Счётчик ссылок на каждый блок, меняется в той же транзакции, что и ревизия. Быстро, но счётчик живёт на другом шарде, и распределённая транзакция дорога.
- Mark-and-sweep: периодически проходим по всем живым ревизиям, отмечаем используемые блоки и удаляем неотмеченные старше N дней. Медленно, но просто и устойчиво к ошибкам.
Задержка в N дней одновременно закрывает и историю версий, и гонку «блок только что загружен, коммит ещё не пришёл».
Шаг 7. Presigned URL: байты мимо API
Через свои серверы гнать десятки гигабит нет смысла. Metadata service выдаёт клиенту короткоживущую подписанную ссылку, и клиент общается с объектным хранилищем напрямую. Хранилище проверяет подпись и срок, не зная ничего о пользователях.
Упрощённая модель того, как это устроено:
import hashlib import hmac import time from urllib.parse import parse_qs, urlencode, urlparse SECRET = b'shared-secret-of-api-and-storage' def sign(method, key, expires): msg = f'{method}\n{key}\n{expires}'.encode() return hmac.new(SECRET, msg, hashlib.sha256).hexdigest() def presign(method, key, ttl=300, now=None): expires = int(now or time.time()) + ttl query = urlencode({'expires': expires, 'sig': sign(method, key, expires)}) return f'https://blocks.example.com/{key}?{query}' def verify(method, url, now=None): u = urlparse(url) q = parse_qs(u.query) key, expires, sig = u.path.lstrip('/'), int(q['expires'][0]), q['sig'][0] if (now or time.time()) > expires: return False return hmac.compare_digest(sig, sign(method, key, expires)) url = presign('PUT', 'blocks/9f86d0', ttl=300, now=1_700_000_000) print(verify('PUT', url, now=1_700_000_100)) # True: подпись верна, срок не вышел print(verify('GET', url, now=1_700_000_100)) # False: подписан другой метод print(verify('PUT', url, now=1_700_000_400)) # False: ссылка протухла
Настоящая подпись S3 (Signature Version 4) сложнее: в неё входят регион, сервис, заголовки и дата, а ключ подписи выводится из секрета цепочкой HMAC. Но принцип тот же, и максимальный срок жизни такой ссылки в S3 — семь дней. На практике ставят минуты.
Что важно сказать про presigned URL:
- Ссылка подписывает конкретный ключ и метод. Если ключ — хеш содержимого, хранилище может проверить, что загруженные байты действительно дают этот хеш (S3 принимает контрольную сумму SHA-256 в заголовке загрузки).
- Ссылка — это право доступа. Её нельзя логировать целиком и нельзя выдавать на долгий срок.
- Для скачивания тот же механизм: GET по подписанной ссылке, плюс CDN для популярных публичных файлов.
- Большие блоки или файлы целиком можно грузить через multipart upload: части грузятся параллельно и докачиваются по одной.
Шаг 8. Синхронизация клиентов
Клиенту нужно узнать, что изменилось, и не перекачивать дерево из миллиона файлов. Для этого у каждого пространства имён есть журнал с монотонным seq, а у клиента — курсор: последний seq, который он применил.
Цикл синхронизации:
- Клиент держит соединение с notification service — long polling или WebSocket (сравнение в статье про WebSocket и long polling).
- Приходит сигнал «в пространстве X что-то изменилось». В сигнале нет данных, только факт.
- Клиент вызывает
GET /changes?cursor=1042и получает записи журнала сseq > 1042и новый курсор. - Для каждой записи сравнивает список блоков с локальными, скачивает недостающие, собирает файл во временный и атомарно переименовывает.
Почему уведомление без данных: если клиент пропустил сигнал (сон ноутбука, обрыв сети), ничего не теряется — при следующем запросе по курсору он получит всё. Notification service может терять сообщения и падать без последствий для корректности. Это хорошее свойство, его стоит проговорить.
Офлайн-клиент, пролежавший месяц, присылает очень старый курсор. Если журнал уже обрезан, сервер отвечает «курсор устарел», и клиент делает полную сверку: получает снимок дерева и сравнивает с локальной базой.
Сколько нагрузки даёт notification service: при 100 млн DAU одновременно онлайн, скажем, 30–50 млн устройств. Это миллионы соединений на кластер шлюзов — та же задача, что в системном дизайне мессенджера.
Шаг 9. Конфликты
Два устройства правят один файл офлайн, оба видели ревизию 1. Кто-то должен победить, и никто не должен потерять данные.
Правило простое: коммит передаёт base_rev — ревизию, от которой клиент начинал правку. Сервер принимает коммит, только если base_rev совпадает с текущей ревизией. Это оптимистичная блокировка, compare-and-swap на уровне строки. Проигравший не перетирает файл, а сохраняется рядом как «конфликтная копия». Ровно так поступает Dropbox: склеивать произвольные бинарные файлы сервер не умеет, а решить за пользователя, какая правка важнее, нельзя.
import hashlib class MetadataServer: def __init__(self): self.blocks = set() # какие хеши уже лежат в блоб-хранилище self.files = {} # path -> {'rev': int, 'blocks': [hash, ...]} self.journal = [] # (seq, path, rev, blocks) — лента изменений self.seq = 0 def missing_blocks(self, hashes): return [h for h in hashes if h not in self.blocks] def commit(self, path, base_rev, hashes, device): if self.missing_blocks(hashes): raise ValueError('сначала загрузите недостающие блоки') current = self.files.get(path) current_rev = current['rev'] if current else 0 if base_rev != current_rev: # кто-то успел раньше: не перетираем, сохраняем рядом path = f'{path} (конфликтная копия {device})' current = self.files.get(path) rev = (current['rev'] if current else 0) + 1 self.files[path] = {'rev': rev, 'blocks': list(hashes)} self.seq += 1 self.journal.append((self.seq, path, rev, list(hashes))) return path, rev def changes_since(self, cursor): return [e for e in self.journal if e[0] > cursor], self.seq def upload(server, path, base_rev, chunks, device): hashes = [hashlib.sha256(c).hexdigest() for c in chunks] for h in server.missing_blocks(hashes): server.blocks.add(h) # здесь клиент шлёт PUT в блоб-хранилище return server.commit(path, base_rev, hashes, device) s = MetadataServer() print(upload(s, 'plan.txt', 0, [b'v1'], 'laptop')) # оба устройства видели rev=1 и правят файл офлайн print(upload(s, 'plan.txt', 1, [b'v2 from laptop'], 'laptop')) print(upload(s, 'plan.txt', 1, [b'v2 from phone'], 'phone')) changes, cursor = s.changes_since(1) for seq, path, rev, _ in changes: print(seq, path, rev) print('новый курсор:', cursor) # ('plan.txt', 1) # ('plan.txt', 2) # ('plan.txt (конфликтная копия phone)', 1) # 2 plan.txt 2 # 3 plan.txt (конфликтная копия phone) 1 # новый курсор: 3
В модели коммит и запись в журнал идут вместе. В реальной системе это одна транзакция на шарде пространства имён — поэтому журнал и файлы шардируют одинаково.
Почему не «последняя запись побеждает» по времени: часы устройств расходятся, а молча выброшенная правка — худший исход для хранилища. Почему не векторные часы, как в key-value хранилище в духе Dynamo: у пространства имён есть одна точка истины — его шард, и монотонной ревизии достаточно. Векторные часы нужны, когда лидера нет.
Отдельные случаи, которые стоит упомянуть:
- Удаление против правки. Одно устройство удалило файл, другое отредактировало. Безопаснее сохранить правку: удаление легко повторить, потерянный текст — нет.
- Переименование папки во время загрузки в неё. Решается тем, что файлы ссылаются на
parent_id, а не на путь. - Совместное редактирование документов — это уже другая задача (OT или CRDT), как в Google Docs. Скажите, что сознательно её не решаете.
Шаг 10. Узкие места и вопросы вглубь
| Вопрос интервьюера | Короткий ответ |
|---|---|
| Что упадёт первым? | шард горячей общей папки и индекс блоков |
| Как не потерять данные? | репликация или erasure coding в нескольких зонах, проверка хешей при чтении |
| Как сэкономить на хранении? | дедупликация, сжатие блоков, перенос холодных данных в дешёвый класс |
| Как ускорить первую синхронизацию? | параллельная загрузка блоков, LAN sync между устройствами в одной сети |
| Как быть с мобильным клиентом? | не синхронизировать всё, а скачивать по требованию, метаданные — полностью |
| Свой storage или облачный? | облачный на старте; Dropbox в 2016 году перенёс основную часть данных из S3 в собственную систему Magic Pocket, но это оправдано только на эксабайтах |
| Как уведомлять об изменениях? | шина событий из журнала, например через очередь сообщений |
Хорошая финальная фраза: «Корректность держится на трёх правилах: блоки неизменяемы и адресуются хешем, метаданные ссылаются только на загруженные блоки, коммит проверяет базовую ревизию. Всё остальное — оптимизации».
Типичные ошибки
- Хранить файлы в реляционной базе. Убивает и стоимость, и производительность на первой же оценке.
- Пропускать байты через API-серверы. Десятки гигабит трафика без пользы. Presigned URL решают это.
- Резать файлы на блоки фиксированного размера и обещать экономию трафика при правках. Вставка одного байта ломает все последующие блоки.
- Записывать метаданные раньше блоков. Другие устройства увидят ревизию, которую нельзя скачать.
- Last write wins по времени устройства. Тихая потеря данных.
- Класть данные в уведомление. Пропущенный пуш тогда означает пропущенное изменение. Уведомление должно говорить только «сходи за курсором».
- Забыть про сборку мусора и историю версий. Удаление блока при удалении файла ломает другие файлы с тем же блоком.
Что почитать дальше
- Консистентное хеширование — как раскладывать блоки по узлам хранилища.
- Шардирование и репликация — для слоя метаданных.
- Индексы в базах данных — индекс блоков и журнала.
- Сокращатель ссылок — ещё один разбор задачи от требований до узких мест.