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

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

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

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

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

— 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.

Когда некий объект SLAB перестает использоваться ядром, ядро добавляет его в один из связных списков массива (в зависимости от того, к какой memcg объект относится, или, грубо говоря, к какой memcg относился процесс, когда он создавал этот объект). LRU (Least Recently Used)

struct lru_list указывает на массив связных списков, и каждой активной memcg соответствует один элемент (list_lru_one) в этом массиве. Сам массив описан следующим образом (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.

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

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

При освобождении части объектов, в страницах 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) ; 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().

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

Эту проблему можно смоделировать с помощью простого 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

00 user 13. Первая итерация продолжается 14 секунд, потому что кэшированные объекты действительно есть в памяти: 0. 78 elapsed 99% CPU
Вторая итерация занимает 5 секунд, хотя объектов уже нет: 0. 78 system 0:13. 59system 0:05. 00user 5. 00user 5. 60elapsed 99%CPU.
Третья итерация занимает 8 секунд: 0. 48elapsed 99%CPU
Четвертая итерация занимает 8 секунд: 0. 48system 0:05. 35system 0:08. 00user 8. 00user 8. 35elapsed 99%CPU
Пятая итерация занимает 8 секунд: 0. 35elapsed 99%CPU 34system 0:08.

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

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

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

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

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

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

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

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


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Из песочницы] Haiku β1 — сделаем /b/ OS великой снова

Совсем недавно (почти 4 месяца назад) вышла новая Haiku (далее — просто BeOS, ибо проект гораздо удачнее ReactOS — настолько, что разница между Haiku и BeOS уже пренебрежимо мала). Да и недавно прочитанный киберпанк-роман Александра Чубарьяна давал понять, что BeOS ...

Минкомсвязи одобрило законопроект об изоляции рунета

Министерство цифрового развития, связи и массовых коммуникаций РФ поддержало законопроект №608767-7 об автономной работе рунета, внесённый в Госдуму 14 декабря 2018 года. Об этом сегодня сообщил замглавы Минкомсвязи Олег Иванов в ходе расширенного заседания комитета Госдумы по информационной политике, информационным технологиям ...