Теперь к главное проблеме: как сделать так, чтобы запись всегда была успешной? Несколько трюков. Во-первых, при факторе репликации
N, каждый узел содержит preference list, состоящий из более чем N узлов. В идеальном мире, запись будет идти в один из N узлов, но если какая-то часть из них недоступна, запись пойдёт через hinted handoff в другой узел. Hinted Handoff — это такая особая запись на "чужую" ноду с хинтом. Допустим, если обычно запись идёт в A, B, C, но запись нужно сделать в D, можно сообщить узлу "вот данные, но они вообще были для узла A`". Тогда `D сохранит данные, но также будет периодически проверять, не поднялся ли A. Как только это произойдёт, D перельёт свои данные в A, где им и место, и удалит их у себя.Во-вторых, для записи используется vector clock. Каждая запись содержит не только данные, но также номер сервера и значение монотонно растущего счётчика. Сервер, который записывает данные, обновит значение счётчика или добавит в список новый счётчик. По двум таким записям очевидно, можно ли автоматически разрешить конфликт. К примеру, если есть две записи
(node: 1, version: 5) и (node: 1, version: 2), очевидно, что вторую можно отбросить, так как она старая, по сравнению с новой записью того же сервера. Именно таким образом работает read repair в Dynamo. Когда при чтении какой-то из узлов возвращает устарелые данные, они обновляются. Но если запись будет (node: 1, version: 4) и (node: 2, version: 5), просто разрешение конфликтов уже не сработает. И здесь ребята из Amazon поднимают довольно важную проблему. База данных редко знает семантику данных. Для базы это всё просто наборы бит, поэтому на уровне хранилищ редко можно получить хорошую тактику разрешения конфликтов. Можно использовать к примеру
last-write-wins. Для некоторых видов данных можно даже наворотить CRDT, которые не факт что разрешат конфликт семантически правильно, но точно разрешат его одинаковым образом на всех нодах. Решение: отдавать конфликты клиенту! Уж программист то точно знает, что две конфликтные записи семантически — это две версии корзины товаров, с вполне понятным алгоритмом их слияния. Немного странно из
get запроса получить гипотетически 2 версии данных, зато конфликты будут разрешаться правильно.Теперь про failure detection и добавление новых нод в кластер. На момент 2007 года у Amazon каждый отдельный сервис сам поднимает и менеджерит кластер Dynamo. Это значит, что общее количество узлов обычно измеряется в сотнях, а не тысячах. В такой ситуации при добавлении новых узлов, хорошо себя показывают gossip алгоритмы (Про gossip писал здесь). Каждый узел самостоятельно строит картину кластера как раз основываясь на сообщениях, полученных по gossip. Интересный момент: тот же gossip не используется для передачи информации о неработающих узлах. Т.е. у Dynamo фактически отсутствовал global failure detection механизм, ноды содержали информацию о неработающих узлах локально (не можешь достучаться — не работает), но не делились ей. Одна из причин: операции по добавлению и удалению узлов делаются в ручном режиме, такой алгоритм просто не нужен.
Ещё немного про антиэнтропию для поддержания одинакового состояния реплик. Чтобы не передавать кучу данных по репликам, используются Merkle Trees. Это такой хитрое дерево у которого хеш родителя состоит из хешей детей. Если хеш в корне двух деревьев одинаковый — оба дерева одинаковые. Если нет — можно сравнить хеши детей, чтобы быстрее обнаружить, в какой из частей поддерева есть расхождение.
И последний интересный кусочек про перформанс. Задержка при записи в кворум из
W узлов определяется задержкой самого медленного узла. А что если при записи в W узлом писать только в буфер в памяти, а в остальные N-W узлов писать в диск? Тогда задержки меньше, при этом запись скорее всего будет в других узлах. Этот хак позволяет Dynamo в 5 раз уменьшить задержки в 99.9 процентиле в пиковые загрузки.