Интересная вещь об этой проблеме — то, что я был очень осторожен в том, как я сформулировал вещи. Я сказал, что хочу, но не уточнил, что нужно сделать. Это было довольно намеренно. В этом отношении тот факт, что я публикую информацию о том, что будет нашим критерием принятия, также является намеренным. Идея состоит в том, чтобы иметь нетривиальную задачу, но что-то, что должно быть очень хорошо понято и легко исследовано. Это также означает, что кандидат должен быть в состоянии написать некоторый нетривиальный код. И я могу многое рассказать о разработчике из такого проекта. В то же время, это очень самостоятельный сценарий. Идея в том, что это то, что вы можете сделать за короткое время.
Причина того, что это интересное упражнение, состоит в том, что это, по крайней мере, две совершенно разные, но связанные проблемы. Во-первых, в файле размером 15 ТБ мы, очевидно, не можем полагаться только на сканирование всего файла. Это означает, что у нас должен быть индекс. А это значит, что мы должны его построить. Интересно, что индекс является отсортированной структурой, что означает, что нам нужно решить проблему сортировки большего количества данных, чем может поместиться в основной памяти.
Вторая проблема, вероятно, проще, поскольку это просто реализация внешней сортировки, и существует множество алгоритмов для ее решения. Обратите внимание, что я не очень заинтересован в реальной эффективности для этого конкретного сценария. Я забочусь о возможности увидеть код. См., Что это работает, и т. Д. Мое решение, например, является однопоточной системой, которая не пытается параллелизма или оптимизации ввода / вывода. Он работает со скоростью более 1 ГБ / мин, а потребление памяти составляет менее 150 МБ. Запросы на уникальное значение возвращают результат в 0,0004 секунды. Запросы, которые дали 153 тыс. Результатов, были выполнены за 2 секунды
При увеличении используемой памяти до 650 МБ, на самом деле нет разницы в производительности, что меня немного удивило.
С другой стороны, весь код, вероятно, крайне неэффективен. Но этого пока достаточно.
Процесс начинается с индексации:
1: var options = new DirectoryExternalStorageOptions("/path/to/index/files");
2: var input = File.OpenRead(@"/path/to/data/Crimes_-_2001_to_present.csv");
3: var sorter = new ExternalSorter(input, options, new int[]
4: {
5: 1,// case number
6: 4, // ICHR
7:
8: });
9:
10: sorter.Sort();
Я на самом деле использую данные о преступности в Чикаго. Это файл объемом 1 ГБ, который я скачал с городского портала Чикаго в формате CSV. Вот как выглядят данные:
ExternalSorter прочитает и проанализирует файл, и начнет читать его в буфер. Когда он достигает определенного размера (обычно около 64 МБ исходных данных), он сортирует значения в памяти и выводит их во временные файлы.
Эти файлы выглядят так:
Первоначально я пытался сделать это с двоичными данными, но оказалось, что это было слишком сложно, чтобы быть легким, и написание этого в удобочитаемом формате облегчало работу с ним. Формат довольно прост, у вас есть значение слева, а справа у вас есть начальная позиция строки для этого значения.
Мы генерируем около 17 таких временных файлов для файла объемом 1 ГБ. Один временный файл на каждые 64 МБ исходного файла. Это позволяет нам поддерживать фактическое потребление памяти на очень низком уровне, но для больших наборов данных мы, вероятно, захотим выполнять сортировку каждые 1 ГБ или даже больше. Наш тестовый компьютер имеет 16 ГБ оперативной памяти, поэтому выполнение сортировки и вывод временного файла каждые 8 ГБ может быть хорошим способом решения проблем. Но это не относится к делу.
Конечным результатом является то, что у нас есть несколько отсортированных файлов, но они не последовательные. Другими словами, в файле # 1 у нас есть значения 1,4,6,8, а в файле # 2 у нас есть 1,2,6,7. Нам нужно объединить их всех вместе. К счастью, это достаточно легко сделать. У нас в основном есть куча, в которую мы вводим записи из файлов. И это в значительной степени заботится об этом. Смотрите сортировку слиянием, если вы хотите узнать больше об этом.
Конечным результатом объединения всех этих файлов является … другой файл, такой же, как они, который содержит все отсортированные данные. Затем пришло время заняться другой проблемой — поиском данных.
Мы можем сделать это с помощью простого бинарного поиска, с оговоркой, что, поскольку это текстовый файл и нет записей или страниц фиксированного размера, на самом деле очень трудно понять, с чего начать чтение.
По сути, я выбираю произвольную позицию байта, затем иду назад, пока не найду ‘\ n’. Как только я нашел символ новой строки, я могу прочитать всю строку, проверить значение и решить, где мне нужно искать дальше. Предполагая, что я действительно нашел свое значение, теперь я могу перейти к байтовой позиции значения в исходном файле и прочитать исходную строку, передав ее пользователю.
Если предположить, что скорость индексации 1 ГБ / мин, для файла 15 ТБ на индексацию потребуется около 10 дней. Но есть и способы обойти это, но я коснусь их в моем следующем посте.
Все это привело к тому, что нам не нужно беспокоиться о таких вещах. Но я считаю, что это исследование хорошо проведено, и мы будем использовать его в будущем.