Как и зачем мы оптимизировали алгоритм очистки SLAB-кэшей в ядре Linux

    Рост популярности контейнеров и их использование в совокупности с контрольными группами выявили серьезную проблему масштабируемости, которая приводит к значительному падению производительности на больших машинах. Проблема в том, что время обхода SLAB-кэшей зависит квадратично от количества контейнеров, а активное потребление больших объемов памяти за короткий период может стать причиной ухода системы в busy loop, потребляющий 100% процессорного времени. Сегодня мне хотелось бы рассказать, как мы решили эту проблему, изменив алгоритм учета использования контрольной группой memcg объектов SLAB-кэшей и оптимизировав функцию shrink_slab().

    Очистка памяти

    Почему вообще встал вопрос оптимизации процессов в ядре? Все началось с того, что один из наших заказчиков, активно использующий контейнеры и контрольные группы памяти (memcg), обратил внимание на странные пики потребления ресурсов процессора, происходящие время от времени. Обычная загрузка системы была порядка 50%, а в пиковые моменты было занято 100% процессорного времени, причем практически все оно потреблялось ядром (sys time).
    Сама нода была многопользовательской, и на ней было запущено порядка 200 OpenVZ контейнеров. Анализ показал, что большое количество пользователей создавали вложенные Docker контейнеры и многоуровневые иерархии контрольных групп памяти. Каждый пользовательский контейнер верхнего уровня содержал порядка 20 точек монтирования и 20 контрольных групп памяти (memcg), созданных systemd. Кроме этого были точки монтирования и контрольные группы, созданные упомянутым выше Docker. Проще говоря, нода была сильно загружена, и нагрузка на нее была намного сильнее, чем среднестатистически у всех остальных наших заказчиков. Нам было интересно найти причину появления этих пиков, поскольку такая же проблема могла проявляться и на менее загруженных машинах, где была малозаметной (например, давать пики по +5% sys time, которые ухудшают производительность).

    Путем манипуляций с perf, удалось поймать пик и снять трейс. Выяснилось, что большая часть процессорного времени расходуется на очистку кэшей SLAB, а именно, кэшей суперблока:

    -  100,00%     0,00%  kswapd0  [kernel.vmlinux]     [k] kthread                                                                             
       - 99,31% balance_pgdat                                                                                                             
         - 82,11% shrink_zone                                                                                                             
           - 61,69% shrink_slab                                                                                                          
             - 58,29% super_cache_count
               + 54,56% list_lru_count_one


    Здесь стоит сделать пояснение и остановиться подробнее на этом вопросе. Всем известно, что ядро на некоторое время кэширует неиспользуемые данные перед тем как окончательно освободить память. Ядро широко использует этот принцип. Например, кэш страниц содержит в себе страницы данных, относящихся к файлу, что существенно ускоряет повторный доступ к ним при чтении (потому что не требуется заново обращаться к диску). В нашем же случае проблема возникла с кэшем метаданных суперблока, содержащихся в двух списках LRU: s_dentry_lru и s_inode_lru.

    LRU (Least Recently Used)

    struct lru_list указывает на массив связных списков, и каждой активной memcg соответствует один элемент (list_lru_one) в этом массиве. Когда некий объект SLAB перестает использоваться ядром, ядро добавляет его в один из связных списков массива (в зависимости от того, к какой memcg объект относится, или, грубо говоря, к какой memcg относился процесс, когда он создавал этот объект). Сам массив описан следующим образом (lru_list::node::memcg_lrus):

    struct list_lru_memcg {
            struct rcu_head     	rcu;
            /* array of per cgroup lists, indexed by memcg_cache_id */
            struct list_lru_one 	*lru[0]; /* Массив связных списков */
    };
    struct list_lru_one {
            struct list_head    	list; /* Связный список объектов */
            /* may become negative during memcg reparenting */
            long                	nr_items; /* Количество объектов в списке */
    };
    

    lru[0] указывает список объектов, относящихся к memcg с ID 0;
    lru[1] указывает список объектов, относящихся к memcg с ID 1;

    lru[n] указывает список объектов, относящихся к memcg с ID n;

    В нашей проблеме фигурируют LRU списки s_dentry_lru и s_inode_lru, и как нетрудно догадаться из названия, они содержат неиспользуемые объекты dentry и inode файловой системы.
    В дальнейшем, при нехватке памяти в системе или конкретной memcg, часть из элементов списка окончательно освобождается, и занимается этим специальный механизм, называющийся shrinker.

    Shrinker

    Когда ядру требуется выделить страницы памяти, а свободной памяти на NUMA-узле или в системе нет, запускается механизм по ее очистке. Он пытается выбросить или сбросить на диск некоторое количество: 1)страниц содержимого файлов из page cache; 2)страниц, относящихся к анонимной памяти в своп, и 3)кэшированных объектов SLAB (с ними и связана проблема, с которой мы столкнулись).

    Выкидывание части кэшированных объектов SLAB влияет на освобождение страниц не напрямую: их размер, как правило, существенно меньше размера страницы, и в одной странице содержатся сотни объектов. При освобождении части объектов, в страницах SLAB возникают свободные промежутки памяти, которые могут быть использованы для создания других объектов SLAB. Этот алгоритм принят в ядре намерено: он простой и довольно эффективный. Интересующийся читатель может посмотреть формулу выбора части объектов для очистки в функции do_shrink_slab().

    Эта функция выполняет собственно очистку части объектов, руководствуясь описанием, переданным ей в struct shrinker:

    static unsigned long do_shrink_slab(struct shrink_control *shrinkctl, struct shrinker *shrinker, int priority)
    {	…
            /* Посчитать объекты */
            freeable = shrinker->count_objects(shrinker, shrinkctl);
            if (freeable == 0)
    	        return 0;
            total_scan = НЕКОТОРАЯ_ЧАСТЬ(freeable);
            while (total_scan >= batch_size) {
    	        /* Освободить объекты */
                    ret = shrinker->scan_objects(shrinker, shrinkctl);
                    total_scan -= shrinkctl->nr_scanned;
            }
            ...
    }

    Применительно к shrinker суперблока, эти функции реализованы следующим образом. Каждый суперблок поддерживает свои собственные s_dentry_lru и s_inode_lru списки неиспользуемых объектов, относящихся к нему:

    struct super_block {
            ...
            struct shrinker s_shrink;   	/* per-sb shrinker handle */
            ...
            struct list_lru     	s_dentry_lru;
            struct list_lru     	s_inode_lru;
            …
    };


    Метод .count_objects возвращает количество объектов:

    static unsigned long super_cache_count(struct shrinker *shrink, struct shrink_control *sc)
    {
            total_objects += list_lru_shrink_count(&sb->s_dentry_lru, sc);
            total_objects += list_lru_shrink_count(&sb->s_inode_lru, sc);
            /* Вернуть часть общего количества объектов) */
            total_objects = vfs_pressure_ratio(total_objects);
            return total_objects;
    }


    Метод .scan_objects собственно, освобождает объекты:

    static unsigned long super_cache_scan(struct shrinker *shrink, struct shrink_control *sc)
    {
            /* Освободить часть объектов из s_dentry_lru */
            prune_dcache_sb(sb, sc);
            /* Освободить часть объектов из s_inode_lru */
            prune_icache_sb(sb, sc);
    }

    Количество объектов, которые нужно освободить, передается в параметре sc. Также, там указана memcg, объекты которой должны быть выкинуты из LRU:

    struct shrink_control {
            int nid; /* ID NUMA узла */
            unsigned long nr_to_scan; /* Количество объектов */
            struct mem_cgroup *memcg; /* memcg */
    };
    

    Таким образом, prune_dcache_sb() выбирает связный список из массива struct list_lru_memcg::lru[] и работает с ним. Аналогично поступает prune_icache_sb().

    Старый алгоритм обхода shrinker’ов

    При стандартном подходе “выкидывание” объектов из SLAB при нехватке памяти в
    sc->target_mem_cgroup происходит следующим образом:

    shrink_node()
    {
            …
            struct mem_cgroup *root = sc->target_mem_cgroup;
            /* Цикл по всем дочерним для sc->target_mem_cgroup групп */
            memcg = mem_cgroup_iter(root, NULL, &reclaim);
            do {
                    …
                    shrink_slab(memcg, ...);
                    …
            } while ((memcg = mem_cgroup_iter(root, memcg, &reclaim)));
            ...
    }
    

    Проходим по всем дочерним memcg и вызываем shrink_slab() для каждой из них. Далее, в функции shrink_slab() мы проходим по всем shrinker’ам и для каждого из них вызываем do_shrink_slab():

    static unsigned long shrink_slab(gfp_t gfp_mask, int nid, struct mem_cgroup *memcg, int priority)
    {
            list_for_each_entry(shrinker, &shrinker_list, list) {
                    struct shrink_control sc = {
                            .nid = nid,
                            .memcg = memcg,
                    };
                     
                    ret = do_shrink_slab(&sc, shrinker, ...);
    	}
    }
    

    Вспомним, что для каждого суперблока добавляется свой shrinker в этот список. Посчитаем сколько раз будет вызван do_shrink_slab() для случая с 200 контейнерами по 20 memcg и 20 точек монтирования в каждом. Всего мы имеем 200*20 точек монтирования и 200 * 20 контрольных групп. При нехватке памяти в самой верхней memcg, мы будем вынуждены обойти все ее дочерние memcg (т.е., вообще все), и для каждой из них вызвать каждый из shrinker из списка shrinker_list. Таким образом, ядро сделает 200 * 20 * 200 * 20 = 16000000 вызовов функции do_shrink_slab().

    При этом, подавляющее число вызовов этой функции будет бесполезно: контейнеры обычно изолированы между собой, и вероятность того, что контейнер CT1 будет использовать super_block2, созданный в CT2, в общем случае невысока. Или, что то же самое, если memcg1 — контрольная группа из CT1, то соответствующий ей элемент массива super_block2->s_dentry_lru->node->memcg_lrus->lru[memcg1_id] будет пустым списком, и нет смысла вызывать do_shrink_slab() для него.

    Эту проблему можно смоделировать с помощью простого bash-скрипта (здесь используются данные из патчсета, который был в дальнейшем передан в ядро):
    $echo 1 > /sys/fs/cgroup/memory/memory.use_hierarchy
    $mkdir /sys/fs/cgroup/memory/ct
    $echo 4000M > /sys/fs/cgroup/memory/ct/memory.kmem.limit_in_bytes
    $for i in `seq 0 4000`;                                                          
    do                              
            mkdir /sys/fs/cgroup/memory/ct/$i;  
            echo $$ > /sys/fs/cgroup/memory/ct/$i/cgroup.procs;
            mkdir -p s/$i; mount -t tmpfs $i s/$i; touch s/$i/file;
    done
    

    Посмотрим что будет, если 5 раз подряд вызывать процедуру сброса кэшей:
    $time echo 3 > /proc/sys/vm/drop_caches

    Первая итерация продолжается 14 секунд, потому что кэшированные объекты действительно есть в памяти: 0.00 user 13.78 system 0:13.78 elapsed 99% CPU.
    Вторая итерация занимает 5 секунд, хотя объектов уже нет: 0.00user 5.59system 0:05.60elapsed 99%CPU.
    Третья итерация занимает 5 секунд: 0.00user 5.48system 0:05.48elapsed 99%CPU
    Четвертая итерация занимает 8 секунд: 0.00user 8.35system 0:08.35elapsed 99%CPU
    Пятая итерация занимает 8 секунд: 0.00user 8.34system 0:08.35elapsed 99%CPU

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

    Новый алгоритм обхода shrinker’ов

    От нового алгоритма хотелось добиться следующего:

    1. освободить его от недостатков старого и
    2. не добавлять новых блокировок. Вызывать do_shrink_slab() только тогда, когда в этом есть смысл (то есть не пуст соответствующий связный список из массива s_dentry_lru или из массива s_inode_lru), но при этом напрямую не обращаться к памяти связных списков.

    Было понятно, что это может обеспечить только новая структура данных поверх разнородных shrinker’ов (бывают shrinker’ы не только суперблока, но и других объектов данных, не описанных в этой статье. Читатель может ознакомиться с ними, поискав по ключевому слову prealloc_shrinker() в коде ядра). Новая структура данных должна позволять кодировать два состояния: “имеет смысл вызывать do_shrink_slab()” и “не имеет смысла вызывать do_shrink_slab()”.

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

    Каждый shrinker получает свой уникальный id (shrinker::id), а каждая memcg — битовую карту, способную вместить наибольший id из зарегистрированных в данный момент. Когда в список s_dentry_lru->node->memcg_lrus->lru[memcg_id] добавляется первый элемент, в битовую карту соответствующей memcg выставляется в 1 бит с номером shrinker->id. То же самое в случае s_inode_id.

    Теперь цикл в shrink_slab() может быть оптимизирован для обхода только необходимых shrinker’ов:

    unsigned long shrink_slab()
    {
            …
            for_each_set_bit(i, map, shrinker_nr_max) {
                    …
                    shrinker = idr_find(&shrinker_idr, i);
                    …
                    do_shrink_slab(&sc, shrinker, priority);
                    …
            }
    }
    

    (Также реализована чистка бита, когда shrinker переходит в состояние “нет смысла вызывать do_shrink_slab(). См. подробнее в коммите на Github.

    Если повторить тест сброса кэшей, то с использованием нового алгоритма он показывает существенно лучшие результаты:
    $time echo 3 > /proc/sys/vm/drop_caches

    Первая итерация: 0.00user 1.10system 0:01.10elapsed 99%CPU
    Вторая итерация: 0.00user 0.00system 0:00.01elapsed 64%CPU
    Третья итерация: 0.00user 0.01system 0:00.01elapsed 82%CPU
    Четвертая итерация: 0.00user 0.00system 0:00.01elapsed 64%CPU
    Пятая итерация: 0.00user 0.01system 0:00.01elapsed 82%CPU
    Длительность итераций со второй по пятую — 0.01 секунды, в 548 раз быстрее, чем было раньше.

    Поскольку аналогичные действия по сбросу кэшей происходят при каждой нехватке памяти на машине, то эта оптимизация существенно улучшает работу машин с большим количеством контейнеров и контрольных групп памяти. Набор патчей (17 штук) был принят в ванильное ядро, и вы можете найти его там, начиная с версии 4.19.

    В процессе ревью патчей появился сотрудник Google, и выяснилось, что они столкнулись с такой же проблемой. Поэтому патчи были дополнительно протестированы на другом типе нагрузки.
    В результате патчсет был принят с 9-й итерации; а его вхождение в ванильное ядро заняло около 4-х месяцев. Также на сегодня патчсет включен в наше собственное ядро Virtuozzo 7, начиная с версии vz7.71.9
    • +22
    • 5,4k
    • 7
    Virtuozzo
    75,00
    Разработчик ПО для контейнерной виртуализации
    Поделиться публикацией

    Комментарии 7

      0
      а его вхождение в ванильное ядро заняло около 4-х месяцев

      я не понимаю — много или мало это? Т.е. вроде как рекорд по скорости, да? Ну, так напишите!
      Нам было интересно найти причину появления этих пиков, поскольку такая же проблема могла проявляться и на менее загруженных машинах, где была до малозаметной (например, давать пики по +5% sys time, которые ухудшают производительность).

      что, простите? Написано совершенно не по-русски («где была до малозаметной „)

      Ну, и обязательная просьба — пожалуйста, выделяйте код форматированием… ну, блин, правда глазки болят к полуночи, чтобы простыни кода воспринимать. Материал-то авторский, но подача… так себе
        0

        А будет ли бекпорт этого в OpenVZ 6?

          +1
          Кажется, вы еще в 2011 году пытались всем объяснить, что не надо это использовать, а тут просите бекпортов?
          k001.livejournal.com/819624.html
            0

            Да, всё так.

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

              К слову, это открытый продукт, патчи в апстриме, и вы можете помочь забекпортить их. Это немного добавит в вашу подпорченую карму:).
                0

                Не прошу бекпортов, а спрашиваю будут ли.


                Потому что большая инертность и куча "легаси", которое проще не трогать, пока оно как-то работает.

          +3
          Молодцы!

          Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

          Самое читаемое