CJSON: внутренний формат Reindexer для обработки данных

В Reindexer используется внутренний формат представления данных CJSON (Compact JSON). С его помощью решаются задачи:

1. Хранение in-memory и эффективная фильтрация — -tuple (в ядре Reindexer, вместе со структурой PayloadValue).
2. Передача данных по сети и хранение на диске - «транспортный» CJSON.

Структура CJSON для обоих случаев схожая, однако между -tuple и «транспортным» CJSON есть различия в способах хранения значений полей документа.

Структура CJSON

Каждое поле кодируется как ctag, за которым следуют data — байты значения в формате, зависящем от типа. Ctag — целое число, закодированное в формате varuint. Ctag включает в себя: тип поля(TagType), имя (TagName) и при ссылке на индексное поле payload — номер поля в PayloadValue.

Формат ctag представлен в таблице:

Возможные значения поля TypeTag:

Словарь имён (TagsMatcher)

TagsMatcher представляет из себя словарь имён, в котором каждому уникальному имени поля сопоставлено числовое значение. Этот механизм используется для более компактной сериализации документов. Объект TagsMatcher'a создаётся в момент создания неймспейса и дальше накапливает новые теги/имена по мере их появления в документах (при этом старые теги никогда не удаляются).

Общее максимальное количество уникальных тегов в одном неймспейсе не может превышать 4095, поэтому не рекомендуется использовать в качестве имён полей различного рода хеши. При достижении этого лимита невозможно будет добавить в неймспейс документ с каким-либо новым уникальным именем поля, которое никогда не встречалось ранее. На текущий момент, единственный способ полностью очистить TagsMatcher от старых имён (если они не используются) это полное пересоздание неймспейса из бэкапа, используя reindexer_tool.

Помимо словаря в объекте TagsMatcher также содержатся:

• StateToken - случайное uint32-значение, идентифицирующее конкретный объект словаря. Используется для синхронизации словарей между узлами;
• Version - текущая версия словаря. Инкрементально возрастает при добавлении новых полей. Каждая следующая версия словаря целиком содержит в себе предыдущую, а также включает как минимум одну новую пару “тег-имя”.

Для правильного декодирования CJSON объекты TagsMatcher для каждого неймспейса синхронизируются между клиентом и сервером, а также между лидером и всеми фолловерами в кластере, используя StateToken и Version.

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

{
    "field1": 123,
    "arr": [
    {
      "obj": {
        "field1": "string",
        "field2": 321
      },
      "arr": [ 1, 1],
      "flag": false
    },
    {
      "obj": {
        "field1": 10.7,
        "arr": []
      },
      "field1": [1, 1]
    }
  ],
  "flag": true
}

в словаре будет создано всего 5 уникальных тегов (TagName = индекс в словаре + 1):

Текущий статус TagsMatcher‘а (Version, StateToken, текущее и максимальное количество тегов в словаре) отображаются в неймспейсе #memstats в поле tags_matcher.

Хранение массивов

Массивы могут храниться двумя способами:

• Гомогенный — все элементы одного типа: TAG_ARRAY + atag (тип элемента и count); каждый элемент пишется в формате этого типа без отдельного ctag на элемент;
• Гетерогенный — элементы разных типов: TAG_ARRAY + atag(TAG_OBJECT, count); у каждого элемента свой ctag с пустым именем и без ссылки на поле payload.

Гетерогенные массивы не бывают индексными.

Многомерные массивы кодируются как смешанные. Однако, если многомерный массив содержит элементы только одного типа, он может быть проиндексирован.

Оба варианта используют atag в дополнение к ctag поля-массива.

atag — формат тега массива

atag — little-endian uint32_t: 6 старших бит — тип элемента, 24 младших — число элементов (TTTTTTNNNNNNNNNNNNNNNNNNNNNNNN).

Формат пакета CJSON

names_dictionary :=
  <uint32(count)>
  [<varint(длина имени)>, <байты имени>] // повтряется `count` раз
  ...

Offset to names dict не всегда присутствует в пакете. Если пакет начинается с TAG_END, за ним размещается Offset to names dict. Если же пакет начинается не с TAG_END, то в нем вообще не содержится словарь имен.

Формат записи

record :=
  ctag := (TAG_OBJECT)
    [ cjson_field :=
        ctag := (TAG_VARINT,name,field) data := <zigzag + base-128> |
        ctag := (TAG_DOUBLE,name,field) data := <8 bytes double> |
        ctag := (TAG_FLOAT,name,field) data := <4 bytes float> |
        ctag := (TAG_UUID,name,field) data := <16 bytes UUID> |
        ctag := (TAG_BOOL,name,field) data := <1 byte: 0 / 1> |
        ctag := (TAG_STRING,name,field) data := <uint32_pack(length)>, <bytes> |
        ctag := (TAG_NULL,name,field) |
        hom_array :=
          ctag := (TAG_ARRAY,name,field)
            atag := (TAG_VARINT|TAG_DOUBLE|TAG_FLOAT|TAG_UUID|TAG_BOOL|TAG_STRING, count)
              [ array_element := <кодирование скаляра> ]
              ... |
        het_array :=
          ctag := (TAG_ARRAY,name,field)
            atag := (TAG_OBJECT, count)
              [ array_element :=
                ctag := (TAG_…) data := <скаляр> |
                ctag := (TAG_OBJECT) [cjson_subfield := cjson_field …] |
                hom_array | het_array
              ]
              ...
        ctag := (TAG_OBJECT,name,field)
          [ cjson_subfield := cjson_field ]
          ...
        ctag := (TAG_END)
    ]
    ...
  ctag := (TAG_END)

Примеры сериализации CJSON

В примерах ниже рассматривается «транспортный» CJSON: для всех полей field = 0.

Сериализация гомогенных массивов

• JSON
• CJSON
• Словарь имен объекта

{ "str_arr": ["hi", "bro"] }

ctag(type: TAG_OBJECT, name: 0, field: 0)       06
  ctag(type: TAG_ARRAY, name: 1, field: 0)      0D
    atag(type: TAG_STRING, len: 2)              02 00 00 02
      2,"hi"                                    02 68 69
      3,"bro"                                   03 62 72 6F
ctag(type: TAG_END, name: 0, field: 0)          07

0 - "str_arr" -> TagName 1

Сериализация гетерогенных массивов

• JSON
• CJSON
• Словарь имен объекта

{ "het_arr": ["hi", true, 123] }

ctag(type: TAG_OBJECT, name: 0, field: 0)       06
  ctag(type: TAG_ARRAY, name: 1, field: 0)      0D
    atag(type: TAG_OBJECT, len: 3)              03 00 00 06
      ctag(type: TAG_STRING, name: 0, field: 0) 02
        2,"hi"                                  02 68 69
      ctag(type: TAG_BOOL, name: 0, field: 0)   03
        1                                       01
      ctag(type: TAG_VARINT, name: 0, field: 0) 00
        123                                     F6 01
ctag(type: TAG_END, name: 0, field: 0)          07

0 - "het_arr" -> TagName 1

CJSON с полями различных типов

• Объект в JSON
• Объект в CJSON
• Словарь имен объекта

{
  "name": "Hello",
  "year": 2010,
  "articles": [
    1,
    2,
    3,
    4,
    5
  ],
  "info": {
    "name": "Info"
  },
  "table": [
    [1,2],
    [3,4]
  ]
}

ctag(type: TAG_OBJECT, name: 0)                06
  ctag(type: TAG_STRING, name: 1, field: 0)    0A
    5,"Hello"                                  05 48 65 6C 6C 6F
  ctag(type: TAG_VARINT, name: 2, field: 0)    10
    2010                                       B4 1F
  ctag(type: TAG_ARRAY, name: 3, field: 0)     1B
    atag(type: TAG_VARINT, len: 5)             05 00 00 00
      1 2 3 4 5                                01 02 03 04 05
  ctag(type: TAG_OBJECT, name: 4, field: 0)    26
     ctag(type: TAG_STRING, name: 1, field: 0) 0A
       4,"Info"                                04 49 6E 66 6F
  ctag(type: TAG_END, name: 0, field: 0)       07
  ctag(type: TAG_ARRAY, name: 5, field: 0)     2D
    atag(type: TAG_OBJECT, len: 2)             02 00 00 06
      ctag(type: TAG_ARRAY, name: 0, field: 0) 05
        atag(type: TAG_VARINT, len: 2)         02 00 00 00
          1 2                                  01 02
      ctag(type: TAG_ARRAY, name: 0, field: 0) 05
        atag(type: TAG_VARINT, len: 2)         02 00 00 00
          3 4                                  03 04
ctag(type: TAG_END, name: 0, field: 0)         07

0 - "name"     -> TagName 1
1 - "year"     -> TagName 2
2 - "articles" -> TagName 3
3 - "info"     -> TagName 4
4 - "table"    -> TagName 5

-tuple и «транспортный» CJSON

-tuple

-tuple в формате CJSON используется для обработки документов ядром Reindexer. Его применение позволяет решить проблему с отсутствием унифицированной структуры записей в документоориентированных БД, когда каждая запись может иметь уникальные поля и нужно где-то хранить информацию по её неиндексным полям.

-tuple — всегда первое (с индексом 0) поле записи (PayloadValue → Item).

Каждое поле описывается ctag (для массивов — ещё atag):

• TypeTag — тип значения;
• NameIndex — TagName (имя в словаре + 1);
• FieldIndex — ссылка на слот в PayloadValue (индекс поля + 1), если значение индексное.

Если поле индексное, в FieldTag хранится его индекс в PayloadType и IndexesStorage (этот индекс также позволяет вычислить его смещение в PayloadValue). При этом в -tuple сериализуется только ctag, а само значение находится в PayloadValue (доступ к нему можно получить через метод PayloadIface::Get(ctag.field)).

Если поле неиндексное, значение ctag.field = 0. Значение поля сериализуется сразу за ctag.

Все документы неймспейса хранятся в NamespaceImpl (массив items_) в виде PayloadValue. У каждого такого документа в нулевом поле находится значение -tuple.

«Транспортный» CJSON

«Транспортный» CJSON используется для передачи по сети и на диске. С ним работают cproto-/grpc-клиенты и серверы, а также проксирование в синхронном кластере и шардировании.

В «транспортным» CJSON (в отличие от -tuple, используемого ядром) каждое поле, независимо от того, индексное оно или неиндексное, кодируется без ссылок на его значение в PayloadValue. То есть значение каждого поля хранится непосредственно внутри объекта CJSON. Ссылки на индексные поля в данном случае использоваться не могут, поскольку клиент может не иметь данных PayloadType.

Пример обхода структуры CJSON

Код взят из функции ядра skipCjsonTag.

В этом фрагменте происходит декодирование/пропуск одного ctag и связанных с ним данных. Помимо этого в fieldsArrayOffsets собирается текущее смещение внутри индексных массивов.

void skipCjsonTag(ctag tag, Serializer& rdser, std::array<unsigned, kMaxIndexes>* fieldsArrayOffsets) {
	switch (tag.Type()) {
		case TAG_ARRAY: {
			// Декодирование массивов
			const auto field = tag.Field();
			const bool embeddedField = (field < 0);
			if (embeddedField) {
				// Декодирование неиндексного массива. Все значения встроены непосредственно в blob
				const carraytag atag = rdser.GetCArrayTag();
				const auto count = atag.Count();
				if (atag.Type() == TAG_OBJECT) {
					// Для гетерогенным массивов считывается явный ctag
					for (size_t i = 0; i < count; ++i) {
						skipCjsonTag(rdser.GetCTag(), rdser, fieldsArrayOffsets);
					}
				} else {
					// Для гомоенных массивов для всех элементов используется тип из atag
					for (size_t i = 0; i < count; ++i) {
						skipCjsonTag(ctag{atag.Type()}, rdser, fieldsArrayOffsets);
					}
				}
			} else {
				// Декодирование индексного массива. Сами значения хранятся внутри PayloadValue, а здесь декодируется только длина
				const auto len = rdser.GetVarUInt();
				if (fieldsArrayOffsets) {
					(*fieldsArrayOffsets)[field] += len;
				}
			}
		} break;
		case TAG_OBJECT:
			// Декодирование вложенного объекта, состоящего из произвольного количества полей
			for (ctag otag{rdser.GetCTag()}; otag != kCTagEnd; otag = rdser.GetCTag()) {
				skipCjsonTag(otag, rdser, fieldsArrayOffsets);
			}
			break;
		case TAG_VARINT:
		case TAG_STRING:
		case TAG_DOUBLE:
		case TAG_END:
		case TAG_BOOL:
		case TAG_NULL:
		case TAG_UUID:
		case TAG_FLOAT: {
			// Декодирование скалярных значений
			const auto field = tag.Field();
			const bool embeddedField = (field < 0);
			if (embeddedField) {
				// Неиндексные склаярные значения встроены непосредственно в blob
				rdser.SkipRawVariant(KeyValueType{tag.Type()});
			} else if (fieldsArrayOffsets) {
				// Для индексных скалярных значений просто корректируется смещение в плоском массиве.
				// Несмотря на то, что на текущем уровне вложенности значение в CJSON является скаляром,
				// оно всё равно может являться частью индекса-массива
				(*fieldsArrayOffsets)[field] += 1;
			}
		} break;
		default:
			throw Error(errParseJson, "skipCjsonTag: unexpected ctag type value: {}", int(tag.Type()));
	}
}

Основные модули работы с CJSON

В Reindexer для работы с CJSON используются следующие основные модули: