[О блоге] [наверх] [пред] [2022-08-08 22:40:58+03:00] [adca349bb86d9ed357051d2452c1a4f9dff24f7c]

Улучшил glocate

В 8e24a68248865cfcd58538871f8b96e6327376d8 я написал glocate. Всё же
жутко напрягает что он жрёт уйму памяти, поэтому повозился над
оптимизацией. Отняло прилично времени, похоже из-за недостатка знаний по
структурам и алгоритмам. Сложности с применением zfs diff-а, который
как-то оттестирован, но наверняка есть крайние случаи и косяки.

Чтобы не есть память, то использую временные файлы. Во время создания
индекса в него пишется прямо на лету почти вся информация о файлах и
директориях. И в памяти запоминаются вычисленные итоговые размеры
директорий (можно и в ещё один временный файл переложить, но и так не
много жрёт (64-бит для каждой директории)). Далее всё это копируется в
ещё один временный файл, на лету заменяя для директорий размеры
сохранённые в памяти.

Это работает вполне себе без проблем и годно. В файле хранится 16-бит
длина имени, имя, 8-бит глубина, 64-бит mtime и размер. Плюс Zstandard
над всем этим, ибо всё равно всё только в потоковом режиме читается и
пишется.

А для применения zfs diff куча кода. По сути я просто создаю
отсортированные списки из файлов для удаления, для добавления и для
изменения. Для каждого добавляемого файла есть запись в списке для
изменения. Записи из БД потоково читаются и смотрится нет ли записи в
списке для удаления. Если есть, то она в новую БД (очередной временный
файл) не попадает. Если есть запись в списке для добавления, и она при
сортировке должна пойти перед прочитанным элементом из БД, то она
вставляется в поток записей. Из списка для изменения берутся данные о
размере и mtime. Если прочитанная запись имеется в списке для изменения,
то у неё обновляется размер и mtime. Так как все списки отсортированы,
то никаких map-ов не используется и смотрятся только верхушки списков.

То есть, имеется поток записей, в котором на лету или удаляются или
изменяются или внедряются новые записи. Всё это идёт во временный файл.
При этом параллельно всё проходит через параллельно работающую горутину
вычисления размеров директорий, такую же как и при создании индекса. И
снова в конце идёт копирование из одного временного в другой, обновляя
размеры директорий.

Дополнительная сложность с переименованием директорий: zfs diff
показывает ровно одну запись, честно. А мне ведь надо всю иерархию, все
элементы изменить. Если есть переименование директорий, то я отдельно
потоково читаю БД, ищу какие файлы надо во что переименовать, и
для каждого элемента создаю отдельную запись в списках удаления,
добавления и изменения.

Таким образом, если есть переименование директорий, то "копирование" БД
(чтение из неё и запись во временный файл) идёт первый раз для узнавания
всей иерархии директорий, второй раз для создания полной БД со всеми
записями, третий раз для актуализации всех размеров директорий. Но
отличное переиспользование кода при этом.

Все эти потоки записей идут через штатные каналы Go, обрабатываются в
горутинах и отлично распараллеливаются. Отдельная горутина для чтеца,
для писателя, для считателя размеров директорий, для модификатора потока
записей. Плюс zstd имеет свои горутины. Я в top-е видел использование
2-3-х ядер без проблем.

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

Поиска как такового нет, кроме как возможности указания части иерархии
для вывода, для последующего grep/whatever. И при этом он просто
потоково читает все записи из БД. Но работает вполне себе шустро:
считанные секунды чтобы выдать результаты (для полугигабайтной БД).

Смотрю на формат БД GNU findutils-ов:
https://www.gnu.org/software/findutils/manual/html_node/find_html/LOCATE02-Database-Format.html
и вижу что у них тоже никакой магии для поиска нету: просто компактный
формат, где объединяется общий префикс. Так как я явно храню знания о
директориях отдельно, чтобы у директории был свой mtime/size, то у меня
аналогично бы вышел вырожденный LOCATE02 формат БД, только вместо общей
длины у меня указывается глубина, вероятность переполнения которой
существенно меньше чем длина текстового префикса. Приятно что оказался
на аналогичном пути.

    [оставить комментарий]