Парсер многогигабитных потоков данных

[Romiras]

Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.

Там конкретно может представлять интерес PicoHTTPParser.
PicoHTTPParser now has a chunked-encoding decoder

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

never write a character-level state machine if performance matters

[Губанов Сергей Юрьевич]

Может интересно будет, вот ссылка на блог (метка H2O) http://blog.kazuhooku.com/search/label/H2O , где автор делится опытом создания быстрого веб-сервера и, в том числе, быстрого и к тому же ещё и stateless, http парсера.

Спасибо.

Посмотрел его код: https://github.com/h2o/picohttpparser/blob/master/picohttpparser.c

Он сначала копирует данные в накопительный буфер, потом парсит обычным stateless парсером.

Мне копировать данные нельзя - не хватит пропускной способности контроллера памяти. Да и сильно накапливать данные мне тоже нельзя - не хватит объёма памяти.

[Губанов Сергей Юрьевич]

Пока сделал следующим способом. Те L7 протоколы которые мне сейчас надо парсить объединяет то, что они текстово-построчные: каждый параметр в новой строке.

Чтобы их парсить "со скоростью света" удобно было бы
1) уметь видеть начало строки (10-20 букв) в виде непрерывного массива (для того чтобы распознать ключевое слово);
2) уметь быстро пропустить текущую строку (если параметр не интересует);
3) уметь считывать значение интересующего параметра.

Данные лежат в списке IP пакетов (в списке буферов). Распознавание организовано как следующий цикл:

1) В начале цикла запрашивается указатель char* на первые несколько букв новой строки (для определённости пусть будет 20 букв). Если до конца текущего IP пакета ещё много места (больше 20 букв), то просто возвращается указатель на текущую позицию (это быстро, за счёт этого peek работает со скоростью света). Если до конца текущего пакета осталось совсем немного (меньше 20 букв), но есть ещё один IP пакет, то несколько оставшихся букв из первого IP пакета и несколько первых букв из второго IP пакета копируются в отдельный 20-буквенный буфер и возвращается указатель на него. Это тоже довольно быстро, ведь надо скопировать всего 20 байт да и то, только на границе IP пакетов. Если пакеты большие, то это случается редко. На всякий случай предусмотрел возможно мёржить в такой буфер до 4 IP пакетов (вдруг будут пакеты по пять байтов  ). Если до конца текущего IP пакета осталось меньше 20 букв, а следующего IP пакета ещё нет (и, возможно, не будет), то пытаемся отыскать символ конца строки '\n' в оставшемся хвосте. Это тоже довольно быстро делается. Если нашли '\n' значит возвращаем указатель на строку и говорим что размер у неё такой-то (меньший 20 байт). На всякий случай предусмотрел возможность искать конец строки в нескольких IP пакетах (до 4 штук).

2) Получив указатель char* на первые 20 букв (или меньше если найден конец строки) определяю что там за ключевое слово написано, если оно мне не интересно, то парсер переводится в состояние "пропустить текущую строку".

3) Если ключевое слово интересно, то парсер переводится в состояние чтения значения после ключевого слова.

То есть состояний у парсера получилось совсем немного...

[Romiras]

На ДРАКОН-схеме алгоритм было бы проще понять.
Ещё надо учесть и IPv6.

[kkkk]

Для таких случаев я запускаю разборщик в параллельном потоке. Он продвигается по рекурсивному спуску по мере поступления данных из главного потока. Для обмена данными я использую POSIX pipe(fd):  в основном потоке - write(fd[1]), в параллельном - read(fd[0]).

[Губанов Сергей Юрьевич]

Для таких случаев я запускаю разборщик в параллельном потоке. Он продвигается по рекурсивному спуску по мере поступления данных из главного потока. Для обмена данными я использую POSIX pipe(fd):  в основном потоке - write(fd[1]), в параллельном - read(fd[0]).

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

[Valery Solovey]

А такой вариант пробовали?

Выделяется довольно большой кольцевой буфер. Единым куском памяти.
Туда с начала и почти до конца (как придётся) пишутся данные из сети. В TCP/IP размер пакета может меняться, поэтому заранее предугадать или задать его нельзя. Или не желательно. Поэтому, очередной пакет пишется туда, где окончился предыдущий пакет. Когда в буфере заканчивается место или размер остатка будет делать работу сети не эффективной, то переходить к началу буфера.

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

[Губанов Сергей Юрьевич]

Выделяется довольно большой кольцевой буфер. Единым куском памяти. Туда с начала и почти до конца (как придётся) пишутся данные из сети.

Мне так нельзя по двум причинам:

1) Мне нельзя копировать данные (трафик запредельно огромный). То есть нет никаких собственных буферов для данных. Я работаю с указателями на области памяти куда сетевые пакеты кладутся чисто аппаратно самим сетевым контроллером.

2) Даже если бы в природе существовал гипер контроллер памяти, который мог бы копировать данные со сверхсветовой скоростью, то таких больших кольцевых буферов мне пришлось бы завести более ста миллионов штук одновременно (столько одновременных потоков данных).

[Kemet]

это же классическая задача поставщика-потребителя!
И вот как она решается на Активном Обероне:

Код: [Выделить]

MODULE BoundedBuffers;
TYPE
  Item* = OBJECT;
 
  Buffer* = OBJECT
    VAR
      h, n: INTEGER;
      B: ARRAY * OF Item;
 
    PROCEDURE Get*(): Item;
    VAR x: Item;
    BEGIN {EXCLUSIVE}
      AWAIT(n # 0); (* буфер не пуст *)
      x := B[h]; h := (h+1) MOD LEN(B); DEC(n);
      RETURN x
      END Get;
 
    PROCEDURE Put*(x: Item);
    BEGIN {EXCLUSIVE}
      AWAIT(n # LEN(B)); (* буфер не полон *)
      B[(h+n) MOD LEN(B)] := x; INC(n)
    END Put;
 
    PROCEDURE &Init(max: INTEGER);
    BEGIN (* инициализатор *)
      NEW(B, max); h := 0; n := 0
    END Init;
  END Buffer;
 
END BoundedBuffers.

[Valery Solovey]

Это решение аналогично моему. И у него та же проблема: Put - аппаратный. Его осуществляет сетевая карта. И поэтому, на операцию записи в буфер налагаются аппаратные и, возможно, ОС-ные ограничения. Операция записи не достаточно гибка, чтобы последовательно записывать данные в один и тот же буфер по кругу. Возможно, частично это можно решить, вмешавшись в работу ОС (управление памятью и драйвер сетевой карты), но я сомневаюсь, что сама сетевая карта будет способна писать данные по любому смещению в памяти. Поэтому, для того, чтобы воспользоваться такой очередью, потребуется копировать данные из исходного буфера в дополнительный, а Сергей хочет этого избежать.

[Kemet]

...

Пример не об очереди, а о многопоточности и синхронизации

[Губанов Сергей Юрьевич]

это же классическая задача поставщика-потребителя!

"Никто ни хрена не понимает за пределами своих собственных работ."

[ilovb]

Приматический интеллект = комбинаторный интеллект

http://vteninn.livejournal.com/8263.html

Любопытно. Это у info21 утащили или он утащил. Или это такая всеобщая догадка? Типа тренд...?

Я вообще уже долгое время над этим размышляю. И все больше убеждаюсь, что человеки практически ничего не делают окромя этого самого "доставания бананов".
То, что там info21 задвигал про второй умотип интересно, но мутно.

Гораздо убедительнее идея, что все человеки тупые как бревна. Даже эти ваши эйнштейны с фенманами.
Вот читал у кого-то мол мозг это тупо популяция клеток, которые могут эволюционировать (скорее приспосабливаться) более эффективно (без нужды дохнуть мильёнами) чем обычные. Ну т.е. там где раньше мульон годов требовался, тепереча достаточно часа... и т.д. и т.п. в том же духе. Кажется довольно правдоподобным. И получается типа бошка - это такой эволюционный котелок, в котором путем комбинирования и отбора выращиваются конкретные мемы, которые посредством социума вовлекаются в другие комбинаторные процессы и т.д.
И как бы нет никакой умности в итоге. Этот ваш эйнштейн нихера бы не добился родившись в окружении других мемов.
Индивидуальные физиологические различия конечно влияют на способность к конкретной умственной деятельности, но это лишь случайное стечение обстоятельств... (мемы + способности)

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

[ilovb]

Во я тупой. Тык это он и есть. (судя по другим текстам)

[Geniepro]

Во я тупой. Тык это он и есть. (судя по другим текстам)

Так профиль вот куда ведёт: http://www.inr.ac.ru/~ftkachov/vteninn/