Of Code & Men

2021-06-01 08:52:51 Самое начало книги. Смысл предложения прямо противоположный оригиналу.
Открыл книгу, закрыл книгу, пошёл искать оригинальный PDF. Открыть/Комментировать

2021-04-20 14:10:29 Надеюсь, когда-нибудь я всё-таки продолжу писать в этом канале про распределённые вычисления.

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

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

Вступайте в канал, подписывайтесь на подкаст, спорьте с нами. Welcome:
https://t.me/readingtogetherdev Открыть/Комментировать

2020-07-08 13:30:20 Простое доказательство CAP-теоремы. Часть III. Применимость

В отличие от многих других теорем, у этой есть прямая практическая применимость, которую очень легко проиллюстрировать.

1. Если мы запускаем нашу систему (базу данных) на одной машине, где отсутствуют сетевые задержки, то мы можем достигнуть CA. То есть, система всегда будет доступна и консистентна.
Если же наша база данных распределена по нескольким узлам, то чем-то придётся пожертвовать:

2. Допустим мы жертвуем консистентостью (AP). То есть, в предыдущем примере, оба процесса написали, что выиграли. Тогда необходимы механизмы компенсации. К примеру, когда связь установится, мы можем сообщить одному из процессов (например, B), что произошла ошибка и он на самом деле не выиграл. Таким образом мы приходим к согласованности в конечном счёте (Eventual consistency). Хотя процесс B может в таком случае и обидеться.

3. С другой стороны, можно легко привести пример ситуации, когда механизмы компенсации не работают. Например, когда два человека, имеющих доступ к банковскому счёту (100$), пытаются одновременно снять с него по 100$. В этом случае, если их запросы попадут на разные узлы и мы пожертвуем консистетностью, то на балансе будет -100$. Но компенсация в данном случае невозможно, потому что деньги уже на руках у клиентов. Для таких ситуаций придётся жертвовать доступностью (CP) и прерывать операцию, если есть проблемы с сетью.

Я попытался проиллюстрировать все возможные пересечения и области применения на диаграмме.
#distributedcomputing Открыть/Комментировать

2020-07-07 10:21:33 Простое доказательство CAP-теоремы. Часть II. Алгоритм Деккера

На рисунке ниже представлена одна из форм алгоритма Деккера. Как видите, всё очень просто. Есть два процесса A и B, каждый из них пытается напечатать свою фразу, о том, что он победил. За счет использования двух переменных x и y, результатом работы этого алгоритма будет максимум одна строчка. Может быть и ноль. Это в том случае, если оба процесса запишут в свои переменные по единице, потом зависнут на неопределенное время, а потом пойдут проверять, что там у соседа. В таком случае оба условия if будут ложными и не будет не напечатано вообще ничего.

Но это только в том случае, если у процесса A есть доступ на чтение к переменной y, а у процесса B к переменной x.
В случае сетевых проблем (которые обозначены тонкой серой линией), у A нет доступа к y, а у B нет доступа к x, по крайней мере на то время, пока сеть недоступна.
Здесь возможно два поведения системы:
* Процесс сообщает об ошибке и мы приходим к ситуации CP (всё консистентно, но не всегда доступно).
* Либо это ситуация AP, то есть оба процесса завершаются успешно, но при этом будут напечатаны оба сообщения. То есть, система приходит в неконсистентное состояние.‌‎ ‎

#distributedcomputing Открыть/Комментировать

2020-07-06 20:48:59 Простое доказательство CAP-теоремы. Часть I. ReCAP

Сегодня стартовали HydraConf и SPTDC. Как всегда, восхитительно. Словил свежий инсайт, которым очень хочется поделиться. Но для понимания необходимо освежить свои знания в распределенных вычислениях.

Речь пойдёт о CAP-теореме. CAP - это первые буквы слов Consistency, Availability и Partition Tolerance. Суть теоремы для распределенных систем (своими словами): допустим, у нас есть система, состоящая из двух и более узлов, между которыми будут сетевые сбои, а они гарантированно будут. Такая система будет устойчива к прерыванию связи между узлами (Partition Tolerance), но при этом может быть всегда доступной (AP), но не всегда консистентной, либо всегда консистентной (CP), но не всегда доступной.
AC вариант не рассматриваем, потому что наличие сети уже подразумевает букву P.

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

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

#distributedcomputing Открыть/Комментировать

2020-06-04 12:36:47 Карантинное:

Не "уборка комнаты", а "рефакторинг обстановки".
Не "незаправленная кровать", а "низко висящий фрукт".
Не “кот”, а “garbage collector”. Открыть/Комментировать

2020-04-17 15:20:22 Сегодня я хотел бы рассказать про замечательную статью, которая стала вехой в науке о распределенных вычислениях. Статья была написана Эдсгером Дейкстрой в дремучем 1965-ом году. В том же году появились Pink Floyd и Velvet Underground, а в это время Дейкстра ввел в компьютерную науку понятие мьютекса. 

Мьютекс (mutex) - это mutual exclusion, взаимное исключение, механизм, который разрешает только одному участнику распределенного процесса войти в критическую секцию. Что-то уже запутанно, да? Рассмотрим всё по порядку.

Есть набор машин, которые в бесконечном цикле вместе молотят какую-то задачу. Ключевое слово "вместе", значит, им надо иногда синхронизировать свои результаты, например, увеличивать на 1 общий счётчик. Существует вероятность того, что если два компьютера одновременно начнут увеличивать общий счётчик, то часть работы может потеряться. Как это возможно? Операции чтения и записи не атомарны. Сперва необходимо прочитать значение счётчика, потом увеличить значение на 1 у себя в памяти, а затем записать заново. Возможна ситуация, когда два компьютера одновременно читают значение счётчика (допустим, это 5), увеличивают на 1 (у обоих станет 6) и по очереди записывают число 6 обратно. В итоге вместо ожидаемых 7, счётчик будет равен 6.

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

Это весьма нетривиальная задача и с момента её постановки прошло три года, прежде чем Дейкстра нашёл решение.  При этом он наложил ряд дополнительных условий:
• решение не зависит от числа компьютеров N и у них нет никакого приоритета в зависимости от порядкового номера;
• решение не завязано на скорости выполнения задач каждым из компьютеров;
• если один из компьютеров зависнет вне критической секции, то это не приведёт к остановке всего процесса;
• должна соблюдаться живучесть системы, то есть прогресс не должен останавливаться из-за того, что все компьютеры только и делают, что говорят друг другу “После вас!“, “Нет, после вас!”

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

#distributedcomputing Открыть/Комментировать

2020-04-07 18:36:48 Перед тем, как углубиться в предметную область, хочу сперва рассказать о mindmap’е. Disclaimer: всё, что я напишу ниже, это моё весьма субъективное видение области, которое позволяет мне хоть как-то ориентироваться и структурировать знания.

Итак, распределенные вычисления. Как видим на схеме, они делятся на две больших области:
* собственно “вычисления“, которые происходят на одной машине,
* и “распространение знания” в системе из нескольких машин.

У этих двух областей есть своя специфика и свои задачи, но есть то, что их объединяет - это “разделяемая память” или shared memory. По-русски термин звучит не совсем однозначно, мне больше нравится вариант “общая память“, но так уж устоялось.

Shared memory на уровне одного компьютера - это, собственно, RAM или абстракции над ней. В случае нескольких машин - это общее состояние, “знание” системы, распределенное между её частями. Общая концепция shared memory приводит и к общей проблеме - как сделать так, чтобы параллельные вычисления не испортили данные в памяти. (Это то, о чём я писал в одном из предыдущих постов - correctness).

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

#distributedcomputing Открыть/Комментировать

2020-04-03 14:34:33 Всё началось с “Книги с кабаном” Мартина Клеппмана. Я год собирался её прочитать, облизывался, но руки так и не доходили. А в конце 2018 года издательство “Питер” расщедрилось и просто так подарило мне электронную версию. Мои ожидания полностью оправдались. Это оказалась дико крутая и полезная книга, которая просто must read для всех, кто разрабатывает production веб-сервисы.

В книге упоминался Лесли Лэмпорт и его логические часы, а спустя какое-то время пришла новость о том, что в Питере состоится конференция “HydraConf”. И Лесли будет на ней выступать. Да и сам Клеппман тоже! Не посетить это мероприятие было нельзя! Но в итоге я попал только на один доклад конференции. Почему? Вместо неё я записался на школу SPTDC, посвященную распределенным вычислениям, которая проходила параллельно в те же дни, в том же здании и даже по докладчикам пересекалась. В общем, это были два тесно связанных мероприятия, только конференция была рассчитана на инженеров-разработчиков, а школа на студентов и академических исследователей.

Тем не менее, чёрт меня дёрнул зарегистрироваться именно на школу (да еще и коллегу, Мишу Кумачёва, с собой затащил). Знали бы мы, на что идём!.. Теория распределенных вычислений для обычного бизнес-разработчика. Наиболее близкая аналогия - это был интеллектуальный кроссфит. Пять дней абсолютного взрыва мозга. Было чувство, как будто вернулся в университетскую аудиторию и слушаешь академические лекции по темам, в которых не понимаешь практически ничего.

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

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

Чтобы освежить с таким трудом полученные год назад знания, а заодно и поделиться ими, я попробую начать в этом блоге серию статей про распределенные вычисления. Чем вообще привлекательна эта область? Эта наука представляет из себя изящный сплав математики, computer science и практических задач. Теоремы и законы здесь математически формальны и сложны, но всё же поддаются пониманию, а аналогии, которые мы так любим в разработке, весьма необычны и красочны. Вслушайтесь: византийские генералы, обедающие философы, выборы на греческом острове. Прекрасно же!

Часть постов блога уже затрагивала эту тему, но есть смысл сперва рассказать о базовых вещах. Для затравки вот вам картинка моего mindmap’а, как мне субъективно видится эта область. По мере раскрытия разных тем mindmap будет расширяться и дополняться. Ну а пост с описанием того, из чего же всё-таки состоит теория распределенных вычислений, ждите в ближайшее время. Stay tuned!

#distributedcomputing Открыть/Комментировать

2020-03-21 13:10:15 В апреле на русском языке выходит замечательная книга Конрада Кокосы Управление памятью в .NET для профессионалов. Я в составе других участников сообщества DotNetRu участвовал в редактировании перевода. Зачем вообще переводить IT-книги на русский и с какими трудностями мы столкнулись, заслуживают отдельного поста. Надеюсь, в скором времени этот пост появится. А пока хотелось бы немного рассказать о самой книге. Каюсь, я сам до сих пор осилил только несколько глав этого 1000-страничного труда. Но даже то, что я успел прочитать, добавило в мой багаж много ценных знаний. Кстати, книга будет интересна не только DotNet-разработчикам, потому что проблемы работы с памятью актуальны для любого языка программирования.

А еще эта книга замечательный образец того, как относительно просто писать о достаточно сложной теме. Предоставлю слово самому автору:
“Я специально воздерживался от упоминания различных случаев и
источников проблем, характерных для конкретных технологий. Они просто …
ну, слишком характерны для конкретных технологий. <…>
Я очень люблю слова: «Дай человеку рыбу — и он будет сыт один день. Дай человеку удочку
— и он будет сыт всю жизнь». Поэтому все знания, изложенные в этой книге,
все сценарии служат одной цели — научить человека ловить рыбу.”

Одним словом, если у вас появилось больше свободного времени, советую потратить его на чтение этой книги. Открыть/Комментировать