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



Рост популярности контейнеров и их использование в совокупности с контрольными группами выявили серьезную проблему масштабируемости, которая приводит к значительному падению производительности на больших машинах. Проблема в том, что время обхода 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.
Третья итерация занимает 8 секунд: 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’ов:

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.

Если повторить тест сбросf кэшей, то с использованием нового алгоритма он показывает существенно лучшие результаты:

$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

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

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

Вы можете помочь и перевести немного средств на развитие сайта



Комментарии (7):

  1. gecube
    /#19600716

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

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

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

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

  2. knutov
    /#19600820

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

    • avagin
      /#19602006

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

      • knutov
        /#19602828

        Да, всё так.

        • avagin
          /#19604570

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

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

          • knutov
            /#19604580

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


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

  3. crazylh
    /#19600898

    Молодцы!