Мне понравился опыт прошлого расследования по фейсбуку, и я решил организовать очередную серию, теперь про Amazon. Для нетерпеливых — в самом конце статьи описан итоговый вариант архитектуры Amazon S3 и проанализированы его свойства.

Не так давно Амазон объявил о переходе S3 с модели eventual consistency на strong consistency, то есть, предоставления гарантии read-after-write, чтения того, что было только что записано. Сообщество отреагировало, но как-то очень вяло: Amazon S3 Now Delivers Strong Read-After-Write Consistency

Первое, что лично мне подумалось в ответ на эти новости: а как же теорема CAP? Подсказки для ответа на этот вопрос ищутся в гугле:

S3 Strong Consistency

So they claim performance and availability will remain same while claiming strong consistency. I was confused at first but then “same” availability isn’t 100% availability. So it indeed CP.

S3: Small announcement, big impact

In this paper about Spanner, we learn that it’s possible to build a CA system (one which prioritises Consistency and Availability) and also build a network so good that the risk of Partitions to be Tolerant of is negligible enough to effectively ignore.

Короче говоря, CAP никуда не делось, вечного двигателя, сверхсветовой передачи информации, или телепорта в амазоне не изобрели. Амазон пошел по логичному пути: пока нет ни единого разрыва сети, БД дает Consistency+Availability гарантии, когда сеть рвется — запросы на запись перестают выполняться, имеющиеся данные замораживаюся в том состоянии, в котором они были до разрыва.

Теперь по самой реализации. Инфа в гугле крайне скудная, пока что лучшее, что удалось найти:
S3 Strong Consistency

If I had to guess, s3 synchronously writes to a cluster of storage nodes before returning success, and then asynchronously replicates it to other nodes for stronger durability and availability. There used to be a risk of reading from a node that didn't receive a file's change yet, which could give you an outdated file. Now they added logic so the lookup router is aware of how far an update is propagated and can avoid routing reads to stale replicas.

А также есть статья в блоге некоего высокопоставленного манагера из Амазона, Вернера Вогельса:
Diving Deep on S3 Consistency

Судя по всему, ключевым архитектором сего чуда был некто Нихил Шах: Nikhil Shah | LinkedIn

DATA ITEM AND WITNESS SERVICE PARTITIONING IN A DISTRIBUTED STORAGE SYSTEM
Patent date Filed Oct 1, 2021 Patent issuer and number P73159-US01

TRANSACTION MANAGEMENT FOR MONOTONIC WRITE CONSISTENCY IN A DISTRIBUTED STORAGE SYSTEM
Patent date Filed Oct 1, 2021 Patent issuer and number P74530-US01

Вбиваем в гугле «strong consistency witness» и «monotonic writes witness», смотрим результаты:
Voting with Witnesses: A Consistency Scheme for Replicated Files
Achieving both low latency and strong consistency in large-scale systems

Первая статья делает акцент на quorum-based консенсусе. Я очень сомневаюсь, что Амазон пошел по этому пути, поскольку пути опроса всего кластера для чтения не пошел даже непревзойденный Apache Zookeeper. Вместо этого Zookeeper делает чтение только с узла-лидера, поскольку дергать весь кластер на каждое чтение — это слишком накладно, и потому я сомневаюсь, что Амазон смог бы отрапортовать про бесплатный апгрейд по усилению согласованности данных. Но мне известна разработка, направленная на оптимизацию конкретно согласованности чтений, в виде модификации Apache ZooKeeper:

Strong and Efficient Consistency with Consistency-Aware Durability

Здесь авторы просто отложили операции записи, за счет чего уменьшили время ответа по запросам записи до уровня асинхронной репликации (и потеряли гарантии сохранности при исчезновении питания, но кого это волнует в 2022?). Монотонность чтений без необходимости опроса всего кластера «гарантировали» списком активных узлов, которые получили актуальные изменения и знают об этом. Можно спорить по поводу того, вовремя ли отвалившиеся узлы поймут, что у них уже нет актуальных данных, и потому сериализуемы ли чтения по кластеру, но ведь чтения несериализуемы даже в оригинальном ZooKeeper по абсолютно той же причине (узел может продолжать думать, что он лидер, хотя в кластере выбран новый лидер) — так что вроде как ухудшения нету.

Однако, даже уровень асинхронной репликации Zookeeper намного хуже масштабируется по записям, чем старый Amazon S3. У меня долго не получалось придумать модель с достаточными гарантиями согласованности данных и при этом хорошей производительностью, пока мое внимание не наткнулось на одну деталь описания Amazon S3:
https://docs.aws.amazon.com/AmazonS3/latest/userguide/Welcome.html#ConsistencyModel

Amazon S3 does not support object locking for concurrent writers. If two PUT requests are simultaneously made to the same key, the request with the latest timestamp wins.

«Last writer wins» — это вариант CRDT, для которого строгие гарантии линеаризуемости/сериализуемости не обязательны, а значит зачем вообще здесь нужен полный кворум и глобальная упорядоченность операций? Соответственно, взор мой возвращается снова на:
Achieving both low latency and strong consistency in large-scale systems
где авторы используют свидетелей (witness) просто как дополнительную гарантию сохранности транзакций в рамках eventual consistency гарантий.

Вам ничего это не напоминает? Мне напоминает устройство Amazon S3 до введения строгой согласованности.

Подытоживая эти улики, лично я склоняюсь к тому, что Амазон под капотом S3 оставил тот же самый eventual consistency, работающий на типичной для той же Amazon DynamoDB и Riak модели «sloppy quorum», например, когда у вас 5 узлов в сети и для подтверждения записи достаточно подтверждения от 2 узлов (а не трех, как это было бы в строгом кворуме). Данные со временем будут раскопированы асинхронно на остальные узлы. Естественно, sloppy quorum никак не защищает от split brain, когда у вас две части кластера теряют связь и начинают независимо изменять файлы (в обоих частях есть по два узла для успешного подтверждения), и потому не знают про изменения в другой части кластера. Очевидно, при восстановлении связи нужно как-то конфликтные изменения разруливать. Amazon DynamoDB/Riak уже давно используют решение «в лоб» — оставлять запись с самым последним timestamp.

По итогу воображается что-то такое:

Для начала рассмотрим поведение уже кэшированного объекта. В систему поступает запрос PUT на обновление файла. Успешный ответ на операцию PUT возвращается только после успешного сохранения на достаточное число персистентных хранилищ (persistent storage) и инвалидации достаточного числа кэшей. Вы может заметить здесь схожесть с процессорным кэшем, про которую упоминал Вернер Вогельс.

Однако, из этой схемы не понятно, что делать, когда объект еще не закэширован. Если пройти "в лоб" по пунктирным стрелочкам, опрашивая почти все сервера при каждом подобном запросе чтения, то получим большую нагрузку на сеть и задержку ответа.

Чтобы 100% найти записанный файл в кластере, нужно чтобы в подмножество серверов, с которых производится чтение, пересеклось хотя бы по одному серверу с подмножеством серверов, на которые файл был записан. Если в кластере 5 узлов и при записи мы ждем подтверждения от двух, то 5-2 = 3 узла могут не знать о файле, и чтобы гарантировано прочитать записанный ответ нам нужно опросить 5-2+1 = 4 узла, то есть, почти весь кластер. Для сравнения, в случае подтверждения записи строгим кворумом в 3 узла, для гарантированного чтения нам нужно будет опросить 5-3+1 = 3 узла, то есть, тот же самый кворум. Короче говоря, чем проще было писать, тем сложнее читать. В идеале хотелось бы, чтобы объект писался синхронно на все хранилища, после чего читать его можно было бы с любого хранилища, но, увы, производительность и задержка ответа такой системы по операциям записи будет хуже, чем у одного единственного хранилища.

Мы хотим, чтобы было просто и писать, и читать. Что делать? Можно условно статически назначить один-два-три узла лидерами, писать и читать только в них:

Но тогда получается, что остальные хранилища являются мертвым грузом, с них нельзя читать данные. Чтобы понять выбранный Амазоном путь, читаем документацию дальше:

Amazon Replication Time Control

S3 Replication Time Control is backed by a Service Level Agreement (SLA) on the replication of 99.9% of objects within 15 minutes during any billing month.

Amazon S3 Event Notifications

Amazon S3 event notifications are designed to be delivered at least once. Typically, event notifications are delivered in seconds but can sometimes take a minute or longer.

Event message structure

The sequencer key provides a way to determine the sequence of events. Event notifications aren't guaranteed to arrive in the same order that the events occurred. However, notifications from events that create objects (PUTs) and delete objects contain a sequencer. It can be used to determine the order of events for a given object key.

You can't use sequencer to determine order for events on different object keys.

Улики подтверждают, что репликация и оповещения происходят через один и тот же механизм. Причем, объекты внутри системы всегда версионированы и у версий есть некий внутренний идентификатор, но в зависимости от настроек пользователя эти версии могут становиться постоянными и получать видимый извне ID пользователю, либо быстро удаляться и извне иметь всегда пустой ID версии ( Adding objects to versioning-suspended buckets ). Теория механизма удаления старых версий подтверждается наличием еще одного подобного механизма, доступного внешнему пользователю: Using S3 Object Lock.

Итак, все объекты внутри версионированы, система следит за изменениями и старается в первую очередь реплицировать старые операции изменения, но при этом порядок операций не соблюдается. Это значит, что запись идет независимо на несколько узлов. В таких условиях единственный способ узнать, где находится последняя версия объекта — собирать эту информацию на один или несколько каталогов. Этот каталог и есть тот самый «свидетель», про который велась речь изначально.

SLA S3 гарантирует, что 99.9% всех изменений будут реплицированы и примерно такое же число всех оповещения будут отправлены в течении 15 минут. Пользуясь этими допущениеми и знанием того, что в результате операции PUT объект попал в первые два хранилища, мы можем с большой вероятностью допустить, что в первые 15 минут этот объект будет именно в первых двух хранилищах, а спустя 15 минут он уже будет во всех хранилищах. В 0.1% случаев можно просто откатиться к полному опросу всех хранилищ.

Таким образом, кэшу-свидетелю достаточно держать в оперативной памяти расположение всех измененных за последние 15 минут объектов (про сам объект больше знать ничего не нужно). Откуда он узнает эту информацию? Те же PUT-роутеры ему ее сообщат. Откуда кэш-свидетель узнает про нереплицированные объекты при холодном старте? Запросит список нереплицированных объектов непосредственно из хранилищ. По сути, кэш-свидетель становится эдаким роутером для запросов чтения, перенаправляя запросы чтения к хранилищу с наиболее актуальной версией объекта.

Поскольку опираться на единственный кэш в GET запросах слишком ненадежно, то их можно выполнять из нескольких кэшей, аналогично избыточности PUT-роутера.

Здесь красным показан путь PUT запроса, оранжевым — асинхронная репликация, зеленым — GET запросы, выполненные до завершения асинхронной репликации.

Эта модель по гарантиям и характеристикам производительности уже очень сильно похожа на Amazon S3:

1. Оптимизирована для чтения единичного объекта (цены запросов чтения S3 примерно в 10 раз ниже запросов записи и запросов списка объектов, Amazon S3 pricing );
2. При отсутствии отказов/перегрузки серверов и сети можно достичь 100% согласованности объектов по read-after-write, monotonic reads, и monotonic writes;
3. При потере связи пары серверов с остальными хранилищами и PUT-роутерами, GET-кэш-роутер может просто выдавать старые версии объекта, причем, в большинстве практических случаев не более старые, чем те, которые недавно были выданы и уже находятся в кэше (monotonic reads consistency). При этом операции записи на отделившихся серверах будут завершаться с ошибкой таймаута;
4. Серьезные сбои с нарушением механизма репликации и оповещений приведут к потере гарантий согласованности данных. В терминах теоремы CAP это что-то ближе к AP (availability when partitioned).

Хочу обратить особое внимание на последний пункт. Грамотное администрирование и эксплуатация собственных глобальных сетей на примере гугла показали, что можно гарантировать бесперебойность каналов связи. Как говорится «не пойман — не вор», то есть, «нет отказов — значит, наша система отказоустойчива». На эту тему мне вспоминается Фукусима, для которой делали оценку не более одной аварии в тысячу лет — правда, эта оценка не упоминает, в какой именно год из этой тысячи лет произойдет авария. То есть, строго говоря, Amazon S3 не предоставляет 100% гарантий согласованности read-after-write, не дает 100% гарантий оповещения «at-least-once», но Амазон этого и не скрывает, и по факту конкретно ваша фирма вряд ли когда-то столкнется с этим сбоем. Хотя, в 2017 этот самый «раз на тысячу лет» уже выстрелил:
Summary of the Amazon S3 Service Disruption in the Northern Virginia (US-EAST-1) Region

Также на всякий случай уточню, что на протяжении всей статьи я рассматривал работу единственого шарда. Горизонтальное масштабирование возможно разбиением пространства ключей по шардам, и недопустимость сравнения значений sequencer из оповещений S3 по двум разным ключам говорит нам о том, что эти ключи могут происходить из разных шардов, хотя виртуально ключи находятся в одном bucket-е.

По предложенной архитектуре S3 у одного шарда из нескольких серверов производительность и отказоустойчивость превышают таковые у единственного сервера, но они не растут бесконечно. Рост числа серверов в шарде приводит к примерно пропорциональному росту межсерверного трафика для PUT-запросов, хотя при малом числе записей возможно достичь примерно линейного масштабирования по чтениям. Самым сочным вариантом расширения этого шарда явяется увеличение числа хранилищ при неизменном числе кэшей, например, 3-4 кэша и 10 хранилищ, что дает почти линейное масштабирование по чтениям и записям до тех пор, пока ограничивающим фактором не станет асинхронная репликация и зависимые от неё требования к оперативной памяти на кэшах (ведь каждый кэш должен знать место хранения всех объектов, измененных за последние 15 минут).