четверг, 16 января 2020 г.

ARC - Adaptive Replacement Cache / ZFS

          Одним из самых известных отличительных качеств ZFS является ARC кэш(Adaptive Replacement Cache). В теории он обеспечивает примерно в 2 раза более высокий cache hit rate по сравнению с классическим LRU.  Алгоритм ARC был предложен  Nimrod Megiddo and Dharmendra S. Modha и описан в следующем whitepaper - https://www.usenix.org/legacy/events/fast03/tech/full_papers/megiddo/megiddo.pdf 
          Как и все гениальное - это алгоритм довольно простой. Ребята подумали и поняли что в принципе есть две стратегии кэширования страниц - кэшировать страницы который были недавно прочитаны и кэшировать страницы к которым часто обращаются повторно. Не смотря на схожесть - эти стратегии противоречат друг другу. Для каких-то паттернов нагрузки важно кэшировать то что было прочитано недавно, для каких-то важно кэшировать только какой-то набор постоянно используемых данных. В реальной жизни эти два паттерна всегда присутсвуют одновременно.  И поэтому ребята предложили иметь два LRU списка - один для недавно прочитанных страниц, второй для часто используемых страниц. Алгоритм пытается адаптироваться к текущей нагрузке и динамически изменять размеры этих списков - отдавая предпочтение либо кэшированию недавно прочитанных страниц либо кэшированию часто используемых страниц. 
           Реальная реализация которая находится в module/zfs/arc.c немного сложнее теоретической: 
  • Она работает с блоками разного размера
  • Она адаптируется к memory pressure. Если памяти не хватает размер обоих списков снижается
  • Не все страницы могут быть вытеснены в каждый момент времени. Если есть внешние ссылки на страницу, она не может быть вытеснена.

среда, 15 января 2020 г.

Реализация AVL дерева в Solaris/ZFS

          Меня всегда интересовали реализации структура данных на практике. Возьмем к примеру AVL-tree. С точки зрения теории все довольно понятно - сбалансированное двоичное дерево, поиск за log n, вставка от константы до log n. Но кроме O(n) есть еще реальное время выполнения операций, и при не слишком большом N это время гораздо важнее чем теоретические выкладки. Да, если N - очень большое то O(n) решает, но в реальной жизни случаи с очень большими N не так часто встречаются. Поэтому практические приемы используемые при реализации той или иной структуры данных не менее важны чем сам алгоритм. Собственно, в чем особенности реализации AVL дерева в Solaris/ZFS ?
  1. Написано на голом C, без классов (как и все то что должно работать в ядре)
  2. Не полезная нагрузка "вставляется" в узлы дерева, а наоборот - структуры данных необходимые для реализации дерева внедряются в те объекты которые планируется класть в дерево. Если быть точным - это даже не объекты а структуры (в терминах C). В результате - и payload и сами структуры данных дерева образуют единых блок данных. В результате резко повышается memory cache locality, в два раза снижается фрагментация данных (в классической реализации узел дерева это одна структура данных, в ней сидит указатель на собственно payload)
  3. Рекурсия не используется, только итерации. Для этого каждый узел дерева содержит указатель на родительский узел. Даже на C рекурсия медленнее чем цикл. Другая причина - этот код должен работать в ядре, где размер стэка не большой.
  4. Реализация не содержит блокировок - предполагается что тот кто использует структуру данных сам знает - нужно ли синхронизировать доступ к ней и если это необходимо - взял нужную блокировку
  5. Реализация не содержит выделений памяти. Все функции принимают на вход указатели на предварительно выделенные блоки памяти там где это необходимо. За счет этого достигается:
    1. Предсказуемость времени выполнения того или иного вызова. Выделение памяти это довольно рискованная в парадигме kernel-программирования операция которая может занять непредсказуемое время и завершиться непредвиденным результатом
    2. Абстрагирование  структуры данных от используемых механизмов выделения памяти.
  6.  Используются разные структуры данных на 32 и 64 битных платформах. Вся работа с структурами данных ведется через макросы. На 64-битной платформе флаги и другие мелкие значения упаковываются в младшие биты указателей. На 64-битной платформе младшие биты указателей всегда равны нулю. 
  7. Данные которые используются в наиболее часто вызываемых функциях, например avl_find() располагают в первых 64 битах структуры данных. Таким образом гораздо выше вероятность того что эти данные уже находятся в кэше процессора
  8. Вместо обычных конструкций ветвления if (больше) then {right} else {left} при обходе дерева используется node = node->child[compare(value, data)]. Почему так ? потому что branch prediction процессора обрабатывает if then конструкции хорошо только тогда когда вероятность переходя по одной из ветвей сильно выше, например при обработке ошибок. В случае прохода по дереву вероятность  пойти по левой и правой ветки примерно одинакова, что будет приводить к miss-prediction и сбросу конвеера процессора. Конвеер современных CPU очень глубокий, поэтому сброс конвеера - это довольно затратная операция. Поэтому вместо этого указатели на левый и правый child помести в массив, и результат сравнения искомого значения с тем что хранится в текущей ноде используется как индекс для получения указателя на следующий элемент дерева. В исходном кода мне кажется это будет понятнее - https://github.com/zfsonlinux/zfs/blob/2476f103069e83e17d2c9cec4191af34a7996885/module/avl/avl.c#L256 

          

вторник, 14 января 2020 г.

Real User Monitoring по взрослому

            Real User Monitoring (RUM) это с первого взгляда довольно простая фигня которую можно чуть ли не за пол дня на коленке запилить. Но если копнуть глубже то понимаешь что большинство реализаций довольно ущербные - те же самые RUM от NewRelic или RUM от Pingdom. Не говоря уже про написанные на коленке варианты.
               Из того что заслуживает внимание - Doppler от Facebook Ребята добавляют в каждый N-й ответ кусок JS-а который выполняет загрузку небольшой картинки с рандомного домена - например  xmdmddddm.dns.facebook.com, тем самым проверяя пессимистичный сценарий полный DNS lookup + HTTP запрос + ответ. Потом загружают еще одну маленькую картинку с того же домена.  Вычтем результат второго эксперимента из первого и получим пессимистичное время DNS lookup.  Второе время - минимальное время загрузки ресурса с сайта FB.  Они также записывают каждый проведенный эксперимент и далее аггрегируют эти  данные по AS-number. Количество автономных систем относительно невелико (около 35к), так что в таком виде данные уже гораздо легче анализировать. 
              Но ребята из dropbox пошли дальше  - https://blogs.dropbox.com/tech/2020/01/intelligent-dns-based-load-balancing-at-dropbox/ . Они сделали свой аналог doppler, с аггрегировали полученные данные  и из них сделали latency-map интернета. Скормили этот map DNS серверам (они используют ns1.com) и используют для latency based балансировки траффика между своими датацентрами. В общем получилась конфетка. 

пятница, 10 января 2020 г.

ZFS monitoring - V2

         Добил наконец-то вторую версию мониторинга ZFS. В ней добавлены метрики получаемые через zpool iostat.   Так как мой первый пул реквест в телеграф до сих пор ждет своего счастливого часа - https://github.com/influxdata/telegraf/pull/6724, этот код пока живет в отдельной ветке - https://github.com/yvasiyarov/telegraf/tree/zfs_zpool_linux2 Все новые метрики также появились в dashboard -  https://github.com/yvasiyarov/zfs-dashboard Теперь он так порядочно распух:

четверг, 9 января 2020 г.

Из интересно-прочитанного

       Довольно интересная статья про монорепу в Яндексе - Arc — система контроля версий для монорепозитория. Доклад Яндекса. Прочитав статью понимаешь что никакая это не система контроля версий - это проложение которое работает поверх SVN и по сути занимается его масштабированием.  Вся монорепа по прежнему лежит в SVN, который обеспечивает единственную операцию - commit в trunk. На Arc лежит масштабирование клиентских операций - их фактически перенесли на сервер, работа с pull реквестами и тд. Пул реквестов в оригинальном SVN нет, но ребятам очень хотелось их. Вот они и навертели их поверх SVN. Но если серьезно - мне нравится их подход к решению проблемы. Он проблемно-ориентированный. Они не сказали - надо все выкинуть к херам и два года пилить свою собственную систему управления исходным кодом, а взяли и решили конкретные проблемы с которыми они сталкивались с минимальным риском для компании. Ведь по сути максимум чем они рискуют - это коммитами в рабочих ветках. А эти данные полюбому сохраняются минимум еще в одном месте - на машине разработчика. Как только ветка вливается в монорепу - за ее сохранность отвечает SVN.
      Прочитал перевод интересной статьи про использование unsafe.Pointer и то какие при этом могут возникать проблемы - https://4gophers.ru/articles/unsafe/#.XhcssCq3p26 

вторник, 10 декабря 2019 г.

Мониторинг ZFS

               Для того чтобы разобраться с зависаниями операций по созданию snapshots в ZFS решил ее замониторить нормально. В Telegraf есть плагин для этого https://github.com/influxdata/telegraf/tree/master/plugins/inputs/zfs Начал разбираться с ним и выяснил забавное - в версии для Linux он собирает кучу детальной информации, но вот самые базовые метрики, на которые нужно смотреть в первую очередь (статус, capacity, fragmentation и тд) - не собирает. Причем такая ущербность присуща только Linux версии, под FreeBSD все нормально.  Нашел Isssue 2,5 летней давности - https://github.com/influxdata/telegraf/issues/2616
Тут во всей красе появился один из недостатков open source проектов - долго обсуждали какое решение лучше,  так и не довели ни одно до конца и забросили.  Я набросал pull request дабы эту проблему наконец-то закрыть - https://github.com/influxdata/telegraf/pull/6724  К сожалению от маинтейнеров ни ответа ни привета.
                  Забил болт, решил не ждать их и использовать свой форк. Набросал тут dashboard - может кому пригодится:

Сам dashboard можно взять отсюда https://grafana.com/grafana/dashboards/11364 или отсюда - https://github.com/yvasiyarov/zfs-dashboard    


вторник, 19 ноября 2019 г.

ZFS и ее особенности

     Поставил себе цель разобраться с тем как работает ZFS. Прочитал кучу полезной и не очень информации.  Потом наткнулся на статью http://www.bog.pp.ru/work/zfs.html Это самое подробное и детальное описание того как работает ZFS которое я встречал. Честно, я очень хотел бы быть хотябы в половину таким же умным как тот кто написал эту статью, но мне далеко еще до этого уровня.  Да, после прочтения статьи первоначальное чувство восторга от "ух ты какая ZFS крутая" смешивается  с горьковатым "херня полная багов", но на самом деле это и есть опыт. Все что есть в этом мире - это хрень полная багов. Просто не все с ними встречаются. 
      У этого же автора есть очень крутая статья про RAID - http://www.bog.pp.ru/hard/raid.html