Глоссарий

Амортизированная сложность

Средняя стоимость одной операции в длинной последовательности операций. Позволяет честно сказать, что добавление в динамический массив стоит O(1), хотя отдельное добавление иногда копирует весь массив за O(n).

Разбор: «Амортизированная сложность на пальцах»

Асимптотическая сложность

Поведение времени или памяти алгоритма при росте размера входа до бесконечности. Отвечает на вопрос «как быстро растёт», а не «сколько миллисекунд»: константы и младшие члены отбрасываются.

Атомарность

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

B-дерево

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

Блокирующий ввод-вывод

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

Виртуальная память

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

Разбор: «Виртуальная память: четыре уровня таблиц»

Взаимная блокировка

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

Динамическое программирование

Метод решения задач, у которых оптимальное решение складывается из оптимальных решений подзадач, и подзадачи повторяются. Результаты подзадач сохраняются, чтобы не считать их заново.

Дескриптор файла

Небольшое целое число, которым процесс ссылается на открытый файл, сокет или канал. Индекс в таблице открытых файлов процесса. Наследуется при fork и может передаваться между процессами через доменный сокет.

Идемпотентность

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

Направление «Бэкенд», модуль 07

Индекс

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

Инвалидация кэша

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

Кворум

Минимальное число узлов, которые должны подтвердить операцию, чтобы она считалась выполненной. Если кворумы чтения и записи пересекаются (R + W > N), читающий гарантированно увидит последнюю подтверждённую запись.

Конкурентность

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

Копирование при записи

Приём, при котором копия данных создаётся не в момент «копирования», а при первой попытке изменить их. До изменения обе стороны разделяют одну физическую память. Так работает fork в современных системах.

Многоверсионность

Способ управления конкурентным доступом, при котором изменение создаёт новую версию строки, а не перезаписывает старую. Читающие транзакции видят снимок данных и не блокируют пишущие — и наоборот.

Мьютекс

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

Обратное давление

Механизм, которым перегруженный получатель сообщает отправителю, что нужно сбавить темп. Без него очередь между ними растёт, пока не кончится память. В TCP роль обратного давления играет окно приёма.

Окно перегрузки

Оценка объёма данных, которые отправитель TCP может держать в сети неподтверждёнными, чтобы не вызвать потерь. Растёт при успешной доставке и резко сокращается при потере пакета.

Перцентиль

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

Планировщик запросов

Компонент СУБД, выбирающий способ выполнения запроса: порядок соединений, методы доступа, алгоритмы join. Решение принимается по оценкам стоимости, построенным на статистике — поэтому устаревшая статистика портит планы.

Прерывание

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

Репликация

Поддержание копий данных на нескольких узлах. Синхронная репликация подтверждает запись только после применения на репликах, асинхронная — сразу, рискуя потерять последние изменения при отказе лидера.

Рукопожатие

Обмен служебными сообщениями, которым стороны согласовывают параметры перед передачей данных. В TCP это три пакета и согласование начальных номеров, в TLS — версия протокола, шифрсьют и ключевой материал.

Разбор: «Трёхстороннее рукопожатие TCP»

Селективность

Доля строк таблицы, которые проходят условие фильтра. Чем меньше доля, тем выгоднее индекс. При селективности выше примерно 20 % планировщик обычно предпочитает последовательное чтение.

Системный вызов

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

Согласованность в конечном счёте

Гарантия, что при отсутствии новых изменений все реплики со временем придут к одному значению. Ничего не говорит о том, сколько займёт это «со временем» и что увидит читатель до схождения.

Транзакция

Группа операций, выполняемых как единое целое. Либо применяются все изменения, либо ни одного. Свойства транзакций описывает сокращение ACID, из которых буква I (изоляция) настраивается уровнями.

Таблица страниц

Структура, по которой процессор переводит виртуальный адрес в физический. В x86-64 — четыре уровня. Результаты недавних трансляций кэшируются в TLB, иначе каждое обращение к памяти стоило бы пяти обращений.

Фантомное чтение

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

Хеш-таблица

Структура данных, отображающая ключи в значения через хеш-функцию. Среднее время доступа — O(1), худшее — O(n) при массовых коллизиях. Реальная производительность сильно зависит от коэффициента заполнения.

Хвост распределения

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