Чипы памяти

Отдельно от микросхем логики (и вместе с тем с ними рядом), хочу посмотреть поближе на память.

У микросхем памяти широкое применение в сетевых устройствах.

Они нужны для Control Plane: стоят рядом с CPU, хранят инструкции процессора и просчитанные таблицы маршуртизации, коммутации, меток итд - это обычная RAM-память.
На модульных железках они нужны для этих целей и на управляющих и на линейных картах. А состояние таблиц синхронизируется между ними.

Это не те таблицы, которыми пользуется чип коммутации - они слишком медленные, поэтому отдельная память устанавливается для хранения так называемых Hard Tables - таблиц для Forwardig Plane. Soft Tables из обычной памяти преобразются в Hard Tables.

Для быстрого поиска по таблицам (за константное время) были изобретены специальные виды памяти: CAM и TCAM.

Различного рода память нужна для буферизации пакетов на входе и на выходе из устройства, и для их хранения, пока обрабатываются заголовки. Это RAM, который может быть в формате GDDR-5/6, HMC, HBM/2.

Ниже мы взглянем на них чуть подробнее.

RAM - Random Access Memory

Классическая оперативная память - куда без неё?

https://fs.linkmeup.ru/images/articles/buffers/ram.png
Мы ей адрес ячейки - она нам содержимое.
В ней хранятся, так называемые Soft Tables (программные таблицы) - таблицы маршрутизации, меток, MAC-адресов.
Когда вы выполняете команду “show ip route”, запрос идёт именно в оперативку к Soft Tables.
CPU работает именно с оперативной памятью - когда он посчитал маршрут, или построил LSP - результат записывается в неё. А уже оттуда изменения синхронизируются в Hard Tables в RAM/CAM/TCAM.
Кроме того, периодически происходит синхронизация всего содержимого всех таблиц на случай, если вдруг по какой-то причине инкрементальные изменения не спустились корректно.
Soft Tables не может быть непосредственно использован для передачи данных, потому что слишком медленно - обращение к оперативке идёт через ЦПУ и требуется алгоритмический поиск, затратный по времени. С оговоркой на NFV.

Второй немаловажный компонент сетевого устройства, реализованный на RAM - это очереди: входные, выходные, интерфейсные. Пока пакет ожидает своего черёда на обработку, обрабатывается в чипе или ожидает своей отправки, он томится в RAM.

Эта память может быть на кристалле чипа коммутации, может быть под одной с ним крышкой, а может и просто находиться неподалёку на плате.

Типы этой памяти меняются в зависимости от задач: SDRAM, DDR, GDDR5, GDDR6, HMC, HBM.

https://fs.linkmeup.ru/images/articles/buffers/hbm_memory.jpg

У меня очевидная слабость к 3д-рендерам

К вопросу о RAM я ещё неоднократно вернусь ниже в секции “Packaging и Advanced Packaging” и вся глава “Память и буферы” посвящена этому.

CAM - Content-Addressable Memory

Это особо-хитрый вид памяти.
Вы ей - значение, а она вам - адрес ячейки.
Content-Addressable означает, что адресация базируется на значениях (содержимом).
https://fs.linkmeup.ru/images/articles/buffers/cam.png
Значением, например, может быть, например DMAC. CAM прогоняет DMAC по всем своим записям и находит совпадение. В ячейке CAM будет указатель на адрес ячейки в классической RAM, стоящей рядом, где хранится номер выходного интерфейса. Дальше устройство обращается к этой ячейке и отправляет кадр, куда положено.
Для достижения максимальной скорости CAM и RAM располагаются очень близко друг к другу.

Note

Не путать данную RAM с RAM, содержащей Soft Tables, описанной выше - это разные компоненты, расположенные в разных местах.

https://fs.linkmeup.ru/images/articles/buffers/cam_logic.png
Прелесть CAM в том, что она возвращает результат за фиксированное время, не зависящее от количества и размера записей в таблице - О(1), выражаясь в терминах сложностей алгоритмов.
Достигается это за счёт того, что значение сравнивается одновременно со всеми записями. Одновременно! А не перебором.
На входе каждой ячейки хранения в CAM стоят сравнивающие элементы (мне очень нравится термин компараторы), которые могут выдавать 0 (разомкнуто) или 1 (замкнуто) в зависимости от того, что на них поступило и что записано.
В сравнивающих элементах записаны как раз искомые значения.
Когда нужно найти запись в таблице, соответствующую определённому значению, это значение прогоняется одновременно через ВСЕ сравнивающие элементы. Буквально, электрический импульс, несущий значения, попадает на все элементы, благодаря тому, что они подключены параллельно. Каждый из них выполняет очень простое действие, выдавая для каждого бита 1, если биты совпали, и 0, если нет, то есть замыкая и размыкая контакт. Таким образом та ячейка, адресом которой является искомое значение, замыкает всю цепь, электрический сигнал проходит и запитывает её.

Вот архитектура такой памяти:

Вот пример работы

А это схема реализации:
https://fs.linkmeup.ru/images/articles/buffers/cam_storage_cell.png
Источник

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

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

  1. Длина результата значительно меньше, чем у входных значений. Так пространство MAC-адресов длиной 48 бит можно отобразить в 16-ибитовое значение, тем самым в 2^32 раза уменьшив длину значений, которые нужно сравнивать, и соответственно, размер CAM. Основная идея хэш-функции в том, что результат её выполнения для одинаковых входных данных всегда будет одинаков (например, как остаток от деления одного числа на другое - это пример элементарной хэш функции).
  2. Результат её выполнения на всём пространстве входных значений - это ± плоскость - все значения равновероятны. Это важно для снижения вероятности конфликта хэшей, когда два значения дают одинаковый результат. Конфликт хэшей, кстати, весьма любопытная проблема, которая описана в парадоксе дней рождения. Рекомендую почитать Hardware Defined Networking Брайна Петерсена, где помимо всего прочего он описывает механизмы избежания конфликта хэшей.
  3. Независимо от длины исходных аргументов, результат будет всегда одной длины. То есть на вход можно подать сложное сочетание аргументов, например, DMAC+EtherType, и для хранения не потребуется выделять более сложную структуру памяти.

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

В этот принцип отлично укладывается также MPLS-коммутация, почему MPLS и сватали в своё время на IP.

Например:

  1. Пришёл самый первый Ethernet-кадр на порт коммутатора.
  2. Коммутатор извлёк SMAC, вычислил его хэш.
  3. Данный хэш он записал в сравнивающие элементы CAM, номер интерфейса откуда пришёл кадр в RAM, а в саму ячейку CAM адрес ячейки в RAM.
  4. Выполнил рассылку изначального кадра во все порты.
  5. Повторил пп. 1-5 ….
  6. Заполнена вся таблица MAC-адресов.
  7. Приходит Ethernet-кадр. Коммутатор сначала проверяет, известен ли ему данный SMAC (сравнивает хэш адреса с записанными хэшами в CAM) и, если нет, сохраняет.
  8. Извлекает DMAC, считает его хэш.
  9. Данный хэш он прогоняет через все сравнивающие элементы CAM и находит единственное совпадение.
  10. Узнаёт номер порта, отправляет туда изначальный кадр.

Резюме:

  • Ячейки CAM адресуются хэшами.
  • Ячейки CAM содержат (обычно) адрес ячейки в обычной памяти (RAM), потому что хранить конечную информацию в CAM - дорого.
  • Каждая ячейка CAM имеет на входе сравнивающий элемент, который сравнивает искомое значение с хэш-адресом. От этого размер и стоимость CAM значительно больше, чем RAM.
  • Проверка совпадения происходит одновременно во всех записях, отчего CAM дюже греется, зато выдаёт результат за константное время.
  • CAM+RAM хранят Hard Tables (аппаратные таблицы), к которым обращается чип коммутации.

TCAM - Ternary Content-Addressable Memory

CAM весьма неплохо подходит для поиска MAC-адресов, где результат всегда заведомо один. А что не так с IP

Если мы возьмём описанный выше CAM, то на любой Destinataion IP он очень редко сможет вернуть 1 во всех битах.
Дело в том, что DIP - это всегда один единственный адрес, а маршруты в таблице маршрутизации - это подсеть или даже агрегация более мелких маршрутов. Поэтому полного совпадения быть почти не может - кроме случая, когда есть маршрут /32.
Перед разработчиками чипов стояло два вопроса:
  • Как это в принципе реализовать?
  • Как из нескольких подходящих маршрутов выбрать лучший (с длиннейшей маской)?
https://fs.linkmeup.ru/images/articles/buffers/tcam.png
Ответом стал TCAM, в котором “T” означает “троичный””. Помимо 0 и 1 вводится ещё одно значение ХЗ - “не важно” (CAM иногда называют BCAM - Binary, поскольку там значения два - 0 и 1).
Тогда результатом поиска нужной записи в таблице коммутации будет содержимое той ячейки, где самая длинная цепочка 1 и самая короткая “не важно”.
Например, пакет адресован на DIP 10.10.10.10.
В Таблице Маршрутизации у нас следующие маршруты:
0.0.0.0/0
10.10.10.8/29
10.10.0.0/16
10.8.0.0/13
Другие
В сравнивающие элементы TCAM записываются биты маршрута, если в маске стоит 1, и “не важно”, если 0.
При поиске нужной записи TCAM, как и CAM, прогоняет искомое значение одновременно по всем ячейкам. Результатом будет последовательность 0, 1 и “не важно”.
Только те записи, которые вернули последовательность единиц, за которыми следуют “не важно” участвуют в следующем этапе селекции.
Далее из всех результатов выбирается тот, где самая длинная последовательность единиц - так реализуется правило Longest prefix match.
Очевидно, что мы-то своим зорким взглядом, сразу увидели, что это будет маршрут 10.10.10.8/29.
Решение на грани гениальности, за которое пришлось заплатить большую цену. Из-за очень высокой плотности транзисторов (у каждой ячейки их свой набор, а ячеек должны быть миллионы) они греются не меньше любого CPU - нужно решать вопрос отвода тепла.
Кроме того, их производство стоит очень дорого, и не будет лукавством сказать, что стоимость сетевого оборудования раньше зачастую определялась наличием и объёмом TCAM.
Внимательный читатель обратил внимание на вопрос хэш-функций - ведь она преобразует изначальный аргумент во что-то совершенно непохожее на исходник, как же мы будем сравнивать 0, 1 и длины? Ответ: хэш функция здесь не используется. Описанный выше алгоритм - это сильное упрощения реальной процедуры, за деталями этого любознательного читателя отправлю к той же книге Hardware Defined Networking.

Алгоритмический поиск

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

Суть этого подхода в том, что вместо прожорливого до денег и электричества TCAM ставится отдельный ASIC, реализующий алгоритмический лукап IP-адреса (или чего-то ещё) и тот же RAM рядом.

TCAM всё ещё применяется в сетевом оборудовании для узкоспециалиазированных задач.

Подробнее послушать о алгоритмах этого класса и деревьях можно в подкасте с Кодом Безопасности.