Хранение кортежей UTF-8 с использованием наименьшего общего технологического знаменателя, только добавление

РЕДАКТИРОВАТЬ: Обратите внимание, что из-за того, как на самом деле жесткие диски записывают данные, ни одна из схем в этом списке не работает надежно. Не используйте их. Просто используйте базу данных. SQLite — хороший, простой.

Какой самый простой, но надежный способ хранения кортежей строк UTF-8 на диске? Хранилище должно быть добавлено только для надежности.

Как часть системы хранения документов, с которой я экспериментирую, мне нужно хранить данные кортежа UTF-8 на диске. Очевидно, что для полноценной реализации я хочу использовать что-то вроде Amazon S3, Project Voldemort или CouchDB.

Однако на данный момент я экспериментирую и еще даже не определился с языком программирования. Я использовал CSV, но CSV, как правило, становится хрупким, когда вы пытаетесь сохранить диковинный юникод и неожиданные пробелы (например, вертикальные табуляции).

Я мог бы использовать XML или JSON для хранения, но они плохо работают с файлами только для добавления. Мое лучшее предположение на данный момент - это довольно своеобразный формат, в котором каждой строке предшествует 4-байтовое целое число со знаком, указывающее количество байтов, которые она содержит, а целочисленное значение -1 указывает, что этот кортеж завершен - эквивалент новой строки CSV . Основной источник головной боли — это необходимость принимать решение о порядке следования целых чисел на диске.

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

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

Редактирование 3. Конечный результат можно просмотреть на странице http://github.com/MetalBeetle/Fruitbat/tree/master/src/com/metalbeetle/fruitbat/atrio/ .


person Zarkonnen    schedule 30.06.2010    source источник
comment
Очень интересный вопрос. У меня нет ответа, но я думаю о чем-то вроде модели хранилища объектов Git. Какой длины обычно бывают эти строки и могут ли они содержать нулевые байты?   -  person Christoffer Hammarström    schedule 30.06.2010
comment
@Chris По большей части они, вероятно, будут довольно короткими и могут содержать нуль. Система действительно во многом похожа на git, но предназначена для хранения документов, а не кода.   -  person Zarkonnen    schedule 30.06.2010
comment
Кроме того, являются ли данные UTF-8 в основном совместимыми с 7-битным ASCII? То есть большинство кодовых точек находятся в диапазоне 0-127?   -  person Christoffer Hammarström    schedule 30.06.2010
comment
@Chris: Да, но все кодовые точки вплоть до астральных планов должны поддерживаться, даже если это неэффективно с точки зрения пространства.   -  person Zarkonnen    schedule 30.06.2010


Ответы (2)


Я бы рекомендовал табуляцию, разделяющую каждое поле, и возврат каретки, разделяющую каждую запись.

В каждой строке замените все символы, которые могут повлиять на поле, и запишите интерпретацию и визуализацию. Это может включать управляющие символы (U+0000–U+001F, U+007F–U+009F), неграфические разделители строк и абзацев (U+2028, U=2029), управляющие символы направления (U+202A–U+ 202E) и знак порядка байтов (U+FEFF).

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

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

Это также было бы легко закодировать, поскольку файл будет действительным документом UTF-8, поэтому можно использовать стандартные процедуры чтения и записи текста. Это также позволяет легко конвертировать в UTF-16BE или UTF-16LE, если это необходимо, без осложнений.

Пример:

U+0009 CHARACTER TABULATION becomes ~TB
U+000A LINE FEED            becomes ~LF
U+000D CARRIAGE RETURN      becomes ~CR
U+007E TILDE                becomes ~~~
etc.

Есть несколько причин, по которым табуляция лучше запятой в качестве разделителя полей. Запятые чаще появляются в обычных текстовых строках (например, в тексте на английском языке), и их придется заменять чаще. А программы для работы с электронными таблицами (такие как Microsoft Excel), как правило, гораздо более естественно обрабатывают файлы с разделителями табуляцией.

person Jeffrey L Whitledge    schedule 30.06.2010
comment
Возможно, тогда можно было бы использовать кодировку URL, так как это уже стандарт. - person Christoffer Hammarström; 30.06.2010
comment
@Christoffer Hammarström - кодирование URL также преобразует пробелы и (я предполагаю) кавычки, которые я бы предпочел сохранить нетронутыми, но, поскольку они, вероятно, будут доступны в языковых библиотеках, использование этого превращает весь этот проект в просто подключение нескольких частей вместе, так что это довольно хорошая идея. - person Jeffrey L Whitledge; 01.07.2010
comment
Да, я согласен, это не должно быть полное кодирование URL, только для проблемных байтов. В противном случае длина большинства несовместимых с ASCII строк удваивалась бы или утраивалась. - person Christoffer Hammarström; 01.07.2010
comment
Или, конечно, можно было бы просто использовать старые добрые управляющие последовательности \\ \r \t \n \x00 - person Christoffer Hammarström; 01.07.2010

Тут в основном мысли вслух...

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

Возможно, вместе с этим можно использовать SCSU.

Или, возможно, стоит взглянуть на формат gzip, и, возможно, обезьянничать, если не использовать его:

Файл gzip состоит из серии «элементов» (сжатых наборов данных).

[...]

Члены просто появляются в файле один за другим, без дополнительной информации до, между или после них.

Каждый из этих элементов может иметь необязательное «имя файла», комментарий и т.п., и я считаю, что вы можете просто добавлять элементы.

Или вы можете использовать бенкод, используемый в torrent-файлах. Или BSON.

См. также Сравнение форматов сериализации данных в Википедии.

В противном случае я думаю, что ваша идея предварять каждую строку ее длиной, вероятно, самая простая.

person Christoffer Hammarström    schedule 30.06.2010