vitus_wagner | Semantic locality

> В современном серверном софте есть некотоая благая подвижка, в которой cli ко всякому сложному софту выводят данные в json. Всё то же самое, но уже с минимальной структурой, так, что не нужно тратить специальные усилия на обработку специальных случаев (пробелы в именах, "неправильные" символы и т.д.). Вместе с jq и другими видами query languages это очень удобно.

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

Edited 2017-03-16 10:25 (UTC)

Вообще, потоковый парсинг json'а уже есть. Тот же jq предполагает, что указанная "семантическая локальность" вообще реализуется посредством стекирования json'ов (закончился один, начинается следующий).

Отсутствие универсального решения, которое бы покорило всех - да, печалит. Но, с другой стороны, отсутствие решения печалит ещё больше.

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

"потоковый парсинг json'а" - это почти оксюморон :)

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

Во-вторых, JSON имеет отягощённую наследственность: у него в нутре гены JS, не предполагающего упорядоченность где-либо, кроме массивов, соответственно, любой обработчик имеет право переставлять ключи местами как попало, и читателю опять же придётся считать их все, прежде чем что-то обработать.

Чтобы обрабатывать это всё потоком - придётся много дополнительных ограничений на JSON наложить. В старом добром же Юниксе, можно было в большинстве случаев говорить о локальности, пока нам кто-нибудь гарантирует ограниченность длинны строки (в смысле line, а не string)

Но потоковые парсеры при этом всё-таки есть. Собственно, в любом потоковом протоколе нам могут подсунуть объект больше нашего буффера размером. Например, строку длиной в гигабайт во внутрь авка. Как только мы эти данные начинаем считать не потоком байтов (для которых локальность 1) или потоком чего-то простого (4 байтовых последовательностей), так тут же локальность начинает становиться величиной условной.

Хотя в том же json'е, например, задача "извлечь 100 Гб значение по ключу из 10000 Гб json'а" вполне решается. Мы просто вешаем обработчик на чтение значения, которое выдаёт значение на stdout по мере чтения, а всё остальное пропускаем. Если у нас при этом нет превышения по размеру ключа (очевидно, что мы не можем найти что-то по ключу, который больше нашей оперативной памяти, т.к. не сможем его передать как параметр программы), то это вполне рабочее.

Я баловался с потоковыми парсерами json'ов, на удивление, это вещь и она может существовать в константной памяти при неконстантных входных данных.

Я поэтому и оговорил ограниченную длину строки. Притом команде sort, например, это не поможет, поскольку она по сути нелокальна, но большинству фильтров этого достаточно. А вот с настоящим JSON этот фокус не пройдёт, даже если мы ограничим длины всех констант, всех массивов и всех хэш-таблиц. Впрочем, если ограничить ещё и глубину деревьев, то таки получится.

Скажи, какую операцию в json'е ты хочешь делать? Многие из них могут выполняться в локальном контексте.

Банальный фильтр, который должен бы быть поточным: читаем входной поток неких токенов с полями, а для тех, у которых выполняется некое условие на поле1 и поле2, выводим в выходной поток поле3 целиком, не вникая в содержимое.

Соответственно, в случае JSON мы всегда можем получить на вход что-нибудь такое:

{
  поле1: значение,
  поле3: { развесистое и глубокое дерево },
  поле2: значение
}

в результате мы должны запомнить всё, что в поле1 и в поле3, прежде чем считаем поле2 и сможем принять решение, выводить ли нам поле3. А это уже нелокальность, приходится помнить много лишнего.

Как часто требуется обрабатывать преогромные деревья, да еще и сортировать их?

Для XML существуют SAX-парсеры, вполне себе работают на многогигабайтных данных.

Там нет проблемы 2, так что при хорошей структуре XML и соответствующих запросах, связка SAX + заточенный под запрос фильтр вполне справляется на ограниченной памяти.

По поводу пайпов согласен.

К примеру, если бы g++ выплёвывал stderr в каком-то структурированном формате, то возможно, было бы проще копаться в template vomit.

Но с другой стороны, благодаря принципу семантической локальности также оказалось возможным реализовать функционал, связанный с командой make в vim - благодаря давнему соглашению о текстовом формате имя_файла:строка:столбец: (make не знает в каком точно формате идёт вывод ошибок). Если каждый раз придумывать свой формат, то взаимодействующие программы будут вынуждены менять код для разбора вывода.

Ну вот смотри. Есть у тебя соглашение "имя_файла:строка:столбец". Строка и столбец - инты. А имя файла - строка, произвольная строка, соответствующая требованиям unix для имени файла.

Этот протокол неконсистентный, ибо он не сможет показать ошибку в файле "пример ошибки в файле:33:44" на строке 2 и столбце 4.

И вот эта неконсистентность между соглашениями (нам обещают stateless-separator, выдавая либо что-то без эскейпинга, либо с ложными срабатываниями) и превращает шелл-пайпы из няшки в ад и некомфортность.

Собственно, что там далеко говорить. Из свежего: systemd положил файлик "-" - и всё, миллион вопросов о том, почему ls ломается.

В целом согласен.

Кстати, я сейчас подумал, что для соблюдения семантической локальности в JSON-протоколе нужно принять соглашение, что бы единичные сущности внутри потока были описываемыми в виде object с ненулевым количеством ключей. Т.к, например, если мы каким-то инструментом (специализированным, интересно - есть ли уже такой?) находим строку


{ "filename": "пример ошибки в файле:33:44", "line": 2, "column": 4 }

то эта строка описывает именно некий объект (семантически-похожий на "упоминание места в файле"), т.к. если бы эта строка была в другой строке, то кавычки были бы заэскейплены.

Edited 2017-03-16 11:20 (UTC)

а что не так с минусом у ls?

edo@edo-home:/tmp/minustest$ touch -
edo@edo-home:/tmp/minustest$ ls
edo@edo-home:/tmp/minustest$ touch "-"
edo@edo-home:/tmp/minustest$ ls
edo@edo-home:/tmp/minustest$ echo 123 > -
edo@edo-home:/tmp/minustest$ ls
-
edo@edo-home:/tmp/minustest$ ls -l
total 4
-rw-r--r-- 1 edo edo 4 Mar 17 12:24 -
edo@edo-home:/tmp/minustest$ ls *
-

На вопрос "А что не так с минусом у touch" вы уже сами себе ответили :)
А теперь попробуйте команду "ls *"
И то же с файлами "--", "-l", "-a" и т.д.

Edited 2017-03-17 20:45 (UTC)

так я же специально написал, что ls * проверил, не страшно для ls имя файла из одного минуса

вот с "-l" фокус удался, да.

Semantic locality

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject

no subject