#shark_whitepaper
Буквально вчера меня триггернуло на фразу "CAP теорема — это миф" от интервьювера. В этом посте мы поговорим о том, как вообще эта теорема появилась на свет, что она значит, и немного затронем важность ограничений, при чтении любых работ по Computer Science. Тема очень обширная, поэтому весь рассказ растянется не только на несколько постов, но и на несколько дней.
Началось все в 2000 году, когда Eric Brewer (ныне — VP of infrastructure в гугле) выступил вот с этой презентацией на кейноуте симпозиума по принципам распределенных систем (PODC). Это большая крутая конференция про все распределенное, которая проходит ежегодно уже почти 40 лет. К моменту этого выступления, мир уже оперировал аббревиатурой BASE на равне с ACID, но вот фундаментальный трейд-офф между C — Consistency, A — Availability и P — partition tolerance был объявлен именно здесь (как минимум, так обычно считается в литературе).
В изначальной постановке трейд-офф звучит как "Consistency, Availability, Partition Tolerance. You can have at most two of these properties for any shared-data system". В этой же презентации приводятся примеры всех трех видов систем. В качестве CA систем приводятся Single-site databases и LDAP. Это важное замечание, так как через какое-то время, различные работы придут к выводу, что разделить CA и CP системы довольно сложно. Хотя бы потому что кратковременное отсутствие сети можно моделировать через отсутствие availability и наоборот (Такого мнения спустя 12 лет придерживается как сам автора, так и спустя 10 лет не только автор).
Вторая важная вещь, которая озвучивается в кейноуте — это DQ principle. Вводится он следующим образом:
Data/query * Queries/sec = constant = DQ
Количество данных, получаемых в одном запросе помноженное на количество запросов в секунду является константной величиной для заданной ноды, с заданными версиями операционной системы и версией программы.
Data/query— это сколько корректных данных возвращается из одного запроса,
queries/second— это производительность ака throughput. Здесь надо оговориться, что речь идет про очень большие и распределенные системы, а сам кейноут должен нести практически смысл. В реальных системах часть данных может быть уже внутри системы, но еще не реплецирована на необходимое количество нод, т.е. существует часть данных, которые уже внутри системы, но еще недоступны. Именно поэтому понятие "количество корректных данных" (data/query) имеет значимый смысл.
Данный принцип утверждает, что в рамках работающей системы нельзя одновременно повысить и качество данных (data/query) и количество обрабатываемых запросов (queries/second). Как минимум без изменения программы / ос / сервера. Забавно, что этот трейдофф consistency/throughput/latency будет через десяток лет рассматриваться уже другими учеными, но об этом мы еще поговорим.
Но вернемся к CAP. В презентации утверждение про "возьми 2 из 3" формулируется как теорема, что фактически неверно. Теорема должна иметь доказательство, т.е. правильнее это было бы назвать другим словом, например принцип CAP или гипотеза CAP, как это делают многие последующие работы.