Красота столбцов данных

Когда мы думаем о наборах данных, мы, естественно, думаем о строковой форме, где строка - это запись, а столбец - это определенное свойство записи.

Хорошо, я снова становлюсь слишком абстрактным, извините. Возьмем пример. Взгляните на это простое представление истории чата в формате JSON:

[
  {
    "message": "Hi Bob. How are you?",
    "timestamp": 1508423069,
    "senderId": 238476,
    "seen": true
  },{
    "message": "This is Alex.",
    "timestamp": 1508423226,
    "senderId": 238476,
    "seen": true
  },{
    "message": "Hi Alex. I am fine. How are you?",
    "timestamp": 1508423238,
    "senderId": 9837498,
    "seen": false
  }
]

Мы видим три сообщения между двумя участниками. Объект сообщения - это строка, а свойства сообщения можно рассматривать как столбцы. Это представление является естественным для нас, именно так данные были сгенерированы, и именно так мы их хранили.

А теперь давайте попробуем что-нибудь, давайте повернем представление:

{
  "messages": ["Hi Bob. How are you?", "This is Alex.", "Hi Alex. I am fine. How are you?"],
  "timestamps": [1508423069, 1508423226, 1508423238],
  "senderId": [238476, 238476, 9837498],
  "seen": [true, true, false]
}

В этом JSON у нас есть представление, ориентированное на столбцы. Наш JSON больше не является массивом объектов, он стал объектом массивов. Это означает, что если нам нужно получить второе сообщение, мы делаем что-то вроде o["messages"][2], а не o[2]["message"].

Таким образом, нам не нужно повторять названия свойств, что приводит к уменьшению размера примерно на 30%. К сожалению, когда дело доходит до JSON, речь идет о преимуществах 🙃. Но давайте рассмотрим одни и те же данные в другой форме. Давайте посмотрим на ту же историю чата в виде файла CSV.

Hi Bob. How are you?,1508423069,238476,true
This is Alex.,1508423226,238476,true
Hi Alex. I am fine. How are you?,1508423238,9837498,false

VS.

Hi Bob. How are you?,This is Alex.,Hi Alex. I am fine. How are you?
1508423069,1508423226,1508423238
238476,238476,9837498
true,true,false

В CSV при повороте представления размер не увеличивается. Количество персонажей осталось прежним, но мы получили еще одно интересное преимущество. Представьте, что мы хотим найти каждое сообщение, содержащее строку «Alex». Простой поиск строки сообщения в CSV-формате, ориентированном на столбцы, может выглядеть примерно так:

var index = 0
var result: Set<Int> = []
for (c1, pos1) in fileContent.enumerated {
  var found = true
  for (c2, pos2) in searchPattern.enumerated {
    if fileContent[pos1+pos2] != c2 { found = false; break }
  }
  if found {
    result.append(index)
  } else {
    if c1 == "," {
      index += 1
    } else if c1 == "\n" {
      break
    }
  }
}

Этот псевдо-код Swift должен визуализировать, что в случае ориентированного на столбцы CSV линейный поиск ограничен первой текстовой строкой, нам не нужно рассматривать другие строки, поскольку мы знаем, что текст сообщения помещается вместе в первой строке. Таким образом, в худшем случае производительность поиска - это длина первой строки, умноженная на длину поискового шаблона. Напротив, если данные будут основаны на строках, в худшем случае производительность будет равна длине всего fileContent, умноженной на длину шаблона поиска. Мы могли бы реализовать менее наивный алгоритм, но он был бы более сложным и все равно имел бы худшую производительность в худшем случае, потому что вы не можете сканировать все символы.

Теперь давайте рассмотрим двоичное представление. В двоичном формате мы можем получить еще больше от данных, ориентированных на столбцы. Повторение одного и того же типа данных упрощает выравнивание. Подождите, что вы имеете в виду под выравниванием?

В Википедии есть статья Выравнивание структуры данных, вы можете прочитать ее и пропустить следующий абзац. Или, если вас больше интересует мое объяснение, вот оно:

Процессоры обращаются к памяти порциями по 8, 16, 32, 64 или 128 бит, в зависимости от типа процессора. Скажем, у нас есть ЦП, который читает 64-битные = 8-байтовые блоки. Можно попросить ЦП перейти к адресу 7 и прочитать 1 байт, потому что ЦП фактически считывает данные с адресов с 0 по 8 и дает вам 7-й байт. Однако, если вы просите ЦП прочитать 2 байта, начиная с адреса 7, вы делаете это неправильно. В лучшем случае вы получите ошибку сегментации, с которой можно справиться, загрузив данные с адреса 0-7, а затем с 8 по 15. В худшем случае это окажется ошибка шины или необработанная ошибка сегментации, что приводит к сбою вашего приложения. Вот почему данные должны быть согласованы. В нашем случае, если у нас есть чтение ЦП 8-байтовыми порциями и нам нужно сохранить 2 байта, адрес, на котором мы можем его сохранить, должен быть n % 8 <= 6.

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

struct S1 {
 let a: Bool
 let b: Int64
 let c: Bool
 let d: Int64
 let e: Bool
}
struct S2 {
 let b: Int64
 let d: Int64
 let a: Bool
 let c: Bool
 let e: Bool
}

Экземпляр struct S1 будет храниться в 40 байтах, но S2 потребуется только 24 байта, даже если они оба хранят одну и ту же информацию. Struct S1 нуждается в 7-байтовом заполнении между свойством a и b, потому что мы не можем прочитать 8 байтов, начиная с адреса 1. То же самое относится к свойствам c и d, и нам придется на всякий случай поставить 7-битное заполнение после свойства e - потому что мы не Не знаю, какие данные будут храниться после S1. В случае S2 нам нужно заполнить только 5 байтов после свойства e.

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

Давайте снова возьмем наш пример истории чата и рассмотрим его как бинарную структуру.

Hi Bob. How are you?\0|1508423069|238476|true

Скажем, мы хотим сохранить сообщение как массив символов UTF8 с 0 в качестве флага завершения строки. Отметка времени будет размером 8 байт. Идентификатор отправителя также является 8-байтовым uint, а флаг увиденного - 1-байтовым логическим значением. Если мы сохраним порядок в том виде, в каком он есть, нам придется добавить к сообщению отступы, потому что отметка времени составляет 8 байт. И там ведь должно начинаться с адреса n % 8 == 0. Итак, чтобы уменьшить потери памяти, мы сохраним запись, как показано ниже

1508423069|238476|true|Hi Bob. How are you?\0

Это нормально, но что происходит, когда мы храним много записей

1508423069|238476|true|Hi Bob. How are you?\0
1508423226|238476|true|This is Alex.\0
1508423238|9837498|false|Hi Alex. I am fine. How are you?\0

Теперь нам все еще нужно добавить отступ в конец текста, потому что следующая запись должна начинаться с адреса n % 8 == 0. Таким образом, в худшем случае у нас будет 7, умноженное на количество записей, как потеря памяти.

Давайте посмотрим на представление, ориентированное на столбцы:

1508423069|1508423226|1508423238
238476|238476|9837498
true|true|false
Hi Bob. How are you?\0|This is Alex.\0|Hi Alex. I am fine. How are you?\0

При таком представлении мы все равно должны добавлять отступы в конце сообщений - на всякий случай. За счет этого теряется до 7 байтов (не на запись, всего), но мы также можем сохранить 3 значения типа bool в виде битового массива всего в 1 байт и выиграть 2 байта или фактически floor(n — (n / 8))bytes для каждой записи типа bool.

Вы можете задаться вопросом, почему нам не нужно заботиться о выравнивании памяти при объединении строк. Я предполагаю, что мы храним строки в кодировке UTF8, что означает, что текст в основном представляет собой массив 1-байтовых символов. При загрузке строки UTF8 в память (класс / структура String) мы загружаем данные побайтно и помещаем их в отдельный буфер. Загрузка одного байта не вызывает никаких проблем.

Мы видим, что хранение данных в виде столбцов может дать преимущества в отношении упаковки байтов . Однако это не так. Мы получаем такие же преимущества в отношении поиска, как описано в разделе CSV. Мы можем пойти еще дальше. Метка времени в двоичном формате описывается как uint размером 8 байтов. Если у нас есть данные фиксированного размера, и мы знаем, где они начинаются и сколько записей у нас есть, довольно легко реализовать произвольный доступ: start + (size * index). В случае истории чата значения отметок времени сортируются по возрастанию. Если у нас есть отсортированный массив, мы можем найти значения или даже диапазоны с помощью двоичного поиска. Это означает, что будет очень эффективно найти сообщения, отправленные в определенный период времени.

Итак, вы говорите, что представление данных с ориентацией на столбцы - идеальное решение?

Ну нет! 🙃

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

В случае CSV (и других текстовых форматов) это довольно плохо. И я говорю о чистых данных CSV, не встраивая их в какую-то промежуточную структуру данных. Текстовый формат не поддерживает доступ к произвольным значениям, нам потребуется выполнить сканирование, чтобы определить, какое значение в столбце принадлежит «третьей» строке.

Бинарные форматы, такие как FlexBuffers и ByteCabinet (формат, над которым я сейчас работаю), могут поддерживать произвольный доступ к значениям. В этом случае получение данных из нескольких столбцов будет разумным, но не так быстро, как с данными, которые упакованы вместе. Если вас интересует, почему, посмотрите статью Местонахождение ссылки.

Итак, вы говорите, что я не должен использовать столбцовое представление данных для пользовательского интерфейса?

Ну нет! 🙃🙃

Вам нужно подумать о своем варианте использования. Если у вас есть представление данных, ориентированное на столбцы, которое поддерживает произвольный доступ, и у вас есть список, который показывает пользователю несколько десятков строк. Это не проблема. Вы можете просмотреть столбцы X (количество свойств) и прочитать записи Y (количество строк). Вам придется прыгать в памяти и, вероятно, сгенерировать промахи кеша, но вы сделаете это только для пары десятков записей, и UX не пострадает. Однако, если вам нужно обеспечить поиск пользователя, вам нужно будет просмотреть все свои данные, и у вас будут тысячи или даже миллионы записей. Более того, загрузка ненужных данных и промах кэша ЦП могут быть весьма заметны с точки зрения UX.

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