Конфигурируемые системы: покрывающие массивы, модели фич и поиск по конфигурациям

В предыдущей статье пространство поиска рождалось из структуры кода. Здесь оно рождается из вариантов сборки и запуска: флаги компилятора, фиче-флаги, версии зависимостей, СУБД, локали, платформы, параметры JVM или PostgreSQL. Каждая такая точка вариативности умножает число возможных систем, и очень быстро выясняется, что «наш продукт» — это не одна программа, а семейство из миллионов программ, из которых вы регулярно собираете и тестируете три.

Отсюда два разных вопроса, и оба решаются поиском:

1. Какие конфигурации тестировать, если все — нельзя? Это комбинаторное тестирование (combinatorial interaction testing, CIT).
2. Какая конфигурация лучшая по производительности, стоимости или памяти? Это оптимизация конфигурации (configuration tuning).

Первый вопрос — основная часть статьи; второй разберём в конце и передадим следующей главе, потому что он весь про дорогой фитнес.

Сколько стоит «протестировать все конфигурации»

Единственный известный мне эксперимент, где команда честно собрала и протестировала всё пространство реального продукта, — работа по генератору JHipster: Halin, Nuttinck, Acher, Devroey, Perrouin, Baudry, «Test them all, is it worth it? Assessing configuration sampling on the JHipster Web development stack», Empirical Software Engineering, 2019. Цифры оттуда стоит запомнить:

• пространство после учёта ограничений — 26 257 конфигураций;
• полный перебор потребовал тысяч часов машинного времени на кластере (месяцы на одной машине);
• около трети конфигураций вообще не собирались или падали — то есть дефекты сидели именно в комбинациях опций, а не в «основном» коде;
• случайная выборка и t-wise-выборки находили большинство дефектных комбинаций за доли процента этой стоимости.

Последний пункт — оправдание всей области. Полный перебор не просто дорог, он ещё и избыточен: дефекты, связанные с конфигурацией, обычно вызываются взаимодействием малого числа опций.

Это эмпирическое наблюдение впервые аккуратно измерили Kuhn, Wallace и Gallo, «Software Fault Interactions and Implications for Software Testing», IEEE TSE 2004: в изученных системах не нашлось ни одного дефекта, для проявления которого требовалось бы согласованное взаимодействие более шести параметров, а подавляющее большинство проявлялось при одном или двух. Отсюда практическое правило: покрывать надо не все комбинации, а все пары (или тройки) значений.

Тест-дизайнерский взгляд на pairwise — какие параметры вообще выделять, где брать классы эквивалентности, когда попарного покрытия достаточно — разобран в статье о тест-дизайне. Здесь мы смотрим с другой стороны: как построить такой набор, когда параметров десятки, между ними есть запреты, а минимальность набора стоит денег в каждом прогоне CI.

Покрывающий массив: формальная постановка

Покрывающий массив $CA(N; t, k, v)$ — это таблица из $N$ строк и $k$ столбцов (параметров), где каждый столбец берёт значения из алфавита размера $v$, и для любых $t$ столбцов в таблице встречаются все $v^t$ комбинаций их значений. Число $t$ называют силой покрытия: $t = 2$ — попарное, $t = 3$ — тройное.

Три факта, определяющие всю практику:

Первая строка — главная хорошая новость области: пространство растёт как $v^k$, а нужный набор тестов — как $\log k$. Именно поэтому CIT работает даже на системах с сотней опций.

Возьмём сквозной пример из пяти параметров — он же нарисован ниже:

Полное пространство — 288 комбинаций. С учётом ограничений валидных — 180. Достижимых пар значений (таких, которые вообще встречаются хотя бы в одной валидной конфигурации) — 97. Задача: построить как можно меньше строк, покрывающих все 97 пар.

Две стратегии построения и почему поиск выигрывает

Жадная: строим тест за тестом

Классика — семейство AETG (Cohen, Dalal, Fredman, Patton, «The AETG System: An Approach to Testing Based on Combinatorial Design», IEEE TSE 1997) и IPOG (реализован в NIST ACTS). Идея: каждый следующий тест выбираем так, чтобы он закрывал максимум ещё не покрытых комбинаций. Быстро, детерминированно по времени, результат чуть больше минимального.

Поисковая: фиксируем размер, минимизируем непокрытость

Переворачиваем задачу: пусть строк ровно $N$; ищем содержимое таблицы, минимизируя число непокрытых пар. Фитнес — число непокрытых пар (минимизируем до нуля), представление — матрица $N \times k$, оператор — замена одного значения в одной ячейке. Дальше работает имитация отжига: если при $N$ решение найдено, пробуем $N - 1$.

Ровно этот подход дал самые компактные известные массивы (Cohen, Colbourn, Ling, «Augmenting simulated annealing to build interaction test suites», ISSRE 2003), и он же лучше переносит ограничения (Garvin, Cohen, Dwyer, «Evaluating improvements to a meta-heuristic search for constrained interaction testing», EMSE 2011).

"""Покрывающие массивы: жадное построение и отжиг при фиксированном числе строк."""
from __future__ import annotations

import math
import random
from collections import defaultdict
from itertools import combinations, product

PARAMS: dict[str, list[str]] = {
    "os":      ["linux", "macos", "windows"],
    "browser": ["chrome", "firefox", "safari", "edge"],
    "db":      ["postgres", "mysql", "sqlite"],
    "cache":   ["redis", "none"],
    "locale":  ["ru", "en", "de", "ja"],
}
NAMES = list(PARAMS)


def is_valid(cfg: dict[str, str]) -> bool:
    """Ограничения: комбинации, которых не существует. Работает и на частичной конфигурации."""
    if cfg.get("browser") == "safari" and cfg.get("os") != "macos":
        return False
    if cfg.get("browser") == "edge" and cfg.get("os") == "linux":
        return False
    if cfg.get("db") == "sqlite" and cfg.get("cache") == "redis":
        return False
    return True


def pairs_of(cfg: dict[str, str]) -> set[tuple[str, str, str, str]]:
    """Пары, покрытые конфигурацией; работает и на частичной — она строится по одному параметру."""
    present = [n for n in NAMES if n in cfg]
    return {(a, cfg[a], b, cfg[b]) for a, b in combinations(present, 2)}


def reachable_pairs(configs: list[dict[str, str]]) -> set:
    """Цель покрытия — пары, достижимые хотя бы в одной ПОЛНОЙ валидной конфигурации.

    В демо мы перебираем пространство целиком (288 штук). На настоящей модели фич
    с 2^300 вариантов тот же вопрос задают SAT-солверу: одна проверка выполнимости на пару.
    Разница принципиальна: пара («safari», «postgres») выглядит безобидно, но её
    достижимость зависит от того, существует ли ХОТЬ ОДНА валидная конфигурация с ней.
    """
    out: set = set()
    for cfg in configs:
        out |= pairs_of(cfg)
    return out


def greedy(target: set, seed: int = 0) -> list[dict[str, str]]:
    """Жадное построение: каждый следующий тест закрывает максимум новых пар."""
    rnd = random.Random(seed)
    uncovered = set(target)
    suite: list[dict[str, str]] = []
    while uncovered:
        best, best_gain = None, -1
        for _ in range(50):                       # 50 кандидатов, берём лучшего
            cfg: dict[str, str] = {}
            for name in rnd.sample(NAMES, len(NAMES)):   # случайный порядок параметров
                options = [v for v in PARAMS[name] if is_valid({**cfg, name: v})]
                if not options:
                    cfg = {}
                    break
                rnd.shuffle(options)              # случайные ничьи: иначе все кандидаты одинаковы
                cfg[name] = max(options, key=lambda v: len(pairs_of({**cfg, name: v}) & uncovered))
            if not cfg:
                continue
            gain = len(pairs_of(cfg) & uncovered)
            if gain > best_gain:
                best, best_gain = cfg, gain
        if best is None or best_gain == 0:
            raise RuntimeError("остались пары, недостижимые при этих ограничениях")
        suite.append(best)
        uncovered -= pairs_of(best)
    return suite


def anneal(target: set, n_rows: int, evaluations: int, seed: int = 0):
    """Отжиг при фиксированном N: фитнес = число непокрытых пар, минимизируем до нуля.

    Счётчик покрытий инкрементальный: замена одного значения трогает k-1 пар, а не весь массив.
    Полный пересчёт стоил бы O(N * k^2) на шаг и убил бы поиск на больших таблицах.
    """
    rnd = random.Random(seed)

    def random_row() -> dict[str, str]:
        while True:
            cfg = {n: rnd.choice(PARAMS[n]) for n in NAMES}
            if is_valid(cfg):
                return cfg

    suite = [random_row() for _ in range(n_rows)]
    count: dict = defaultdict(int)
    for row in suite:
        for p in pairs_of(row):
            count[p] += 1
    cost = sum(1 for p in target if count[p] == 0)
    best, best_cost = [dict(r) for r in suite], cost
    t0, t1 = 4.0, 0.05                            # расписание охлаждения: геометрическое

    def apply(row_before: dict, row_after: dict) -> int:
        """Обновляет счётчики и возвращает дельту числа непокрытых целевых пар."""
        delta = 0
        for p in pairs_of(row_before):
            count[p] -= 1
            if count[p] == 0 and p in target:
                delta += 1
        for p in pairs_of(row_after):
            if count[p] == 0 and p in target:
                delta -= 1
            count[p] += 1
        return delta

    for step in range(evaluations):
        if cost == 0:
            break
        temp = t0 * (t1 / t0) ** (step / evaluations)
        i = rnd.randrange(n_rows)
        name = rnd.choice(NAMES)
        cand = dict(suite[i])
        cand[name] = rnd.choice(PARAMS[name])
        if cand[name] == suite[i][name] or not is_valid(cand):
            continue                              # невалидные соседи просто не рассматриваем
        delta = apply(suite[i], cand)
        if delta <= 0 or rnd.random() < math.exp(-delta / temp):
            suite[i] = cand
            cost += delta
            if cost < best_cost:
                best, best_cost = [dict(r) for r in suite], cost
        else:
            apply(cand, suite[i])                 # откат счётчиков
    return best, best_cost


if __name__ == "__main__":
    full = [dict(zip(NAMES, c)) for c in product(*PARAMS.values())]
    valid = [c for c in full if is_valid(c)]
    target = reachable_pairs(valid)
    print(f"комбинаций {len(full)}, валидных {len(valid)}, достижимых пар {len(target)}")
    sizes = [len(greedy(target, seed=s)) for s in range(10)]
    print(f"жадный: медиана {sorted(sizes)[5]} строк, разброс {min(sizes)}-{max(sizes)}")
    for n in (14, 15, 16, 17):
        ok = sum(anneal(target, n, evaluations=20_000, seed=s)[1] == 0 for s in range(10))
        print(f"отжиг при N={n}: полное покрытие в {ok}/10 запусках")

Реальный вывод:

комбинаций 288, валидных 180, достижимых пар 97
жадный: медиана 18 строк, разброс 17-19
отжиг при N=14: полное покрытие в 0/10 запусках
отжиг при N=15: полное покрытие в 0/10 запусках
отжиг при N=16: полное покрытие в 10/10 запусках
отжиг при N=17: полное покрытие в 10/10 запусках

Три вывода из этих чисел:

1. Поиск компактнее жадности: 16 строк против 18. На игрушечном примере это −11 %, на реальных моделях с десятками параметров разрыв обычно того же порядка. Если конфигурация — это полный e2e-прогон на 20 минут, две сэкономленные строки означают 40 минут в каждом ночном билде.
2. Отжиг честно упирается в границу: при $N = 15$ даже на бюджете в 200 000 итераций остаётся ровно одна непокрытая пара — похоже, 16 близко к настоящему минимуму. Поиск умеет не только находить решение, но и давать эмпирическую оценку «меньше, скорее всего, нельзя».
3. 180 валидных конфигураций против 16 строк — сокращение в 11 раз при сохранении всех парных взаимодействий. Именно на этом множителе живёт вся практика конфигурационного тестирования.

Сложность

Ограничения: почему здесь штраф не работает

В статье про пространство поиска мы отстаивали штрафы против жёстких запретов: штраф сохраняет связность ландшафта. Здесь — исключение, и важно понимать, почему.

Невалидная конфигурация не «чуть хуже» валидной. Её не существует: safari на Linux нельзя установить, тест на ней не запустится, и никакого частичного кредита за неё дать нельзя. Штраф в таком случае лишь заставляет поиск тратить оценки на заведомо мёртвые точки.

Три рабочих подхода:

1. Фильтр при генерации (как в коде выше): оператор мутации порождает только валидных соседей. Просто и быстро, пока ограничения проверяются локально.
2. SAT-солвер как оракул. Модель фич переводится в булеву формулу (каждая опция — переменная, ограничения — импликации), и все вопросы адресуются солверу: «валидна ли эта конфигурация?», «существует ли валидная конфигурация с этой парой?», «достройте частичную конфигурацию до валидной». Это стандарт для больших моделей — ядро Linux описывается десятками тысяч переменных Kconfig, и никакой ручной фильтр там не поможет.
3. Remove-and-repair: разрешаем поиску временно нарушать ограничения, но перед оценкой чиним конфигурацию солвером. Дороже, зато операторы поиска остаются простыми.

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

Выборка, когда даже пары дороги

Если одна конфигурация — это полная сборка продукта на полчаса, 16 строк ещё терпимо, а вот 3-wise на сотне опций (сотни строк) — уже нет. Тогда переходят от покрытия к выборке (sampling), и здесь есть тонкость, которую легко пропустить.

Случайная выборка конфигураций почти никогда не равномерна. Если генерировать значения независимо и отбрасывать невалидные, вероятность попасть в конфигурацию сильно зависит от структуры ограничений: опции, участвующие в большом числе запретов, будут представлены систематически реже. Действительно равномерная выборка решений булевой формулы — отдельная сложная задача (#SAT-мира), и её состояние исследовано в работе Plazar, Acher, Perrouin, Devroey, Cordy, «Uniform Sampling of SAT Solutions for Configurable Systems: Are We There Yet?», ICST 2019: строго равномерные сэмплеры не масштабируются на реальные модели, а быстрые — смещены.

Практический вывод из этого честнее академического: не гонитесь за равномерностью, гонитесь за релевантностью. У вас, в отличие от исследователей, есть телеметрия: вы знаете, какие конфигурации реально существуют у пользователей. Взвесьте пары по реальной популярности и покрывайте в первую очередь их — это тот же самый поиск, только с весами в фитнесе:

def weighted_uncovered(count: dict, weights: dict[tuple, float]) -> float:
    """Фитнес с весами: непокрытая пара стоит столько, сколько стоит её пропустить.

    weights[pair] — доля пользователей (или инсталляций) с этой комбинацией.
    Пара «edge + ja», которой нет ни у кого, штрафуется в сотни раз слабее,
    чем «chrome + ru» с половиной трафика.
    """
    return sum(w for pair, w in weights.items() if count.get(pair, 0) == 0)

Такая постановка немедленно превращается в многокритериальную: покрытие популярных пар против размера набора против стоимости прогона — и решается ровно тем аппаратом, что в статье про Парето и NSGA-II.

Как это ставится в конвейер

Тестировать все 16 конфигураций на каждый пуш — расточительство; тестировать одну — самообман. Рабочая схема — уровни с разной силой покрытия и разной частотой.

Две детали, без которых схема не работает.

Приоритизация внутри массива. Строки покрывающего массива не равноценны: если прогон прервётся на середине, хочется, чтобы уже выполненные строки покрывали как можно больше. Это задача приоритизации, знакомая по генерации тестов и решаемая тем же жадным правилом «следующей ставим строку, добавляющую максимум нового покрытия» (Bryce, Colbourn, «Prioritized interaction testing for pairwise coverage with seeding and constraints», IST 2006).

Seeding. В массив всегда принудительно включают конфигурации, которые обязаны быть протестированы: эталонную прод-конфигурацию, конфигурацию самого крупного клиента, ту, на которой в прошлый раз сломалось. Алгоритм строит массив «поверх» этих строк, покрывая только оставшиеся пары. Это дёшево и резко повышает доверие к результату.

Как встроить всё это технически — планирование матриц сборки, кеширование, время прогона — смотрите в статье про тесты в CI и управлении конфигурацией.

Вторая задача: найти лучшую конфигурацию, а не сломать её

До сих пор конфигурации были объектами тестирования. Теперь они — кандидаты решения: у системы есть сотня параметров (размеры пулов, флаги JIT и GC, параметры планировщика PostgreSQL, лимиты контейнеров), и надо найти набор, при котором latency минимальна, а расход памяти в бюджете.

Формально это обычная SBSE-задача: представление — вектор значений параметров, фитнес — измеренная производительность, операторы — изменение одного параметра. Отличия от всего, что было в треке, — два, и оба неприятные:

• Оценка стоит минуты: развернуть, прогреть, прогнать нагрузку, померить. Никакие 20 000 итераций тут невозможны — бюджет измеряется сотнями оценок.
• Оценка шумна: соседний под, сборщик мусора, тепловой троттлинг. Разница в 3 % может быть реальной, а может быть погодой (подробности измерения — в статье о бенчмаркинге).

Две ветки решений, обе живые:

1. Модели влияния (performance-influence models). Вместо поиска строим предсказательную модель «конфигурация → производительность» на небольшой выборке замеров, а потом оптимизируем уже её — модель считается мгновенно. Классика подхода — Siegmund и соавторы, «Performance-influence models for highly configurable software systems», ESEC/FSE 2015 (инструмент SPLConqueror). Побочная польза огромна: модель отвечает не только «какая лучшая», но и «какие опции вообще влияют и как они взаимодействуют».
2. Поиск с суррогатом внутри цикла: байесовская оптимизация и суррогат-ассистированные эволюционные алгоритмы, где дешёвая модель отсеивает бесперспективных кандидатов, а реальный замер тратится только на лучших. Это тема следующей главы, там же — OtterTune для СУБД, автотюнинг компиляторов и распределение бюджета замеров.

Обратите внимание на пунктирные связи: обе задачи питают друг друга. Найденная тюнингом «лучшая» конфигурация обязана попасть в тестовый массив как seed, иначе вы отправите в прод режим, который никогда не тестировался целиком.

Типичные ошибки

1. Считать, что pairwise ловит всё. Он ловит дефекты, вызванные парой опций. Дефект, требующий тройки, попадётся только случайно. Если цена отказа высока (платежи, безопасность), поднимайте силу покрытия на критичном подмножестве параметров, а не на всех сразу.
2. Игнорировать ограничения. Массив, где четверть строк невалидна, — это не 16 конфигураций, а 12 плюс четыре красных билда и потерянное доверие к прогону.
3. Считать «недостижимую» пару непокрытой. Если пара не встречается ни в одной валидной конфигурации, требовать её покрытия — значит зациклить генератор. Целевое множество обязано строиться через проверку выполнимости, а не перемножением алфавитов.
4. Перестраивать массив каждый прогон. Стохастический алгоритм даст другой набор, и вы потеряете сравнимость между ночными билдами. Массив — версионируемый артефакт.
5. Равные веса у всех комбинаций. «Edge + японская локаль + SQLite» может не существовать ни у одного пользователя. Телеметрия превращает абстрактное покрытие в осмысленное.
6. Полный пересчёт покрытия на каждом шаге. $O(N \cdot k^2)$ вместо $O(k)$ — самый частый способ сделать поиск бесполезно медленным.
7. Тюнинг по одному замеру. Шум в измерениях производительности легко даёт 5–10 %; без повторов и статистики вы оптимизируете погоду, а не конфигурацию.
8. Оптимизация конфигурации в отрыве от тестирования. Найденный «оптимум» с непротестированной комбинацией флагов — прямая дорога к инциденту.

Мини-итог

• Конфигурируемая система — это семейство программ; полный перебор невозможен, а полностью игнорировать вариативность — значит тестировать не то, что у пользователей.
• Дефекты конфигураций почти всегда вызываются взаимодействием одной-двух опций, поэтому целью становится покрывающий массив силы 2–3, а не полный перебор.
• Размер массива растёт логарифмически по числу параметров и экспоненциально по силе покрытия; построение минимального массива NP-трудно, поэтому его строят жадно или поиском.
• Поиск (отжиг с инкрементальным счётчиком покрытия) даёт более компактные массивы, чем жадность: на примере статьи 16 строк против 18 при 180 валидных конфигурациях.
• Ограничения здесь — не штраф, а жёсткая проверка: фильтр при генерации или SAT-солвер как оракул валидности и достижимости.
• В CI массив живёт уровнями: смоук на PR, попарное покрытие ночью, тройное — по расписанию; строки приоритизируются, обязательные конфигурации добавляются seeding’ом.
• Вторая задача — поиск самой быстрой конфигурации — упирается в дорогой и шумный фитнес, и решается моделями влияния и суррогатами.

Источники

• Kuhn, Wallace, Gallo. «Software Fault Interactions and Implications for Software Testing», IEEE TSE 2004.
• Cohen, Dalal, Fredman, Patton. «The AETG System», IEEE TSE 1997.
• Cohen, Colbourn, Ling. «Augmenting simulated annealing to build interaction test suites», ISSRE 2003.
• Garvin, Cohen, Dwyer. «Evaluating improvements to a meta-heuristic search for constrained interaction testing», EMSE 2011.
• Halin et al. «Test them all, is it worth it?», EMSE 2019 — полный перебор пространства JHipster.
• Plazar et al. «Uniform Sampling of SAT Solutions for Configurable Systems», ICST 2019.
• Siegmund et al. «Performance-influence models for highly configurable software systems», ESEC/FSE 2015.
• Инструменты: NIST ACTS, PICT, FeatureIDE.

Что дальше

Обе задачи этой статьи упёрлись в один и тот же барьер: одна оценка стоит дорого. Прогон конфигурации — минуты, замер производительности — минуты и ещё шумит. Всё, что мы знаем про поиск, предполагало десятки тысяч оценок; здесь их сотни. Следующая статья — про то, как жить в этом режиме: кэш и инкрементальность, дешёвые приближения, суррогатные модели и байесовская оптимизация, распределение бюджета между кандидатами.

Дорогой фитнес: кэш, суррогатные модели и байесовская оптимизация