Стресс-тест сервера: ошибка на краю кодировки

Если ты строишь генератор стресс-теста по границам кодировок и умеешь уменьшить найденный контрпример, листай до «Теперь сам».

Как думаешь, найдёт ли тест ошибку

Очередь событий на куче проверили стресс-тестом: 300 случайных наборов по 1-6 событий, номера от 1 до 20, ход от 1 до 4, сверка с сортировкой. Расхождений нет. Можно ли выкатывать на сервер, где номера событий доходят до десятков тысяч?

Ответь себе до чтения. Раздел 26 учил брать маленькие значения - там живут ошибки логики: равенства, касания, пустые входы. Но у очереди есть ограничение, которого нет в логике: ключ ход · 1000 + номер верен, только пока номер меньше 1000. На номерах до 20 эта граница не встретится никогда. Маленькая область покрыла логику и пропустила кодировку.

На что это похоже

Проверка формы на сайте. Тестировщик вводит имена «Аня», «Боб», «Ян» - всё работает. А потом приходит пользователь с фамилией из 40 букв, и поле в базе на 32 символа молча обрезает её. Ошибка не в логике формы, а на границе хранения - и туда тест не заглядывал.

Механизм: границы как часть области генератора

Стресс-тест из раздела 26 ищет ошибки там, где их порождает генератор. Маленькие диапазоны делают частыми совпадения и края логики. Но у сборки есть ещё одна порода ошибок - ошибки упаковки: два числа в одном, координаты в одном номере клетки, строка фиксированной длины, предел точного счёта 2⁵³ у учебного движка. У каждой такой упаковки есть граница, и за ней она молча портит данные, не бросая исключений.

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

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

Правило

Генератор стресс-теста сборки выдаёт не только маленькие значения, но и значения у каждой границы кодировки и ограничения из кода. Найденный контрпример уменьшай: уменьшение по числам само остановится на границе, которую ты пропустил.

Разбор: одна и та же очередь, два генератора

Быстрая очередь на куче с упакованным ключом против эталона-сортировки пар. Два стресс-теста по 300 попыток - номера до 20 и до 1100.

import random

def bystro(sobytiya):
    # очередь событий на куче; ключ - одно число ход * 1000 + номер
    kucha = []
    for s in sobytiya:
        x = s[0] * 1000 + s[1]
        kucha.append(x)
        i = len(kucha) - 1
        while i > 0 and kucha[(i - 1) // 2] > kucha[i]:
            kucha[i], kucha[(i - 1) // 2] = kucha[(i - 1) // 2], kucha[i]
            i = (i - 1) // 2
    poryadok = []
    while len(kucha) > 0:
        poryadok.append(kucha[0] % 1000)
        kucha[0] = kucha[len(kucha) - 1]
        kucha.pop()
        i = 0
        while True:
            m = i
            for d in [2 * i + 1, 2 * i + 2]:
                if d < len(kucha) and kucha[d] < kucha[m]:
                    m = d
            if m == i:
                break
            kucha[i], kucha[m] = kucha[m], kucha[i]
            i = m
    return poryadok

def medlenno(sobytiya):
    # эталон: сортировка пар [ход, номер] - порядок по определению
    out = []
    for s in sorted(sobytiya):
        out.append(s[1])
    return out

def stress(maks_nomer, popytok):
    for k in range(popytok):
        n = random.randint(1, 6)
        nomera = set()                  # номера событий различны
        while len(nomera) < n:
            nomera.add(random.randint(1, maks_nomer))
        sob = []
        for nomer in sorted(nomera):
            sob.append([random.randint(1, 4), nomer])
        if bystro(sob) != medlenno(sob):
            return [k + 1, sob]
    return [popytok, "расхождений нет"]

random.seed(6)
for maks in [20, 1100]:
    r = stress(maks, 300)
    print("номера до", str(maks) + ": попыток", r[0])
    print("   ", r[1])

номера до 20: попыток 300
    расхождений нет
номера до 1100: попыток 1
    [[4, 129], [4, 314], [4, 759], [4, 898], [4, 902], [3, 1089]]

Генератор здесь простой - он лишь расширил диапазон номеров; по правилу урока в него ещё добавляют явные 999, 1000 и 1001, чтобы граница встретилась наверняка, а не по удаче. На номерах до 20 очередь безупречна: упаковка верна для любых номеров меньше 1000, и тест её не мог опровергнуть. На номерах до 1100 первая же попытка дала расхождение: событие с номером 1089 упаковалось как 3 · 1000 + 1089 = 4089 - то же, что ход 4 с номером 89, - и встало не на своё место. Граница правила: расширение области генератора удорожает поиск ошибок логики - случайные номера до 1100 реже совпадают и реже касаются. Поэтому генераторы смешивают: большая часть входов маленькая, а отдельные значения берутся у известных границ.

Разбор: уменьшение находит границу

Шесть событий из стресс-теста - что виновато? Уменьшаем: выбрасываем события, потом уменьшаем ход и номер каждого на 1, пока быстрый ответ расходится с эталоном.

import random

def bystro(sobytiya):
    # очередь событий на куче; ключ - одно число ход * 1000 + номер
    kucha = []
    for s in sobytiya:
        x = s[0] * 1000 + s[1]
        kucha.append(x)
        i = len(kucha) - 1
        while i > 0 and kucha[(i - 1) // 2] > kucha[i]:
            kucha[i], kucha[(i - 1) // 2] = kucha[(i - 1) // 2], kucha[i]
            i = (i - 1) // 2
    poryadok = []
    while len(kucha) > 0:
        poryadok.append(kucha[0] % 1000)
        kucha[0] = kucha[len(kucha) - 1]
        kucha.pop()
        i = 0
        while True:
            m = i
            for d in [2 * i + 1, 2 * i + 2]:
                if d < len(kucha) and kucha[d] < kucha[m]:
                    m = d
            if m == i:
                break
            kucha[i], kucha[m] = kucha[m], kucha[i]
            i = m
    return poryadok

def medlenno(sobytiya):
    # эталон: сортировка пар [ход, номер] - порядок по определению
    out = []
    for s in sorted(sobytiya):
        out.append(s[1])
    return out

def oshibka(sob):
    # признак: быстрый и эталон разошлись
    return bystro(sob) != medlenno(sob)

def umenshit(sob):
    # 1) выбрасываем события по одному, пока ошибка держится
    i = 0
    while i < len(sob):
        proba = sob[:i] + sob[i + 1:]
        if len(proba) > 0 and oshibka(proba):
            sob = proba
        else:
            i = i + 1
    # 2) уменьшаем ход и номер каждого события на 1, пока ошибка держится
    menyalos = True
    while menyalos:
        menyalos = False
        for i in range(len(sob)):
            for d in [[1, 0], [0, 1]]:
                novoe = [sob[i][0] - d[0], sob[i][1] - d[1]]
                if novoe[0] >= 1 and novoe[1] >= 1:
                    proba = sob[:i] + [novoe] + sob[i + 1:]
                    if oshibka(proba):
                        sob = proba
                        menyalos = True
    return sob

najdeno = [[4, 129], [4, 314], [4, 759], [4, 898], [4, 902], [3, 1089]]
mal = umenshit(najdeno)
print("найдено стресс-тестом:", len(najdeno), "событий")
print("после уменьшения:", mal)
print("быстро:", bystro(mal), "| эталон:", medlenno(mal))

найдено стресс-тестом: 6 событий
после уменьшения: [[1, 1000]]
быстро: [0] | эталон: [1000]

От шести событий осталось одно, ход уменьшился до 1, а номер - с 1089 до 1000 и ни шагом ниже: при номере 999 ошибка пропадает. Уменьшение само нашло границу кодировки. Контрпример [[1, 1000]] объясняет дефект без отладчика: ключ 1 · 1000 + 1000 = 2000, а 2000 % 1000 = 0 - номер 1000 при распаковке стал нулём. Граница правила: уменьшение находит контрпример, минимальный относительно своих правок (раздел 26), - а не самый маленький на свете, - и не чинит код. Исправлений два: множитель больше любого возможного номера (100 000, если номера меньше ста тысяч, - и проверка этого предела при добавлении события) или ключ без упаковки - пара, которую сравнивают по полям.

Что ломается без этого

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

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

Шесть событий вместо одного. Контрпример не уменьшили - и полдня ищут, при чём тут ход 4 и событие 902.

Зачем это в работе

Переполнения 32-битных счётчиков, обрезка полей в базе, упаковка нескольких флагов в одно число, время в секундах, которое не влезло в 32 бита в 2038 году, - всё это ошибки на краю кодировки. Их находят генераторы, которые знают границы, и уменьшение контрпримера, которое останавливается ровно на краю.

Теперь сам

1. Ключ ход · 100 + номер, номера от 1 до 250. Какой минимальный контрпример даст уменьшение?
2. Координаты клетки упакованы как r · 128 + c. Какие значения c генератор обязан выдавать?
3. Почему уменьшение номера на 1 за шаг остановилось ровно на 1000?