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

Сергей Кузнецов

Обзор февральского, 2012 г. номера журнала Computer (IEEE Computer Society, V. 45, No 2, February 2012).

Авторская редакция.
Также обзор опубликован в журнале «Открытые системы»

Февральский номер журнала Computer посвящен теореме CAP Эрика Брюэра (Eric Brewer), сыгравшей большую роль в становлении нового направления развития средств управления данными, в котором отрицаются традиционные технологии управления данными, и которое ассоциируется с туманным термином NoSQL. Я не раз писал о своем отношении к «теореме» Брюэра (см., например, здесь), и не буду повторяться в этом обзоре, где, очевидно, следует излагать идеи авторов статей.

Тематическая подборка состоит из вводной заметки приглашенного редактора и пяти регулярных статей (кроме них, в номере опубликованы еще две больших статьи, к теореме CAP отношения не имеющие). Заметка приглашенного редактора, в роли которого выступает Саймон Шим (Simon S.Y. Shim, San Jose State University), называется «Возрастающее влияние теоремы CAP» («The CAP Theorem’s Growing Impact»).

В течение долгого времени для управления вычислительными данными по умолчанию использовались коммерческие реляционные системы управления базами данных компаний Oracle, IBM, Sybase и Microsoft, поддерживающие свойства ACID (atomicity – атомарность, consistency – согласованность, isolation – изоляцию и durability – долговечность хранения). Однако при наличии феноменального роста объема данных, генерируемых в Web (Винт Серф (Vint Cerf) назвал это явление «лавиной информации»), на пути применения этого традиционного подхода к хранению данных возникло трудно преодолимое препятствие.

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

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

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

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

Тематическую подборку по праву и справедливости открывает статья самого Эрика Брюэра (University of California, Berkeley) «CAP через двенадцать лет: как изменяются “правила”» («CAP Twelve Years Later: How the “Rules” Have Changed»). Интересно, что сам Брюэр впервые написал статью, прямо посвященную придуманной им в 2000 году «теореме».

В течение десятилетия после появления теоремы CAP (по естественным причинам при пересказе статьи Брюэра я не буду брать в кавычки слово теорема – С.Кузнецов) разработчики и исследователи использовали эту теорему (а иногда и злоупотребляли ей) в качестве довода в пользу исследования разнообразных распределенных систем. Движение NoSQL, кроме того, применяло формулировку теоремы в качестве аргумента против традиционных баз данных.

В теореме CAP утверждается, что в любой сетевой системе, обеспечиваюшей хранение совместно доступных данных, одновременно могут поддерживаться не более двух из следующих трех свойств:

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

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

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

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

Статью «Соображения относительно теоремы CAP» («Perspectives on the CAP Theorem») представили Сет Гильберт и Нэнси Линч (Seth Gilbert, National University of Singapore, Nancy A. Lynch, Massachusetts Institute of Technology). Среди любителей теоремы CAP эта пара теоретиков распределенных систем известна ненамного меньше, чем сам Брюэр, потому что принято считать, что они первыми формально доказали эту «теорему».

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

Интерес к теореме CAP частично объясняется тем фактом, что она иллюстрирует более общее свойство распределенных систем: невозможность одновременного гарантирования безопасности и живучести ненадежной распределенной системы. Если говорить неформально, алгоритм является безопасным, если при его выполнении не может произойти что-либо плохое. Согласованность в смысле теоремы CAP является классическим свойством безопасности: любой ответ, возвращаемый клиенту, является корректным. В отличие от этого, алгоритм является живучим, если при его работе когда-либо происходит что-либо хорошее. Доступность является классическим свойством живучести: на каждый запрос когда-либо поступает ответ. Наконец, система может являться ненадежной во многих отношениях, допуская поломки, потерю сообщений, подвергаясь зловредным атакам и т.д. Теорема CAP – это всего лишь один пример одновременной недостижимости согласованности и доступности в ненадежных системах.

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

Автором статьи «Компромиссы, связанные с согласованностью, в современных распределенных системах баз данных» («Consistency Tradeoffs in Modern Distributed Database System Design») является Дэниел Абади (Daniel J. Abadi, Yale University).

Хотя исследования в области распределенных систем баз данных (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 (рекомендуемое произношения -- pass-elk): если имеется разделение сети (partition – P), то приходится жертвовать либо доступностью (availability – A), либо согласованностью (consistency – C); иначе (else – E), если система функционирует нормально, то приходится жертвовать либо временем реакции (latency – L), либо согласованностью данных (consistency – C).

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

Автором статьи «CAP и управление данными в облаках» («CAP and Cloud Data Management») является Раджу Рамакришнан (Raghu Ramakrishnan, Yahoo).

Относительная простота поддержки типовых операций над данными в приложениях управления данными в 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 P. Birman, Daniel A. Freedman, Qi Huang, Patrick Dowell, Cornell University).

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

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

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

Вне подборки о теореме CAP опубликованы еще две крупные статьи. Статью «Информационная безопасность: новые угрозы или знакомые проблемы?» (Information Security: New Threats or Familiar Problems?» написал Гари Кесслер (Gary C. Kessler, Norwich University).

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

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

Полный перевод статьи опубликован во втором номере журнала «Открытые системы» за 2012 г.

Авторами статьи «Защита от уязвимостей Web-приложений» (« Defending against Web Application Vulnerabilities») являются (Nuno Antunes, Marco Vieira, University of Coimbra, Portugal).

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

Наибольшие риск и опасность в среде Web вызывают внедрение SQL-кода (SQL injection), позволяющее злоумышленникам изменять SQL-запросы, направляемые в систему баз данных, и межсайтовый скриптинг (cross-site scripting, XSS) (www.owasp.org/index.php/Category:OWASP_Top_Ten_Project). В атаках первой категории в некорректно закодированных приложениях вставляются и выполняются команды злоумышленников, что позволяет им получить доступ к критичным данным и ресурсам. XSS-уязвимости возникают, если приложение посылает в Web-браузер данные, поставляемые пользователями, без должной проверки этого контента.

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

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

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