Pull to refresh

Разбираем ACID по буквам в NoSQL

Reading time 7 min
Views 36K

Мотивация


Ни для кого не секрет, что при наличии сформулированного эвристического правила под названием CAP Теорема в противовес привычной RDBMS-системе класс NoSQL-решений не может обеспечить полную поддержку ACID. Нужно сказать, что для целого ряда задач в этом нет никакой необходимости и поддержка одного из элементов приводит к компромиссу в разрешении остальных, как итог — большое разнообразие существующих решений. В данной статье я бы хотел рассмотреть различные архитектурные подходы к решению задач по частичному обеспечению требований к транзакционной системе.

«A» Атомарность


Атомарность гарантирует, что никакая транзакция не будет зафиксирована в системе частично. Будут либо выполнены все её подоперации, либо не выполнено ни одной

NoSQL системы обычно выбирают высокую производительность не в угоду транзакционной семантике, так как её соблюдение вносит дополнительные затраты на обработку. Многие системы всё же обеспечивают гарантию на уровне ключа или строки(Google BigTable) или предоставляют api для атомарных операций(Amazon DynamoDB), при которой только один поток может модифицировать запись, если вы, к примеру, хотите иметь счётчик посещений пользователя, распределённый по кластеру. Большинство систем придерживаются неблокирующих read-modify-write циклов. Цикл состоит из трёх этапов — прочитать значение, модифицировать, записать. Как видно, в мультипоточной среде есть много вещей, которые могут пойти не так, к примеру, что если кто-то изменит запись между фазами чтения и записи. Основной механизм разрешения таких конфликтов — использование алгоритма Compare and Swap, — если кто-то изменил запись в процессе цикла — мы должны понять, что запись поменялась и повторить цикл до тех пор, пока не установится наше значение, такой алгоритм выглядит более предпочтительным перед полностью блокирующим на запись механизмом. Количество таких циклов может быть очень большим, поэтому нам необходим некий timeout на операцию, по истечению которого операция будет отклонена.

«C» Консистентность


Транзакция достигающая своего нормального завершения и, тем самым, фиксирующая свои результаты, сохраняет согласованность базы данных. Учитывая специфику NoSQL к распределению информации по серверам — это означает — все ли реплики, содержащие копию данных всегда содержат одну и туже версию данных

В силу специфики, современные NoSQL обязаны выбирать высокую доступность и способность к горизонтальному масштабированию кластера, — получается что система не может обеспечить полную согласованность данных и идёт на некоторые допущения в определении понятия согласованности. Различают два подхода:

Строгая консистентность

Такие системы гарантируют, что реплики всегда способны прийти к соглашению об одной версии данных, возвращаемых пользователю. Некоторые реплики не будут содержать это значение, но когда система будет обрабатывать запрос значения по ключу, машина всегда сможет решить, какое значение вернуть — просто оно будет не всегда последним. Как это работает — к примеру у нас есть N реплик одного и того же ключа. Когда приходит запрос на обновление значения ключа, система не отдаст результат пользователю, пока W реплик не ответят, что они получили обновление. Когда пользователь запрашивает значение, система возвращает ответ пользователю ответ тогда, когда хотя бы R реплик вернули одно и то же значение. Тогда мы считаем систему строго консистентной, если соблюдается условие R+W>N. Выбор значений R и W влияет на то, сколько машин должны ответить перед тем, как ответ вернётся пользователю, обычно выбирают условие R+W=N+1 — минимально необходимое условие по обеспечению строгой консистентности.

Возможная консистентность

Некоторые системы(Voldemort, Cassandra, Riak) позволяют выбрать R и W при которых R+W<N. Когда пользователь запрашивает информацию, возможны моменты, когда система не может разрешить конфликт между версиями значений ключа. Для разрешения конфликтов применяется тип версионирования, называемый vector clock. Это вектор, ассоциированный с каждым ключом, который содержит счётчики изменений для каждой реплики. Пусть сервера A, B и C — реплики одного и того же ключа, вектор будет содержать три значения (N_A, N_B, N_C), первоначально инициализированный в (0,0,0). Каждый раз, когда реплика изменяет значение ключа, она увеличивает значение своего счётчика в векторе. Если B изменяет значение ключа, который ранее имел версию (39, 1, 5) — вектор изменит своё значение на (39, 2, 5). Когда другая реплика, скажем C, получает обновление с реплики B она сравнивает значение вектора со своим. До тех пор, пока все свои счётчики вектора меньше чем те, что пришли с B, пришедшее значение имеет стабильную версию и можно перезаписывать свою собственную копию. Если на B и C находятся векторы, в которых некоторые счётчики больше, а некоторые меньше, например, (39, 2, 5) и (39, 1, 6), тогда система идентифицирует конфликт.

Разрешение этого конфликта различается на разных системах, Voldemort возвращает несколько копий значения, отдавая разрешение конфликта на откуп пользователю. Две версии пользовательской корзины на сайте могут быть слиты без потери информации, тогда как слияние двух версии одного редактируемого документа требует вмешательства пользователя. Cassandra, которая хранит timestamp каждой записи, возвращает самое последнее в случае определения конфликта, этот подход не позволяет слить две версии без потери информации, зато упрощает клиентскую часть.

«I» Изолированность


Во время выполнения транзакции параллельные транзакции не должны оказывать влияние на её результат. Здесь так же имеет значение понятие уровней изолированности транзакции

Cassandra, начиная с версии 1.1 гарантирует, что если вы делаете обновление:

UPDATE Users
SET login='login' AND password='password'
WHERE key='key'


то никакое конкурентное чтение не увидит частичное обновление данных(login изменился, а password — нет), причём это справедливо только на уровне строк, которые находятся в рамках одного column family и имеющие общий ключ. Это может соответствовать уровню изоляции транзакции read uncommitted, при котором разрешаются конфликты lost update. Но Cassandra не предоставляет механизма отката на уровне кластера, к примеру, возможна ситуация, когда login и password, будут сохранены на каком-то количестве нод, но недостаточном W для того, чтобы отдать пользователю верный результат, при этом пользователь вынужден разрешать этот конфликт сам. Механизм обеспечения изоляции заключается в том, что для каждой изменяемой записи создаётся невидимая, изолированная для клиентов версия, которая впоследствии автоматически заменяет старую версию через механизмы Compare and Swap, описанные выше.

«D» Надёжность


Независимо от проблем на нижних уровнях (к примеру, обесточивание системы или сбои в оборудовании) изменения, сделанные успешно завершённой транзакцией, должны остаться сохранёнными после возвращения системы в работу. Другими словами, если пользователь получил подтверждение от системы, что транзакция выполнена, он может быть уверен, что сделанные им изменения не будут отменены из-за какого-либо сбоя.

Самым прогнозируемым сценарием сбоя можно рассмотреть отключение питания или рестарт сервера. Полностью надёжная система в данном случае не должна вернуть ответ пользователю, пока не запишет все изменения из памяти на жёсткий диск. Запись на диск слишком долгая операция и многие NoSQL системы идут на компромиссы в угоду производительности.

Обеспечение надёжности в рамках одного сервера

Стандартный диск выдерживает 70-150 операций в секунду, что составляет пропускную способность до 150 Мб/c, ssd — 700 Мб/c, DDR — 6000 — 17000 Мб/c. Поэтому обеспечением надёжности в рамках одного сервера при обеспечении высокой производительности является сокращение числа записи со случайным доступом и увеличение последовательной записи. В идеале, система должна минимизировать число записей между вызовами fsync(синхронизации данных в памяти и на диске). Для этого применяются несколько техник.

Контролирование частоты fsync

Redis предлагает несколько способов для настройки того, когда вызывать fsync. Можно настроить, чтобы он вызывался после каждого изменения записи, — что является самым медленным и безопасным выбором. Для улучшения производительности можно вызывать сброс на диск каждые N секунд, в худшем случае вы потеряете данные за N последних секунд, что может быть вполне приемлимо для некоторых пользователей. Если надёжность совсем не критична, то можно отключить fsync и полагаться на то, что система сама в какой-то момент синхронизирует память с диском.

Увеличение последовательной записи через логирование

Для эффективного поиска данных NoSQL системы часто используют дополнительные структуры, например — B-деревья для построения индексов, — работа с ним вызывает множественные случайные доступы к диску. Для уменьшения этого некоторые системы (Cassandra, HBase, Riak) добавляют операции обновления в последовательно-записываемый файл, называемый redo log. Пока некоторые структуры записываются на диск достаточно редко, лог пишется часто. После падения недостающие записи можно восстановить с помощью лога.

Увеличение пропускной способности группировкой записей

Cassandra группирует несколько одновременных изменений в течение короткого окна, которые могут быть объединены в один fsync . Такой подход, называемый group commit, увеличивает время отклика для одного пользователя, т.к. он вынужден ждать несколько других транзакций для фиксирования своей. Преимущество здесь получается за счёт увеличения общей пропускной способности, т.к. несколько случайных записей могут быть объединены.

Обеспечение надёжности в рамках кластера серверов

Из-за возможности непредвиденных выходов из строя дисков и серверов необходимо распределять информацию по нескольким машинам.
Redis представляет собой классическую master-slave архитектуру для репликации данных. Все операции, связанные с мастером, спускаются до реплик в виде лога.
MongoDB представляет собой структуру, в которой заданное количество серверов хранит каждый документ, причём есть возможность задать количество серверов W<N, описанное выше, которое минимально необходимо для записи и возврата управления пользователю.
HBase достигает мультисерверной надёжности за счёт использования распределённой файловой системы HDFS.

В целом можно заметить некоторую тенденцию современных NoSQL-средств в сторону обеспечения большей консистентности данных. Но всё же пока SQL и NoSQL-средства могут существовать и развиваться параллельно и решать абсолютно разные задачи.
Tags:
Hubs:
+17
Comments 22
Comments Comments 22

Articles