-
Канал о прекрасном в мире IT. Вайтпейперы по распределённым системам, БД и всему что с ними связанно. 🦈 По вопросам/советам/предложениям: @aquatir
Введение в семейство алгоритмов Gossip (4/4)
Кажется осталось только поговорить о самом главном... Где, собственно, gossip используется, а где лучше не стоит. Для начала практические применения:
- Распространение обновления данных по сети (data dissemination). Самое банальное и логичное применение. Ещё когда слова gossip не было, эпидемические алгоритмы использовались как раз для распространения данных.
- Создание топологий. Один из интересных подходов — сначала построить по сети случайное дерево, и пускать обновления уже по нему. Наличие фиксированной структуры резко увеличивает скорость сходимости, так как алгоритм фактически может стать детерминированным, вместо вероятностного. В некоторых сетях важно просто иметь более-менее актуальную информацию о топологии, например в сети маломощных устройств, коммуницирующих через какой-нибудь wifi. Для слабых устройств gossip очень хорошо подходит ещё и из-за малого размера сообщений и нагрузок на сеть.
- Мониторинг доступности. Gossip можно использовать для пресловутого failure detection. Вообще мониторинг доступности в распределенных системах — это большая тема, в которой не всё так однозначно. Отложим её до одного из следующих циклов.
- Подсчёт агрегатов. Внезапно, gossip подходит и для поиска сумм, средних и прочих агрегатов. Работает это за счёт немного хитрых алгоритмов и передаваемой в сообщении полезной нагрузки. Снизу приложу статью почитать поподробнее.
- Resource allocation. Gossip можно применять, чтобы отсортировать всё узлы в большой сети по некоторому показателю (например cpu, memory, network). Такая сортировка подходит для решения задачи: «как разделить X задач по Y машинам, чтобы всем хватило ресурсов»
Но не все так гладко. Поскольку gossip «медленно и верно» докатывается до сходимости, есть ситуации, в которых следует подумать о целесообразности его использования:
⁃ Большое количество изменений, каждое из которых распространяется по протоколу. Всё дело в том, что полное распространение происходит за O(log(n)). Если в системе живут одновременно несколько событий, они и распространяются одновременно. Либо сразу все вместе. В первом случае, это много трафика, во втором, сообщения большого размера. И то, и другое — вещи, которых gossip пытается избежать.
⁃ Не подходит для быстрой синхронизации данных, так как сама суть gossip в том, что раунды происходят редко, по сравнению со временем сетевых задержек.
⁃ Любые гарантии в gossip имеют вероятностный характер. Иногда таких гарантий может быть недостаточно, особенно когда важна производительность высоких процентилей задержек.
⁃ Мало информации о том, как gossip работает в системе, предполагающей Byzantine fault. Всё-таки это система, основанная на том, что соседние ноды не пытаются вредить.
⁃ В маленьких сетях с редкой сменой количества участников броадкаст/алгоритмы консенсуса могут работать и быстрее, и эффективнее.
⁃ Если gossip используется в качестве механизма уменьшения энтропии, нужно всегда отдавать себе отчёт, почему энтропия возникла. Бороться нужно с причиной, а не следствием. Gossip подходит как механизм для обхода редких отказов детерминированного алгоритма. Как магическая пуля для исправления любых отказов даже он не справиться.
Источники:
- Про плюсы и минусы: Birman, Ken. 2007. "The promise, and limitations, of gossip protocols"
- Про peer sampling service: Mark Jelasity, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten van Steen. "The Peer Sampling Service: Experimental Evaluation of Unstructured Gossip-Based Implementations".
- Где используется gossip: Kermarrec, Anne-Marie, and Maarten van Steen. "Gossiping in distributed systems."
- Про агрегаты на gossip: David Kempe, Alin Dobra, and Johannes Gehrke. "Gossip-Based Computation of Aggregate Information."
Введение в семейство алгоритмов Gossip (2/4)
Gossip — это не только удивительно полезные, но и достаточно простые алгоритмы. Каждая нода в сети может исполнять один и тот же код обмена, состоящий из двух тредов: активный занимается отправкой данных узлам сети, а пассивный их обработкой.
Работать алгоритмы могут не только в push режиме, когда ноды направляют свои сообщения соседям, но также и в pull, когда узлы наоборот «затягивают» сообщения от соседей. Может быть также и pull-push модель, когда один узёл делает и то, и другое. Очень упрощенно, алгоритм выглядит так:
Активный тред:
1. Выбрать соседний узел
2. Если push
2.1. выбрать сообщения для отправки
2.2. направить в выбранный узел
3. Если pull
3.1. получить сообщения от узла
3.2. обработать сообщения
Пассивный тред:
1. Получить сообщение
2. Если pull
2.1. выбрать сообщения для отправки
2.2. направить в выбранный узел
3. обработать сообщения.
Когнитивные искажения (2/2)
Следующий на очереди у нас selection bias или ошибка отбора. Она заключается в неправильно собранной выборке при измерении статистической величины. Например, если вы в новостях услышали про одного-двух людей, которые заразились коронавирусом после прививки, из-за этого нельзя делать вывод что прививки не работают. Если у ваших друзей сработало решение A, из этого не следует, что вам нужно его повторять. Возможно, стоит найти более репрезентативную выборку. Разновидностью ошибки отбора является ошибка выжившего или survival bias. Люди в интернетах сплошь и рядом рассказывают об успехах, но практически никто не говорит о неудачах. Это создаёт ложную уверенность, поскольку голоса тех, у кого не получилось или тех, кто «не выжил», не попадают в выборку.
Перейдём к спонсору одновременно и токсичных комьюнити, и синдрома самозванца, а именно к ошибке атрибуции или attribution bias. Её суть заключается в том, что некоторым людям при рационализации успехов или неудач других людей более свойственно приписывать эти успехи/неудачи внутренним характеристикам индивида, а не сложившимся обстоятельствам. Почему ваш джун сломал приложение в проде? «Потому что он глупый» — ответ неверный. Любая ситуация состоит из суммы человека и условий, в которых он находится. Стресс, отсутствие понятных инструкций, незащищенная от человеческих ошибок среда — всё это не менее, а скорее более важно, чем интеллектуальные способности конкретно взятого индивида.
Здесь же синдром самозванца. Некоторым людям свойственно занижать свои способности на фоне других людей. Во многом это происходит, потому что успех других воспринимается как следствие их героического характера, силы воли или поля искажения реальности. Ошибка атрибуции заключается в полном игнорировании состояния реальности, которая также имеет влияние на успех или неудачу. Каждая мелочь в многогранном мире, начиная от количества родительской заботы в детстве, заканчивая макроэномической ситуации, влияет на успешность. Исключительных людей, гениев, которые и вправду имеют врожденные способности, единицы по сравнению с остальными.
Напоследок, «утро вечера мудренее» или эффект недавнего, он же recency bias. Из-за этого «искажения», более ранние события или информация воспринимаются как более важные. После долгой и нудной ручной работы всегда хочется потратить дни на её автоматизацию, хотя возможно ручную работу нужно делать раз в год и это нецелесообразно. Или любимый мной процесс ретроспективы. Как много раз вам приходилось придумывать пункты для ретро прямо во время этого ретро? При таком подходе, вы непроизвольно будете считать за более важные самые недавние события. Кстати, если до этого вы не слышали про когнитивные искажения и завтра же попробуйте списать все проблемы на них, это тоже будет проявлением эффекта недавнего.
Consistent Hashing и Akamai Technologies (2/2)
А теперь история. Двое из авторов работы Daniel Lewin и Frank Leighton — основатели Akamai Technologies. Компания делает CDN и security решения. Это Cloudflare/Fastly в мире ентерпрайза. Через них проходит по разным оценкам до 30% всего трафика в мире. Работа датируется 1997 годом и говорит как раз о том, как эффективно раздавать страницы в Интернете. В 1998 году авторы попали в финал конкурса MIT $50к Entrepreneurship Competition (сейчас MIT $100k. Инфляция!), основав в этом же году компанию. Собственно на двух идеях из работы: Random Trees и Consistent hashing, и основана архитектура Akamai CDN.
31 марта 1999 года происходит знаменательное событие для Akamai и для мира. В свет выходят Звездные войны. Эпизод 1: Скрытая угроза. Да ещё и онлайн. «Онлайн» в конце 20 века до появления ютуба значило «Вы можете скачать файл в формате Real Video, QuickTime или AVI и посмотреть на своем ПК». Официальный и эксклюзивный дистрибьютор — apple.com. Собственно, apple.com практически сразу же падает и продолжает лежать недоступным на протяжении половины дня. Но сеть Akamai, которая уже успешно справилась с раздачей более миллиона копий трейлера звездных войн за сутки, продолжает жить. PR скандала не случилось.
01 апреля 1999 года Стив Джобс решает лично позвонить одному из сооснователей компании Paul Segan, но тот принимает звоном за первоапрельскую шутку своих коллег и кладет трубку. На сотрудничество компаний этот инцидент не повлиял.
11 сентября 2001 года трагически погибает один из основателей Akamai и соавторов работы Daniel Lewin. Убит одним из террористов на борту самолёта American Airlines Flight 11, который врезался в первую, северную башню Всемирного торгового центра.
2001 год: консистентное хеширование начинает применяться в первых P2P сетях. В таких сетях нужно чтобы все узлы могли знать, где лежит какой файл. Первые версии, например Napster, хранили такую информацию централизовано, что позволяет легко отключить всю сеть при падении главного узла. Далее ко второму поколению, например сеть Gnutella, появилась идея раздавать такую информацию через broadcast. Это работало пока узлов в сети было мало. Наконец третье поколение P2P сетей, начиная с Chord, уже начали использовать консистентное хеширование. Преимуществом такого хеширования для P2P является то, что не обязательно знать о расположении всех остальных серверов в сети. Достаточно знать несколько, которые находятся рядом. Частично даже современный BitTorrent продолжает использовать consistent hashing.
2006 год: Амазон запускает пока недоступную для широкой общественности Dynamo, которая тоже использует консистентное хеширование для партиционирования и репликации. Цель — хранить максимум информации надежно на простом железе и быстро её раздавать. Это важная веха, так как Амазон через год также публикует вот эту работу (Dynamo: Amazon’s Highly Available Key-value Store).
В дальнейшем consistent hashing стал применяться и в Cassandra, и в Ryak, и в Couchbase, Akka, Gluster, и ещё в десятках других продуктах. Сейчас это одна из базовых структур данных / алгоритмов для построения сетей с частой сменой количества участников.
Epidemic Algorithms for Replicated Database Maintenance (2/2)
Замечательные рассуждения приводятся и об удаление данных при эпидемиях. Недостаточно отправить сообщение "удалить данные", потому что при наличии конкурирующих сообщений с изменениями, эпидемия по обновлению может перебороть эпидемию по удалению. Поэтому приходится хранить death certificate — некоторое сообщение, при получении которого все более старые сообщения можно игнорировать. Эти сообщения нужно хранить какое-то время, но не всё так просто.
Во-первых, выбрать правильное время хранения тяжело, т.к. в большой сети может всегда существовать недоступный узел, при этом недоступным он может быть долго, например дольше времени хранения. Во-вторых, всегда есть вероятность наличия residual узлов, которые вообще не получили информацию об удалении. При этом, существующие сертификаты тоже нужно когда-то удалять, так как они бесполезны, а место занимают.
В таких случаях можно использовать как минимум две техники. Первая — это использовать вместе с эпидемическим алгоритмом дополнительный способ синхронизации. Вторая — хранить death certificate на некоторых нодах в спящем состоянии. Когда такой узел получает обновление для спящего мертвого сертификата, он пробуждает сертификат и запускает новую эпидемию по удалению этого уже, казалось бы, удаленного элементы. Тут мы успешно перейдем к производной первой проблемы — когда удалить спящий сертификат...
Есть и другая сложность. Часть обновлений — это в самом деле легальное "возрождение" ранее убитых данных. Решить её в статье предлагается через заведение второго таймштампа. Один используется при обычных обновлениях, второй для активизации после удаления. Если узел активизирован после таймштампа сертификата, значит сертификат неверен и все узлы, которые одновременно пытаются распространить и удаление и обновление, должны прекратить распространять удаление и вообще уничтожить свой death certificate.
В заключении работы рассматривается, как вообще такие алгоритмы работает в реальных сетях, где узлы находятся на разном расстоянии, но при этом все соединены. Вывод в целом очевиден: эффективнее построить пространственный индекс (spatial index) и ходить по более близким элементам с большей вероятностью, чем по менее близким. При чем пруф есть как математический (который я не понял ¯\_(ツ)_/¯), так и экспериментальный. А вот если взять более необычные топологии сети, например когда узлы соединены в мини-кластеры и лишь малая часть нод общается между кластерами, тут всё становится ужасно как во времени сходимости так и в проценте residual узлов. И если pull-модель ещё как-то справляется, то push-модель при симуляциях может вообще не выйти за пределы одного кластера.
Отзыв на Database Internals
#shark_recommends
Пару месяцев назад тот-самый Martin Kleppmann, автор книжки с кабанчиком, был автором недели в слаке DataTalks (ссылка на слак там же). Это такое интересное мероприятие, когда автор какой-нибудь книжки в основном по data science или ml в течение недели отвечает на любые вопросы участников. На следующей после него неделе рассматривалась книжка Database Internals от Alex Petrov, которая для меня стала настоящим открытием!
Книга поделена на две части. Первая полностью про архитектуру БД, преимущественно о хранении. И это самая подробная таксономизация алгоритмов хранения в базах данных, которая мне пока что встречалась в литературе. Не, я конечно слышал, что там в постгре используется B-tree, но этих самых B-tree оказывается сильно больше, чем 5 видов, так ещё для каждого мешок разных оптимизаций. Забавно как можно каждый день пользоваться БД, при этом иметь очень посредственное представление, как оно там работает... Однозначно рекомендую.
Вторая часть про распределенные системы. Здесь снова больше про алгоритмы, чем про "построение правильных приложений". Вот вам 4 вида Gossip и 6 разных Paxos'ов, разбирайтесь! Благо есть ссылки на все 222 пейпера-источника. Половину из них мы здесь ещё рассмотрим. 💪
Если вы думали, что почитать про распределенные системы после книжки с кабанчиком или просто всегда хотели узнать, как там база данных внутри двигает битики, однозначно читайте, не пожалеете.
Всё есть трейдофф
Трейдофф — решение, в рамках которого одни характеристики рассматриваемой системы улучшаются за счёт ухудшения других. Обычно трейдоффы рассматриваются в контексте технических решений. Например, добавим кеш — получим меньше latency, но больше потребление памяти. Добавим ещё 2 ноды в кластер из 3, получим больше availability, но усложним схождение консенсуса и возможно схватим проблем с консистентностью (CAP, вот это всё). В экономике есть схожее понятие — альтернативные издержки. Это максимальная потерянная выгода из-за принятого решения. Сколько бы можно было заработать, если вместо школы построить торговый центр? А если парковку вместо автомойки?
Трейдоффы — хороший способ ведения дискуссий. Можно спорить до хрипоты в поисках оптимального решения, а можно нарисовать табличку с плюсами и минусами каждого и отталкиваться от объективных фактов и метрик. Здесь правда сразу появятся две проблемы. Во-первых, не все факты объективны, а не все метрики можно быстро собрать. Во-вторых, факторов может быть очень много, так как практически всё есть часть трейдоффа. О некоторых таких факторах мы поговорим.
Рассмотрим ситуацию. Вы штурман в ралли-команде и готовитесь к новому маршруту. У вас много времени на подготовку, но маршрут для вас новый. Вы предполагаете с какой скоростью нужно проезжать разные участки маршрута и составляете на первый взгляд разумный план. Теперь вы мчите на трассе, одно колесо полуспущено, а вместо обещанного гравия на земле песок. По плану нужно лететь на X км/ч, но вы предпочитаете замедлиться, главное — доехать. Трасса не изменилась, но вы приняли разное решение при планировании и на дороге, потому что время на принятие решения и объём доступной информации — два важных фактора в трейдоффах. Можно потратить время и узнать больше о системе, а лишь затем принять решение, либо действовать прямо сейчас. К разработке эти два фактора относятся самым непосредственным образом. Никто не умеет правильно разделять системы на доменные области и вводить правильные абстракции с первого раза. Просто информации не хватит. Сделать сейчас как видно, а потом переделать — не просто разумный шаг, а единственно верный при отсутствии всей нужной информации и времени на её сбор.
Ещё один важный фактор — это сложность системы. Любое дополнение к продукту понижает его понятность, так как разбираться в отсутствующем коде не нужно. Сложность системы вступает в конфликт с несколькими другими факторами. Во-первых, с производительностью. Здесь я лучше Шипилёва не скажу (доклад + расшифровка), обязательный доклад вообще для всех. Во-вторых, сложность находится в конфликте со скоростью внесения дальнейших изменений. Чем труднее разобраться в текущем состоянии, тем сложнее это состояние поменять. Проблема здесь в том, что обе эти характеристики объективно подсчитать практически невозможно. Помогает только опыт и собранные грабли. Отдельно стоит сказать про "давайте всё перепишем с новым подходом". Период времени пока система будет находиться в состоянии между "старым" и "новым" варьируется и часто не заканчивается никогда. В безупречном мире система остаётся понятной и функционирующей даже в промежуточном состоянии, но этого бывает тяжело достичь.
Есть и много других интересных факторов. На каком языке писать? Это зависит и от размера коммьюнити, и от количества кандидатов на локальном рынка труда, и от бюджета, и лишь где-то в последнюю очередь от личных предпочтений, количества фичей и "модности" языка. Что выбрать, новую фичу в продукт или задачу из техдолга? Опять-таки, огромный вагон характеристик в трейдоффе. Финансовые показатели, на которые повлияет фича, время на реализацию, степень риска нестабильности продукта при откладывании техдолга, степень риска, что конкуренты реализуют фичу быстрее. Куда ни посмотри, любое решение — это трейдофф между десятками разных факторов. Только если учитывать все их можно сделать оптимальный выбор. А пока я в трейдоффе между карьерой и психологическим здоровьем выберу второе, и пойду смотреть сериальчики вместо литкода.
Про алгоритмы на собеседованиях
За последнюю неделю, я наткнулся аж на раз и два поста про то, как неправильно большие компании нанимают разработчиков. Истории звучат всегда как под копирку... либо «десять тысяч лет я делаю реальный софт, а меня не берут», либо «задачи непрактичные и бесполезные. Кому нужны ваши алгоритмы». Позиции кандидатов можно посочувствовать, но это скучно, поэтому время вызывать адвоката дьявола.
Начнём издалека. IT системы постоянно растут, обрабатывают все больше и больше запросов-в-секунду и петабайт-в-месяц. Каждые новые x10, а то и х5 клиентов требует рефакторингов, новых подходов, архитектуры. Создание чего-либо с нуля это дорого, долго и никаких гарантий, поэтому по возможности предпочтение отдаётся "проверенным решениям". Зачем писать свою кеш-систему, если можно взять готовую? Для чего думать над корректной асинхронностью, если уже изобрели системы обмена сообщениями?
Подход подкупает логичностью. Возьмём решение, которое у кого-то уже сработало, реализуем у себя. Затем оставим на веки вечные, до тех пор, пока оно справляется с нагрузкой / профилем / объемом данных / и т.д. Естественно все нужные нам параметры замерим. Получается и риски минимизировали, и время на разработку сократили, и еще можно хвастаться, что у нас в стеке +1 модный баззворд. Красота!
Вернёмся снова к компаниям и их собеседованиям. Вы создатель нового успешного стартапа, наняли первых пятерых разработчиков методом... разговора по душам конечно же, как же ещё, ведь вы люто ненавидите алгоритмические задачки на интервью. Проходит несколько месяцев. Теперь в компании уже 50 разработчиков. Проводить собеседования самому становится тяжело, поэтому функция оценки кандидата уходит в команды. Но вот незадача, то наймут короля токсичности, то супер-звезду, которому через полгода надоест, то сэра самозванца (не тот, который синдром, а тот который бездарен в своей профессии) Надо что-то делать...
Начинает создаваться некий формальный процесс найма, цель которого — нанимать более подходящих кандидатов. Как и в IT, этот процесс покрывается метриками от оценки кандидата до среднего времени жизни сотрудника и удовлетворённости своей работой. Появляются пулы вопросов, обязательная culture fit часть, exit-интервью, круговые ревью, в общем используются готовые решения, которые у кого-то уже сработали.
Ваш стартап стал серьёзной компанией. Теперь вы нанимаете по 50 человек в месяц, вы уже мыслите числами и метриками. При вашем текущем подходе только 60% кандидатов выходят на средний уровень производительности команды за 4 месяца. Получается остальные 40% не дотягивают! Возможно, думаете вы, проблема в том, что к нам приходят технически слабо подготовленные специалисты. Ваш Вице-Президент-По-HR советует вам посмотреть на опыт компании "условно-гугл" и давать алгоритмические задачи. Вам эта идея противна, но с ней соглашается совет директоров. Придется делать. Но мы же большая и умная компания, поэтому проведём A/B тест. 80% кандидатов поведём по старому процессу, а 20% по-новому, с алгоритмами.
И о чудо, через полгода замеров оказывается, что из тестовой когорты, которая проходила алгоритмические задачи, вышло на нужную вам производительность за 4 месяца 89% сотрудников. Это на 29% больше, чем ранее, прирост почти в два раза! Вы не верите в алгоритмы, пытаетесь еще одной A/B когорте дать упрощенные задачки, метрика падает до 63%. Следующей даёте 3 дизайн секции и 1 на программирование. Поднимается до 74%, но это не 89%. Да что же такое! Вам самому противно в душе, но цифры говорят, что алгоритмы работают, а остальные подходы не работают.
Вас ненавидят в интеренатах, поносят "не имеющие ничего общего с реальностью" алгоритмические секции. Но почему-то когда процесс найма становится другим, кандидаты нанимаются плохие. Да, ваш процесс раз в месяц отсеивает очередного создателя homebrew (если что, он извинился), да ваш HR бренд в каком-то смысле страдает... Но ведь оно работает. А работает — не трогай. Хочешь поменять — сначала измерь. Только не пытайся доказать, что с алгоритмами статистически и вправду лучше найм, не поверят!
История CAP теоремы (6/6)
Последняя работа, о которой я бы хотел упомянуть, это критика CAP от Martin Kleppman, того самого автора книжки с кабанчиком.
Первая часть посвящена, собственно, разбору CAP из 3 частей. Что не так, что не понятно, где термины даются не четко, и какие из этого всего вытекают проблемы. К концу даже доказывается ряд теорем, очень похожих на CAP, но без двусмысленных формулировок. Эта часть на 100% формальная, и мы её пропустим, но сама терминология и доказательство поразительно лаконичны. Рекомендую почитать, если вам нравится такой формат.
Вторая часть рассказывает про фреймворк delay-sensitivity. Идея заключается в том, что в настоящий момент существует пропасть между теоретическими изысканиями, такими как формальное доказательство CAP теоремы и практическими системами. Например, в современном мире слишком высокая задержка (latency) приравнивается к недоступности сервиса (SLA/O, вот это все). Значит нужно построить такую модель терминов, которая помогла бы разговаривать на одном языке исследователям и разработчикам, при этом покрывала бы реальные кейсы.
Модель выстраивается в 2 этапа. Сначала задаются теоретические нижние границы времени выполнения операций чтения и записи для разных уровней консистентности в зависимости от сетевых задержек (обозначаются здесь через d). Каждый уровень сопровождается ссылкой на доказательство.
- linearizability — и чтение, и запись O(d). Пруф.
- sequential consistency — либо чтение, либо запись O(d). Второе из двух может быть O(1). Пруф.
- casual consistency — обе операции за O(1). Пруф 1, пруф 2.
Следует помнить, что наличие формального доказательства вовсе не обозначает применимость в реальном мире. Например, оказывается что casually consistent хранилище может и читать и писать за константу. Вот только для этого нужно передавать еще мешок данных, по которым можно определить эту самую casualty, что в реальных системах нецелесообразно. Поэтому, в частности, в реальном мире существуют более слабые гарантии, например eventually consistent системы.
А дальше, собственно, идет терминология delay-sensitivity фреймворка:
- Availability следует считать эмпирической величиной, равной проценту успешных запросов от количества общих в период времени. Чуть подробнее про эмпирическое значение availability я писал тут.
- Delay-sensitive — это свойство алгоритма, обозначающее, что ему нужно ждать задержку d пока шаг выполнится. В противоположность ставиться delay-insensitive, которым ждать не нужно. Как пример — запись в мастер может сделаться сразу же, а вот репликация данных в другие ноды минимум за d.
- Network Faults. Должны включать в себя не только полный network partition, но так же и периодические потери пакетов (ака "сеть моргнула") и внезапное превышение средних задержек. Все три показателя важны для реальной системы.
- Fault Tolerance — следует использовать вместо понятия partition tolerance. Алгоритм должен описывать какие ошибки он может пережить (например, потерю менее половины нод), а также что происходит, если лимит ошибок превышен.
- Consistency должен обозначать одну из известных моделей. Слово strong consistency не имеет смысла и лишь усложняет понимание.
Приживется ли терминология, покажет лишь время. Работа молодая, ей едва ли стукнуло 6 лет!
А на этом наш сказ про CAP закончился. Осталось только подвести итог:
- Под словом CAP понимают две вещи. Первая — формально доказанное утверждение, которое практически не имеет применений в реальности. Вторая — набор суждений про вечный трейдофф consistency/availability/latency/throughput/что-угодно-ещё.
- Разделение сети (partition tolerance) — это возможная, но далеко не единственная ошибка, которая может возникнуть в системе. В реальном мире нужно защищаться от всего.
- Доступность (Availability) в литературе и в реальном мире — две в сущности независимые вещи. В работах это "возможность получить результат", в мире — эмпирическая метрика.
- Даже без явных ошибок, в распределенной системе есть трейдоффы, а все эти консистентности и доступности — не бинарные величины, а точки на спектре.
История CAP теоремы (4/6)
Поэтому предлагается решать такие конфликты аж четырьмя способами:
1. После обнаружения разделения сети, не позволять делать часть операций. Дубовый и прямолинейный способ, единственное что, пользователи страдают, а также определить, какие операции опасные, а какие нет для конфликтов восстановления — задача непростая.
2. Собирать отладочную информацию. Например, собирать version vectors, а после восстановления, объединять их в консистентное состояние. В теории хорошо, на практике зависит от того, как долго длится разъединение, и какие операции происходят.
3. Использовать коммутативные и иммутабельные операции, а еще лучше даже conflict-free replicated data types. Проблема в том что не все можно реализовать на CRDT. Особенно тяжело для них выполнять инварианты. Сложить несколько плюсов и минусов баланса — просто. Сложить две разные корзины товаров, как множества тоже просто. Сделать так, чтобы ни одна операция не вывела баланс за нуль — сложно.
4. Вести аудит операций, а затем запускать компенсирующую логику. Подход похож на version vectors, но может быть реализован самыми неожиданными способами. Например, банк может взимать плату за овердрафт, в качестве компенсации за то что баланс уменьшился ниже нуля, если сможет доказать, что это пользовать сам одновременно снял деньги в банкомате и перевел на другой счет.
Как обычно, в реальном мире простых решений нет. Формальные доказательства не спасают, а только заставляются задумываться. Но история CAP теоремы все еще не закончена...
История CAP теоремы (2/6)
Когда же принцип CAP стал теоремой? Это произошло в 2002 году в вайтпейпере под авторством Seth Gilbert и Nancy Lynch. Я очень советую почитать сам вайтпейпер, т.к. доказательство элементарное в рамках тех ограничений, которые задаются для рассматриваемой системы. Если что, то же самое доказательство есть с картинками, тут уж точно все станет понятно (Нет, серьезно, универские доказательства из матана в десятки раз более замудренные, чем то что написано в работе по CAP)
Как известно, когда дело доходил до формальных доказательств, нельзя просто так брать и рассматривать все множество доступных вычислений. Нужно оперировать некими определениями, ограничениями и моделями. В частности в этой работе вводятся следующие ограничения:
- Рассматривается асинхронная модель взаимодействия. Асинхронная это значит 2 вещи. Во-первых, невозможно отличить отказ системы от "тормозов". Во-вторых, любое сообщение может доставляться и обрабатываться неопределенное, но не бесконечное время. В целом первое следует из второго.
- Consistency рассматривается, как атомарность или линеаризуемость. Это значит, что система для внешнего наблюдателя всегда выглядит так, словно она состоит из одного сервера. Более формально, в линеаризуемой системе всегда существует линейная упорядоченность (total order) всех операций относительно единственно-верных часов.
- Partition Toleranse вернее partition (разделение сети) рассматривается как бессрочное разделение.
- Availability. Здесь формулируется как "любая не вышедшая из строя нода должна возвращать корректный результат".
Сама формулировка теоремы следующая:
- Availability
- Atomic consistency
in all fair executions (including those in which messages are lost)
Обратите внимание, что уже на уровне формулировки не учитывается возможность существования CA систем. Формулировка вообще ничего не говорит про "выбери 2 из 3". После этой теоремы, идет еще следствие из нее, в котором говорится, что условие недостижимо даже при отсутствии пропавших сообщений.
Приблизительно здесь заканчивается первая половина всей работы! Во второй рассматриваются менее строгие системы, а именно системы, оперирующие в partially synchronous модели. Это модель, в которой у каждой ноды есть свои часы (не синхронизированные между друг другом). Так вот, в такой системе все еще невозможность обеспечить одновременно availability и atomic consistency в общем случае, но это становится возможно если не потерять ни одного сообщения.
Давайте перейдем теперь к самому интересному... Что же не так с CAP? Ответ выходит прямиком из ограничений, необходимых для доказательства теоремы.
Во-первых, консистентность как линеаризуемость. Это очень жесткое требование, и большинство современных хранилищ данных, в принципе не могут функционировать линеаризуемо.
Во-вторых, разделение сети рассматривается как бессрочное. Большинство современных систем надеются на то что связь когда-нибудь восстановится. Таким образом ограничение теоремы про бесконечные промежутки разделения сети имеет мало общего с реальным миром.
Наконец, в-третьих, доступность. В ограничениях теоремы указывается, что система доступна, когда любая работающая нода отвечает корректно. В реальном мире обычно достаточно, когда какое-то подмножество нод возвращает корректный результат.
Получается, что главная проблема CAP теоремы в целом заключается в том, что модель и ограничения, в рамках которых она рассматривается, практически неприменима для реального мира. Тем не менее эта работа все еще корректна и верна! Неприменима вовсе не то же самое, что неверна. С другой стороны, раз уж она не применима практически всегда, почему вендоры хранилищ данных так любят говорить CP у них или AP? Вот это уже вопрос, на который у меня нет ответа.
На этом пока что все. В следующих постах мы рассмотрим, что нового появилось рядом с CAP за следующие ~ 15 лет после её выхода.
The Calculus of Service Availability
#shark_whitepaper
Сегодняшняя красивая большая пдфка формально не является вайтпейпером, т.к. выпущена не университетом, особо ничего нового не изучает и написана не в две колонки. Тем не менее, я не могу пропустить публикации инженеров гугла (когда рано или поздно их нахожу...), т.к. во-первых, питаю слабость ко всем этим SRE штукам, а во-вторых, емкие, но при этом содержательные тексты — большая редкость.
Итак, в работе кратко рассказывает, чем вообще живут SRE, и начинается все с простой математики availability:
Availability = MTTF / (MTTF + MTTR)
Где:
Availability — доступность. Какой процент времени система может корректно делать свою работу (обрабатывать запросы, перекладывать сообщения, и т.д.)
MTTF (Mean time to failure) — среднее время до отказа. Обратная величина от частоты сбоев.
MTTR (Mean time to repair) — среднее время до исправления. Здесь имеется ввиду время, через которое система придет в свои изначальное корректное состояние. Т.е. недостаточно придумать, как починить, нужно еще и применить решение.
Главная фишка этой математики в том, что из нее можно делать довольно очевидные выводы. Как повысить доступность? Смотрим на уравнение, и видим, что путей всего два:
1. Увеличить числитель, т.е. увеличить среднее время между отказами (MTTF). Делать это можно при помощи более обширного тестирования, более аккуратного деплоя (В рамках rollout policy, если такая есть, к примеру) или уменьшением скоупа отказа: географическая изоляция отказов, шардирование, graceful degradation и т.д.
2. Уменьшить знаменатель, т.е. сократить время на обнаружение и устранение проблемы (MTTR). Как говориться, быстро поднятое упавшим не считается. Здесь помогает настройка мониторинга и алертинга, интеллектуальные системы восстановления и развертывания, а также, что не менее важно, обучение сотрудников и chaos engineering.
Вторая интересная мысль из статьи — доступность сервиса не может быть больше общей доступности всех зависимостей. Если ваша БД лежит 53 минуты в течение года (99.99%), то даже при вашей 100% доступности, 53 минуты в течение года вы тоже будете не работать. Отсюда следствие: доступность зависимостей должна быть больше, чем ваша. Иначе, математика не сходится.
В конце также приводится длиннющий список разных способов повышения доступности. Очень рекомендую почитать всем, но если вы больше по хардкору или не нашли того что искали, то тут бесспорным победителем по полноте и понятности информации будут аж три книги по SRE от гугла сразу. Я советую читать справа налево (снизу вверх, если вы с мобилки).
Ну и самое главное. Как гугл решает свои проблемы — это бесспорно интересно, но может не иметь вообще никакого отношения к вашему продукту.
Maturity модели документации.
#shark_whitepaper
- Вайтпейрпер 1
- Вайтпейперт 2
Есть вбить в гугл "documentation maturnity model" возвращается какое-то немыслимое количество статей и вайтпейперов. Те две, которые я взял в качестве основы, лишь пример. Проблема документации в современных системах, на мой взгляд - это следующий этап развития глобального тренда микросервисной архитектуры, и об этом определенно стоит говорить.
Итак, в чем суть. Мы уже знаем, что микросервисы — это скорее всего будущее разработки программного обеспечения, потому что ни один другой способ разработки ПО не обеспечивает такую простоту скалирования команд, одновременно обеспечивая такой уровень доступность. Вы просто нанимаете еще одну 2-pizza team, и они начинают практически независимо от всех остальных команд приносить полезность. Как минимум так оно должно работать в теории. Но тут есть парочка больших жирные НО. На практике оказывается, что чтобы быть независимым, нужно понимать, что происходит вокруг. Тут на помощь как раз должна приходит документация, но часто ее качество оставляет желать лучшего. Сегодня я постараюсь рассмотреть понятие maturity model, на примере документации программного обеспечения.
Maturity model - это с одной стороны определитель вашего текущего уровня развитости некоторого аспекта разработка, а с другой стороны указатель на то, какие сложности есть на вашем уровне, и какой шаг нужно предпринять следующим, чтобы стать более взрослой организацией. Если речь идет о разработке ПО, их вообще довольно много. Начать можно с CMM, затем плавно перейти к SECMM CMMIВ, в общем, читать неперечитать. В случае с документацией все чуть-чуть проще, можно выделить 5 уровней развитости:
1. Неконтроллируемая / ручная документация. Основные признаки: лишь отдельные люди понимают важность и цели ведения документации. Документация редкая и неполная. Нет ни процесса ни требований к содержанию. Как правило, обновление документации - это индивидуальные усилия, которые происходят не в рамках установленных процессов, а по воле отдельно взятых личностей.
2. Полуавтоматическая / неконсистентная. Появляются стандарты ведения документации, но им следуют еще не все. Появляется возможность автоматического создания части документации (Например, openapi).
3. Полуавтоматическая / конкретная. Появляются правила, когда и в каком объеме нужно вести документацию. Стандарты к продукту документации закреплены, и все их придерживаются (продукт — это как выглядит документация, какие элементы блок-схем используются и т.д.). Появляется возможность связывать части документации между собой через гиперссылки.
4. Автоматическая / статическая. Стандарты к процессу создания документации закреплены, и все их придерживаются. Ключевое различие с предыдущем пунктом - процесс vs продукт. На 3 пункте было важно, чтобы созданная документация отвечала поставленным требованиям. На 4 уровне важность смещается в сторону процесса. Здесь необходимо, чтобы документация создавалась постоянно, при этом соответствовала правилам. Организации на таком уровне могут страдать от чрезмерной документации. Любое действие всегда описывается, но где описывается не всегда понятно, так как поиска по документации, возможно, еще нет.
5. Автоматическая / динамическая / персонализированная. Документация умеет подстраиваться под читателя. Можно выделить лишь те части, которые в настоящий момент интересны. Можно создавать свою версию документации и просматривать историчность изменений. Этот уровень недостижим без специальных инструментов для чтения и поддержки документации. Как правило, они разрабатываются внутри организации. Помимо персонализации, также должны существовать средства поиска по документации.
Что и как с этим делать? Шаг номер 1 — определить текущий уровень. Шаг номер 2 — работать над улучшениями. Здесь важно не прыгать выше головы и не решать проблемы на уровень выше. Если документация пишется хаотично и бессистемно (уровень 1) — сначала нужно систематизировать продукт документации (ур. 2), а лишь потом переходить к уровню 3 — вводить процессы по написанию этой документации
Fault-tolerant виртуалки VMWare (2/2)
Самое удивительно, как много проблем в мире решаются приблизительно похожим метод — записыванием событий в лог. Тут тебе и write-ahead-log в БД и репликация брокеров сообщений и event sourcing и что вообще только не придумаешь!
Ну и кулстори под конец, как я в первый раз увидел битый бинарный лог постгреса и успешно ничего с этим не сделал, а во всем конечно же виноваты неправильные бекапы!
У нас неделю назад на работе внезапно упала на слое разработки (хоть здесь повезло!) мега-виртуалка, на которой жил и мастер кубера, и инстанс постгреса, и кафка, и что там только еще не жило, так как маленький стартапчик, делаем как умеем. Такое большое событие, конечно, заметили, и сразу была вызвана оперативная бригада админов, постановивших, что виртуалка, на которой все это добро жило, умерла и стартовать через рестарт отказывается. ВМ была оперативно поднята из бекапа, все сервисы снова развернуты, и какое-то время все было хорошо... пока не начали происходить аномальные события.
Есть значит какие-то бизнесовые последовательности действий и записей в бд, которые с ними ассоциируются. Например перед заведением человеку карты, он обязательно должен пройти идентификацию, но перед идентификацией, человека нужно завести, как клиента. Стали обнаруживаться пользователя, у которых еще нет клиента, но при этом он уже пытается завести карту. Сначала подумали на ошибки в коде, но этот код не трогался как минимум неделю, с чего бы ему было падать.
Через какое-то время пришла в голову идея зайти в логи постгреса, который нам радостно сообщил, что ядро у вас багованное, обновитесь. Ну и еще ошибки записи в лог файлы 🤔
2021-02-15 14:34:09.543 UTC [45268] ERROR: unexpected data beyond EOF in block 6 of relation base/16384/16642
2021-02-15 14:34:09.543 UTC [45268] HINT: This has been seen to occur with buggy kernels; consider updating your system.
Сделай это за меня! (2/2)
До кучи, кому мало своей некомпетентности, добавим еще 1 бич юных лидов - полный вагон обязанностей в отсутствии полномочий. Вы, конечно, "руководите" коллективом, но можете ли вы повлиять на запрлаты этих людей? Или уволить их всех к чертям? Можно конечно как Жанна д'Арк быть прирожденными лидером и вести всех за собой на чистой харизме и вдохновляющих речах, но когда у вас нет права подписывать документы на отпуск, вы уж конечно извините, но с руководством это имеет мало общего. Доброе слово - это хорошо, но с реальными проблемами иногда хотелось бы справиться пистолетом.
Вот и получается, что лиду нужно бежать со всех ног, чтобы только остаться на месте. Это мы еще не дошли до самого интересного. Смотрите, раз полномочий особых нет, то какая деятельность страдает в первую очередь? Правильно, та, где полномочия больше всего нужны! А это наша цифра 1 - управление процессами внутри команды. Раз мы ей больше не занимаемся, время на эту деятельность равномерно распределяется по другим областям. Насколько этот пункт важнее остальных четырех? Давайте попробуем представить идеальный мир и порассуждать дальше.
Возьмем 5 видов деятельности из поста выше и расставим их в кучки просто ради эксперимента:
Берем 2, 3, 4. Немного общения с коллегами + оба технических навыка. Получаем... синьор разработчика.
Берем 2 и 5. Вся работа - сплошная болтовня. Получаем менеджера!
2, 4, 5 - говорит со всеми и всем помогает, но код сам не пишет... Это же продуктовнер!
Оказывается четырьмя из пяти видами деятельности может заниматься помимо лида еще несколько человек. Получается что главная и основная работа лида, которую не может делать никто кроме этого самого лида - это управление процессом внутри команды! Та самая деятельность, на которую лид забил, так как у него нет возможности ей заниматься из-за отсутствия полномочий! Значит, нужно всего-то дать ему пистолет и все станет хорошо! Но только пока пистолета не было, время на эту задачу уже распределилось по другим задачам. Занавес.
Введение в семейство алгоритмов Gossip (3/4)
Для решения всех этих проблем часто используется абстракция под названием peer sampling service. Идея такая: давайте хранить только некое число c «соседних узлов». Тогда при получении нового сообщения со списком узлов, нужно проводить некую агрегацию двух состояний — того, которое есть на ноде приёмнике и того, которое пришло с ноды передатчика. Наличия ограничения в c также значит, что фраза «отправить случайно ноде» меняет свой смысла. Случайных всего c и из них нужно выбрать какую-то из нод.
Более формально, с peer sampling service алгоритмы gossip разделяются по трём параметрам.
1. Peer selection. Периодически узел берёт из своего списка c одного соседа, с которым он обменяется состоянием. Можно выделить 3 основные способа, как это делается:
--- rand. Выбор случайного узла.
--- head. Выбор самого близкого узла.
--- tail. Выбор самого дальнего узла.
2. View selection. После обмена информацией о соседях, на узле находятся два списка соседей. Один, который был на узле изначально, и второй, пришедший от соседа. Их нужно соединить, учитывая ограничение в c соседей. Делается это тоже одним из трёх способов:
--- rand. Общий список c соседей формируется из произвольных узлов.
--- head. Списки объединяются, а затем остаются только c самых близких к текущему узлу соседей.
--- tail. Списки объединятся, а затем остаются только c самых дальних от текущего узла соседа.
3. View propagation. Определяет алгоритм, которым обмениваются узлы обмениваются информацией. Об этом уже было выше. Есть 3 способа:
--- push. Узел направляет свое состояние соседям.
--- pull. Узел забирает состояние от соседей.
--- push-pull. Объединение двух способов. Например сначала направляет, потом забирает.
Таким образом, работу peer sampling service можно описать кортежем из трёх элементов (ps, vs, vp). Разумеется можно придумать и другие, гибридные алгоритмы для ps и vs, например, но пока нам хватит самых простых. Реальные алгоритмы это к примеру (head, tail, push-pull) или (rand, rand, push).
Тут встаёт логичный вопрос, какой из 27 вариантов самый лучший? Как обычно, самого лучшего во всех ситуациях нет, всё трейдофф и мы обречены на несовершенные решения. Но отдельно взятые сочетания всё-таки выделяются перед другими.
Больше половины алгоритмов можно отбросить сразу, поскольку они стабильно приводят к нежелательным ситуациям:
- (head, *, *). Если выбирать для отправки только ближайшие ноды, в сети узлов будут образовываться кластеры. Это нежелательно, так как кластеры нод менее устойчивы к разделению. К тому же любые не-случайные топологии ухудшают вероятностные гарантии gossip.
- (*, tail, *). Если при отбрасывании нод из списка соседей всегда оставлять только самые дальние, новые ноды попросту не смогут стать частью топологии. Я очень долго думал, почему это так, но всё-таки дошло. Понадобилось всего 2 страницы рисования картинок...
- (*, *, pull). Проблема с этими вариантами очень похожа на первый, но немного по-другому. Модель pull приводит к образованию звездообразных топологий. Такая же проблема с гарантиями, как в первом пункте.
Из хороших алгоритмом можно выделить следующие:
- (*, *, push) хуже со сходимостью, чем у аналогов, но push протоколы лучше всего восстанавливаются при массовых отказах сети. При чём для ненормального математика отказ — это сразу -50% нод или больше. Кстати, процент узлов, при отключении которого практически гарантировано произойдёт разделение сети, ведёт себя в случае со случайными алгоритмами как percolation threshold. Больше математики!
- (*, *, pushpull) в среднем лучше по всем показателям, кроме восстановления при отказах.
- (rand, head, *) создают полное покрытие быстрее и равномернее, чем аналоги. Сеть, построенная такие алгоритмом, сложнее всего располовинить.
- (tail, *, *) немного больше случайности и немного медленнее сходимость чем другие. Но с tail надо быть осторожным, так как например (tail, rand, push) медленно увеличивает количество мёртвых нод, потому что рано или поздно в списке соседей остаются только самые дальние ноды.
Введение в семейство алгоритмов Gossip (1/4)
#shark_whitepaper
Gossip — ещё одно слово, часто встречающиеся в литературе и бложиках на медиуме, которое скрывает за собой бесконечные пласты статей разных умных дядек. В качестве знакомства, я осилил четыре из них, но расскажу о трёх, а по четвертой пройдусь вскользь, так как она оказалась супер специфичной. Исторически, gossip появился из дремучей работы 1987 году про эпидемические алгоритмы, о которой я писал тут. Информация оттуда не нужна, чтобы понять этот пост, но может быть интересно. Пост из четырёх частей, так что устраивайтесь поудобнее. В первой введение, затем описание самого протокола на псевдокоде, далее работа gossip в очень больших сетях и в завершении, практические применения и проблемы.
Семейство протоколов gossip — это специфичный набор алгоритмов по обмену данными в сети узлов. Идея в следующем: пусть каждый узел раз в промежуток времени находит один из случайных соседних узлов и направляет ему некоторое сообщение. Так делает каждый узел, который уже получил обновления. Когда все узлы направили сообщение, завершается первый раунд обмена. Раунды проходят до тех пор, пока обновление «не потеряет актуальность». Сообщения содержат не только полезные данные, но и информацию о сети, которой обладает узел. Если проще — каждая нода направляет список соседей, о которых знает она сама. Если долго передавать такую информацию, рано или поздно все ноды сети будут знать о существовании всех узлов. Удобно. В некоторых вариантах gossip информация о других нодах сети — это и есть вся полезная нагрузка.
Киллер фича алгоритмов именно в случайном выборе соседней ноды. Именно случайность позволят gossip алгоритму работать даже при отказах значительной части сети. Почему используется слово «протокол», а не «алгоритм» определить сложно. Возможно это связано с тем, что исторически gossip использовался как низкоуровневый подход для обнаружения топологий в огромных сетях. Сетевики вообще любят всё вокруг называть протоколами.
Семейство gossip это десятки вариаций очень похожих алгоритмов, поэтому разумно выделить их общие характеристики:
- Периодический, попарной обмен данными между узлами сети.
- При обмене данных передаётся небольшое количество информации. Gossip протокол в идеальном мире не должен съедать всю пропускную способность сети.
- Обмен данными происходит редко. «Редко» в данном случае значит сильно реже чем средние задержки (latency) в сети. Идеальный gossip не создаёт значимой нагрузки на сеть узлов. Это позволяет использовать gossip, как дополнение к другим алгоритмам обмена данными.
- Надежный канал связи не требуется. Более того, новые узлы могут вступать в сеть даже во время работы алгоритма.
- При взаимодействии между узлами A и B, либо один из них, либо оба сразу меняют своё состояние. Кинуть пинг другому узлу это ещё не gossip.
- Соседние ноды выбираются случайным образом. В идеальном мире с равномерно распределенной вероятностью. В реальности правда достичь её всё равно не удастся, об этом тоже ниже.
- Время распространения обновления по всем узлам сопоставимо с O(log(n)).
Обмен данными между случайными нодами приводит к тому, что gossip протоколы дают только вероятностью консистентность. Здесь речь идёт не столько о вероятности того, что система перейдёт в консистентное состояния, сколько о времени, когда это произойдет — большинство вариаций практически гарантированно смогут распространить данные по сети когда-нибудь. В случае с gossip консистентность можно объяснить фразой на подобии «с вероятностью 99%, через 30 раундов каждая нода в сети получит обновления». Так сказать, how eventual is eventually consistent?
Когнитивные искажения (1/2)
Пока настаивается пост про gossip в продолжении этого, поговорим о когнитивных искажениях — устойчивых шаблонах поведения, свойственных для людей в определенных ситуациях. Мне вообще не очень нравится русскоязычный вариант термина, так как «искажение» как будто слово из области Матрицы или путешествий во времени. В английском варианте этот термин звучит как cognitive bias, где bias переводится как предвзятость или склонность. Склонность — не правило. Суть в том, что какая-то часть людей, оказавшись в конкретной ситуации, с большей вероятностью поведёт себя определенным образом. Именно на вас «искажение» может не действовать, но в целом тенденция прослеживается. И конечно никто не пытается объяснить все сложные механизмы человеческого мышления через пару примеров.
«Склонностей» в мире людей бесчисленное множество и мы с ними сталкиваемся каждый день. Рассмотреть их все точно не получится, поэтому я поговорю только о тех, с которыми сам пытаюсь бороться, но всё ещё не умеют. На вики есть замечательная инфографика по теме, кто захочет изучить подробнее или просто залипнуть. А ещё алфавитный список на английской вики.
Начнем с chois-supportive bias или искажения сделанного выбора. В IT постоянно приходится принимать какие-то решения. Они бывают глобальные: на каком языке писать, какое хранилище данных выбрать, кого из двух кандидатов нанять или более локальные, например какой из 3 видов синтаксиса выбрать, чтобы реализовать задачу. При принятии решений применяется разная аргумента от «вот тут дядька на медиуме написал» и пресловутого "best practice" до экспериментов и замеров. «Искажение» заключается в том, что после принятия решения, вся методология летит в трубу. Наш выбор начинает казаться более правильным по необъективным причинам, а вместе с тем, отвергнутый вариант становится менее интересным. Всякий раз, когда на вопрос «почему вы всё не сделали на технологии B, вместо A?» вам хочется поднять голос на человека, остановитесь и задумайтесь, а почему, собственно, не сделали? Если ваш выбор A > B основывался на фактах, то они скорее всего всё ещё верны. Если не основывался, а покричать хочется, то вы столкнулись с искажением. Вам хочется защитить ваш вариант, потому что он ваш, а не потому что он объективно верный.
Вносить изменения в процессы или технологии в IT вообще крайне тяжело. Мало того, что сделанный выбор кажется более верным, так ещё люди в принципе предпочитают оставить всё как есть. Это называется status quo bias. Под эту категорию попадают и допотопное легаси, которое никто не хочет трогать не потому что риски, а потому что так сложилось. И бесконечные алгоритмы на собеседованиях (хотя я пытался их рационализировать). И что самое плохое, процессы в IT. Вам кажется что скрам не работает и ежедневные созвоны не нужны? Попробуйте доказать это ближайшему менеджеру.
Consistent Hashing и Akamai Technologies (1/2)
#shark_whitepaper
Я честно пытался написать привычный tl/dr по работе по консистентному хешированию (Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web), но пока готовился, понял, что интереснее даже не сама работа, а то, как развивался мир после нее. Кому все-таки хочется хардкора, матан начинается с четвёртой страницы и не заканчивается до самого конца. А если вы в первый раз видите словосочетание «консистентное хеширование» то советую посмотреть ссылка один просто хорошая и ссылка два лекция Стенфорда. Матана там нет, я проверил.
Сначала о работе. Идея заключается в том, чтобы выстраивать кеши друг за другом в Random Tree. Каждой странице при помощи случайной равномерной хеш-функции h присваивается некий путь от первого кеша до вершины. Таких функцию несколько, т.е. есть больше чем 1 путь, по которому можно получить страницу. Браузер может вычислить этот путь, выбрав одну из хеш-фунцию. Запрос приходит на первый кеш, и если тот содержит страницу, отдаёт её, а если нет, направляет запрос на следующий кеш. Тот на следующий, на следующий и так до тех пор, пока запрос не доберётся до сервера, где страница уж точно есть. Страница сохраняется в кеше только после того, как кеш увидит запрос этой страницы несколько раз. Здесь важно, что у каждой страницы несколько случайных путей по дереву кешей в зависимости от выбранной хеш-функции. Разные клиенты будут получать разный путь к одной и той же странице, эффективно размазывая её по всему дереву кешей, что позволяет избавиться от перегруженных нод. В работе перегруженные ноды называют swamping. Доказательство того, что такое размазывание работает тоже есть.
Поскольку сеть в целом нестабильная, а нагрузка даже без swamping узлов может расти, нужно как-то добавлять дополнительные ноды в сеть и поднимать старые. Но ведь мы использует хеш-функции для определения пути от первого кеша до сервера. Обычно при изменении размера хеш-таблицы (в нашем случае, при вылете ноды), нужно заново вычислять значение хеш-функции для большинства ключей. Здесь как раз на помощь и приходит consistent hashing. Если использовать консистентную хеш-функцию в качестве функции h ещё на самом первом шаге при выборе случайного пути, можно добиться того, что большая часть случайных путей не будет перестраиваться при добавлении или удалении новых нод из сети.
Epidemic Algorithms for Replicated Database Maintenance (1/2)
#shark_whitepaper
Классическая дремучая работа из 1987 года, когда самыми крутыми компаниями в IT были Xerox и IBM, которая в будущем станет основой для большинства алгоритмов поиска сбоев (failure detection) и уменьшения энтропии (entropy reduction). Благодаря этой работе появится, например целая семья алгоритмов-протоколов с общий названием gossip. Они используются практически везде, где есть необходимость поддерживать несколько узлов, например в Consul, Cassandra, AWS S3 (раскрывают в постмортеме) и в десятках других продакшон-грейд продуктах.
Эпидемические алгоритмы/протоколы так называются не случайно, а в честь особого вида математики, изучающего распространение эпидемий. Да, такая математика тоже существует. Вот например целая книжка по теме, очень актуально. Только в случае с алгоритмами цель — заразить наибольшее количество узлов, а не предотвратить заражение. Эдакий Plague Inc на транзисторах.
Терминология берётся из всё той же математики эпидемий. Узлы сети разделяются на 3 вида:
- susceptible — ещё не получили обновление.
- infective — уже получили и распространяют.
- removed — уже получили и не распространяют.
Задача стоит в том, чтобы распространить обновление по распределенной сети узлов, при этом уменьшить число узлов, которые ни разу не получили обновление, т.е. остались susceptible (такие узлы называются residue). При этом эпидемия должна завершиться за минимальное количество сообщений (traffic), а также алгоритм должен сойтись (convergence) максимально быстро. Сходимость измеряется как по среднему времени, так и по времени между первым и последним сообщением.
Эпидемия начинается с того, что некий узел переходит в состояние infective, и начинает распространять обновления. Их распространение происходит на случайным образом выбранные соседние узлы. После попытки заражения, узел с заранее заданной вероятностью k переходит в состояние removed, т.е. перестает распространять обновления. Эпидемия завершается, когда в сети отсутствуют infective узлы, т.е. все узлы либо уже распространили и перешли в removed, либо никогда не получили обновление и остались в susceptible. Процесс заражения можно разделить по нескольким критериями:
- Blind / Feedback. При blind распространении узел всегда после отправки сообщения проверяет, нужно ли ему перейти в removed. При feedback только если новая нода уже получала обновление. Использование feedback увеличивает трафик, так как нужно вернуть и ответ, но зато позволяет резко сократить процент residue узлов после завершения пандемии.
- Counter / Coin. В общем случае, узел переходит в removed с вероятностью 1/k, т.е. по броску k-гранной монетки. Подход counter значит, что узел не бросает монетку, а отключается только после n отправленных сообщений. Трейдофф здесь между "хранить счётчик" и не хранить. Кажется мелочь, но в системе может одновременно происходить несколько волн эпидемии с разными обновлениями, а счётчик нужно хранить на каждую из них на всех infective узлах, так что накладные расходы могут быть большими. Возможно также использовать и комбинированный подход, когда сначала отсылается n сообщений, а затем узел отключается с вероятностью k.
- Push / Pull. Обычно узлы заражают соседей по push модели, так как рассылают сообщения сами. Можно сделать алгоритм наоборот, когда все узлы сети сами начнут запрашивать сообщения от соседей. При наличии большого количества эпидемий одновременно, это работает даже лучше, чем push (пруфы в статье, спойлер: там матан с производными), но генерирует больше трафика. Оба подхода можно использовать одновременно в push-pull модели.
Вас уже сотня человек! Спасибо всем большое, что читаете, я все ещё радуюсь каждому новому подписчику 🎉
В честь знаменательной даты, распишу план на ближайшие месяцы (годы):
- Запилить сайт. Иногда хочется делать разборы пейперов с картинками, возможно даже с анимашками. При этом закрываться за пейволом медиума ну такое. Это план на долго вперёд, мб к концу года и появится.
- Больше циклов про распределенные системы: как минимум разбор пейперов по алгоритмам failure detection, leader election, а также моделям консистентности и алгоритмам консенсуса. Хочется сделать полезный ресурс в стиле Jepsen, но с дорожной картой по топикам распределённых систем.
- Классические пейперы по базам данных: про ARIES, про B-Trees и прочее.
- Рандомные посты про всё на свете: От мотивации до архитектуры.
- Возможно несколько работ по обучению как науке, т.к. недавно заинтересовался темой.
А и конечно же важный опрос!
Кеширование и TinyLFU
#shark_whitepaper
#shark_recommends
Работы как сегодняшняя (ссылка-клон) не позволяют делать по посту о пейперах раз в неделю, так как информации слишком много. Это исследование настолько открывает границы сознания, что его нужно перечитать несколько раз. Сначала, чтобы восхититься красотой идеи, затем чтобы понять суть.
Для начала отойдём на несколько шагов назад. Когда дело касается "оптимизации доступа", в первую очередь речь идет про техники, рассматривающие идею data locality. Данные "ближе" получить быстрее, чем данные "дальше". В L1 кеш процессора обратиться быстрее, чем в память, а в память быстрее, чем на жёсткий диск. Идея не ограничивается одной машиной, потому что запрос в тот же дата-центр также дешевле, чем в соседний.
Кеширование на уровне приложений — это как правило вынесение части данных в память. Но память не бесконечная, поэтому приходится придумывать алгоритмы инвалидации кеша, т.е. предполагать, какой элемент в кеше наименее полезен и выкидывать его. Про основные алгоритмы можно почитать здесь, но нам интересно погрызть гранит науки дальше.
Логично предположить, что элемент будет полезным, если его скоро вызовут ещё раз, т.е. на временной шкале два вызова находятся близко. Но инсайт заключается ещё и в том, что важность представляет не только расстояние во времени между вызовами, но также и частота этих вызовов. Техники, рассматривающие и оптимизирующие частотные и временные характеристики данных, относятся к идеи time locality по аналогии с data locality.
Нагрузки в реальных системах имеют непредсказуемый характер, а размер кеша ограничен. Какой элемент нужнее, который вызывался только что или который не вызывался давно, но за пару минут до этого был самым популярным по частоте вызовов? Пейпер показывает, приводит бенчмарки, и доказывает, что частота — тоже важный критерий для инвалидации кеша.
TinyLFU (Least frequently used) — это небольшая прослойка перед основным кешом, который может работать, например, на LRU. Её задача контролировать удаление данных в соответствие с частотой их вхождения. Основной кеш предлагает свой вариант, а TinyLFU решает, удалить ли то что предложил кеш или что-то другое. Подсчёт частоты может реализовываться через фильтр Блума с подсчётом или Count-min sketch (CM sketch).
Задача подсчёта частоты сама по себе не решается в лоб, поскольку смотреть просто на количество вхождений нельзя. Данные могут быть сначала очень полезны, но с течением времени их важность падает. Поэтому TinyLFU также использует технику ageing или cooling. Периодически или при достижении определенных условий, вес определенного ключа или набора ключей уменьшается. Таким образом, частота стремится к нулю, если не происходят повторные запросы.
Существует и другая особенность. Часто бывает удобнее все данные класть в кеш и получать только оттуда. Если все записи проходят через кеш, среди них скорее всего будут и одноразовые записи, которые лучше бы вообще не сохранять. Эта идея реализуется через механизм под названием doorkeeping. Смысл в том, чтобы при первом обращении класть данные в обычный LRU кеш, и только если по этим же ключам будут еще обращения, перекладывать их в основное хранилище в памяти. Размер doorkeeping области — параметр конфигурации кеша.
Все эти мысли и техники объединяются в пейпере в алгоритм W-TinyLFU (Window TinyLFU). Он используется в Java библиотеке Caffein. Это уже реализованная идея, опробованная в продакшене, протестированная, как на сгенерированных данных (Zipfian distribution, SPC1-like трейсы. Последнее — некий синтетический трейс для проверки I/O операций. Я нашёл упоминание только здесь), так и на реальных примерах. Алгоритм работает как минимум не хуже любого другого, а чаще немного лучше. Больше бенчмарков есть в самой работе.
Отдельно стоит отметить богатейшую теоретическую базу для этого исследования. Это аж 57 источников! Не каждая книга может похвастаться таким длинным списком. Если всё читать не хочется, основная выжимка, которая включает другие алгоритмы кеширования и инвалидации, представлена в доке Caffein в конце.
История CAP теоремы от формулировки до критики.
> https://telegra.ph/Istoriya-CAP-teoremy-04-03
История CAP теоремы (5/6)
Следующая важная работа для истории CAP это "утверждение" PACELC (произносится pass-elk) под авторством Daniel J. Abadi. Иногда ее называют "теорема PACELC", что совершенно неверно, т.к. сама работа не содержит формальных доказательств, это скорее рассуждения и логические выводы. Исторически она вышла на пару месяцев раньше, чем 12-лет-спустя, но статьи друг от друга не зависят и представляют разные элементы одних и тех же трейдоффов.
Формулировка следующая:
PACELC: if there is a partition (P), how does the system trade off availability and consistency (A and C); else (E), when the system is running normally in the absence of partitions, how does the system trade off latency (L) and consistency (C)?
История CAP теоремы (3/6)
Продолжаем наш рассказ. Следующая важная веха вокруг CAP теоремы случилось аж спустя 12 лет с момента первой презентации. Автором этого огромного поста снова стал Eric Brewer. Забавно, что факт доказательства теоремы им практически полностью игнорируется. Но с другой стороны, оно и понятно, потому что у CAP есть 2 жизни. Первая — это формальные доказательства, задача которых задать верхнюю и нижнюю границу возможного. А второе — это реальные системы, в которых существуют реальные трейдоффы. Им и посвящен этот пост.
Статья начиная с разъяснений, почему нельзя просто так брать определение из теоремы и кричать, что тут у вас AP, а тут CP — настоящие системы слишком сложны.
Во-первых, partition tolerance предполагает, что система знает о разделении. Это, к сожалению, не всегда так. Сеть может разрываться в неожиданных местах, так что для одной части системы некоторая нода недоступна, а для другой части доступна. Более того, независимые части системы в целом могут продолжать работу даже при разделении сети. Возьмем, например, сервис такси в Северной Америке и Европе. Всегда ли необходимо наличие связи между ними? Скорее всего нет, так как никто не будет вызывать такси из Вашингтона в Амстердам. При этом эти 2 части могут продолжать обрабатывать запросы, даже когда сети между ними нет.
Во-вторых, разделение сети — далеко не единственная возможная проблема. Система вполне может потерять и доступность, и консистентность после неудачного релиза. А для некоторых систем недоступностью будет слишком высокие задержки, хотя запросы все еще будут обрабатываться (например, биржевые роботы). Строго говоря, консистентность и доступность — это не бинарные понятия. Является ли доступной система, которая успешно возвращает 99% данных, а 1% произвольно дропает? С точки зрения формальных определений — нет. С точки зрения стриминг-портала, вполне себе рабочий вариант.
В-третих, чему посвящена основная часть статьи, отказ от консистентности в пользу доступности часто недостижим. Лучше что можно сделать — это отложить момент наступления консистентности. Никто не любит, когда их данные теряются. Как быть?
Для начала, было бы хорошо обнаруживать недоступность между компонентами. Здесь человечество изобрело уже множество подходов от синхронных health чеков с таймаутами (напомню, что формально CAP рассматривается в асинхронной системе. Синхронных операций в такой системе нет) до алгоритмов консенсуса. Следующие шаг — перейти в явный режим работы при разделении сети, а при восстановлении, собственно, провести компенсации.
Звучит хорошо, на практике все не так просто. Чтобы корректно восстановить консистентность, после возобновления сетевой доступности, нужно знать как минимум все инварианты системы. Инварианты — это условия, которые должна оставаться верными в любой ситуации. Баланс не может быть меньше нуля, у пользователя может быть ровно 1 аккаунт, по одному закажу должен быть ровно один платеж и прочие-прочие-прочие ситуации. Знать и учитывать все это сложно. Еще сложнее, уметь корректно разрешать конфликтные ситуации. Пусть за время конфликта один и тот же заказ сначала отменился, а чуть попозже взял и оплатился. Что делать? Поди его там разбери, что хотел сделать пользовать!
История CAP теоремы (1/6)
#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) имеет значимый смысл.
Отзыв на Microservices Patterns.
Книги о том как правильно делать микросервисы у меня часто оставляют двоякое ощущение. Здесь тебе расписывают роскошные easy-to-use hides-complexity решения, но почему об этих решениях редко говорят на конференциях матерые инженеры... Не считая CEO компаний, которые делают IT продукты для микросервисов (как автор!) или консалтеров. С другой стороны, опыт поддержки решений в настоящем продакшене после каждой главы непристойно орет: "врёте, сударь!". Нельзя просто взять и решить проблему распределенных транзакций через Саги. Потому что, помимо проблемы технической (как это делать?), есть еще проблема поддержки. Как этот код потом менять? Как объяснить новому человеку принцип работы саги из 10 частей? Наконец, как решать проблемы, когда что-то пойдет не так? И не предлагайте мне тесты и меры предосторожности, если даже вся аутентификация в гугле может сломаться из-за бага, внесенного за пару месяцев до инцидента!
Будем считать, настроение задано. Мне редко не нравятся книги. Обычно я об этом молчу, но здесь молчать невозможно, так как паттерны микросервисов — книга, которая может вас похоронить под сложность системы, которую она предлагает создать! Давайте по существу.
Рассказ начинается с грустной истории девушки Mary — CTO компании по доставке еды Food to Go, день которой был испорчен очередным совещанием на тему, почему разработка опять продолбала все сроки. Проблема имеет глобальный характер, а значит и решать её нужно глобально — переписыванием всего на микросервисы!
В следующих главах речь идет о решении разных проблем в МС архитектуре. Везде есть ссылки на довольно удобный ресурс, где в стиле банды четырех кратко описываются те или иные паттерны. Каждая глава логически состоит из двух частей. В первой приводится теоретическое описание паттерна, его плюсы, а вот минусы почему-то иногда опускаются. Во второй идут примеры на фреймворке автора, который к тому же построен поверх Spring'а. Да, книга называется Microservices Patterns: with examples in Java не случайно. Так как фреймворк один из тех easy-to-use hides-complexity решений, вы вроде можете понять код, но это все равно что читать псевдокод, так как все спрятано под магический DSL. Как оно работает под коробкой остается загадкой. Тем более остается загадкой, как эти примеры кода можно будет использовать у себя.
Немного есть и на тему тестирования микросервисов. Здесь все стандартно, пирамида, моки, кусочек про consumer driven contract. К сожалению, нет ничего про chaos engineering, но зато есть очень много про то что end-to-end это slow и brittle и вообще не делайте их. С этой позицией я не согласен категорически! Но об этом я поворчу в следующий раз. Также есть обзор техник деплоя от "деплоим jar'ик" до "деплоим в кубер".
И наконец глава, которая практически оправдала эту книгу! Глава 13 - refactoring to microservices. Почти в конце книге находится фраза, которая могла бы поменять все мое отношение к этому произведению, если бы она была в начале. Фраза, которая даже не удостоилась фирменной рамочки, как максимально важная мысль!
> You should first try simpler solutions. If, and only if, you still have software delivery problems should you then migrate to the microservice architecture.
Тысячу раз, да! Во-первых, ни одно техническое или организационное решение не имеет смысла, вне контекста проблемы! Во-вторых, любое решение — это компромисс (trade-off). При чем компромисс не только между "здесь у нас такие-то технические свойства, а здесь сякие-то", но также между "время можно потратить на это или на то". Кто из вас с пустым беклогом, пусть первый бросит в нее камень! Между простым и быстрым решением, которое почти решит проблему и сложным и долгим, которое решит её полностью, часто правильным будет первое, а не второе.
А что касается книги, если у вас и так гора опыта и bullshit фильтр выкручен на максимум — смело читайте, не повредит. Листинги можно пропускать. Если вы только знакомитесь с миром микросервисов, начните лучше с Фаулера, а затем переходите к его гайду.
Real Time
Эволюция естественных языков — крайне занимательный процесс. Существует несколько подходов / теорий на тему того, как это происходит. Тут и фактор экономии усилий (зачем нужны лишние буквы?), фактор лени, да и просто устаревание старых терминов. Забавно что в IT этот процесс протекает исключительно быстро.
Я как уже рассказывал немного о той-самой работе Роя Филдинга, о понятии архитектура, которое она вводит, и о том что REST — это не другое название для HTTP API, а полноценный архитектурный стиль, являющийся базой для ни много ни мало стандартов HTTP 1.1 и 2.0. Наверное скоро настанет время рассказать более подробно. Тем не менее, меньше 20 лет понадобилось, чтобы изначальный смысл слова REST забылся, и теперь RESTом (или даже RESTful) зовется любое API, которое используется больше, чем единственный http метод POST и хоть как-то разумно именует url'ы, если урлы вообще есть. Это я еще не вспоминаю про гипермедиа, существование которого является совершенно необходимым условием, чтобы API мог называться REST / RESTful.
Где-то на одном уровне с RESTом по частоте неправильного использования находится и понятие real time. Слишком часто в литературе real time приравнивается к "почти мгновенно", хотя фактически этот термин имеет вообще мало отношения к скорости, а говорит скорее о гарантиях. Сегодня я расскажу что к чем и чем отличаются non real-time системы от soft / firm и hard real time.
Итак, приступим. Понятие real-time зародилось в жутко бородатые годы. Из банальной википедии следует, что самый старый цитируемый источник относится аж к 1965 году! В то время как вы понимаете, проблемы производительности IT систем очень сильно отличались от современных. POSIX тогда еще не было, домашних компьютеров в целом тоже, амазон и гугл обещали появиться через 30 лет и 33 года соответственно. Зато было много разных математиков, которые изучили разные прикольные штуки. Одной из таких штук является создание систем реального времени.
А что если бы мы могли делать системы, которые отвечают строго в рамках заданных временных границ на все запросы к ним, даже при наличии параллельных задач? Т.е. вы пихаете в систему какие-то данные, а она вам говорит "этот запрос я закончу не позже X, а этот не позже Y". Если прямо совсем цитировать википедию, система реального времени — это система, корректность которой зависит не только от логической корректности, но и от времени, когда операция была завершена. Соответственно real-time системы разделяются в зависимости от того, что будет, если не уложиться в заданные временные ограничения:
- Hard real-time системы. Не уложиться в дедлайн == отказ системы. Такие системы часто сочетают в себе механические элементы. Пример: принтер. Лазер должен светить строго в определенный момент. Не раньше и не позже.
- Firm real-time система. Пропустить дедлайн можно... но полезность результата в таком случае равняется нулю. Пример: роботы для высокочастотной торговли. Если решение не принято вовремя — его уже нет смысла принимать. Часто такие системы не включают в классификацию, так как есть еще и третий вид.
- Soft real-time системы. При пропуске дедлайна, наблюдается деградация полезности результата. Деградация при этом может быть довольно стремительная. Не получил вовремя GPS сигнал — скорее всего старый сигнал можно не ждать, так как его полностью заменит новый, но совсем небольшие опоздания в принципе допускаются.
Так вот, главная задача системы реально времени — это не высокая производительность, а постоянное время ответа. Загрузил 10 запросов, получил 10 ответов через 10 секунд. Загрузил 10000, получил 10000 через 10000 секунд. Поэтому для их реализации используются немного другие операционные системы (другая реализация шедулера задач) и немного другие библиотеки. И хоть супер-быстрый-реактивный сервис на вашем любимом языке и вправду летает, называть его системой реального времени, скорее всего не совсем корректно. А если корректно — для этого нужно показывать график с плоской чертой latency в любом процентиле, а не throughput.
Fault-tolerant виртуалки VMWare (1/2)
#shark_whitepaper
Идея создать хештег про вайтпейперы у меня была давно, т.к. их количество в reading list уже перевалило штук за 30, и каждую неделю увеличивается еще на 2-3. Попробую раз в неделю рассказывать вам о какой-нибудь новой или старой (или очень старой...) работе, которая как максимум может быть полезна в современном мире. Или как минимум почешет ту самую мышцу, из-за которой мы зачем-то продолжаем постоянно читать про про новые языки, фреймворки и все такое прочее.
Итак, сегодняшний вайтпейпер - The Design of a Practical System for Practical System for Fault-Tolerant Virtual Machines Fault-Tolerant Virtual Machines https://pdos.csail.mit.edu/6.824/papers/vm-ft.pdf
О чем: как VMwar делают fault-tolerant репликацию ВМ.
В чем вообще беда: традиционно репликация ВМ делается через копирование состояния CPU, памяти и I/O девайсов. Если часто идут сигналы - нужно много копировать, а это большой сетевой канал. Вот было бы здорово, если бы можно было копировать, но при этом не съедать на это весь канал.
Оказывается, эту проблему можно решить, если рассматривать ВМ, как конечный автомат. На вход основной ВМ подаются сигналы, она изменяет свое состояние, а также записывает их в некий logging channel. Эти сигналы читаются второй ВМ, обрабатываются, и если результат работы детерминированный, то обе ВМ оказываются в идентичном состоянии. Такой подход в статье зовется Deterministic Replay. Помимо этого также необходимо задерживать ответный сигнал основной ВМ, пока дополнительная ВМ не увидит его в логе (Output Rule). При этом, так как выходной сигнал – это асинхронный I/O, в целом нет необходимости блокировать всю ВМ на время репликации, хотя при сильных задержках такая необходимость может и возникнуть.
Все еще остается проблема недетерминированных операций, таких как вычитывание времени дня, но такие кейсы можно выделить и решать в индивидуальном порядке. Ну и конечно, еще нужно подумать о том, как одна ВМ будет сменять другую. Поэтому нужно добавить хардбиты между основной и репликой, чтобы знать когда упало и научиться брать через любимый test-and-set значение свойства "я основная ВМ", чтобы можно было передать управления (fault tolerant должен предусматривать fault!).
Сделай это за меня! (1/2)
Большую часть времени руководить чем-то или за что-то отвечать довольно весело. Можно влиять на процессы вокруг, видеть
явный эффект от своей работы, помогать людям развиваться и достигать своих целей. Но у меня почему-то постоянно горит от этой деятельности, так что зумерам и не снилось! Полотно ниже - рефлексия на тему "что не так с миддл-менеджментом aka лидством в IT".
Во-первых, про миддл менеджмент. Будем рассматривать лида первого уровня, вся команда которого состоит из individual contributor'ов - программистов / тестировщиков / аналитиков и т.д. Возможно у больших дядь с лидами в подчинении боль уже совершенно другая, тут уж я не в курсе.
Во-вторых, постараемся определить, чем вообще занимается лид. Тут мы сразу обнаружим первую проблему, потому что ответить "всем" - это правда и неправда одновременно.
Навскидку, поле деятельности лида состоит минимум из 5 вещей:
1. Управление процессами внутри команды. Деятельность, направленная на то, чтобы вверенная или набранная команда работала эффективнее и более прогнозируемо. Вообще не имеет ничего общего с технической работой условного синьора. Абсолютно другой набор навыков, практик и подходов.
2. Внутренние коммуникации. Здесь имеется ввиду коммуникация с соседями - аналитиками, тестировщиками, фронтендерами для бекенда и наоборот. В общем, с людьми которые уже не команда, но еще и не очень далеко, чтобы общаться по почте и на Вы.
3. Непосредственный вклад в основную деятельность команды. Для разработчика - писать конфиги и код, для тестировщика - тестировать. То чем когда-то занимался лид, который раньше был миддлом или сеньором. То чем он бы хотел заниматься побольше, но ситуацию часто бывает против.
4. Опосредованный вклад в прогресс команды и компании. Сюда относится крайне полезная, но НЕ основная деятельность, которая помогает эту самую основную деятельность выполнять лучше. Это может быть и написание документации, и разбор инцидентов с продакшона, и написание библиотек, и выкорчевыванием требований из головы заказчиков.
5. Внешние взаимодействия. Например, общение с провайдерами какого-то там вашего сервиса SMSок или с инженерами компании-партнера. Сюда же можно отнести то что вроде как пункт номер 2 - общение с людьми из одной копании, если оно происходит долго через почту, без сроков и гарантий, и в особенности на Вы!
Это мы все еще только идем к проблеме, осталось чуть-чуть! Можно ли заниматься всеми ими? Да не вопрос! Эффективно? Вот тут уже начинаются проблемы. Из этих видов деятельности что-то похожее между собой имеют только 3, 4, так как это по большей части "техническая экспертиза" и 2, 5, так как это про общение с человеками, работу с ожиданиями и договоренности. Получается чтобы эффективно делать все, нужно разбираться минимум в 3 областях знаний - что такое процессы и как ими управлять (1), обладать хардскилами (3-4) и уметь говорить с людьми и получать от них то что хочется (2, 5).
Проблема здесь, как и практически во всем, что связано с людьми, заключается в неоправданных ожиданиях. Приходит, значит, к нашему юному лиду его начальник и говорит: "сделай это за меня!". Не прямо такими словами, конечно. Формулировки варьируются от "пожалуйста, займись <... вот этим ...>" до "а чейта еще ничего не сделано по задаче <... в трекере нет, слышу в первый раз ...>". С одной стороны угроза жизни важная задача, с другой стороны - несостоятельность и в половине видов деятельности, которыми нужно заниматься. Хорошо быть разработчиком, страдать с мнимым синдромом самозванца, когда от тебя ничего кроме пары коммитов в день и не требуют. Жизнь лида же - это как жизнь волка из советской игры, где из 4 разных труб падают яйца, при чем все яйца совершенно разного размера и формы (разные виды деятельности), и у вас нет времени даже подумать, как бы сделать так, чтобы яйца не падали, так как все время их нужно ловить!