четверг, 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