Миллионы объектов со стабильными адресами, или как удержать состояние под строгим RT дедлайном цикла

Рассмотрим класс задач, который встречается в разных областях. Долгоживущий процесс держит состояние из нескольких миллионов объектов по 2 КБ каждый. На это состояние напрямую указывают и другие потоки, в том числе внешние, и заменить эти указатели копированием или доступом через менеджер не позволяет сама архитектура. Например, потокам интерфейса с аппаратной частью нужно читать данные в реальном времени, без какой‑либо синхронизации с главным потоком. Рядом крутится цикл обработки событий, и его итерация обязана завершаться за десять миллисекунд. Это строгий RT дедлайн.

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

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

Решения взяты из реального проекта, библиотеки‑ядра libgsml3parser для построения программной GSM/2G базовой станции. Там роль объекта играет сессия абонента, а 3GPP правила задают конкретные таймеры. Оба решения переносятся на любую систему того же класса ограничений почти без изменений. Исходный код доступен в репозитории GSM L3 для сверки.

Четыре свойства, из которых следует всё остальное

Разберём требования по отдельности.

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

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

Кэш‑локальность. Свойство у данных простое. То, что читается и пишется на каждом кадре, должно лежать рядом по адресу и оставаться вместе при повторных обращениях. В литературе эту близость, пространственную плюс временную, зовут одним словом. Кэш‑локальность (cache locality). А состояние объекта в нашей задаче как раз такое. Его читают и пишут на каждом входящем кадре. Двухкилобайтная непрерывная область раскладывается на тридцать две кэш‑линии по шестьдесят четыре байта, а те же поля, разложенные по отдельным узлам в разных местах кучи, растянут доступы на несколько сотен таких линий.

Активные объекты и своё время цикла. Цикл не должен трогать объекты, с которыми сейчас нет работы, достаточно обходить тех, с которыми работа идёт прямо сейчас. Второй момент касается времени. Таймеры не обращаются к системным часам. Время, в котором они живут, отсчитывается явными приращениями, которые передаёт цикл обработки событий. Каждый вызов tick(delta) сдвигает протокольное время на заданную величину. Системное время внутри цикла с бюджетом даёт дрейф и джиттер, а протокольное исключает оба эффекта сразу.

Почему стандартные варианты не подходят

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

Первая, плотный массив с удалением через замену последним элементом. Классический приём плоских хэш‑таблиц, быстрый и компактный. Он умирает на стабильном адресе. Удаляем одну запись, в её место переезжает другая, и у этой другой теперь новый адрес. Все внешние указатели на неё устаревают в тот же момент. Контракт ломает одно‑единственное удаление, при любом масштабе.

Вторая, узловой контейнер. Это unordered_map с записями в unique_ptr. Узлы при перестройке не передвигаются, так что адрес здесь действительно стабильный, первое свойство проходит. Второе и третье проваливаются вместе. Каждая запись это отдельное выделение в куче, миллион объектов значит миллион блоков по два килобайта. Создание и уничтожение превращаются в непрерывный поток обращений к аллокатору, с фрагментацией и непредсказуемыми пиками отклика поверх. В проекте для этой схемы есть зафиксированная оценка потолка. Десять миллионов записей занимают около 21 гигабайта ещё до накладных расходов самого аллокатора. Обход идёт скачками с узла на узел, а не последовательным чтением. Куча выдает адреса без какого‑либо паттерна, предиктор не может угадать, откуда придёт следующая линия, и каждая кэш‑линия достаётся по полной цене обращения в память.

Третья, арена с тикетами. Записи живут в одном непрерывном регионе, который выделяют редко, и потом не перемещаются до конца жизни. Наружу выдаются не адреса, а индексы в этом регионе, условные тикеты. Стабильный адрес здесь есть, выделений мало, локальность на месте. Проблема в том, что наружу нужно выдавать именно указатель на запись. Радио‑потоки читают состояние в реальном времени без синхронизации, и код через C‑интерфейс ожидает объект, а не его номер. Любой доступ через тикет это лишний шаг по таблице прямо на пути, который прогоняется на каждом кадре.

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

Таблица слотов и блоки записей

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

Первая часть, таблица слотов, это массив 32-битных слов, длина которого равна степени двойки. Хэш‑функция для каждого ключа выдаёт позицию слова, с которого начинается проверка. Слово в большинстве случаев хранит номер записи, на которую этот ключ указывает. Кроме того, слово может нести одно из двух специальных значений. Значением 0xFFFFFFFE помечен свободный слот, на котором обрывается проверка. Значением 0xFFFFFFFF помечен слот, где запись была, а теперь её удалили. Именно такую метку в литературе называют tombstone.

Вторую часть занимают сами записи. Они лежат друг за другом блоками по шестьдесят четыре, и каждый блок выделяется одной порцией памяти при создании, после чего его никогда не перемещают. Блоки держит список указателей. Для каждого блока в этом списке лежит один адрес, и когда появляются новые блоки, список растёт или даже пересоздаётся целиком. Записи от этого никак не страдают. Перекладывается только набор адресов в самом списке, а блоки продолжают лежать там же, где и раньше.

Есть ещё одна деталь, на которой держится пересборка без перемещения записей. Каждая запись хранит обратный номер того слота таблицы, который сейчас указывает на неё. При перестройке нужно заново раскидать записи по словам новой таблицы, а у каждой переписать только этот обратный номер. Адрес при этом никто не трогает.

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

Тут можно задать вопрос о том, зачем вообще нужны эти номера, если речь всё время шла про стабильные адреса. Номера существуют исключительно внутри самой раскладки. SDR потоки и чужие языки, подключённые через C‑интерфейс, получают только адрес записи и не видят никакого номера. Внутри номер оправдан двумя соображениями. Слово таблицы занимает четыре байта, тогда как полный 64-битный адрес требует восемь, поэтому хранение номера вдвое компактнее. Кроме того, из номера, сдвиг на шесть бит вправо показывает, к какому блоку принадлежит запись, а маска по младшим шести битам выдаёт позицию внутри блока. В коде список блоков носит имя mSlabs. Элемент списка по номеру блока возвращает начало блока, и запись достаётся двумя индексациями подряд.

// idx это внутренний номер записи, наружу он не утекает
Entry& e = mSlabs[idx >> 6][idx & 63];

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

Почему в блоке именно шестьдесят четыре записи? Здесь действует баланс двух эффектов. Блок из шестидесяти четырёх двух килобайтных записей весит около 128 КБ. Для аллокатора это размер, не порождающий мелкой фрагментации. Неполный последний блок оставляет не более шестидесяти трёх пустых мест, а на реестре в миллионы объектов это доля процента памяти.

Что происходит на уровнях кэша CPU

Память CPU неоднородна. Между ядром и оперативной памятью стоит несколько уровней кэша. Идём от ядра к памяти. Каждый следующий уровень больше предыдущего, но медленнее его, а обращение в него обходится дороже, чем в предыдущий. На многих ядрах перед всеми остальными уровнями есть ещё и нулевая ступень, L0, небольшой кэш декодированных операций, в котором живут развёрнутые тела горячих циклов. Попадание в этот кэш стоит порядка одного такта, операция исполняется сразу. Следом идёт кэш первого уровня, L1, объёмом в десятки килобайт на ядро, он разделён на кэш данных и кэш инструкций. Попадание сюда стоит уже несколько тактов. За ним следует L2 объёмом от нескольких сотен килобайт до пары мегабайт на ядро, обращение в который обходится пятнадцатью‑двадцатью тактами. Выше всех кэшей ядра находится общий для чипа L3 размером в десятки мегабайт и, на больших чипах, в сотни, попадание в него стоит уже несколько десятков тактов. После всех уровней кэша остаётся оперативная память. Если данных нет ни в одном кэше, обращение туда стоит около сотни тактов процессора, а по реальному времени это уже несколько сотен наносекунд.

Есть ещё одна особенность устройства уровней, которую стоит понять до продолжения. Каждый уровень кэша устроен не как сплошная область памяти, а как n‑way ассоциативный массив. Адрес распадается на метку, номер набора и смещение внутри линии, поэтому один набор может одновременно держать линии, относящиеся к не более чем n разным адресам. Из этого устройства следует важный для локальности эффект. Блоки с горячими адресами, которые попадают в одни и те же наборы, конкурируют за их ограниченное число мест и вытесняют сами себя. И так даже тогда, когда весь объём данных уложился бы в этот уровень. Последовательный поток по соседним адресам себя так не ведёт. Его линии разлетаются по наборам ровно и давления на политику замещения не создают.

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

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

Поэтому все компоненты записи лежат в ней инлайном, без единого указателя на отдельно выделенный объект. Запись остаётся одним объектом в собственных тридцати двух кэш‑линиях, а не графом из узлов, где у каждого свой дом в куче. Запись обязана оставаться меньше четырёх килобайт, чтобы её нельзя было незаметно вырастить за пределы этой раскладки.

Именно так проявляется та самая кэш‑локальность из раздела о требованиях. Разница между тридцатью двумя соседними линиями и несколькими сотнями разрозненных в том, что объём данных остаётся прежним, но собрать их в один последовательный поток уже невозможно. Каждая из этих линий обходится процессору полным промахом памяти.

Тот же разговор, только об инструкциях. Тело цикла над миллионами объектов не должно вытеснять себя из кэша инструкций собственным рабочим множеством. Десятков килобайт L1 достаточно, пока тело остаётся коротким. У нас оно короткое. Обход одной записи сводится к проходу по тридцати двум таймерным слотам фиксированного массива, без виртуальных вызовов и прыжков в общие структуры. Маршрутизация входящего кадра сводится к индексному чтению в компактной таблице на несколько десятков килобайт, которая с запасом живёт в L1 или L2 ядра. Альтернативные схемы удлиняют горячий путь и по коду, и по потоку ветвлений. Timing Wheel или Hashed Wheel Timer на весь процесс, очередь с сортировкой по дедлайнам. Давление на кэш инструкций живёт ровно там.

Куда уходит место удалённой записи и когда нужна пересборка таблицы

Удаление не освобождает место записи в таблице слотов. Дело в том, как устроен поиск при открытой адресации. Он идёт от позиции ключа по соседним слотам один за другим и останавливается либо на найденной записи, либо на свободном слоте. А свободный слот означает, что записи в таблице нет. Если бы она была, проверка дошла бы до неё. Поэтому после удаления нельзя просто вернуть слот в состояние свободного. Каждый поиск, чей путь пролегал через этот слот, остановился бы на нём раньше времени и не дошёл бы до записей, стоящих в той же цепочке дальше. Слот удалённой записи получает метку об удалении (tombstone). На такой метке поиск не останавливается, он просто перепрыгивает её и продолжает проверку следующих слотов.

Возникает вопрос, что в таблице вообще может накапливаться. Ведь новая сессия занимает освобождённое место. Ответ простой. На двух уровнях хранения всё происходит по‑разному. На уровне памяти не копится ничего. Освобождённый адрес тела записи сразу возвращается в список свободных адресов реестра, и тело следующей созданной сессии займёт один из этих адресов. Данные циркулируют по одним и тем же адресам один к одному, и при устойчивом обороте объектов реестру не приходится запрашивать у аллокатора новые блоки памяти. Таблица слотов перерабатывает удалённые места лишь отчасти. Вставка встаёт на место метки об удалении только тогда, когда эта метка оказывается на её собственном пути проверки. То есть встречается раньше первого свободного слота. А во всех остальных случаях вставка занимает по‑настоящему свободный слот, и отметка продолжает лежать в таблице.

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

Замедляет реестр именно эта доля, а не память. Поиски и вставки проходят по занятым слотам подряд, пока не встретят первый свободный, а метки лежат внутри этих проходов и удлиняют каждый из них. Так что чем их больше, тем дороже обходится одна операция. Время операции берётся из бюджета цикла, ограниченного десятью миллисекундами. Именно ради этого таблицу и пересобирают. Не ради памяти, которую новые записи и так снова заняли. А чтобы вернуть поискам прежнюю скорость.

Осталось выбрать само условие пересборки. Первым кандидатом в него становится общая занятость таблицы, суммарное число слотов, занятых записями и метками вместе. С желанием пересобирать таблицу тогда, когда эта доля превышает X процентов. У такой конструкции не существует работающей настройки порога. Число занятых слотов при удалении не меняется, поскольку каждое удаление лишь заменяет запись меткой и ни одного слота при этом не освобождает. Поставим порог ниже обычного уровня занятости, и условие выполнится ещё до первой волны оттока. Тогда таблица пересоберётся после каждого отдельного удаления, потратив полное время пересборки там, где по сути нечего чистить. Поднимем порог выше, и никакая волна оттока его не достанет. Число занятых слотов вырастает только при приросте числа записей, а этот процесс уже покрывает удвоение таблицы, срабатывающее при семидесяти процентах заполнения. Из всех величин с каждым удалением меняется только одна, доля слотов с метками. Поэтому пересборка и привязана именно к ней. Как только эта доля превышает половину всех слотов, таблица пересобирается на месте, без изменения размера.

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

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

Отдельного разговора заслуживает порядок действий при самом удалении, потому что безопасность этого места держится на последовательности операций, а не на механизмах работы с памятью. Помимо главной таблицы по TMSI на одну запись указывают индекс каналов связи и индекс IMSI, а сессия может числиться во вспомогательных множествах активных таймеров и активных процедур. Обход этих множеств идёт независимо от главной таблицы. Если тело сессии разрушить до того, как выведут её из всех вспомогательных структур, следующий обход найдёт уже разрушенную сессию и обратится к памяти, в которой объекта больше нет. Поэтому при удалении запись сначала выводят из вспомогательных индексов и множеств, а её тело в главной таблице разрушают самым последним. Тот же порядок соблюдается и внутри таблицы. Сначала слот получает метку об удалении и перестаёт быть доступным для поиска. Деструктор тела запускается только после этого. К моменту разрушения все пути извне к этому адресу уже закрыты, так что гонка исключена самой последовательностью действий, а не дисциплиной разработчиков.

Что даёт неизменность адреса за пределами хранилища

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

У поиска есть и верхняя граница, а это важно для цикла с жёстким бюджетом дедлайна. Число попыток проверки не превышает числа занятых слотов плюс единица. Принцип голубятни гарантирует встречу свободного слота в пределах этого числа, если такой вообще есть. А когда места в таблице совсем нет, вставка завершается ошибкой, а не бесконечным циклом.

Старая реализация находила запись для удаления полным обходом таблицы. Через кэши CPU при таком обходе проходят все данные реестра, гигабайты стриминга из памяти ради одного удаления. Двести тысяч таких удалений на миллионе объектов занимали десятки секунд. Теперь это один поиск по ключу, и та же работа занимает доли секунды.

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

Наиболее неожиданным потребителем этого свойства оказалась обвязка других языков. Через C‑интерфейс к ядру подключаются Python и не только. Сессия передаётся туда заёмным объектом. По терминологии такой контракт называют borrowed. Под непрозрачным C‑указателем без собственного времени жизни лежит сама запись. Без копирования, без таблиц соответствия, без единого выделения на выдачу. Такой контракт в принципе невозможен, пока записи перемещаются. Остаются только два пути. Либо копировать данные при каждой выдаче. Либо вести учёт того, кто и какой адрес держит. Раскладка памяти оказывается не внутренней оптимизацией. В этом случае она становится частью публичного API.

Обход только активных объектов

Под активным объектом ниже понимается объект, у которого сейчас идёт работа по протоколу. Запущенный таймер или открытая процедура.

Таймеры размещены внутри объектов. У каждой сессии есть собственный менеджер на тридцать два фиксированных слота под именованные протокольные таймеры. В GSM их девятнадцать, имена от T3101 до T3395. Альтернатива тут одна, общий таймер на весь процесс. Будь то Timing Wheel, Hashed Wheel Timer или очередь с сортировкой по дедлайнам, в данной задаче эта альтернатива проигрывает дважды. Во‑первых, любое включение или выключение любого из миллионов таймеров становится записью в общую структуру, а значит работой под общей блокировкой. В нашей схеме включение таймера не затрагивает никого, кроме владельца. Всё происходит целиком в собственных кэш‑линиях его записи, здесь нет ни прыжка в общую структуру, ни дополнительного промаха памяти. Достаточно записать одно слово в фиксированный массив той записи, которую цикл только что прочитал. Во‑вторых, любая такая конструкция опирается на системные часы, и каждый её шаг означает их чтение. В нашем проекте время приходит явно из цикла обработки событий, каждая его итерация передаёт приращение tick(delta). По нему двигается протокольное время, без единого обращения к системным часам на этом пути.

Остаётся один вопрос. Как обойти только объекты с активными таймерами, не перебирая всё хранилище? Решение построено на уведомлениях о переходе числа активных таймеров через ноль. Каждый менеджер отслеживает два события, когда их число выросло с нуля и когда упало обратно в нуль. На оба события срабатывает один и тот же обработчик, указатель на C‑функцию плюс одно слово контекста. std::function здесь не используется. Он больше по размеру и умеет выделять память при копировании, а тут это лишнее.

По этим уведомлениям реестр держит два множества, объекты с активными таймерами и объекты с запущенными процедурами. Пройти по живому множеству, удерживая блокировку на всё время, нельзя, об этом следующий абзац. Поэтому итератор здесь устойчив к изменениям данных. По терминологии это robust iterator, он ходит по снимку множества, а не по самому множеству. Каждый обход состоит из трёх шагов. Первым шагом, пока удержана блокировка, множество активных копируется в локальный вектор указателей. По памяти это непрерывный блок данных размером с число активных объектов, а не со всем реестром. Даже десять тысяч таких указателей занимают 80 килобайт, снимаются одним последовательным чтением и живут во втором уровне кэша ядра CPU на всё время обхода. На втором шаге отпускается блокировка. И только на третьем шаге итератор начинает ходить по скопированному списку.

Отпуск блокировки кажется само собой разумеющимся, но это самое уязвимое место конструкции. Во время обхода истекает какой‑то таймер. Его истечение вызывает обработчик «активность упала в нуль». А этому обработчику нужен тот же самый мьютекс. Мьютексы в C++ нерекурсивны. Удерживать блокировку на всё время обхода невозможно, взаимоблокировка наступила бы уже при первом реальном истечении таймера. В системе, где отложенная работа ждёт исполнения по несколько секунд, это вопрос не «если», а «когда».

У этого итератора второе требование, чтобы он не терял события. Истечения накапливаются в буфер, который передаёт вызывающий. Если буфер заполняется посреди обхода, событие не отбрасывают. Таймер переустанавливается на одну миллисекунду и доходит до вызывающего на следующем обходе. Для протокола это требование, а не вежливость. Потерянное истечение означает клиента, который будет ждать повторную передачу. А сеть эту передачу уже считает выполненной.

Итог такой. Десять тысяч активных объектов среди двух миллионов неактивных обход занимает 1,4 миллисекунды. Бюджет цикла в десять миллисекунд соблюдается с семикратным запасом.

Осталось сказать, где эти цифры живут физически. Десять тысяч активных записей вместе весят около двадцати мегабайт. Это больше кэша второго уровня любого ядра CPU. А на типичных процессорах больше и всего кэша третьего уровня чипа целиком. Обход активного подмножества идёт прямо из оперативной памяти. Попаданий в кэш ядра там по определению нет. Те самые 1,4 миллисекунды на десять тысяч объектов складываются из последовательного чтения примерно двух килобайтных записей напрямую из оперативной памяти. Бюджет ставили под эту реальность. Проектирование под предположением, что активное множество «резидентно в кэше», строило бы систему на допущении, которое на таком масштабе не выполняется ни на одном реальном процессоре.

Выгода инлайновой раскладки проявляется в первую очередь на меньшем множестве. Записи активно обменивающихся абонентов перечитываются и перезаписываются на каждом входящем кадре. Десятки‑сотни таких объектов весят вместе десятки‑сотни килобайт, помещаются в L1 или L2 одного ядра и остаются там между кадрами. Последующие касания становятся попаданиями, а не стримингом из памяти. Эта часть дизайна масштабируется не с общим реестром, а с числом параллельно живых разговоров. Это и есть та самая нагрузка, которую цикл обязан обслужить в бюджете.

Конкурентный доступ без вложенных блокировок

Конкурентная история построена на том, что хранилище разбито на N независимых шардов. Их число N задаётся параметром шаблона и фиксировано на этапе компиляции. Оно обязано быть степенью двойки. Каждый шард представляет собой полностью независимый реестр со своим набором индексов и собственным замком. Запись попадает ровно в один шард по хэшу своего ключа и остаётся в нём до конца жизни, потому что ключ у неё не меняется. Требование про степень двойки здесь не случайное. Чтобы узнать номер шарда, накладывают на результат хэша маску. Сам переход ничего не стоит на горячем пути. С последовательными ключами (идентификаторы выдаются именно так, через растущий счётчик) маска распределяет записи по всем шардам ровно, без скоплений.

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

Отдельно стоит сказать про то, какими именно бывают lock‑и. У каждого шарда свой читательский lock, в терминологии C++ это shared_mutex. Несколько читателей могут одновременно находиться внутри одного шарда, не исключая друг друга. Писатель берёт его эксклюзивно и дожидается, пока последний читатель уйдёт. Потоки, занятые разными шардами, друг друга по определению не замечают. Даже холодный путь, который не знает TMSI записи, держится той же дисциплины. Поиск по IMSI или по каналу обходит шарды последовательно, на короткое время запирая каждый, проверяя, живёт ли там искомая запись, и отпуская lock ещё до перехода к следующему. Так что даже в этом случае захваченными одновременно бывает не больше одного замка. Из этого следует невозможность взаимоблокировки по порядку захватов. Она исключена не потому, что каждый вызывающий соблюдает некий порядок. А потому, что такого порядка как объекта просто нет. Ни один поток никогда не держит два замка одновременно. А без двух lock‑ов в одних руках циклическое ожидание между потоками образоваться не может.

У того же разделения есть кешевый эффект на многоядерном процессоре, который стоит разобрать отдельно. Объект lock занимает одну кэш‑линию памяти. Когда за один и тот же lock сражаются многие потоки, эта линия на каждом захвате и отпускании переезжает с ядра на ядро. Каждая такая передача сбрасывает копии линии из кэшей остальных ядер по протоколу согласованности. Так что чем больше потоков дерётся за общий lock, тем больше реального времени уходит на перенос одной линии вместо полезной работы. Вот где платит общая структура. Любое включение любого из миллионов таймеров становится записью в этот общий объект. Все её таймеры держатся на одной кэш‑линии, и ядра постоянно возят её между собой. В шардовой раскладке эти потери становятся локальными. За lock конкретного шарда оспаривают его только потоки, которые в этот самый момент заняты записями этого шарда. Все остальные шарды трудятся параллельно, не трогая его, и их lock не мигрирует между ядрами. А сами записи, пока с ними работает один поток, никого другого к своим линиям не подпускают и спокойно живут в кэше того ядра, которое их сейчас читает или меняет.

Осталось перейти на сторону потребителей хранилища, тех, кто использует его извне. Это потоки, о которых шла речь в начале статьи. SDR потоки читают состояние на каждом кадре, внешняя диагностика читает его в произвольный момент, коды на других языках получают записи через C FFI интерфейс. Записей у этих потоков нет, есть только ключ абонента. Поэтому все они входят в хранилище одним и тем же поиском по TMSI, той самой процедурой из раздела про таблицу слотов. Хэш выдаёт стартовый слот, проверка идёт по соседним до свободного. Вопрос здесь не в том, как искать. Вопрос в том, что поиск возвращает и на каких условиях можно пользоваться тем, что он вернул. Выдать запись наружу можно двумя способами, а выбор между ними определяет, кто ещё может обращаться к этой записи, пока вы её читаете.

Первый способ, обычный поиск. findByTMSI на короткое время берёт общий lock своего шарда, находит запись и возвращает её сырой указатель, после возврата не удерживая никакого lock‑а. Безопасность такого указателя держится не на механизме, а на договорённости. Указатель остаётся валидным ровно до тех пор, пока другой поток не обратится к этой записи ради изменения или удаления.

В нашей системе этого хватает для SDR‑потоков. Указатель получается поиском при создании сессии и запоминается на весь сеанс, дальше каждое чтение идёт без единого lock‑а. Менять запись под этими чтениями по определению некому, с данной сессией в каждый момент времени занят единственный писатель. Это та самая ситуация о которой мы говорили выше, поток интерфейса читает состояние в реальном времени без какой‑либо синхронизации.

Если же во время вашего чтения другой поток может изменить или удалить запись, просто договорённости не хватает (между возвратом указателя и первым обращением по нему запись могли уже удалить). Для таких случаев есть второй способ, поиск с защитой. Он возвращает вместе с адресом объекта, который удерживает общий lock шарда ровно настолько долго, насколько он нужен.

struct LockedSession {
SubscriberSession* session; // валидна, пока жив guard
SharedGuard guard; // удерживает общий lock своего шарда
};

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

Измерения

Замеры сделаны на одном и двух миллионах записей, это рабочие масштабы проекта. «Создание всех» в таблице значит заполнение всего реестра из пустого состояния. «Поиск всех по ключу», последовательный поиск каждой записи по ключу, то есть по одному поиску в таблице слотов на запись. «Обход 10 000 активных» это один проход обхода активного подмножества из десяти тысяч записей среди всего остального.

Вместе колонки таблицы читаются просто. Полные операции растут вместе с реестром, и полные поиски удваиваются ровно от одного миллиона к двум. Обход активных в этом росте не участвует. Десять тысяч записей обходятся за 1,4 миллисекунды, живут ли они среди одного или среди двух миллионов соседей. Отдельно стоит посмотреть на память. На двух миллионах объектов она занимает около 4 гигабайт, что почти совпадает с размером чистого состояния, два килобайта умножить на два миллиона. Накладные расходы раскладки на таком масштабе в процессе не проявляются.

На десяти миллионах записей замеров не делали. Состояние там само по себе весит около двадцати гигабайт, и это ещё без учёта чего‑либо.

Когда конструкция избыточна

Прежде чем переносить эту раскладку в свой проект, проверьте, нужны ли вам вообще то, что она даёт. Даёт она две вещи. Стабильный адрес записи, который можно выдать кому угодно снаружи сырым указателем. И обход, который трогает только живые прямо сейчас объекты. В других задачах того или другого нет, и тогда конструкция становится избыточной.

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

Если же задача ставит цель единого обзора времени по всем таймерам процесса, тут своя история. Вопрос «что сработает следующим» должен решаться в любой момент, и миллионы объектов не должны его замедлять. Такие вопросы решают общие конструкции, Timing Wheel, Hashed Wheel Timer или приоритетная очередь по дедлайнам. Уведомления о переходе через ноль такого обзора не дают, они отвечают только на вопрос, кто жив прямо сейчас. Для обхода один этот вопрос и есть всё нужное.

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

И напоследок про цену самой раскладки. Каждый обход активного подмножества делает два полных прохода по тридцати двум таймерным слотам каждого активного объекта. Множества, которыми реестр следит за живыми объектами и процедурами, сделаны на unordered_set, а этот контейнер выделяет память при росте. Числа скромные, но их стоит сопоставить с тем, что вы в итоге получаете. Конструкция на базе технических решений выше, окупается только при совпадении трёх условий. Интенсивный оборот объектов, масштаб в миллионы и сырые указатели, уходящие в чужие потоки и другие языки. Уберите любое из них, и обычный контейнер снова окажется проще.