Когда, как и зачем стоит применять теорему CAP

Теорема CAP сыграла большую роль в становлении нового направления развития средств управления данными, в котором отрицаются традиционные технологии управления и которое ассоциируется с термином NoSQL. Тематическая подборка состоит из вводной заметки приглашенного редактора и пяти регулярных статей.

Заметка приглашенного редактора Саймона Шима (Simon Shim) называется «Возрастающее влияние теоремы CAP» (The CAP Theorem’s Growing Impact). В течение долгого времени для операций с вычислительными данными по умолчанию использовались коммерческие реляционные системы управления базами данных компаний Oracle, IBM, Sybase и Microsoft, поддерживающие свойства ACID (Atomicity — атомарность, Consistency — согласованность, Isolation — изоляцию и Durability — долговечность хранения). Однако при наличии феноменального роста объема данных, генерируемых в Сети, на пути применения этого традиционного подхода к хранению данных возникло препятствие.

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

Для того чтобы управлять экспоненциально увеличивающимися потоками данных, компании Google, Amazon, Yahoo, Facebook и Twitter разработали альтернативные решения, в которых данные сохраняются в базах NoSQL. Этот термин ввел в обиход в 1998 году Карло Строцци применительно к базам данных, в которых в качестве языка запросов не используется SQL, а позже Эрик Эванс употребил его для характеристики нереляционных и распределенных баз данных. Указанные компании разрабатывали свои системы NoSQL в рамках проектов open source, и позже они получили широкое распространение для хранения больших массивов данных.

Общей характеристикой систем NoSQL является поддержка гибкой схемы базы данных, горизонтальная масштабируемость и отказ от поддержки свойств транзакций ACID. Для достижения масштабируемости и надежности данные сохраняются и реплицируются в распределенных системах, часто не в одном ЦОД. Для обеспечения устойчивости к разделению сети и снижения задержек при выполнении операций записи данных, в этих системах ослабляются требования к согласованности данных, что позволяет выполнять операции обновления данных асинхронно, а потенциально возникающие конфликты могут разрешаться при выполнении операций чтения. Следовательно, система может передавать пользователям несогласованные значения из распределенных хранилищ данных в зависимости от того, где выполняется операция чтения. Сами пользователи или приложения должны справляться с этой потенциальной несогласованностью.

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

Тематическую подборку открывает статья самого Эрика Брюэра (Eric Brewer) «CAP через двенадцать лет: как изменяются “правила”» (“CAP Twelve Years Later: How the «Rules» Have Changed”). Любопытно, что сам Брюэр впервые написал статью, прямо посвященную придуманной им же в 2000 году «теореме». В течение десятилетия после появления теоремы CAP разработчики и исследователи использовали ее как довод в пользу исследования разнообразных распределенных систем. Движение NoSQL, кроме того, применяло формулировку теоремы в качестве аргумента против традиционных баз данных. В теореме CAP утверждается, что в любой сетевой системе, обеспечивающей хранение совместно доступных данных, одновременно могут поддерживаться не более двух из следующих трех свойств:

• согласованность (consistency) в смысле наличия единственной копии данных, соответствующей последней по времени операции обновления;
• высокий уровень доступности этих данных (high availability) при наличии операций обновления;
• устойчивость к разделению сети (tolerance to network partitions).

Эта формулировка теоремы побуждает разработчиков к применению более обширного набора архитектур систем и архитектурных компромиссов, и действительно, в последнее десятилетие появилось множество новых систем. Значительно вырос и уровень полемики в связи с соотношением ценности согласованности и доступности. Формулировка «два из трех» всегда была обманчивой, поскольку приводила к чрезмерному упрощению взаимосвязей между свойствами. Теперь эти нюансы становятся существенными. Теорема CAP препятствует использованию только крошечной части пространства возможных проектных решений: достижению абсолютных доступности и согласованности при наличии разделения сети, которое возникает редко.

Хотя разработчики по-прежнему вынуждены выбирать согласованность или доступность при наличии разделов, имеются широкие возможности при выборе средств управления разделами сети и восстановления целостности сети после ее разделения. Цель теоремы CAP в современной интерпретации должна состоять в максимизации комбинаций согласованности и доступности, имеющих смысл для конкретных приложений (рис. 1). Такой подход предполагает наличие планов поддержки функционирования системы при разделении сети и восстановлении ее связности, что позволит разработчикам относиться к теореме CAP не как к исторически установленному набору ограничений.

Рис. 1. В начале работы системы данные согласованы и остаются такими, пока не начнется разделение сети. Для поддержки доступности данных разделенные узлы продолжают выполнять операции в режиме разделения, порождая несогласованные состояния данных S1 и S2. Когда восстанавливается связность сети, начинается процесс восстановления данных после разделения. В ходе этого процесса система объединяет состояния S1 и S2 в согласованное состояние S', а также компенсирует все ошибки, сделанные в режиме разделения

Статью «Соображения относительно теоремы CAP» (“Perspectives on the CAP Theorem”) представили Сет Гильберт (Seth Gilbert) и Нэнси Линч (Nancy Lynch). Среди любителей теоремы CAP эти теоретики распределенных систем известны чуть меньше, чем сам Брюэр, — принято считать, что они первыми формально доказали эту «теорему». Почти 12 лет тому назад Брюэр выдвинул идею о наличии фундаментального соотношения между согласованностью, доступностью данных в распределенной системе и ее устойчивостью к разделению сети. Это соотношение, называемое теоремой CAP, с тех пор широко обсуждается. Интерес к теореме частично объясняется тем фактом, что она иллюстрирует более общее свойство распределенных систем — невозможность одновременно гарантировать безопасность и живучесть ненадежной распределенной системы. Если говорить неформально, алгоритм является безопасным, если при его выполнении не может произойти что-либо плохое. Согласованность в смысле теоремы CAP является классическим свойством безопасности: любой ответ, возвращаемый клиенту, считается корректным. В отличие от этого, алгоритм является живучим, если при его работе когда-либо происходит что-либо хорошее. Доступность является классическим свойством живучести — на каждый запрос когда-либо поступает ответ. Наконец, система может быть ненадежной во многих отношениях, допуская поломки, потерю сообщений, подвергаясь зловредным атакам и т. д. Теорема CAP — это лишь один пример одновременной недостижимости согласованности и доступности в ненадежных системах.

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

Автором статьи «Компромиссы, связанные с согласованностью, в современных распределенных системах баз данных» (“Consistency Tradeoffs in Modern Distributed Database System Design”) является Дэниел Абади (Daniel Abadi). Хотя исследования в области распределенных систем баз данных (distributed database system, DDBS) ведутся уже несколько десятилетий, в индустрии DDBS начали использоваться недавно, и для этого имеются две основные причины. Во-первых, современным приложениям приходится работать со все возрастающими объемами данных и большим числом транзакций в единицу времени, что вызывает потребность в гибко масштабируемых базах данных. Во-вторых, повышающийся уровень глобализации и увеличение темпов бизнеса приводят к необходимости размещать данные поблизости от клиентов, которые распределены по всему миру. Примерами DDBS, созданных в последние 10 лет и ориентированных на достижение высокого уровня масштабируемости иили повсеместной доступности, являются SimpleDB/Dynamo/DynamoDB , Cassandra, Voldemort , Sherpa/PNUTS , Riak, HBase/BigTable , MongoDB , VoltDB/H-Store и Megastore .

DDBS — это сложные системы, и конструировать их нелегко, поэтому будет кстати любое средство, помогающее разработчикам найти компромиссы при создании DDBS. В частности, теорема CAP оказалась исключительно полезной разработчикам для обоснования предлагаемых возможностей системы, а также помогала разобраться в маркетинговой шумихе вокруг многих коммерческих СУБД. Однако с того времени, когда было представлено первое формальное доказательство теоремы CAP, ее все хуже понимали и все менее правильно использовали. Например, многие разработчики приходили к неверному выводу, что теорема накладывает определенные ограничения на возможности DDBS при нормальном функционировании системы, и поэтому реализовывали DDBS с неоправданно ограниченной функциональностью. На самом же деле теорема устанавливает ограничения только при наличии некоторых видов сбоев и не ограничивает возможностей системы в режиме нормального функционирования.

Тем не менее имеются фундаментальные ограничения, влияющие на возможности DDBS при ее работе в нормальном режиме, и эти ограничения сказались на различных проектных решениях при разработке известных систем. Одно из таких ограничений состоит в том, что потребность в компромиссе между согласованностью и временем реакции системы влияет на архитектуру DDBS в большей степени, чем ограничения теоремы CAP. Более полную картину компромиссов, связанных с согласованностью данных, можно получить, заменив CAP на PACELC: если имеется разделение сети (partition), то приходится жертвовать либо доступностью (availability), либо согласованностью (consistency); иначе (else), если система функционирует нормально, то приходится жертвовать либо временем реакции (latency), либо согласованностью данных (consistency).

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

Автором статьи «CAP и управление данными в облаках» (“CAP and Cloud Data Management”) является Раджу Рамакришнан (Raghu Ramakrishnan). Относительная простота поддержки типовых операций над данными в приложениях управления данными в Web приводит к появлению систем, которые обеспечивают баланс эффективности запросов на выборку и транзакций, изменяющих состояние данных, для эффективной поддержки масштабируемости, гибкости и высокого уровня доступности. Точка зрения, выраженная в данной статье, основана на опыте автора по разработке платформы управления данными PNUTS (Platform for Nimble Universal Table Storage) компании Yahoo, находящейся в эксплуатации с 2008 года. В 2011 году на основе PNUTS работало более 100 приложений, поддерживающих основные потребности компании. Платформа и приложения выполняются на тысячах серверов, разбросанных по 18 географически разнесенным ЦОД, причем число приложений и объем нагрузки быстро возрастают.

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

Последнюю статью тематической подборки под названием «Преодоление ограничений теоремы CAP с применением репликации с гибкими состояниями» (“Overcoming CAP with Consistent Soft-State Replication”) написали Кеннет Бирман (Kenneth Birman), Дэниэль Фридман (Daniel Freedman), Ки Хуан (Qi Huang) и Патрик Доувелл (Patrick Dowell). Главным следствием теоремы CAP является то, что в любой службе, основанной на репликации данных, могут поддерживаться только два из этих трех свойств. Для доказательства теоремы исследователи выбрали сценарий, в котором такая служба вынуждена выдавать ответы на конфликтующие запросы при потере связности территориально распределенной сети, когда не менее чем в двух несвязанных центрах данных хранятся копии одних и тех же данных и в период утраты связности сети в службу поступают операции обновления этих данных. Узлы, содержащие реплики данных, отвечают на запросы, не будучи информированы о наличии конфликта, и в результате возникает несогласованность данных, которая может ввести в заблуждение конечных пользователей.

Однако бывают важные ситуации, когда разработчики облачных систем полагаются на подходы к репликации данных или сервисов, к которым не применимы существующие доказательства теоремы CAP. В статье обсуждается один из таких случаев: масштабируемый сервис, выполняемый на первом уровне единственного ЦОД. В сегодняшних ЦОД используются сети с резервированием, в которых почти никогда не образуются несвязные разделы: от соответствующего сервиса не требуется устойчивость к разделению сети. Тем не менее многие разработчики облачных приложений опираются на общую форму теоремы CAP, полагая, что масштабируемость и гибкость несовместимы с поддержкой строгих видов согласованности.

В статье исследуется новая форма согласованности данных при наличии их репликации при использовании одного центра обработки данных. В модели сочетаются соглашения о порядке выполнения операций обновления и некоторая разновидность долговременного хранения, которую авторы называют «избавлением от амнезии» (при наличии n реплик данных приложение не забывает об операции обновления, пока в рабочем состоянии находится хотя бы одна реплика). Эксперименты показывают, что предложенный подход обеспечивает масштабирование и в целом работает на удивление хорошо.

Вне тематической подборки опубликованы еще две крупные статьи. Статью «Информационная безопасность: новые технологии и старые принципы?» (“Information Security: New Threats or Familiar Problems?”) написал Гэри Кесслер (Gary Kessler). Трудно считать защиту информации новым понятием, но для тех, кто вырос в эпоху Интернета, сложно воспринимать любые аспекты информационной безопасности вне контекста битов и байтов. При планировании защиты от атак злоумышленников такая точка зрения является ограниченной. С другой стороны, тем, кто вырос до появления Интернета и обладает большим опытом в области ИТ и обеспечения целостности информации, свойственны более широкие взгляды, позволяющие выходить за рамки защиты информации и обнаруживать шаблоны в действиях злоумышленников, а также выявлять сходство между различными угрозами для безопасности. При таком представлении становится понятно, что подавляющее большинство современных проблем в области защиты (и, вероятно, тех, что появятся в будущем) аналогично проблемам, имевшимся в докомпьютерную и даже дотехнологическую эпоху. Исторический взгляд на состояние дел в сфере информационной безопасности с 60-х годов до настоящего времени подтверждает это утверждение.

Авторами статьи «Защита от уязвимостей Web-приложений» (“Defending against Web Application Vulnerabilities”) являются Нуно Антунес (Nuno Antunes) и Марко Виера (Marco Vieira). В защите современных Web-приложений могут быть бреши, а повсеместная распространенность описаний этих приложений делает их легким объектом для атак, в которых обнаруживаются и злонамеренно используются различные уязвимости. Наибольшие риски и опасности в среде Web вызывают внедрение SQL-кода (SQL injection), позволяющее злоумышленникам изменять SQL-запросы, направляемые в систему баз данных, и межсайтовый скриптинг (cross-site scripting, XSS). В атаках первой категории в некорректно закодированных приложениях вставляются и выполняются команды злоумышленников, что позволяет им получить доступ к критичным данным и ресурсам. XSS-уязвимости возникают, если приложение посылает в браузер данные, поставляемые пользователями, без должной проверки контента.

Хотя отчет организации Open Web Application Security Project за 2009 год показывает увеличение инвестиций на обеспечение безопасности, в исследовании за 2010 год организации NTA Monitor отмечается, что безопасность в Web в действительности уменьшилась по сравнению с предшествующим годом. Уязвимости Web-приложений создают огромные проблемы для компаний и организаций. В соответствии с последним отчетом WhiteHat Security уязвимыми являлись 63% исследованных сайтов, и в каждом из них имелось в среднем шесть неустраненных брешей безопасности. Эти уязвимости порождают и питают теневую экономику, основанную на злоумышленных атаках и похищении данных и ресурсов.

Web-приложениям требуется эшелонированная защита, позволяющая избегать или минимизировать уязвимости. Она основывается на том предположении, что каждая мера защиты может отказать, а безопасность в целом зависит от наличия нескольких уровней механизмов, которые страхуют друг друга от сбоев и отказов. Чтобы снизить вероятность успешных атак, разработчики программного обеспечения должны прилагать специальные усилия для принятия надлежащих мер безопасности. Достижение этой цели возможно только путем применения различных методов и инструментальных средств, гарантирующих безопасность на всех фазах жизненного цикла разработки программного обеспечения (рис. 2).

Рис. 2. Упрощенное представление жизненного цикла разработки программного обеспечения

Всего доброго, до следующей встречи, Сергей Кузнецов, kuzloc@ispras.ru .