Вспомнил, что у меня завалялся substack и начал потихоньку переводить в него свои посты из внутреннего блога компании, скопившиеся за последний год. Первый просто — что вообще такое ваши эти Service Level Indicators.

https://open.substack.com/pub/sharkinit/p/service-level-what-part-1-defining?r=36tm5&utm_campaign=post&utm_medium=web

Параллельно, я кажется стал немного понимать, почему сложно что-либо менять одновременно в 5-6 инженерных командах, но пока не совсем понимаю, как это переложить в слова. Что-нибудь придумаю :D

Читать полностью…

Observability (1/2)

Последний месяц я внедряю в компании Observability с DataDog взамен старых добрых Prometheus & Grafana. Пока команды в восторге, MTTD (mean time to detect) упал с часов до минут, operations теперь могут заниматься планами на будущее, а не тушением пожаров. Сплошной успех, поэтому расскажу что это такое, и почему классические дашборды должны умереть.

Observability — это способность понимать поведение системы при взгляде снаружи, без знания того, как система работает изнутри. Система с observability позволяет разобраться в причинах неизвестных ранее проблем (unknown unknown). Она предоставляет достаточно данных, чтобы ответить на вопрос "что происходит?" на любом уровне: от единичного запроса до региона или системы в целом. И самое главное — она уже хранит все необходимые данные. Если вам нужно сделать ещё 1 дашборд или дописать кусочек кода, чтобы собрать ещё одну метрику — это не observability.

Основной инструмент observability это распределённые трейсы , но с несколькими особенностями, в основном приходящимися на хранилище для этих трейсов.

Поддержка high-cardinality. Cardinality — это мощность. Как мощность множества. High-cardinality — данные, у которых может быть много возможных значений. Например уникальный ID пользователя имеет максимальную cardinality, потому что он никогда не повториться для другого пользователя. Год заказа — низкую cardinality, потому что он всегда одинаковый в течение года.

Трейс и хранилище трейсов должны содержать не только базовую информацию, такую как ID сервера, регион, время исполнения, тип запроса, но также и специфичные для конкретного запроса и конкретной команды (разработки) параметры: ID пользователя, номер заказа, дата регистрации, идентификатор сессии и т.д. Именно high-cardinality данные позволяют отвечать на специфичные запросы, например "какая средняя latency на запросы в Германии для серверов, развернутых на AMI amzn2-ami-hvm-x86_64-gp2 для пользователей, делающих первый заказ?". Ответ на такие вопросы без изменения системы — вся суть observability.

Поддержка high-dimensionality. Каждый трейс может быть уникальным, поскольку он содержит набор параметров специфичный только для него. Для одной команды важен один набор параметров, для второй — другой. High-dimensionality это способность хранить и эффективно анализировать произвольный, меняющийся набор данных. Система должна одинаково хорошо справляться и с трейсом в 10 полей, и с трейсом в 100 полей. Более того, каждое из этих полей может ещё иметь и high-cardinality.

Быстрый поиск. Observability нужна чтобы отвечать на вопросы здесь и сейчас. Это значит: 1) данные должны быстро попадать в систему, 2) данные можно быстро вытащить из системы, что сложно, из-за high-dimensionality и high-cardinality, но 3) данные довольно быстро теряют полезность, а значит их довольно скоро можно удалить. Главная полезность в том, чтобы решить текущую проблему, а не анализировать трейсы спустя год или два, хотя технически такое тоже возможно.

Читать полностью…

Dynamo: Amazon’s Highly Available Key-value Store (3/3)

Совсем чуть-чуть про работу 2022 года (usenix pdf).

Что не сработало: Symetry подход с preference list. В Dynamo запись может быть через любую из N нод. Выбираться скорее всего будет первая, но не обязательно. В DynamoDB реплики выбирают лидера через Multi-Paxos и только он отвечает за запись и за "консистентные" чтения. Лидер же записывает WAL и реплицирует его follower-узлам.

Интересная особенность произошла с hinted handoff. Не написано что он НЕ используется, но появился новый хак. Обычно узел хранит данные в виде B-Tree + WAL с лидера. Хак: Лидер может создать специальную Log replica — ноду, в которой только WAL. Такой узел создать быстрее, так как с ним не нужно делиться всем B-Tree, при этом он помогает со сбором кворума.

Что всё ещё работает: ноды и раньше не поддерживали global failure state. Но теперь есть Paxos, в котором ноды сами могут начинать голосование за нового лидера, если посчитают, что старый умер. Иногда ноде только кажется, что лидер умер, что редко, но приводит к ошибкам с двумя лидерами. Такое поведение называют gray failure. Причины: лагающая сеть, медленные машины, да куча всего. Чтобы этого избежать, узел сначала опрашивает соседей, чтобы узнать у них, видят ли они мастера. Если соседи мастера видят, то нода отказывается от идеи попытаться начать раунд голосования за нового лидера.

Что совершенно отвал башки: для проверки алгоритма репликации, как и для S3, в DynamoDB Amazon использует TLA+ модели. Говорят, что парочку неочевидных багов они уже нашли. Кстати, если хотите познакомиться в TLA+ поближе, тут недавно запустился https://learntla.com!

Читать полностью…

Dynamo: Amazon’s Highly Available Key-value Store (1/3)

Сегодня две работы. Первая: та самая статья про Dynamo из 2007 года (pdf), когда она ещё не была частью AWS и не называлась DynamoDB. "Та самая" эта работа, поскольку это редкий случай, когда куча разных идей по построению хранилищ были объединены в единое решение, которое не только работало, но и обеспечивало очень большой сайт. И о котором написали. В те далекие времени Amazon был e-commerce в первую очередь, AWS появился всего годом ранее, а DynamoDB так вообще вошла в сервисы AWS только к 2012 году. Вторая — свежий пирожок, опубликованный буквально пару дней назад спустя 10 лет эксплуатации сервиса DynamoDB (usenix pdf).

При создании Dynamo Amazon исходил из нескольких ограничений:

- key-value. Логика большинства сервисов, к примеру корзины товаров, достаточно простая, и реляционная модель не принесёт значительного успеха.
- Heterogeneity & Symmetry. Все узлы выполняют одну и ту же работу. Но узлы разные, значит они могут выдерживать разную нагрузку.
- Запись всегда должна быть успешной. Пусть и с конфликтами.
- Variable consistency. Клиент сам может выбрать соотношение читателей и писателей в кворуме R+W > N.

Теперь как это всё добро работало.

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

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

Следующая проблема — репликация. При факторе репликации N, данные нужно забросить ещё на N - 1 ноду. Как их выбрать? Решение гениальное: просто пихать данные на следующие N - 1 нод в кольце 🤷‍♂️. Если кольцо состоит из A -> B -> C -> D -> A, и фактор репликации 3, то данные на узле A также будут на узлах B и C. С виртуальными узлами чуть сложнее, потому что нет гарантии что следующий виртуальный узел находится на другой физической машине. Но это решается чуть более умным программированием.

Читать полностью…

Классификация масштабируемости (2/2)

Наконец, моё любимое — масштабируемость кадров [3]. Как сделать так, чтобы 10 разработчиков не перессорились, пока пишут вместе код? А когда их станет 100? А как в такой толпе ещё бы сделать так, чтобы а) все придерживались одних стандартов и б) количество коммуникаций росло медленнее, чем линейно? Линейный рост коммуникаций быстро перестаёт работать. Люди не машины, и постоянно общение даже с десятком коллег — уже тяжело. Куда уж там ещё расти. Связанная вещь: какой должен быть процесс найма, чтобы нанять 15 разработчиков за год? А пять тысяч? И насколько они отличаются.

Ещё более интересная проблема: как безопасно менять код, которые пишут несколько тысяч человек в день? А как его разворачивать? Гугл вот для этого живет в самописном монорепозитории, в который несколько десятков тысяч коммитов в месяц делает робот[3]. Но самое-то интересно: другие компании не сильно меньше не живут в монорепе, не пользуются роботами (или скрывают) и нормально себя чувствуют. Кто более прав? 🤷‍♂️

Отдельная, но связанная тема: как поддерживать продукты, которым уже по 10+ лет? Разработчики редко столько работают в одной компании, т.е. эти знания каким-то образом нужно передавать. В [4] есть глава про это, и про другую интересную тему: deprecation продуктов, ака как правильно выводить что-то из эксплуатации.

Здесь ещё можно было бы припомнить и безопасность, ведь когда становится больше «всего», становится и больше дыр. И R&D с инновациями в больших компаниях. Когда разработка чего-нибудь новенького переходит из разряда «приятный бонус», в необходимое конкурентное преимущество. И про организацию роста сотрудников и стратегий удержания. Как обычно, чем дальше в лес, тем больше дров.

Источники:

1. Usama Naseer, Luca Niccolini, Udip Pant, Alan Frindell, Ranjeeth Dasineni, Theophilus A. Benson Zero Downtime Release: Disruption-free Load Balancing of a Multi-Billion User Website.
2. B. Clifford Neuman. Scale in Distributed Systems.
3. Rachel Potvin Josh Levenberg. Why Google Stores Billions of Lines of Code in a Single Repository
4. Titus Winters, Tom Manshreck, Hyrum Wright. Software Engineering at Google. Не знаю на что дать ссылку, но официальная бесплатная PDFка точно где-то есть.

Ссылка на часть 1.

Читать полностью…

Дедлоки (2/2)

Первый инсайт: дедлоки не возникают просто так, для них необходимо 3 условия: exclusive access, no-preemption, hold-and-wait + одно достаточное: circular wait.

Второй инсайт: чтобы побороть дедлок, достаточно избавить от одного из условий!

Пункт 2 особенно интересен, и позволяет другими глазами взглянуть на работу с ресурсами и привычные «программистские трюки». Например: почему часто разделяют локи на read-only и write-only локи? Для перформанса, конечно. Но ещё и потому что в read-only локе не может возникнуть дедлок, так как он не эксклюзивный (первое условие)!

Или вот я недавно сделал нечаянно не concurrent индекс в postgres на табличку с парой сотен миллионов записей и всё встало колом. Решение проблемы — preemption! Руками грохаем транзакцию и дедлок перестаёт существовать. И это магистры компьютерных наук знали ещё в 70-ых. Подобные же механизмы можно и автоматизировать. Правда не так просто. С одной стороны, обнаружение дедлока — в сущности задача на графах, где просто нужно правильно пройтись по ребрам от процессов до ресурсов. С другой, граф постоянно меняется буквально пока по нему проходишься. Кажется решений проблемы в общем случае нет, но в частных, например только в БД, они есть и работают.

С hold-and-wait тоже интересно. А что если бы процесс сразу же запрашивал все ресурсы, которые ему требуются? Или по крайней мере захватывал бы их постепенно, но при не успехе отпускал бы все уже захваченные. Такой подход, оказывается, тоже убирает проблему дедлоков. К сожалению, не каждый процесс знает наперёд ни все нужные ему ресурсы, ни порядок, в котором они будут захватываться. Опять в общем случае решить тяжело, в частном вполне. Например обычно заранее известно, сколько памяти и CPU нужной новой виртуалке/контейнеру, а это тоже ресурсы, за которые тоже может быть конкуренция. Там правда ситуация не обязательно завершиться дедлоком, а скорее перемещением одного из процессов, но это детали. Раскидывать задачи по компьютерам — очень сложная задача, поэтому в как-нибудь в следующий раз.

Наконец, circular-wait. А пусть все ресурсы должны захватывать только в определенном порядке. К примеру, перечислим все ресурсы в системе от 1 до n. И добавим условие: если процесс захватил ресурс 1 <= k <= n, он может захватить только любой другой ресурс с номером m, где m < k. Другими словами, процессу сначала нужно захватить самый «высокоуровневый» ресурс, а дальше все ресурсы пониже. Наличие нумерованных ресурсов и одного условия на их захватывание также позволяет избавиться от дедлоков. Полный пруф есть в [5].

Все эти подходы можно широкими мазками разделить на 3 категории:

- Detection. Подходы, которые по графу ресурсов и их зависимостей позволяют обнаружить дедлок. Для борьбы используется preemption.
- Prevention. Цель: задизайнить систему таким образом, чтобы дедлок был невозможен. Например: пронумеровать ресурсы и ввести условие их захвата. Или запретить захватить ресурс, а затем ждать второй.
- Avoidance. Подходы, при которых система переходит только из одного «безопасного» состояния в другое. Решение о выдаче ресурса принимается динамически, к примеру во время запроса. Самый популярный алгоритм: алгоритм банкира. К сожалению для него необходимо, чтобы процессы сразу знали, какие ресурсы им нужны.
- Алгоритм страуса. Или ничего не делать. Стратегия при которой программист сажается на on-call и ему выдаётся кнопка «отмена».

Ресурсы:
1. E.G. Coffman, M. Elphick, A. Shoshani. System Deadlocks.
2. Richard C. Holt. Some deadlock properties of computer systems.
3. S.S. Isloor, T.A. Marsland. The Deadlock Problem: An Overview.
4. Gertrude Neuman Levine. Defining deadlocks.
5. Charles M. Shub. A Unified Treatment of Deadlock.

Читать полностью…

ARIES (8/8)

Заключение.

ARIES — эффективный и достаточно простой алгоритм записи и восстановления. Он работает за счёт полного повтора истории. Как было показано на примере, он продолжает работать даже при множественных рестартах подряд. ARIES может работать в steal + no-force режиме buffer manager. Другими словами, он не требует чтобы коммиты записывали грязные страницы на диск, а также позволяет записывать страницы даже во время транзакций.

ARIES проводит восстановление в три шага.

Сначала происходит анализ записей в WAL. При анализе восстанавливается состояние таблицы грязных страниц DPT, а также таблицы незавершённных транзакций TT.

В следующей фазе — Redo, состояние буферов страниц в памяти приводится в полное соответствие с WAL. После исполнения Redo, внутреннее состояние страниц идентично тому, каким оно было до начала процесса восстановления.

Наконец, в фазе Undo откатываются транзакции, которые не успели сделать коммит до начала рестарта. Во время Undo каждой update записи WAL, относящейся к незавершённой транзакции, в обратном хронологическом порядке записывается CLR запись. Точно такая же запись обычно записывается в WAL при роллбеках в нормальном режиме работы. Такой подход позволяет с одной стороны, упростить алгоритм восстановления при повторных рестартах, а с другой, ограничить максимальное количество новых записей в WAL, которые будут созданы во время восстановления. При создании CLR использует протокол write-ahead, как и при обычной записи в нормальном режиме.

Я уже вышел за все мыслимые и немыслимые рамки размера поста, поэтому, пожалуй, закончу. Есть ещё пара вещей, о которых не рассказал.

Первое — это чекпоинты. База данных периодически может снимать текущее состояние таблицы грязных страниц DPT и незавершённых транзакций TT и записывать в какое-нибудь надежное место. Такой подход позволяет во время фазы анализа ARIES не просматривать вообще весь журнал, а сначала восстановить чекпоинт, и накатывать обновление уже с него.

Второе — каждая фаза ARIES может не только без проблем пережить рестарт, но также может запускаться параллельно и безопасно в несколько потоков. Это достигается за счёт локов на уровне страницы. Более того, во время каждой фазы БД может делать чекпоинты. Так к примеру чекпоинт после фазы анализа позволит не делать анализ повторно, если второй рестарт произойдёт сразу.

Третье — я сказал, что ARIES позволяет делать гранулярные локи, т.е. лочить и на уровне страницы, и на уровне отдельной строчки, но не сказал как. С локами в базах вообще всё сложно, когда-нибудь про лок-менеджеры напишу отдельный пост.

Четвёртое — есть распределёный ARIES! D-ARIES: A Distributed Version of the ARIES Recovery Algorithm (ссылка). А ещё ARIES (вернее WAL) оптимизирован под жёсткие диски. SSD последовательная запись нужна в меньшей степени, т.е. на них можно сделать более эффективный алгоритм. Пример такого алгоритма есть в работе From ARIES to MARS: transaction support for next-generation, solid-state drives (ссылка). Это всё добро тоже в беклоге.

Источники:

[1] ARIES whitepaper https://dl.acm.org/doi/10.1145/128765.128770
[2] Прекрасное youtube видео про ARIES от Dr. Jens Dittrich https://www.youtube.com/watch?v=S9nctHdkggk . Там целый университетский курс видео-лекций про базы данных.
[3] Ramakrishnan, Gehrke — Database Management System Third Edition (ссылка)
[4] Peter Bailis Joseph M. Hellerstein Michael Stonebraker — Readings in Database Systems Fifth Edition. Она же Red Book. (ссылка)

Ссылка на первый пост из 8.

Читать полностью…

ARIES (6/8)

Алгоритм восстановления. Фаза анализа и redo.

Алгоритм восстановления в ARIES состоит из трёх шагов: анализ, redo-фаза, undo-фаза. Фазы всегда исполняются в такой последовательности даже если рестарт завершился неуспешно и его надо перезапустить.

Фазы рассматривать будем на примере WAL, в котором на момент восстановления находятся 4 записи, после которых произошёл рестарт. Здесь мы добавим поле pageId, чтобы показать, как меняется таблица грязных страниц DPT. Пусть есть две транзакции, одна исполняется на странице X, а другая на странице Y. WAL будет выглядеть следующим образом.

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
-- RESTART

Здесь есть транзакция 2 (начинается с записи 31), которая завершилась коммитом и транзакция 1, в которой произошло 2 обновление, которые попали в WAL, но коммита не произошло. Так как транзакции должны происходить атомарно, вторая транзакция после восстановления должна откатиться.

В фазе первой фазе — анализе, ARIES проходится по записям в WAL и восстанавливает состояние таблицы грязных страниц DPT и таблицы незавершенных транзакций TT.

К примеру после анализа первых двух записей 30 и 31, в DPT будут записи:

X, 30
Y, 31

После анализа всех записей до 33, DPT содержит:

X, 30
Y, 31

Как видите, после анализа двух последних записей ничего не поменялось. DPT говорит о грязных страницах. Этой таблице важна лишь первая запись, которая сделала страницу грязной. Коммиты не имеют никакого значения для DPT, поскольку ARIES может работать в no-force режиме, т.е. коммит не означает, что страница записалась в диск.

Теперь к таблице завершённых транзакций. После анализа записей 30 и 31, TT выглядит так:

1, 30
2, 31

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

После анализа последних двух записей TT превратится в:

1, 32

Как видите, транзакция 2 исчезла из TT, поскольку та успела сделать коммит. Последнее изменение в транзакции 1 произошло в строке с LSN 32, поэтому она всё ещё находится в TT.

Последняя вещь которая происходит в фазе анализа — это поиск LSN, с которого нужно начать Redo фазу. Для этого просто берётся минимум из записей в таблице грязных транзакций DTP. В нашем случае это запись c LSN 30.

Фаза 2 — это Redo. Во время исполнения Redo буферы страниц приводятся в то же самое состояние, в котором они были до рестарта. Если анализ только создал таблицу DTP и TT, во время redo фазы та часть данных о страницах, которая хранится в памяти, приведётся в полное соответствие с информацией в WAL. Другими словами грязные страницы действительно станут грязными в памяти. Во время Redo фазы исполняются даже обновления транзакций, которые завершились неуспешно, как транзакция 1 в нашем случае.

Читать полностью…

ARIES (4/8)

Содержание WAL в ARIES.

Наконец-то подошли к самому интересному, как собственно ARIES работает. Он работает через повторение истории. Это значит, что в WAL должно содержаться достаточно информации, чтобы эту самую историю повторить, а значит надо сначала поговорить о кусочках, из которых состоит WAL и вспомогательных структурах в БД. Сейчас будет много наименований и терминов, но ниже пример, так что держитесь. В крайнем случае в конце последнего поста есть ссылка на youtube лекцию — очень советую, если останутся вопросы.

Поскольку запись в WAL идёт последовательно, каждой записи в нём можно присвоить некий монотонно возрастающий номер. Он называется log sequence number или LSN. В некоторых ситуациях LSN даже не нужно присваивать, так как запись идёт последовательно, т.е. в качестве LSN подойдет адрес на диске. Это работает до тех пор, пока лог не перестанет помещаться на диске. Чтобы избежать уже этой проблемы, если свои хаки, например диск можно рассматривать как циклический буфер, а LSN будет записываться как адрес + количество циклов, но это детали реализации. Важно одно — каждая запись в WAL содержит LSN, по которому можно построить историю обновлений БД.

Помимо LSN каждая запись также содержит 3 другие поля: prevLSN, TrId и type. PrevLSN указывает на предыдущую запись в лог, созданную транзакцией под номером TrId. Другими словами, набор записей с одинаковым TrId образуют связный список, где предыдущую запись всегда можно найти по prevLSN.

Type указывает на тип записи. Типов в разных источниках выделяют разное количество, но нам хватит трёх. От типа зависит, какие ещё поля содержатся в одной записи в WAL.

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

Далее идёт запись, отвечающая за изменения или создание новых данных, а именно "update". Каждое обновление содержит помимо prevLSN, TrId и type="update" ещё 3 новых поля. Первое pageId — страница, на которой происходит обновление, а второе и третье — redoData и undoData. Redo — это непосредственно те изменения, которые вносятся в рамках транзакции. Там может быть какой-нибудь инкремент значения или новое значение для колонки. Undo — обратная операция. Если Redo — инкремент, Redo — декремент. Если Redo — новое значение, в Undo будет содержаться старое. Не так важно, лежит ли в undo/redo изменение в логическом виде или результат после его применения — оба подхода работают, важно что в одной update записи в WAL написано и как применить изменение, и как его откатить.

Последний интересный вид лога — это компенсирующие логи, они же compensation log records они же CLR. Такие логи записываются базой при роллбеках. На каждую запись с типом update при полном роллбеке будет по одной записи с типом CLR, только применяться они будут в обратно порядке. Сначала откатиться самый старый апдейт, потом тот что был перед ним и так далее. Каждый CLR Помимо prevLSN, TrId и type="compensations" содержит pageId, который как и в update логах обозначает номер страницы, а ещё два поля, которые я назвал особым образом, чтобы стало понятнее, но не уверен что получилось.

Первое поле: redoTheUndoData. CRL используется при роллбеках, т.е. он откатывает транзакцию. Информация об откатывании находится в связанном "update" логе в поле undoData. CRL как раз таки и содержит эту undoData в поле redoTheUndoData. Иными словами, CRL говорит о том, какую операцию нужно исполнить, чтобы откатить связанную запись.

Второе поле: undoNextLSN. В нём хранится информация о записи в WAL, которую нужно откатить после того, как откатится текущая. Если откатить нужно только одну запись, здесь может содержаться null или другой аналог пустого значения. Таким образом несколько CRL логов не связаны между собой напрямую, но опосредованно связаны через undoNextLSN.

Читать полностью…

ARIES (2/8)

БД с высоты птичьего полёта. Работа с памятью и диском.

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

Как и в любом другом процесс, часть данных БД находится в энергозависимой памяти, она же RAM, она же просто «память». При этом основная задача базы данных — сохранять данные в энергонезависимую память: на HDD, SDD, ленточные накопители (tape drive) в зависимости от того, что у вас там есть под рукой и какой сейчас год. Энергонезависимые устройства обычно сильно медленнее читают, и уж тем более записывают данные, чем память. Настолько медленно, что у БД нет совершенно никакой возможности транслировать запросы на чтения и записи напрямую в диск. Получается дилемма. С одной стороны, БД должна всё сохранять в диск, чтобы данные не терялись. С другой, часть данных нужно хранить в памяти, потому что диски слишком медленные. А информация из памяти пропадает сразу, как только выключается свет или умирает процесс с БД.

Самый прямолинейный выход из такой ситуации: хранить в БД буфер памяти (memory buffer), отображаемый периодически один-к-одному на диск. Решение не идеальное, поскольку объём дисков обычно многократно больше объёма памяти, всё хранить не получится. К тому же записывать и читать прямо весь буфер сразу — затратно. Не синхронизировать же в самом деле по 32+ ГБ RAM за раз. Но выход есть: хранить только какое-то количество страниц (page) в памяти. Страницы обычно делают одинакового размера — так с ними проще работать. Здесь мы исходит из предложения, что все данные разом скорее всего не нужны, поэтому можно хранить только ту часть, с которой сейчас идёт работа.

Выходит, в БД хранится некий набор страниц, отображаемых 1-к-1 на участки диска. А теперь финт ушами. Вот мы вытащили страницу из диска и храним её в памяти. Поскольку единственный способ поменять содержимое диска — записать страницу, пока этого не произошло, наша страница — это точное отображение данных на диске. И она хранится в памяти. Значит любой запрос к данным на диске можно адресовать к этой самой странице в памяти. Это от нескольких раз до нескольких порядков быстрее!

Теперь про запись. Пока данные на странице не поменялись, т.е. пока страница остаётся «чистой» — можно даже не ходить в диск, так как данные есть в памяти. Как только данные на странице поменялись, она становится «грязной» (dirty page). Такую страницу нужно запись на жёсткий диск, чтобы она снова стала чистой. Записью и чтением страниц из памяти и наоборот в БД занимается компонент под названием buffer manager (Далее — BM). Кстати, если вам кажется, что вы что-то такое про страницы и синхронизации уже слышали, то как оно и есть! Виртуальная память в ОС работает довольно похожим образом, правда у ОС не стоит задачи все данные впихнуть в диск, а ещё есть аппаратная поддержка. Тем не менее, подходы и даже терминология очень схожи.

Читать полностью…

Конфиги будущего (2/2).

Идея применять машинное обучение для оптимизации хранения и выпиливания всяких сложных эвристик довольно популярная, и в последнее время исследований становится всё больше. Вот ещё работа: Automatic I/O stream management based on file characteristics (acm). Здесь рассматривается, как при помощи ML в SSD можно уменьшить write amplification — «лишние» операции записи, необходимые из-за особенностей организации SSD. По замерам получилось в среднем улучшение на 21.6%. Немного магии, и ваш SSD работает на 1/5 дольше и чуть-чуть быстрее.

А в From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees (usenix) оптимизируются LSM деревья, которые являются одной из базовых структур данных для построения хранилищ. Здесь прирост составляет 23% - 78%.

Даже в среде распределенных алгоритмов кеширования ML находит себе место, как в Stacker: an autonomic data movement engine for extreme-scale data staging-based in-situ workflows (acm). Здесь речь про кеш, а значит в качестве важнейшней характеристики используют среднее время ответа (latency). Прирост составляет в среднем ~27%.

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

Самое-то красивое: из раза в раз оказывается, что накладные расходы на поддержку ML алгоритма отбиваются приростом производительности, который он предоставляет. И это лишь вершина айсберга! Очень интересно, к чему в итоге лет через 15 придут хранилища и операционные системы, когда в мире существуют такие исследования. Нужен ли вообще будет программист для настройки системы или оно само там всё решит и выдаст оптимальный конфиг.

Ещё интересные, какие новые подводные камни и уязвимости мы получим от запихивания ML алгоритмов прямо в ядро. Не перерастёт ли проблема «выучить 500 параметров конфигурации ОС и БД» в проблему «выучить 500 параметров конфигурации ML алгоритма».

И уже по традиции. Немного шагнув в сторону из привычного IT пузыря, открывается просто необъятно интересный мир. И если вы думали начать учить ML и ждали знак, то вот он. А я тем временем прихожу в норму и постараюсь в следующий раз вернуться как можно раньше с разбором ARIES — одной из важнейших работ для современных транзакционных систем.

Читать полностью…

Как работают SSD (3/3)

FTL и старение.

SSD довольно быстро захватили несколько рынков у HDD во многом потому что используют те же самые интерфейсы. Но в HDD нет никаких проблем с перезаписью данных, а SSD так физически не могут работать из-за того что страницы не перезаписывают, а ещё из-за постоянного процесса сборки мусора. Всё дело в том что операционная система при работе с SSD видит только логическое пространство адресов памяти, физическое же пространство скрыто. За преобразование логического адреса в физический отвечает компонент под названием Flash Translation Layer (FTL).

Но тут тоже есть проблемы. Нельзя просто так соотнести логические адреса на физические по нескольким причинам:

- Ячейки в SSD «стареют» с каждым P/E циклом, поэтому по-хорошему перезаписей должно быть настолько мало, насколько это возможно.
- Некоторые данные изменяются часто, а другие практически никогда. Опять-таки со стороны «старения» ячеек это нежелательная характеристика. Нам бы хотелось, чтобы диск устаревал более-менее равномерно. А значит... данные нужно периодически передвигать.
- Очистка данных происходит по-блочно. Если в блоке есть часть нужных и часть ненужных данных, нужные сначала придётся переместить, а лишь затем очистить блок. Если операционная система будет писать данные как попало, таких перезаписей будет слишком много. Одновременно с этим, отчистка данных — долгая операция. Она в несколько раз медленнее записи.
- Чтение и запись возможна только по странице. Запись исправить довольно просто — вставить буфер размера, равного размеру страницы, а вот с чтением тяжелее. Кажется здесь магии особой нет и нужно просто записывать «похожие» данные рядом.

Поэтому в SSD в качестве алгоритма для FTL часто применяет подход под названием log-block mapping, даже пейпер есть. По своей сути он немного напоминает алгоритмы работы LSM хранилищ. Идея в том, чтобы хранить записи в виде «лога», а затем сливать данные нескольких блоков в один.

Алгоритм приблизительно следующий:

1. На SSD заводится таблица маппинга логических блоков в физические. Помимо маппинга блоков, внутри каждого блока отдельно заводится по таблице маппинга страниц в физические страницы. Один блок помечается как log, остальные как data блоки.
2. Операционная система выдаёт записи по произвольным адресам. Например сначала 3, потом 7, потом 13 и так далее.
3. Записи по этим адресам, возможно, уже существуют в каких-то других data блоках. Это всегда можно определить по таблице маппинга страниц внутри блока.
4. SSD записывает новые записи последовательно в log блок.
5. Когда log блок заполняется, его содержимое сливается (merge) вместе с каким-нибудь из data блоков, а результат записывается в свободный блок. Таким образом создаётся новый data блок, и возможно, удаляется старый.
6. На место log блока назначается новый.

Такой подход, во-первых, позволяет уменьшить количество лишних данных, которые нужно бессмысленно переносить, с другой, позволяет более равномерно «состаривать» ячейки SSD.

В заключении, ещё несколько слов:

- SSD — удивительная технология. Например они поддерживают просто невероятный уровень параллелизма для практически всех операций. Подробнее можно почитать в Design Tradeoffs for SSD Performance (ссылка). Или в ссылках тут. Я лишь поскрёб вершину айсберга.
- Оптимизация программ под SSD — это фактически выбор конкретных объёмов на чтение/запись в зависимости от размера составных блоков SSD, таких как страницы и блоки. Проблема в том, что просто подобрать размер страницы тут не получится, всё сильно сложнее.
- Бенчмарки это всё ещё сложно. Особенно бенчмарки SSD.
- В мире за пределами software пузыря происходят удивительные вещи.

Читать полностью…

Как работают SSD (1/3)

Структура SSD и особенности работы.

Теперь о том, как SSD в принципе работают. Здесь самое понятное «объяснение для программистов», которое я только находил. Если хочется посмотреть на более хардкорный материал про внутренности, то здесь есть ещё один очень хороший пост. Что первая ссылка, что вторая — посты из шести частей. В каждом огромное количество ссылок на работы и другие посты, читать не перечитать.

SSD состоят из нескольких компонентов. Само хранилище основано на flash-памяти, т.е. набора определенным образом соединенных транзисторов, которое можно программировать и стирать. «Программировать» в данном случае значит «записывать», но так уж устоялась терминология. По-английски это называется Program/Erase cycle или просто P/E цикл.

Биты памяти хранятся в ячейках, которые, собственно, состоят из транзисторов. Есть две схемы подключения транзисторов — NOR и NAND. Про отличия можно почитать тут, главное запомнить, что большая часть SSD в компьютерах и серверах построены по технологии NAND. Ячейки в NAND flash памяти не вечные, и их ресурс стремительно уменьшается с каждым P/E циклом, об этом будет ещё ниже.

Самый простой вид ячеек это SLC — Single level cell. Хранят 1 бит, очень быстрый доступ (latency), живут долго. Level здесь обозначает уровень зарядка. Здесь либо заряд есть, либо его нет.

Следующий тип это MLC — Multi level cell. "Multi-level" здесь говорит о том, что такая ячейка не просто хранит или не хранит заряд. Она может хранить один из «определенных уровней заряда». Условно — не заряжена, немного заряжена, средне заряжена, полностью заряжена. Таких определенных уровней может быть 4 — тогда можно представить 2 бита. А может быть 8 — тогда ячейка называется TLC — Triple-level cell и хранит она 3 бита.

Чем больше уровней, тем сложнее доступ к информации, т.е. растёт latency и уменьшается время жизни ячейки. При этом чем больше уровень, тем больший объём информации можно запихнуть в одно и тоже количество транзисторов, т.е. есть трейдофф. Либо быстрые, долговечные и малообъёмные SLC, либо медленные и менее долговечные, но зато большие MLC/TLC. Большая часть современных компьютеров и значительная часть серверов использует SSD с ячейками MLC/TLC. SLC применяются в ентрепрайзных серверах и стоят астрономические деньги.

Вне зависимости от типа ячейки, следующим уровнем иерархии является страница, состоящая из ячеек. Страницы бывают разного размера в разных моделях SSD от 2 КБ до 16 КБ. Несколько страниц объединяются в блок. В одном блоке как правило 128 или 256 страниц. Таким образом в зависимости от объёма страницы, объём блока будет как правило от 256 КБ до 4 МБ.

Иерархия ячейка < страница < блок очень важна для SSD из-за фундаментальных особенностей их работы:

- Во-первых, считать или записать можно только страницу целиком. Надо вам прочитать 2 байта — читаете всю страницу на 16 КБ. Неприятно, но что делать.
- Во-вторых, удаление данных (E — erase в P/E цикле) происходит по-блочно. Нельзя удалить только одну страницу, только все 128/256 страниц в блоке целиком.
- В-третьих, страницы нельзя перезаписывать. Однажды записанная страница остаётся неизменной, пока блок (со всеми страница) не будем удалён. Отсюда, собственно и P/E цикл.

Читать полностью…

Спасибо /channel/lilfunctor за репост и привет всем новоприбывшим! Приятно проснуться знаменитым 😎 Небольшой пост про ожидания и что ещё почитать.

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

Дисклеймер: я не эксперт в распределённых системах. В обычной жизни я перекладываю XML'ки и реже JSON'ы на Java. Поэтому ничто здесь не является советом! Всегда рад любым уточнениям, исправлениям или дополнительному материалу. Велком в комментарии.

Из интересных постов, пока можно почитать что-нибудь из списка:

- История CAP теоремы. Гайд на 18к символов, как перестать называть БД AP/CP и начать жить.
- Эпидемические алгоритмы и их развитие — протокол/алгоритм Gossip. Госсипов сотни вариаций, здесь разбор основных идей.
- Алгоритм кэширования TinyLFU. Кеширование это не только «положить данные поближе». Иногда нужно знать, что класть.
- Немного токсичный пост про понятие Real-Time. Спойлер: «Быстро» != "Real Time"

Читать полностью…

Впервые в жизни зарегистрировался на серьёзное мероприятие с кучей статей: https://www.hotstorage.org/2021/attend.html

Программа тут. Всё бесплатно, приходите тоже!

Ожидание: ничего не пойму.

Как минимум один пейпер будет не адово хардкорный. Почему важно измерять не только абсолютную производительность, но и эффективность на примере алгоритмов консенсуса. Краткое содержание есть в статье: http://charap.co/scalable-but-wasteful-or-why-fast-replication-protocols-are-actually-slow/

Читать полностью…

Observability (2/2)

Цель быстрого поиска в поддержке core analysis loop — подхода к решению "любой" проблемы:

0. Получить алерт или другое оповещение о том, что что-то идёт не так
1. Посмотреть визуализацию трейсов: есть ли явные outliners? Прослеживается ли корреляция между разными данными?
2. Просмотреть данные по разным dimensions, к примеру сгруппировать по статусу запроса, региону, номеру дата центра. Цель: убрать максимум данных, чтобы outliners всё ещё были видны, другими словами — сузить область в которой скорее всего находится проблема.
3. Применить фильтр из 2 и вернуться к пункту 1. Повторять до того, как проблема не станет очевидной. Для примера: на первом шаге смотреть на весь регион, на второй на одну availability zone, на один ДЦ, на одну стойку в ДЦ и т.д.

Чтобы получить мощный инструмент Observability, достаточно просто устроиться в Meta  или Google, которые свой шарманки сделали лет эдак 10 назад. Для всех остальных есть вендоры: Honeycomb, Datadog, Lightstep и пр. Но можно начать играться и бесплатно через OpenTelemetry — это стандарт, которому пытаются соответствовать все вендоры с разной степенью успеха. Первый шаг — инструментация кода, чтобы начать собирать трейсы + отправлять их куда-то. Второй — добавление кастомных business-specific тегов или целых трейсов. Технически всё достаточно просто, а про "социальную" сторону я расскажу в следующий раз.

Источники:
- Observability Primer от OpenTelemetry
- Charity Majors, Liz Fong-Jones, George Miranda Observability Engineering

Читать полностью…

No updates update

Я одинаково плохо пишут и вступления, и введения, тем более спустя полгода молчания, поэтому краткая выжимка из моей жизни за последний год:

- Нашел работу Staff инженером и переехал в Дубай в маленький стартап,
- Попал под сокращение 30% сотрудников через 2.5 месяца. Fun fact: за два дня до сокращения согласовал с CTO + CPO "стратегию" на следующий год. Плохая была стратегия 🤔
- Нашел новую работу за 10 дней, но снова Senior, потому что стремно в панике запускать ещё один поиск на Staff позицию,
- За следующие полгода прочитал 0 "технических" книг, 0 пейперов, сбил режим сна, прошёл десятка два игр, начал носить очки, восстановил режим сна...

И вот только сейчас почувствовал силы что-то снова писать. Всем привет! План такой:

Во-первых, никаких "публичных обещаний" и графиков постов, которые я ни разу и не соблюдал. Я понял что физически не могу повторять за principle инженерами из Google и AWS с двумя лонгридами в неделю.

Во-вторых, разборы статей. Мне очень нравится как получились разборы целых тем, как в случае с CAP теоремой, дедлоками или Gossip'ом. Сам даже перечитываю. Но понять одну статью — это квест на 6-20 часов, а писать такие посты даже тяжелее, чем читать. Они будут, но скорее всего поменьше.

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

В-четвертых, у меня скопился беклог из десятка постов на отвлечённые темы от отзывов на нетехнические книжки до баек про внедрение Observability. Так что легкое чтение снова вернётся. Ура.

Читать полностью…

Dynamo: Amazon’s Highly Available Key-value Store (2/3)

Теперь к главное проблеме: как сделать так, чтобы запись всегда была успешной? Несколько трюков. Во-первых, при факторе репликации N, каждый узел содержит preference list, состоящий из более чем N узлов. В идеальном мире, запись будет идти в один из N узлов, но если какая-то часть из них недоступна, запись пойдёт через hinted handoff в другой узел. Hinted Handoff — это такая особая запись на "чужую" ноду с хинтом. Допустим, если обычно запись идёт в A, B, C, но запись нужно сделать в D, можно сообщить узлу "вот данные, но они вообще были для узла A`". Тогда `D сохранит данные, но также будет периодически проверять, не поднялся ли A. Как только это произойдёт, D перельёт свои данные в A, где им и место, и удалит их у себя.

Во-вторых, для записи используется vector clock. Каждая запись содержит не только данные, но также номер сервера и значение монотонно растущего счётчика. Сервер, который записывает данные, обновит значение счётчика или добавит в список новый счётчик. По двум таким записям очевидно, можно ли автоматически разрешить конфликт. К примеру, если есть две записи (node: 1, version: 5) и (node: 1, version: 2), очевидно, что вторую можно отбросить, так как она старая, по сравнению с новой записью того же сервера. Именно таким образом работает read repair в Dynamo. Когда при чтении какой-то из узлов возвращает устарелые данные, они обновляются. Но если запись будет (node: 1, version: 4) и (node: 2, version: 5), просто разрешение конфликтов уже не сработает.

И здесь ребята из Amazon поднимают довольно важную проблему. База данных редко знает семантику данных. Для базы это всё просто наборы бит, поэтому на уровне хранилищ редко можно получить хорошую тактику разрешения конфликтов. Можно использовать к примеру last-write-wins. Для некоторых видов данных можно даже наворотить CRDT, которые не факт что разрешат конфликт семантически правильно, но точно разрешат его одинаковым образом на всех нодах.

Решение: отдавать конфликты клиенту! Уж программист то точно знает, что две конфликтные записи семантически — это две версии корзины товаров, с вполне понятным алгоритмом их слияния. Немного странно из get запроса получить гипотетически 2 версии данных, зато конфликты будут разрешаться правильно.

Теперь про failure detection и добавление новых нод в кластер. На момент 2007 года у Amazon каждый отдельный сервис сам поднимает и менеджерит кластер Dynamo. Это значит, что общее количество узлов обычно измеряется в сотнях, а не тысячах. В такой ситуации при добавлении новых узлов, хорошо себя показывают gossip алгоритмы (Про gossip писал здесь). Каждый узел самостоятельно строит картину кластера как раз основываясь на сообщениях, полученных по gossip. Интересный момент: тот же gossip не используется для передачи информации о неработающих узлах. Т.е. у Dynamo фактически отсутствовал global failure detection механизм, ноды содержали информацию о неработающих узлах локально (не можешь достучаться — не работает), но не делились ей. Одна из причин: операции по добавлению и удалению узлов делаются в ручном режиме, такой алгоритм просто не нужен.

Ещё немного про антиэнтропию для поддержания одинакового состояния реплик. Чтобы не передавать кучу данных по репликам, используются Merkle Trees. Это такой хитрое дерево у которого хеш родителя состоит из хешей детей. Если хеш в корне двух деревьев одинаковый — оба дерева одинаковые. Если нет — можно сравнить хеши детей, чтобы быстрее обнаружить, в какой из частей поддерева есть расхождение.

И последний интересный кусочек про перформанс. Задержка при записи в кворум из W узлов определяется задержкой самого медленного узла. А что если при записи в W узлом писать только в буфер в памяти, а в остальные N-W узлов писать в диск? Тогда задержки меньше, при этом запись скорее всего будет в других узлах. Этот хак позволяет Dynamo в 5 раз уменьшить задержки в 99.9 процентиле в пиковые загрузки.

Читать полностью…

Scaling Memcache at Facebook

За последние 4.5 месяца я успел эмигрировать в Дубай, получить лычку Staff Engineer, попасть под сокращение (потерять лычку :D), пройти 22 собеса за 2 недели и найти ещё одну работу. Если кто-то хочет в Дубае найти финтех или перевезти сюда котов, пишите. Я походу стал экспертом.

Когда-то давно у меня был план сделать цикл с разбором работ по алгоритмам консенсуса, но этот план теперь там же где российская экономика и мои нервишки, поэтому ближайшие пару постов будут более расслабленными. А именно: несколько работ о том, как компания X сделала Y. Такие пейперы легко читать, а состоят они в основном из практичных советов и цифр, нежели зубодробительной математики и фундаментальных доказательств. Сегодня поговорю о Scaling Memcache at Facebook от 2013 года (ПДФ на usenix). Формат тоже попроще: больше повествования и меньше тягомотины, но ничего не обещаю. Поехали!

Итак Фейсбук решил доработать и так неплохо работающий memcached, потому что могут. В работе memcached — это сам кеш, а memcache (без d) — кластер, на котором крутятся memcached. Первая интересная находка — использовать UDP для get запросов вместо TCP. Set и delete всё ещё по TCP. Результат: теряются 0.25% запросов, зато -20% latency в среднем. В работе -20% на графике average of medians. Я не очень понимаю этот оборот, но походу это в районе 50% процентиля, потому что медианы...? В любом случае, в 95-ом процентиле прироста почти нет, т.е. быстрее становятся медленные запросы, что хорошо. Правда 0.25% потерь — это всё-таки много, поэтому имплементация оборачивает потерянные пакеты и out-of-order delivery в клиентские ошибки, а клиент там сам уже ретраит. Фейсбуку норм, потому что некоторые страницы делают тысячи обращений в memcache, и сделать пару ретраев недорого.

Кстати о ретраях и ошибках. Фейсбук использует отдельный пул под названием gutter, размером 1% от общего размера memcache для обработки запросов с ошибкой. Клиент делает запрос, не получает ответа (т.е. не cache miss, а прямо Connection Error), далее делает повторный запрос в gutter. Если в gutter данных тоже нет, они добавляются туда. Данные в gutter устаревают быстро, чтобы часто не инвалидировать. Такой подход мало того что защищает от 99% ошибок при доступе к memcache, так ещё и превращает 10-25% промахов в попадания. К тому же дополнительный слой защиты бекенда от запросов. В идеальном мире данные есть в memcahce, если тот умер, то в gutter, только если и в нём нет, запрос идёт в бекенд. Правда трейдофф тоже есть, данные в gutter могут быть старыми. Потому и время жизни записей в gutter короткое.

Ещё пара фишек с удалением и записью. Во-первых, при cache miss, клиенту выдаётся lease token на ~10 секунд (дефолт) на конкретный ID для записи данных. Другие клиенты не могут обновить запись, пока у кого-то есть токен. Это позволяет бороться с циклами запись-перезапись при конкурентном доступе. Во-вторых, lease token помогает в борьбе с thundering herds — ситуации, когда много клиентов пытаются получить один и те же данные. Если клиент пытается получить запись, на которую выпущен lease token, клиент самостоятельно уйдёт в небольшое ожидание и повторит запрос ещё раз, потому что обычно между захватом lease token и самой записью проходит несколько милисекунд. Так запрос не попадёт в cache miss, а вернётся с более долгой задержкой.

Связанная, но немного отдельная проблема — это конкурентные удаления. При удалении, записи какое-то время ещё хранятся в особой структуре данных (какой — не написано) При промахе, клиент может по своему усмотрению либо получить lease token для дальнейшей записи, либо получить устаревшие данные. Опять cache miss превращается в hit, но со старыми данными. Удобно.

В работе есть ещё пара интересных моментов с разогревом нового инстанса из соседнего, а не из бекенда, батчинг запросов, и как решить read-your-writes (спойлер: помечать записи и читать с мастера), но для первого поста за 4.5 месяцев я думаю достаточно.

Читать полностью…

Классификация масштабируемости (1/2)

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

Начнём с самой очевидной ситуации — масштабируемость численных показателей. Этот пункт включает не только вертикальную масштабируемость (серверы пухнут), и горизонтальную (серверов становится больше), но и другие интересные проблемы. Раньше IPv4 хватало всем, а теперь приходится выкручиваться. Раньше все наши 3 nginx'а можно было запихнуть в DNS, а теперь тысячи их, не лезут! Некоторые решения ещё можно запихнуть под гребёнку «горизонтальной масштабируемости», как к примеру использование хранилищ, оптимизированных на запись или разделение читателей и писателей. Но некоторые компании делают совершенно безумные вещи!

Зачем фейсбук пропускает запрос через L4+L7 балансировщик, а затем делает это внутри ДЦ ещё раз? [1] Это не просто «горизонтальная масштабируемость». Это совершенно другой уровень борьбы с физическими ограничениями интернета и старых протоколов.

Немного перпендикулярная, но связанная ситуация — оптимизация затрат, важность которой растёт линейно с ростом, собственно, затрат. На уровне стартапа с 5 людьми со стоимостью всей инфраструктуры в пару тысяч в год, экономия 1% процессорного времени скорее всего копейки. Для какого-нибудь гугла 1% — это десятки миллионов долларов.

Далее идёт географическая масштабируемость, которая приносит за собой а) задержки б) прекрасные возможности для оптимизации. К примеру, так ли сервису такси в Москве важно знать, что точно такой же сервис такси доступен в Нью-Йорке? Явно никто в здравом уме на закажет такси из Нью-Йорка в Москву. Значит ли это, что их можно разделить, тем самым упростив поддержку локальных серверов? Ответы совершенно неочевидны. Для бизнес-анализа данные от разных частей одного приложения собрать всё равно придётся, но для непосредственно оперирования системы вроде как нет.

Гео-распределённость приносит за собой ещё одну проблему — необходимость в административной масштабируемости. «Административный» не самое удачное слово с миллионом смыслов, но я его краду из [2], так что оставим как есть. Речь идёт про особенности роста большого бизнеса, оказывающие влияние на техническую составляющую. Например, как в техническом плане происходит поглощение одной компании другой? Каким образом мега-корпорация интегрирует продукты от сотни других компаний, так сказать "at scale"? Здесь есть большая часть юридических вопросов, но от чисто технических проблем всё равно не убежать.

Похожая, но отличающаяся группа проблем — юридические особенности в разных странах. К примеру, каким образом в каждой из стран нужно хранить персональные данные? И как жить с тем, что кассовый чек везде выглядит по-разному? А можно ли делиться этими данными? Ответ на каждый из вопросов влияет и на скорость роста, и на общий вид технических решений. Особенно трудно здесь финансовым и медицинским компаниям, там иерархия проверяющих органов растёт уже несколько веков и следит за каждым чихом. Быстрый «онбординг» новых стран тоже не очень подходит в понятия вертикальной и горизонтальной масштабируемости.

Часть 2 🔽.

Читать полностью…

Дедлоки (1/2)

Всех с наступившим! 🐌

Решил я тут почитать, что умные дядьки пишут про дедлоки. Как обычно оказалось, что поверхностное понимание уровня «пройти интервью» неверно от начала до конца, а в реальности всё супер интересно и конечно известно уже последние лет 50.

Дедлок или deadly embrace, как их называл товарищ Дейкстра (тот самый, который алгоритм) — ситуация бесконечного ожидания, при которой группа процессов не может продолжать работу, пока «внешние силы» не совершат определенные действия. Слово «процесс» здесь не имеет отношения к процессам в операционной системе. Процесс в дедлоке — некий автомат с набором состояний. Такими состояниями могут быть «процесс А не владеет ресурсами» или «процесс B владеет ресурсом alpha и пытается получить ресурс beta». На самом деле определение не совсем корректное в 100% ситуаций, но для обсуждения большинства подходов подойдёт.

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

Такой дедлок называется либо ресурсным, либо interleaved дедлоком. Первое более привычное и популярное название, второе я нашёл только в [4]. Для возможности его возникновения необходимо выполнение 3 условий:

1. Exclusive access. Только один процесс может захватить ресурс одновременно.
2. No-preemption. Процесс, захвативший ресурс, не может быть прерван.
3. Hold and wait condition. Должны разрешаться ситуация, при которой процесс захватил сначала один ресурс, а теперь ждёт пока освободится второй. Не отпуская при этом первый.

Наличие этих условий в системе ещё не гарантирует возникновение дедлока! Это только необходимые условия. Их наличие означает существование unsafe region[5] — такого набора состояний процессов, попав в которое, ни один из процессов не может завершить свою работу.

При наличии unsafe region достаточно найти лишь 1 набор состояний, чтобы обеспечить дедлок. Оно же последнее условие:

4. circular wait condition. Процессы и ресурсы должны иметь возможность собираться в «цепочку». К примеру: Процесс A владеет ресурсом a при этом хочет захватить ресурс b, которым владеет процесс B, который хочет завладеть ресурсом a. Если обозначить эти отношения стрелочками:

a -> A значит процесс A владеет ресурсом a.
A -> b значит процесс A хочет завладеть ресурсом b.

Схематично получится круг (ну или квадрат):

a  -> A
^     |
|     v
B <-  b

Читать полностью…

ARIES (7/8)

Алгоритм восстановления. Фаза Undo.

Наконец Фаза 3 — Undo. После исполнения первых двух фаз, таблица незавершённых транзакций TT может быть не пуста. Эти транзакции не успели сделать коммит. Значит они должны откатиться, чтобы сохранить свойство атомарности.

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

1. Выбирается запись с самым большим LSN.
2. Если запись update — эта запись откатывается при помощи CRL записи в WAL. Той самой записи, которая обычно записывается в WAL при роллбеках. Фактически ARIES подменяется неуспешные транзакции на успешные, которые просто сделали роллбек. В TT добавляется новая CLR запись для дальнейшего анализа.
3. Если эта запись CLR -> вместо неё добавляется её значение undoNextLSN. Если этого значения нет, запись удаляется из TT.

Посмотрим на примере выше. WAL всё ещё выглядит следующим образом:

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
-- RESTART

Undo фаза смотрим в TT. Видит там запись 1, 32 и начинает её откатывать при помощи clr записи. После отката новое состояние WAL будет:

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]

А TT обновится до

1, 34

Добавление новой CLR записи в WAL следует такому же write-ahead протоколу, как и добавление обычных записей. Другими словами, эта запись не может попасть на диск, пока она не будет сохранена в журнал WAL.

При откате 32 записи видно, что эта транзакция связана с записью 30 (поле prevLSN). Это значение копируется в undoNextLSN CLR записи. Таким же образом undoData копируется в redoTheUndoData.

Пусть в этот момент происходит ещё 1 рестарт. ARIES же обещает, что всё будет работать и при рестартах. Посмотрим!

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]
-- RESTART 2

Снова запустим анализ. После анализа первых 4 записей (30-33) состояние TT и DPT такое же, как было и раньше в конце первого рестарта.

DPT:
X, 30
Y, 31
TT:
1, 32

Но анализ ещё не завершен, ведь есть запись под номером 34. После обработки этой записи DPT не изменится, а вот TT поменяется на

1, 34

Как видите это ровно такое же состояние, в котором был TT во время undo фазы предыдущего рестарта. ARIES пришёл ровно в тоже самое состояние, что и раньше.

Redo фаза снова обновит состояние буферов страниц. Останется только завершить процесс восстановления в undo фазе. Снова смотрим на запись с самым большим LSN — это запись 34. Пункт 3 алгоритма говорит, что если запись является CLR, значение в TT должно обновиться на undoNextLSN. Новое состояние TT:

1, 30

Снова ищем самый большой LSN по TT. Находим 30. Запись update, поэтому надо откатить при помощи CLR. У записи нет prevLSN, значит это последняя CLR запись. Теперь состояние WAL будет:

30. [-, 1, X, "u", k+=2, k-=2]
31. [-, 2, Y, "u", n-=3, n+=3]
32. [30, 1, X, "u", k+=9, k-=9]
33. [31, 2, Y, "c"]
34. [32, 1, X, "clr", k-=9, 30]
35. [34, 1, X, "clr", k-=3, -]

А в TT получится:

1, 35

Остался последний шаг — вытаскиваем самый больше LSN из TT — 35. Это CLR, значит значение в TT для транзакции 1 в соответствии с пунктом 3 нужно обновить на undoNextLSN, но там "-". Это значит, мы произвели полный откат транзакции и запись можно удалить. Наконец-то в TT больше нет записей. Состояние базы данных успешно восстановлено.

Читать полностью…

ARIES (5/8)

Пример WAL, прочие структуры данных.

Настало время привести пример. Для упрощения я опущу работу со страницами, полями pageId и покажу как связаны все записи в WAL.

Пусть есть некая страница X с двумя поля k и n. Есть также две параллельные транзакции, одна увеличивает k на 2, а вторая уменьшает n на 3. Затем первая транзакция снова увеличивает k на 9. Пока ни одна не успела сделать коммит. Каждая запись в WAL я обозначу числом, которое равно LSN, но как вы помните, писать LSN не обязательно — для этого подойдёт и адрес лога. Начну писать лог с середине, чтобы тоже лишний раз не путаться. Вместо "update" будет просто "u", "commit" — "c", а "compensation" заменю на "clr"

Напомню, что запись с типом update содержит поля prevLSN, TrId, pageId (опустим), redoData и undoData:

77. [-, 1, "u", k+=2, k-=2]
78. [-, 2, "u", n-=3, n+=3]
79. [77, 1, "u", k+=9, k-=9]

Первые две записи содержат "-" вместо поля prevLSN, поскольку они являются первыми изменениями в своих транзакциях. Запись 3 (LSN = 79) в поле prevLSN содержит 77 — это указание на LSN предыдущей записи, сделанной этой транзакцией, т.е. записи с LSN = 77.

Теперь пусть транзакция 2 сделать коммит, а транзакция 1 сделает полный роллбек предыдущих обновлений, затем увеличивать k на 13, а затем сделает коммит. Получится следующая ситуация:

77. [-, 1, "u", k+=2, k-=2]
78. [-, 2, "u", n-=3, n+=3]
79. [77, 1, "u", k+=9, k-=9]
...
88. [78, 2, "c"]
89. [79, 1, "clr", k-=9, 77]
90. [89, 1, "clr", k-=2, -]
91. [90, 1, "u", k+=13, k-=13]
92. [91, 1, "c"]

Для начала посмотрим на запись 89. В поле redoTheUndoData содержится k-=9 — ровно тоже самое, что содержалось в предыдущей записи 79 с типом update в поле undoData. Фактически здесь при создании CLR записи происходит копирование данных. В поле undoNextLSN содержится 77, т.е. указатель на следующая запись, которую нужно откатить во время этого роллбека. Оно скопировано из prevLSN той записи, которая откатывается. У записи с LSN 79 в поле prevLSN записано 77.

Если бы в undoNextLSN не было бы данных, это означало бы, что роллбек частичный, т.е. откатывается только одна запись из двух. Другими словами, наличие записи в undoNextLSN означает, что роллбек ещё не завершён. Когда роллбек откатит последнюю запись в CRL в undoNextLSN не будет ссылки. Именно этот случай показан в записи под номером 90. Здесь тоже CLR запись, но следующий за ней записи нет, поэтому в поле undoNextLSN стоит "-".

Помимо особого способа заполнения WAL, ARIES ещё нужно поддерживать рядом с журналом две таблицы. Их можно собрать по WAL, поэтому достаточно держать их в памяти.

Первая — это таблица грязных страниц dirty pages table (DPT). В ней содержится всего два поля: pageId для номера страницы и указатель на первую запись в WAL, после которой страница стала грязной. Это поле называется recoveryLSN и оно используется для поиска той записи, с которой нужно начинать восстановление. Таблица меняется в двух случаях. Если очередная запись в WAL изменила страницу, которая была чистой — сюда добавляется номер этой страницы и номер LSN записи. Если же страница синхронизируется на диск, запись из DPT удаляется.

Вторая нужная для работы ARIES структура — это таблица транзакций transactions table (TT). В ней находятся все незавершённые транзакции с указанием их идентификатора TrID, а также последнего изменения, произошедшего в рамках этой транзакции lastLSN. У каждой записи в WAL есть указатель на предыдущую запись в поле prevLSN, т.е. все записи объединены в связный список. В TT указывается транзакция и её последнее изменение, т.е. фактически запись здесь — это указатель на голову связного списка. Записи в TT обновляются всякий раз когда в рамках транзакции происходит изменение. Запись удаляется при коммите или полном роллбеке.

Читать полностью…

ARIES (3/8)

БД с высоты птичьего полёта. Политики buffer manager и write-ahead logging.

Buffer manager в транзакционной системе может работать в разных режимах, которые иногда называют политиками. Одна из таких политик — steal / no steal. Суть такая: внутри транзакционной системы исполняются... транзакции. Они меняют содержимое чистых страниц из-за чего те становятся грязными. Одна транзакция может одновременно менять содержимое нескольких страниц. Протекать транзакция тоже может относительно долго, вплоть до коммита или полного роллбека. Здесь встаёт вопрос — а можно ли записать грязную страницу на диск, сделав её чистой, до того, как все транзакции, использующие эту страницу, завершатся. Если так можно делать, BM придерживается steal политики. Если нельзя, т.е. записать можно только страницы, над которыми сейчас не происходит изменения, используется no steal политика.

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

Другая важная политика BM — force / no-force. При force политике транзакция не может завершиться коммитом, пока все её изменения не будут записаны на энергонезависимое хранилище. Другими словами, каждая транзакция всегда синхронизирует свои изменения на диск. Force политика очень упрощает процесс восстановления, потому что если транзакция успела сделать коммит до отказа БД, данные точно есть в хранилище. С другой стороны, при force политике про производительность можно забыть. Синзронизировать вообще каждое изменение в диск — супер затратно.

ARIES позволяет работать с самым мягким набором политик — steal + no-force, и всё ещё обеспечивать «гарантированное» сохранение данных. В кавычках, потому что нельзя взять и отбросить все мириады особенностей OS, дисков, SSD и их драйверов из-за которых вроде запись гарантируется, но не всегда. Прежде чем перейти к ARIES, осталось сказать про алгоритм/протокол write-ahead logging. Протоколом он называется в самой работе.

Write-ahead logging использует в системах, в которых страницы с изменениями перезаписываются. Другими словами, существует одна копия страницы на диске и её клон в памяти в виде чистой или грязной страницы. Никаких вторых версий в другом месте, только одна копия. Такой подход накладывает некоторые ограничения, а именно: при использовании WAL, перед тем как грязная страница в памяти получит право перезаписать страницу на диске, сначала на диск обязательно должен быть сохранён лог, содержащий изменения. Сначала лог с информации об обновлении, потом само обновление. Поэтому подход и называется write-ahead logging.

WAL в общем случае — это привычный всем лог. Как и любой лог, пишется он только вперёд. Синхронизация такого лога также происходит достаточно быстро, поскольку старые данные не могут меняться. Слово «синхронизация» здесь используется не случайно, потому что WAL это очередной буфер, который живет в памяти БД и гипотетически может не дожить до записи на диск. Чтобы этого не происходило, как правило БД синхронизирует WAL при коммитах/прерываниях транзакций. Ещё одна причина для синхронизации WAL — превышение размер буфера или просто по времени. В постгресе к примеру размер буфера и время после которого произойдёт запись можно даже настроить.

Замечу ещё, что протокол write-ahead logging и сам журнал с логами часто в литературе называется одним словом — WAL. Обычно это не приводит к путанице, так как по контексту понятно, идёт ли речь о протоколе или о файле. В общем случае, протокол WAL — это правило, из-за которого обновление страницы в диск может попасть только после того, как в этот же диск попадёт обновление журнала. А лог WAL — это файл с записями о транзакциях.

Читать полностью…

ARIES (1/8)

Введение.

ARIES — алгоритм записи и восстановления данных в транзакционных системах, основанный на write-ahead logging (WAL). Он поддерживает как полный, так и частичный роллбек транзакций, подходит для разных политик buffer manager (часть БД, отвечающая за запись данных с памяти в диск и обратно. Подробнее — ниже), а также позволяет использовать гранулярные блокировки вплоть до блокировки отдельных строк. ARIES основан на полном повторе истории при восстановлении. Другими словами, он не делает разницы между транзакциям, которые успели сделать коммит до начала рестарта, и теми что не успели. ARIES сначала всегда восстанавливает состояние базы до того, каким оно было перед рестартом, а лишь затем откатывает неуспешные транзакции. Такой подход позволяет значительно упростить алгоритм восстановления, особенно если первый его запуск завершился неуспешно. ARIES работает даже при множественных рестартах.

Довольно сложно найти 100% подтверждения, какие базы и когда использовали ARIES. В разных источниках к ним добавляют и Oracle DBMS, и Microsoft SQL server, и IBM DB2. Часто в документациях не пишут, что БД использует ARIES напрямую, но похожие идеи всё равно просачиваются.

ACID и ARIES.

ARIES частично связан с понятием ACID — четырьмя важными свойствами любой транзакционной системы. Поскольку ARIES отвечает за запись и восстановление, он является частью A — Atomicity и D — Durability из ACID. Опосредованно ARIES позволяет делать гранулярные локи, т.е. влияет и на I — Isolation.

Если на чистоту, акроним ACID не особо-то и удачный, в основном из-за путаницы в определениях, которую он создает. К примеру, atomicity здесь не имеет отношение к атомарным операциям в языках программирования и ОС. В ACID, A — это возможность прервать транзакции в любой момент до её полного окончания. Consistency часто не относится к самой БД, а скорее к тому, как данные внутри неё используются приложением. И уж точно consistency в БД и consistency в CAP к примеру — совершенно разные вещи. С Isolation ещё сложнее. Изоляция говорит о том, как БД работает с конкурентными операциями. Фактически, уровень изоляции задаёт, какие ошибки и ситуации можно, а какие нельзя считать корректными. Это определение очень похоже на модели консистентности, но C в ACID уже есть... Хоть c durability вроде как проблем не возникает.

Ещё одна причина, почему ACID несёт больше семантики, чем настоящего смысла заключается в том, что в БД все эти свойства обеспечиваются одновременно. Нет отдельной подсистемы, отвечающий только за durability или только за atomicity, это всё алгоритмы и структуры данных.

ARIES (Algorithm for Recovery and Isolation Exploiting Semantics) — один из самых влиятельных и дремучих алгоритмов записи и восстановления данных. Работа (пдф) датируется 1992 годом, но похожие алгоритмы существуют примерно с 60-70-ых, когда первые базы данных только появились. Идеи из ARIES всё ещё используются повсеместно, а сама работа уже цитировалась более 1500 раз (по google scholar)! Практически любой другой труд про транзакционность или восстановление упоминает ARIES.

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

Вторая-третья часть поста посвящена работе памяти и дисков в БД и подходу write-ahead logging. Само описание ARIES начинается с четвёртого поста и продолжается до конца.

Читать полностью…

Конфиги будущего (1/2)

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

- Во-первых, параметры самого приложения. К примеру postgresql.conf для посгри или несколько десятков, а то и сотен конфигов для kafka.
- Во-вторых, если приложение работает на VM — ещё сотня-другая параметров сверху. Даже если VM нет, часто разные флажки конфигурации, компиляции или самого процесса могут влиять на производительность.
- В-третьих, в любом случае запускать процесс придётся поверх операционной системы. Очередная сотня конфигурируемых параметров на нетворкинг, на работу с памятью и на файловую систему.

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

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

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

Первый шаг — перестать конфигурировать каждую систему руками. Пусть сами себя конфигурируют! Это можно сделать, например, при помощи достаточно быстрого алгоритма машинного обучения в ядре ОС, как в работе A Machine Learning Framework to Improve Storage System Performance (acm). Называется этот ML фреймворк KML и на некоторых нагрузка с RocksDB он показывает х2 производительности... правда из работы не совсем понятно по сравнению с чем. Думаю верно предположить, что сравнение идёт с ОС без каких-либо ручных изменений конфигурации. Здесь рассматривается только абсолютное количество операций с KML, и например ни слова не говорится про средние задержки, но надо же с чего-то начинать.

Идея следующая: оптимизировать I/O нагрузку можно за счёт правильных вызовов и конфигурации readahead. Трассировку, сбор данных и выделение памяти можно оставить в kernel space, там же реализовать примитивы для построения ML алгоритмов, нейросетей и работы с плавающей точкой. Для удобства, обучать модель можно как в kernel space, так и в user space. Можно обучить на известной заранее нагрузке, а затем положить модель в ядро. Обучение и переобучение также по последнему слову техники: хоть онлайн, хоть офлайн, синхронно, асинхронно, в общем, как угодно. Работа не зря называется фреймворк для улучшение производительности. Ещё бы ссылку на гитхаб приложили, но видимо не всё сразу.

Если KML запущен в kernel space, он гипотетически может переобучаться под нагрузку прямо в режиме онлайн, но в работе рассматривается немного другой путь. Авторы сначала замеряют четыре разные вида нагрузки на RocksDB (различаются по количеству чтений и записей), а затем строят классификатор. Его задача — проанализировать текущую неизвестную нагрузку и найти похожую из четырёх уже известных конфигураций.

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

Читать полностью…

Как работают SSD (2/3)

Сборка мусора и не верь бенчмаркам своим.

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

1. Скажем SSD записать любое значение, например X=5. Оно попадает в первую страницу первого блока.
2. Затем скажем записать X=6. Запись X=5 не может поменяться, она остаётся, но рядом появится ещё одна запись X=6 уже на второй странице первого блока, которая и будет актуальной. Таким образом у вас как бы тратиться в два раза больше места на хранение «мусора».
3. Наконец скажем записать X=7. SSD запишет её на первую страницу уже второго блока, а первый блок полностью очиститься от данных. Мусор удалён.

Программистам на memory managed языках этот алгоритм может показаться очень похожим. В действительности, в SSD происходит процесс «сборки мусора». Мусор накапливается, а значит его нужно удалять. В хорошей ситуации он удаляется где-нибудь в бекграунд процессе, в плохой — перед вставкой данных.

Есть и ещё одна особенность. У данных в SSD нет никаких «областей видимости» или количества ссылок, как в языках программирования. В общем случае, SSD даже не знает, что данные перестали использоваться. Он может это узнать, если поверх тех же данных пойдёт новая запись. Для решения этой проблемы используется два подхода. Во-первых, многие операционные системы поддерживают команду TRIM, задача которой — сообщить SSD, о том что блок памяти больше не нужен, а значит его можно отчистить. Во-вторых, на многих SSD выделяют физически доступной памяти на 15-25% больше, чем логически адресуемой. Это называется over-provisioning. Поскольку эту память не видит операционная система, но видит SSD, её можно иногда использовать при повышении нагрузок для временного хранения блоков, например.

Плохие новости для программист здесь заключаются в том, что из-за сборки мусора бенчмарки производительности SSD несут очень спорную информацию. Просто замерить, как там новенький диск записывает 20 минут данные — недостаточно. Нужно понагружать его хотя бы пару часов под нагрузкой из и чтений, и записей, чтобы вообще увидеть эффект от сборки мусора, особенно когда там агрегат на 16 ТБ. При этом паттерн нагрузки от производителя может вообще не соответствовать данным реального приложения.

Вторая опасность бенчей SSD — замер только одного показателя, как правило общей производительности (throughput). Это, конечно, не то что нам нужно при наличии сборки мусора, потому что процесс сборки может случиться внезапно, что влияет на задержки (latency). А ещё есть такой показатель, как количество операций чтения/записи в секунду IOPS (Input/Output Operations Per Second). Он тоже не какая-то фундаментальная характеристика, а параметр, зависящий от нагрузки. Конечно, чем больше IOPS тем лучше, но зависит от данных. 10к IOPS где каждая операция передаёт 1 КБ дают меньшую производительность, чем 5к IOPS с 4 КБ данных в каждом запросе.

Как обычно бывает с бенчмарками, лучший вариант — делать бенчи самому на своих данных.

Читать полностью…

HotStorage 2021

Сходил я тут месяц недели назад на HotStorage 2021. Так сходил, что IT пузырь вокруг в очередной раз надорвался. В мире снова интересного сильно больше, чем можно выучить за одну жизнь. В первой части личный опыт о том, чем «конференции с пейперами» отличаются от обычных IT конференции, почему это безумно интересно, а также как их найти. Далее большая часть про то, как работают SSD. Это здоровенный кусок, поэтому с подборкой крутейших докладов с конфы я приду через несколько дней. Всё равно чтобы понять градус безумия нужно сначала прочитать про SSD.

Для начала программа и сами работы. Конференция в основном про новинки в области SDD и способов хранения. Удивительное отличие от обычных IT конференций — 10-15 минутные записи выступлений. Записи можно объяснить ковидом, но 10 минут на довольно сложные работы? Что ещё интереснее, за эти 10 минут в принципе удаётся что-то понять.

Вторая удивительная вещь. Представленные работы это не теоретический бред магов в башнях из слоновой кости, которые JSON в своей жизни не видели, а совершенно наоборот. Чуть ли не главный вопрос после любой работы — что там с использованием / adoption фичей и технологий, так как у SSD с этим проблемы.

SSD — технология молодая, развивается стремительно, но индустрия софта подстраивается под эти новинки за пару тройку лет, а за это время появляется уже что-нибудь новенькое и нужно подстраиваться заново. Не помогает и тот факт, что в Software индустрии как-то принято пихать везде вариации "Computer As A Service" подхода, когда компьютер это какое-то количество процессоров, объём RAM и объём дисков, а не конкретные характеристики оборудования. SSD же наоборот сложная железяка, с которой нужен особый подход, но и прирост производительности от них можно получить на порядок, а то и больше.

Если всё ещё не убедил, то очень рекомендую посмотреть час кейноута (или полчаса на х2 скорости!). Это самый крутой кейноут, который я видел. Называется он I/O Acceleration from the Bottom Up, а рассказывает SVP storage в Samsung, а так же доктор CS Sangyeun Cho. Ссылка.

Топ 4 забавных факта с этого выступления:
- Количество памяти, которое можно впихнуть на 1 квадратный миллиметр SSD (Areal Density) растёт на 80% в год. Тренд продолжается последние 20 лет.
- Некоторые SSD настолько быстрые, что для них бутылочным горлышком выступает скорость PCI / SAS / SATA интерфейса.
- В 2017 году Samsung выпустил SSD на 16 TB под названием PM1633a. На момент выпуска это самый объёмный диск среди одновременно и SSD, и HDD в мире. Стоил в то время он дороже, чем слиток золота такой же массы.
- За счёт обработки данных ближе к SSD (Для гугления это называется Near-data processing) можно иногда получить х166 к скорости выполнения сложных join'ов на MariaDB. Подробнее о том как это работает в пейпере.

В целом, мне очень понравился формат, буду ходить ещё. На HotStorage 2021 я вышел через блог Aleksey Charapko, у которого там был пейпер в соавторстве. У него, кстати, есть еженедельная reading group, очень рекомендую, если интересно. Там часто выступают сами авторы работ, например как в работе про FoundationDB, о которой я писал тут. Можно просто читать, если ходить нет сил.

К сожалению, я не нашёл единый сайт со всеми конференциями такого рода, скажите, если знаете. Пока работает только магия твиттера, поскольку почти у всех конференций есть там профили. На кого подписаться: во-первых, профили ассоциаций-организаторов конференций USENIX и ACM как правило репостят что-то новенькое. Во-вторых, можно найти конкретные конференции, например тот же HotStorage или вот недавно прошёл ESEC/FSE.

Читать полностью…

FoundationDB: A Distributed Unbundled Transactional Key Value Store

#shark_whitepaper

Пока я пытаюсь осилить ARIES, немного ненапряжного и очень свежего case-study от июня 2021 года. Работа про распределенное KV хранилище FoundationDB. Всех авторов перечислять не буду, так как это 21 человек. Оригинал можно почитать по первой ссылке здесь.

FoundationDB (FDB) была разработана более 10 лет назад, и с тех пор используется в Apple, как одно из основных хранилищ данных, а с 2017 года проект доступен на github. Это NewSQL хранилище, т.е. помимо гибкости и средств для масштабирование, свойственных NoSQL решениям, FDB также поддерживает транзакционность аж до strict serializability, но не без ограничений, конечно же.

Обычно базы данных предоставляют все свои компоненты в виде одного процесса. Т.е. условный инстанс postgres — это одновременно и транспортный слой, и оптимизатор запросов, и execution engine, и storage engine. FDB идёт другим путем, используя опыт современных cloud-first подходов к созданию хранилищ данных. Она основана на unbundled architecture, т.е. база данных — это не один процесс, а несколько взаимодействующих процессов, каждый из которых может быть запущен на отдельном сервере и масштабироваться независимо. Такой подход позволяет подстраивать БД под профиль нагрузки по чтению и записи.

FoundationDB позиционирует себя, как фундамент, поверх которого можно реализовать дополнительную логику. Например, на основе FDB работает и графовый движок JanusGraph, и record-layer — очень упрощенный вариант реляционной БД, и даже прямо сейчас происходят попытки перевести CouchDB на FDB.

FDB логически состоит из двух слоёв: управляющий слой (Control Plane) и слой данных (Data Plane). Слой данных дополнительно делится ещё на три компонента: Transaction System (TS), Log System (LS) и Storage System (SS).

При чтении, клиент запрашивает версию записи в TS, а потом идёт напрямую в Storage System. При записи, запрос попадает в TS, который обеспечивает транзакционность через сочетание optimistic concurrency control (OCC) и multi-version concurrent control (MVCC). Всё происходит lock-free прямо в памяти. Далее запрос записывается в Log System, где хранится Write-Ahead Log (WAL), после чего ответ возвращается клиенту. Обновления WAL затем агрессивно считываются компонентами Storage System. Сейчас SS представляет собой инстансы SQLite (а я думал она нигде не используется...), но в планах заменить их на RocksDB. Кстати период MVCC насильно установлен в пять секунд. По словам авторов, это заставляет клиентов больше думать над тем, как правильно составлять запросы, что в целом звучит как правильный путь для OLTP хранилищ. Скалировать много маленьких запросов проще, чем подстраиваться и под тяжёлые, и под легкие запросы одновременно.

Ещё одной особенностью FDB является процесс восстановления при сбоях, называемый реконфигурацией. Когда Control Plane обнаруживает ошибки в TS/LS или просто попытку развернуть новую версию БД, он просто останавливает старые инстансы и запускает новые. Весь процесс занимает до пяти секунд. Это позволяет использовать реконфигурацию как для обновлений, так и для восстановления при ошибках. Более того, настолько быстрый процесс восстановления — то что доктор прописал для нестабильной cloud-based среды.

И последняя убер фича FDB — это simulation фреймворк, который писался ещё до начала работы над самой БД. Дело в том, что тестировать базы данных довольно тяжело. Здесь часто не помогают просто «юнит-тесты», так как проверить, что база всегда выполняет свои гарантии консистентности или durability очень сложно. Количество кейсов практически неограниченно. Симуляционный фреймворк позволяет производить сотни запусков компонентов БД в минуту, вносить произвольные ошибки на разных уровнях (сеть, диски, запросы и т.д.) и проверять, работает ли FDB, как ожидается. Более того, неудачные запуски всегда можно переиграть, так как сам фреймворк детерминированный.

Читать полностью…

Введение в семейство алгоритмов Gossip -> первый из четырёх постов
/channel/shark_in_it/79

Читать полностью…