Сегодня две работы. Первая: та самая статья про Dynamo из 2007 года (pdf), когда она ещё не была частью AWS и не называлась DynamoDB. "Та самая" эта работа, поскольку это редкий случай, когда куча разных идей по построению хранилищ были объединены в единое решение, которое не только работало, но и обеспечивало очень большой сайт. И о котором написали. В те далекие времени Amazon был e-commerce в первую очередь, AWS появился всего годом ранее, а DynamoDB так вообще вошла в сервисы AWS только к 2012 году. Вторая — свежий пирожок, опубликованный буквально пару дней назад спустя 10 лет эксплуатации сервиса DynamoDB (usenix pdf).
При создании Dynamo Amazon исходил из нескольких ограничений:
- key-value. Логика большинства сервисов, к примеру корзины товаров, достаточно простая, и реляционная модель не принесёт значительного успеха.
- Heterogeneity & Symmetry. Все узлы выполняют одну и ту же работу. Но узлы разные, значит они могут выдерживать разную нагрузку.
- Запись всегда должна быть успешной. Пусть и с конфликтами.
- Variable consistency. Клиент сам может выбрать соотношение читателей и писателей в кворуме
R+W > N.Теперь как это всё добро работало.
Поскольку хранилище key-value, этот key надо как-то соотнести с сервером. Нагрузка большая, поэтому кластер периодически придётся расширять. Выход — надёжный как швейцарские часы алгоритм консистентного хэширования (если первый раз — лекция Стэнфорда с подробным объяснением). Но не так всё просто. Во-первых, наивное разделение кольца хешей на кусочка приводит к неравномерной нагрузкой на разные узлы. Вернее не приводит, а не позволяет что-то с ней сделать. Во-вторых, узлы гетерогенные, значит некоторые могут принять больше нагрузки, а некоторые меньше. В-третьих, при падении узла вся нагрузка перейдёт на следующий узел, что может его прикончить.
Решение: виртуальные узлы. Кольцо делится на некоторое количество виртуальных узлов, а каждому физическому узлу присваивается несколько виртуальных. Нодам помощнее — больше, послабее — меньше. При этом виртуальные узлы могут находиться в произвольных точках кольца. Теперь при падении физической ноды, её виртуальные узлы начнут обрабатываться не "следующим" в цепочке, а сразу всеми или почти всеми другими узлами кольца.
Следующая проблема — репликация. При факторе репликации
N, данные нужно забросить ещё на N - 1 ноду. Как их выбрать? Решение гениальное: просто пихать данные на следующие N - 1 нод в кольце 🤷♂️. Если кольцо состоит из A -> B -> C -> D -> A, и фактор репликации 3, то данные на узле A также будут на узлах B и C. С виртуальными узлами чуть сложнее, потому что нет гарантии что следующий виртуальный узел находится на другой физической машине. Но это решается чуть более умным программированием.