CAP теорема

Часто приходится слышать фразы вроде: "CAP теорема доказана" или: "Это не возможно из-за CAP теоремы". Я решил разобраться, что такое CAP теорема, и что доказано.

Высказывание Брювера

CAP теорема - это утверждение о работе распределенных БД. В 2000 году в своем докладе Брювер сформулировал это утверждение. Оно звучало примерно так.

Не существует распределенных баз данных, в которых бы одновременно выполнялись три свойства:

1. Согласованность (Consistency)
2. Доступность (Availability)
3. Устойчивость к разделению сети (Partition tolerance). То есть устойчивость к сбоям в сети.

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

Формализация и доказательство

Далее вышла очень интересная статья в 2002 году, где высказывание Брювера было формализовано.

1. Под согласованностью подразумевалась атомарность. То есть, если завершилась какая-то операция записи, то операция чтения, которая следует за ней возвращает это новое значение или еще более новое.
2. Доступность. Если запрос поступает в узел, который не вышел из строя, то этот запрос будет корректно выполнен.
3. Устойчивость к разделению сети. Произвольное число сообщений внутри сети могут потеряться.

Далее, невозможность этих трех свойств одновременно была доказана для асинхронных сетей.

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

Доказательство самой CAP теоремы строится очень просто. Рассматривается сеть из двух узлов G1 и G2, между которыми пропала связь. В узел G1 идет запрос на запись, а затем в G2 на чтение. Если выполняется доступность, то будет получен ответ на запрос чтения, но получены будут старые данные, так как между узлами нет связи (не согласованные данные). То есть, либо свойство доступности не выполняется, либо согласованности.

Далее, авторы утверждают, что все же наши сети не совсем асинхронные и рассматривают менее пуританскую модель сети. И почти так же доказывается CAP теорема для частично-синхронной сети.

Частично-синхронная сеть - это модель сети, где каждый узел имеет синхронизированные часы, которые могут показывать разное время, но увеличивают (переключают) время одновременно. То есть каждый узел может узнать сколько времени прошло от одного события до другого и на всех узлах эта величина будет одинаковой. Также каждое сообщение или доставляется за определенное время Tmsg, либо теряется. А каждый узел обрабатывает каждое сообщение за время Tlocal.

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

Что инженеры?

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

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

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

Третье требование могло бы быть сформулировано вероятностно. Например, что вероятность отказа - функция от количества потерянных сообщений среди n подряд идущих во всей системе. И если эта функция O(min[1, 1 / e^(n/2)]), тогда системе устойчива к разделению сети. Где n - число узлов в системе. И это тоже будет формализацией теоремы Брювера.

То есть не доказано, что нельзя создать систему, в которой выполняются требования CA, а требование P выполняется с большой долей вероятности. А если построить такую систему, то можно будет забыть про CAP теорему.

Также CAP тезис может быть неверным в другой модели сети, отличной от сформулированных во второй статье.

Итог

Инженеры часто говорят, что CAP теорема доказана в том смысле, в котором ее сформулировал Брювер, но формализована и доказана немного другая теорема.

Доказанная же теорема, на мой взгляд, сформулирована так, как удобно математикам доказывать ее правоту, но не отражает реального положения дел в прикладном смысле. И не исключена возможность систем, которые в каком-то смысле опровергают исходный тезис Брювера.

Кстати, в следующем посте я расскажу об одной очень интересной распределенной системе.

LRU, метод вытеснения из кэша

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

Интересно, что статья набрала 23 плюса, а в закладки добавило уже 84 человека)

Rework - бизнес без предрассудков

Авторы являются выдающимися в своем деле людьми, основателей 37signals. Сама книжка маленькая и легко читается, мне очень понравилось. Авторы достаточно категоричны, но я с бОльшей частью согласен.

Я даже решил для себя выписать наиболее понравившиеся заголовки:

1. Игнорируйте реальный мир (много скептиков)
2. Значимость обучения на ошибках завышена (учатся на успехах)
3. Трудоголизм (как алкоголизм)
4. Отсутствие времени не оправдание
5. Нарисуйте линию на песке (Видение конечной цели)
6. Вам требуется меньше, чем вы думаете. Принимайте ограничения
7. Начинайте бизнес, а не стартап (т.е. сами зарабатывайте)
8. Создайте половину продукта, а не недоделанный продукт (Качество, а не количество)
9. Принять вызов – значит продвинуться вперед
10. Звучание – на кончиках ваших пальцев (Инструменты не так важны)
11. Перерывы – враги продуктивности (Поток и все дела)
12. Совещания токсичны
13. Не будьте героем (Про работу)
14. Кого волнует, что они делают? (О конкурентах)
15. Будьте хороши для использования в домашних условиях (О продукте)
16. Пройдите за кулисы (Расскажите о своей деятельности)
17. Никто не любит пластиковые цветы (Недостатки могут быть плюсом)
18. Маркетинг – это не отдел (Всё, что вы делаете - маркетинг)
19. Миф о неожиданной сенсации (Success-stories: google, facebook,...)
20. Работают все (Кто не работает, тот не ест)
21. Берите сотрудников на тест драйв (Надо проверить сотрудника в условиях близких к "боевым").

Как нанимать программиста

Больная тема.
В интернете можно найти различный опыт:
Пример обманчивости субъективных оценок
Не нанимайте умных
Советы Пола Грэма

Если первая статья просто занимательная. То вторая скорее сюрреализм. "Надмозги", нанятые автором, создали дерьмовенькую глючную инфраструктуру вместо использования стандартной. Много мозгов для этого не надо. В третьей статье скорее адекватные советы, с которыми в большинстве согласен.

Я тоже задался этим вопросом. Затем я перечислил список критериев, которыми на мой взгляд должен обладать программист. Для каждого критерия предложил способ проверки.

1. Уметь писать код. Да-да, очень многие просто не умеют писать код.
Нужно придумать простую задачку строк на 100. Затем предложить соискателю реализовать ее за час-другой.

2. Умение разбираться в чужом коде. С этим у большинства тоже проблемы.
Вот зачем давать в тестах на c# вопрос, как установить в комментариях ссылку на другой элемент? Лучше включить несколько примеров кода, потребовав разобраться, что он делает. Можно также дать програмку строк на двести с багом, и попросить найти ошибку.

3. Умение учиться).
Это, видимо, надо пытаться понять субъективно.

4. Мозги.
Пара задач на сообразительность не помешают.

5. Все остальные человеческие качества. Лучше отдать hr-ам; пусть делают вид, что нужны-)

Задачка о товарах.

Не так часто в работе можно встретить интересные задачки. А два года назад во времена работы в логистике, мне одна такая попалась. Фактически, заказчик описал алгоритм, и его надо было реализовать:
Пусть есть Q единиц товара. Есть k точек, по которым необходимо распределить товар. При этом точка i может принять не более qi товара. Также заданы пропорции p1, ..pk, по которым необходимо распределить товар. То есть, если нет ограничения qi, то точка i получает (pi * Q)/(p1 + ...+pk) товара(забудем на время об округлении).

Алгоритм распределения товара таков:

1. Найдем одну из точек таких, что qi <= (pi * Q)/(p1 + ... + pk). Тогда положим точке i товара qi и вычеркнем ее из дальнейшей работы (положим k = k -1, Q = Q — qi, удалим qi и pi).


2. Продолжаем шаг 1 до тех пор, пока не перестанем находить такую точку.


3. Каждой из оставшихся точек положим (pi * Q)/(p1 + ... + pk) товара.


3. *. На самом деле в пункте 3 есть проблема с округлением, которую я опустил. Реально же алгоритм может выглядеть так. Положим m = Q mod k. Отсортируем точки по qi. И первые k - m точек получат [(pi * Q) /(p1 + ... + pk)], оставшиеся же ](pi * Q) / (p1 + ... + pk)[. Где [] - округление вниз, а ][ - вверх.

Если реализовывать такой алгоритм, то шаг 1 может повториться k раз (например у точек большой излишек товара). Тогда итоговая сложность такого алгоритма O(k^2).

Можно придумать эквивалентный алгоритм со сложностью O(k * logk). А именно, отсортируем все точки по отношению qi / pi.
Тогда, все точки, которые мы находили на шаге 1, фактически окажутся в начале. И алгоритм привратиться в следующий:

1. Пока qi <= (pi * Q) / (p1 + ... + pk) , аналогично первому шагу пред. алгоритма полагаем товара qi...


2. .Для оставшихся точек выполняем пункт 3*.

Во-первых, несколько слов о корректности исходного алгоритма.

Верно следующее утверждение.

Если точка j подходит под вычеркивание, а вычеркнута точка i, то после этого точка j все равно подходит.
Докажу.
Не умаляя общности пусть i = 1, а j = 2.
Фактически дано q1 <= Q * p1 / P(можем выбрать точку 1), и q2 <= Q * p2 / P (можем выбрать точку 2), надо доказать, что q2 <= p2 * (Q - q1) / (P - p1) (т.е. , что можем выбрать точку 2, после того, как выбрали точку 1).
Действительно, покажем, что Q*p2 / P <= p2 * (Q - q1) / (P - p1). После преобразований получается P * Q - Q * p1 - P * Q + P * q1 = P * q1 - Q * p1 <= 0 (из первого нер-ва).

Утверждение говорит, распределение товара не зависит от того, в каком порядке выбираются точки в пункте 1.

Также верно следующее утверждение.

Пусть точки упорядочены по qi/pi. Тогда если точка i+1 может быть вычеркнута, то и точка i также может быть вычеркнута. Не ограничивая общности, положим i равной 1, а P = p1 + ... pk.

Докажу это простенькое утверждение.
Фактически, дано q1/p1 <= q2/p2 (условие упорядоченности) и q2 <= (p2 * Q) / P (можем вычеркнуть точку 2).
Необходимо показать, что q1 <= (p1 * Q ) / P, то есть что можем вычеркнуть и точку 1.

1. q1 <= q2 * p1 / p2.


2. q1 <= (p1 * p2 * Q) /(P * p2).
   То есть q1 <= (p1 * Q) / P, что доказать и требовалось.

Еще нужно итоговое утверждение об одиноковости вычеркнутых точек.
Утверждение.
Из последнего утверждения и следует эквивалентность алгоритмов.

Интересно, что решение очень простое, а анализ и доказательство заставляют немного подумать.:). Аналитики местные говорили, что пользователи не понимают сложных алгоритмов. И я её когда-то сделал на интуиции(то есть не доказал, но почти понял, что это так).

А вот и не динамика! SRM 453 Div 1 500.

Прикольную задачку решил на днях.
Спортивный турнир, играют N команд. За победу команда получает w очков, за ничью d. Дано, какая команда сколько набрала очков в конце турнира(Points[i]).
Требуется подсчитать минимальное суммарное количество игр, которое должны сыграть команды, чтобы получить такие очки, либо вывести, что такая комбинация очков не возможна.

Обозначим максимально число очков S(в условии задачи не превосходило 10000). Кстати, N по условию не превосходило 50.

Сразу в голову приходит динамика, но я не смог придумать лучше, чем O(N * S * S), что понятно не успевает.
Однако, есть довольно простое и интересное решение.
Наблюдения:
1. Нужно либо максимизировать, либо минимизировать суммарное число ничьих.
2. Пусть D[i] число ничьих, которые сыграла команда i. Тогда конфигурация D[1], ...D[N} ничьих описывает корректный турнир, тогда и только тогда, когда сумма всех элементов четна, и удвоенные максимальный элемент не должен превосходить сумму всех элементов.

Пусть gcd = GCD(d, w); -- GCD = наибольший общий делитель.

Таким образом нам достаточно на начальном шаге D[i] максимально возможным, так что существует число побед W[i] i-й команды, что D[i] * d + W[i] * w == Points[i];

А затем производить итерации, каждый раз делая, пока возможно:
1. Проверяем корректность текущей конфигурации пункты (1 и 2). Если корректна, то обновляем минимально число матчей.
2. Полагаем D[i] = D[i] - w / gcd;

Если каждый раз максимальный элемент выбирать за O(N), то сложность получается O(N * N * S). Что достаточно для решения задачи. Однако, можно поддерживать очередь с приоритетами, и сложность падает до O(N * Log(N) * S). А с помощью двух списков вообще можно сделать за O(N * S).

Как уменьшить число ошибок в программе

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

Меня достали ошибки, которые я делаю в программах. Причем я делаю их и в олимпиадных задачах и в промышленных.

Наиболее известные способы борьбы с ошибками в промышленно программировании:
1. Тестирование (Unit-тесты).
2. Взгляд со стороны (либо сам через какое-то время, либо Code review). Парное программирование сюда же.
3 Знание системы и понимание прикладной области.

Но как быть, если они не спасают? Что, если ошибки проходят? Можно увеличивать качество исполнения этих практик, но важно пытаться уменьшить, а лучше вообще избавиться от ошибок. В олимпиадном же программировании использовать эти практики почти не возможно(первую и вторую в ACM можно, но лучше бы без них).

Возможно ли писать код вообще без ошибок? Конечно нет! Я смотрел скринкасты, того, как программирует Петя Митричев(неоднократный победитель различных соревнований по программированию), он тоже ошибается и отлаживается. Но стремиться к отстутствию ошибок надо, другого пути нет.

Для написания кода как такового без ошибок, видимо важны следущие факторы:
1. Концентрация и внимание. Важно ничего не забыть из мелочей и идей. Например, часто реализуя сложную функцию, после окончания, возвращаешься на уровень выше и забываешь какую-то деталь. Правда, тут может помочь правило "писать сверху вниз", то есть последовательно полностью реализовывать каждый уровень.

2. Въедливость. Очень важное качество, так нелюбимое слабым полом. Всегда должна быть мысль: "а что, если?". Все краевые и нестандартные случаи должны быть продуманы. Иначе, очень обидно, написав сложный функционал, сделать ляп в проходном месте.

3. Вообще, кодерский опыт(то есть те самые ошибки и работа над ними). Ты должен знать свои слабые стороны. Типа забываю проверить на null, деление на ноль, выход за пределы массива, переполнение, опечатки, дублирование и долго-долго продолжаем. Может вести табличку допущенных ошибок?

Вообще, эти же факторы отвечают за качество и тестирования, и code review.

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