Как работает ZFS — часть 2: metaslab

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

Здесь я немного усложню задачу — в первой части был описан только один vdev; здесь их у нас будет несколько, поскольку алгоритм должен выбрать и vdev, куда мы будем писать блок данных, и metaslab внутри vdev'a. В продакшн системе может быть несколько десятков vdev, и правильно распределить данные по ним критично — перебалансировать их мы уже не сможем без копирования всех данных. Цель правильного алгоритма — распараллелить данные так, чтобы на каждом девайсе их было примерно одинаковое количество, выровнять неравномерное заполнение, но и не перегрузить один из девайсов (это будет тормозить запись на весь пул).

 NAME STATE READ WRITE CKSUM
 tank ONLINE 0 0 0
 c1t6d0 ONLINE 0 0 0
 c1t5d0 ONLINE 0 0 0

Для начала, важное замечание: ZFS рассчитан на то, что все девайсы в пуле имеют одинаковый размер. Иначе, например если добавить 2Тб диск в пул из 1Тб дисков, на 2Тб диске в результате окажется в два раза больше данных, и он начнёт влиять на суммарный IOPs системы — алгоритм аллокатора учитывает процент заполнения, а не количество данных в байтах.

На данный момент в ZFS есть четыре алгоритма аллокатора. Переменная zfs_metaslab_ops содержит поинтер на структуру space_map_ops_t, в которой есть поинтеры на семь функций, которые использует каждый конкретный алгоритм. Например, в Illumos используется алгоритм metaslab_df, и соответствующий стракт с поинтерами на функции выглядит вот так:

static space_map_ops_t metaslab_df_ops = {
 metaslab_pp_load,
 metaslab_pp_unload,
 metaslab_df_alloc,
 metaslab_pp_claim,
 metaslab_pp_free,
 metaslab_pp_maxsize,
 metaslab_df_fragmented
};

Пять из этих функций используются во всех алгоритмах; разница собственно только в metaslab_*_alloc() и metaslab_*_fragmented() — сам аллокатор, и функция, которая решает насколько фрагментировано свободное место в конкретном metaslab. Аллокаторы, которые можно использовать: DF (Dynamic-Fit), FF (First-Fit), и два экспериментальных, CDF и NDF — что они означают, не знает никто.

FF из них самый простой — он пишет куски данных в первое попавшееся свободное место при трассировке АВЛ-дерева по порядку, и разделяет блоки записи на сегменты, если они не влезают. За счёт этого, FF — очень медленный алгоритм, так как для записи одного блока он должен трассировать всё дерево, пока не наберётся достаточное количество сегментов. Для записи 1ГБ данных, например, worst case — 20 млн сегментов по 512 байт, и очень сильная фрагментация данных как результат. FF используется другими алгоритмами как последний вариант, если они не могут найти место по-другому — например, DF изпользует FF если в данном метаслабе меньше 4% свободного места (int metaslab_df_free_pct = 4;). Единственный плюс FF в том, что он единственный может заполнить фрагментированный метаслаб на 100%.

*DF алгоритмы работают по другому — они строят карту свободного места freemap в том метаслабе, в который на данный момент идёт запись, сортируют ее по размеру и/или близости кусков непрерывного свободного места, и пытаются выбрать наиболее оптимальный вариант размещения данных с точки зрения скорости записи, количества движений головки диска, и минимальной фрагментации записываемых данных.

Например, для всех них работает функция metaslab_weight(), которая даёт небольшой приоритет метаслабам, которые находятся на внешних регионах пластины диска (для short-stroke эффекта). Если использовать только SSD, то имеет смысл тюнить ZFS, отключая эту часть алгоритма, потому-что к SSD short-stroking не применим.

Итак, в алгоритмы аллокатора данные попадают из ZIO pipeline — оттуда вызываются функции metaslab_alloc() (сам аллокатор для записи) и metaslab_free() (освобождаем место, собираем мусор).

metaslab_alloc(spa_t *spa, metaslab_class_t *mc, uint64_t psize, blkptr_t *bp,
 int ndvas, uint64_t txg, blkptr_t *hintbp, int flags)

Туда передаётся: *spa — поинтер на структуру самого массива данных (zpool); *mc — класс метаслабов, в котором в том числе есть поинтер на zfs_metaslab_ops; psize — размер данных; *bp — поинтер на сам блок; ndvas — количество независимых копий данных, которое требуется для данного блока (1 для данных; 2 для большинства метаданных; 3 в некоторых случаях для метаданных, которые находятся высоко в АВЛ-дереве. Смысл в дупликации метаданных в том, что если единственный блок с метаданными для сегмента дерева утерян, мы теряем всё, что находится под ним. Такие блоки называются ditto blocks, и алгоритм старается писать их на разные vdevы).

Далее, txg — порядковый номер группы транзакций, которую мы пишем; *hintbp — подсказка, используемая для того, чтобы блоки которые рядом логически были также рядом на диске, и шли на тот же vdev; flags — 5 бит, которые позволяют аллокатору узнать нужно ли использовать какие-либо специфические варианты аллокации — использовать или игнорировать подсказку *hintbp, и использовать ли ganging (просьба писать группу child блоков на тот же vdev, что и их header, для более эффективной работы ZFS prefetch и vdev cache).

define METASLAB_HINTBP_FAVOR 0x0
define METASLAB_HINTBP_AVOID 0x1
define METASLAB_GANG_HEADER 0x2
define METASLAB_GANG_CHILD 0x4
define METASLAB_GANG_AVOID 0x8

/*
 * Allow allocations to switch to gang blocks quickly. We do this to
 * avoid having to load lots of space_maps in a given txg. There are,
 * however, some cases where we want to avoid "fast" ganging and instead
 * we want to do an exhaustive search of all metaslabs on this device.
 * Currently we don't allow any gang, zil, or dump device related allocations
 * to "fast" gang.
 */
#define CAN_FASTGANG(flags) \
 (!((flags) & (METASLAB_GANG_CHILD | METASLAB_GANG_HEADER | \
 METASLAB_GANG_AVOID)))

 /*
 * If we are doing gang blocks (hintdva is non-NULL), try to keep
 * ourselves on the same vdev as our gang block header. That
 * way, we can hope for locality in vdev_cache, plus it makes our
 * fault domains something tractable.
 */

Далее, собственно, идёт самая важная часть кода, в которой логика самого выбора метаслаба для записи: metaslab_alloc_dva(). В функции почти 200 строк хитрого кода, который я попытаюсь объяснить.

Сначала, мы берём все группы метаслабов для всех vdev'ов, и проходимся по ним циклом аллокатора (mg_rotor), используя подсказки, если они есть. Мы пропускаем vdev'ы, на которые запись в данный момент нежелательна, например те, в которых умер один из дисков, или идёт восстановление raidz-группы. (Don't allocate from faulted devices.) Мы также пропускаем диски, на которых были какие-то ошибки записи, для данных у которых на дисках будет только одна копия. (Avoid writing single-copy data to a failing vdev.)

Ротор работает по кругу пока не кончатся данные, отправленные на запись. Внутри этого цикла, по очереди выбирается оптимальный vdev, потом в нём, используя metaslab_group_alloc(), выбирается лучший метаслаб, потом решаем сколько данных записать в этот метаслаб, сравнивая процент использования vdev'a с другими. Эта часть кода очень критична, поэтому привожу ее полностью:

 offset = metaslab_group_alloc(mg, psize, asize, txg, distance,
 dva, d, flags);
 if (offset != -1ULL) {
 /*
 * If we've just selected this metaslab group,
 * figure out whether the corresponding vdev is
 * over- or under-used relative to the pool,
 * and set an allocation bias to even it out.
 */
 if (mc->mc_aliquot == 0) {
 vdev_stat_t *vs = &vd->vdev_stat;
 int64_t vu, cu;

 vu = (vs->vs_alloc * 100) / (vs->vs_space + 1);
 cu = (mc->mc_alloc * 100) / (mc->mc_space + 1);

 /*
 * Calculate how much more or less we should
 * try to allocate from this device during
 * this iteration around the rotor.
 * For example, if a device is 80% full
 * and the pool is 20% full then we should
 * reduce allocations by 60% on this device.
 *
 * mg_bias = (20 - 80) * 512K / 100 = -307K
 *
 * This reduces allocations by 307K for this
 * iteration.
 */
 mg->mg_bias = ((cu - vu) *
 (int64_t)mg->mg_aliquot) / 100;
 }

Например, если нам надо записать 1МБ данных на массив из двух дисков, один из которых заполнен на 20%, а второй — на 80%, мы запишем 819КБ на первый, и 205КБ на второй. Здесь, кстати, можно сделать одну очень интересную вещь — несколько месяцев назад я добавил статистику latency для каждого vdeva в ZFS (она находится в vdev_stat_t->vs_latency[] в NexentaStor; в Illumos пока не добавили), и её можно использовать в качестве одного из факторов при записи новых данных, либо учитывая и её и свободное место в какой-либо пропорции, либо используя только её. Такой изменённый алгоритм я тоже написал, но он пока не используется в продакшн-системах. Он имеет смысл когда либо в массиве есть диски разного типа и скорости, либо когда один из дисков начинает умирать (тормозить), но пока не настолько плох, и на нём нет ошибок.

Наконец, итерация за итерацией, цикл отправляет все данные на запись в metaslab group, и заканчивается для этой transaction group (txg), a в группе метаслабов работает система metaslab_weight() (см. начало статьи), и через систему space map, учитывая maxfree (максимальный кусок непрерывного свободного места), с помощью трассировки АВЛ-деревьев и соответствующего алгоритма (DF, FF, CDF, NDF) распихивает данные оптимальным для алгоритма образом, после чего мы наконец получаем физический адрес блока, в который мы будем писать на диск, и данные идут в очередь на запись в sd (Scsi Device) драйвер.