Механизм распределённого индексированного хранения кеша

[svp]

Если есть на форуме заинтересованные в сабже пргограммисты, прошу принять участие в мозговом штурме проблемы.

1. Необходимо реализовать механизм индексации кеша, позволяющий быстро (желательно без обращений к файловой системе) определять есть ли в кеше тот или иной тайл.
Вариант реализации:

- Индексная структура должна представлять собой набор вложенных списков прямоугольников и относиться к кешу определённого уровня Z=1..24.
- Координаты прямоугольников соответствуют номерам тайлов.
- Прямоугольники могут быть негативными, позитивными, либо бинарными.

* Тайл с координатами, принадлежащими негативному прямоугольнику и не принадлежащими его дочерним прямоугольникам, считается отсутствующим в кеше.
* Тайл с координатами, принадлежащими позитивному прямоугольнику и не принадлежащими его дочерним прямоугольникам, считается присутствующим в кеше.
* Бинарный прямоугольник содержит (Width * Height) бит данных, где каждый бит определяет наличие или отсутствие соответствующего ему тайла в кеше.
- Прямоугольник верхнего (нулевого) уровня всегда имеет координаты (0, 0)-(2^(z-1)-1, 2^(z-1)-1) и является негативным.
- Любой небинарный прямоугольник четного уровня вложенности -- негативный.
- Любой небинарный прямоугольник нечетного уровня вложенности -- позитивный.

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

Остаётся реализовать алгоритмы добавления тайла, удаления тайла, быстрого слияния и вычитания индексных структур, оптимизации индексной структуры.

Следить за целостностью индексаного файла можно несколькими способами:

- посредством программы, закачивающей тайлы в кеш;
- посредством обработки события от файловой системы на добавление\удаление файла;
- можно формировать индекс заново.

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

3. Такой механизм индексирования позволит также определять для каждого кеша маску, по которой в него будут сохранятся тайлы. То есть можно завести несколько кешей (общий, Город1, Город2, город3 и т.д.) и в каждый кеш тайл будет сохраняться только в случае соответствия маске данного кеша. Таким образом можно легко делиться кешами тайлов отдельных городов. При этом сами маски будут занимать буквально несколько десятков байт и определение принадлежности им тайла будет происходить мгновенно (простая проверка принадлежности точки списку прямоугольников).

4. Карта покрытия региона тайлами i-го уровня будет строиться так же быстро. Достаточно обойти в ширину всё индексное дерево и отобразить позитивно или негативно все прямоугольники.

У кого есть какие соображения относительно алгоритмов добавления и оптимизации?

[mega-art]

Жаль сам не программист... Все описанное выше просто необходимость. Пункты 3 и 4 двойная необходисмость. Так же надо заложить возможность обмена (не только выгрузки, но и загрузки) выделениями (областями) ввиде одного файла, а не структурированного кэша.

[svp]

ввиде одного файла, а не структурированного кэша.

В readme SAS.План ете уже приводили способ хранения кеша в одном файле с помощью TrueCrypt. Если учесть, что утилита отлично поддерживает командную строку, то на первое время такого решения для объединения кеша в один файл, ИМХО, вполне достаточно. Копирование происходит на порядок быстрее.
Вот командная строка быстрого монтированиякеша:

Код: Выделить всё

D:\Utils\TrueCrypt\TrueCrypt.exe /v /q /p 123 /lz T:\Maps\SAS_Cache.tc

Демонтирование:

Код: Выделить всё

D:\Utils\TrueCrypt\TrueCrypt.exe /q /dz

Здесь ключи /lz и /dz означают, что кеш будет смонтирован/демонтирован как диск Z:
/p 123 -- это пароль к файлу раздела. В моём случае он равен просто 123. Смысла в нём нет никакого, но в данном случае пустой пароль не пропускает прога. Рекомендую всем ставить пароль 123, как международно-межконфессиональный=)
T:\Maps\SAS_Cache.tc -- это у меня путь к файлу с кешем.
А здесь D:\Utils\TrueCrypt\TrueCrypt.exe лежит сам TrueCrypt. Он, кстати, не нуждается в установке. Его можно просто скопировать и он будет работать.
При всём выше сказанном путь у кешу в SAS.Планете у меня прописан такой: Z:\SAS_Cache\

Существенный недостаток такого метода хранения кеша в том, что размер кеша надо выделять заранее и даже, если примонтированный раздел пуст, файл его будет занимать выделенный объём и не будет сжиматься архиваторами из-за того, что имеет шумоподобное содержание.
С учетом всего этого у SAS.Планеты есть, ИМХО, пока что более вжные и насущные проблемы, чем хранение кеша в одном файле.

[vgrigor]

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

Хранение можно также также не слишком избыточное, но с избыточностью (заполнение 80%), т.к. это обеспечивает максимальную скорость, согласно практике индексов БД:
файл со своим форматом, куда все пишется или читается посекторно - по 64 кб, кратно квадратам-
вначале лежит хэш больших квадратов, со смещениям его блока вложенных, и.т.д.

Когда индекс заполнится, можно предложить оптимизировать кэш.

[YashpeR]

и всё таки двигаемся к проблеме хранения КЭШа
о чём я и писАл 3 мес назад...
нужен КЭШ - ES 1.95 ... там и индексация предусмотрена была...
и насчёт обмена/объединения/разделения КЭШей всё продумано...
другого врядли выдумаем... к тому КЭШу группа людей приходила почти 1,5 года (!)

www.toall.ru
проект скоро закрою - нет время.
смотрим, читаем...

[zed]

берется большой квадрат, в котором 32 на 32 средних, в каждом в котором 32 на 32 элементарных

А может, будет удобнее сделать как в гугле: каждый квадрат содержит 4 (2x2) дочерних, которые в свою очередь - то же 2х2 дочерних и т.д. до, например, 10 уровней вглубь. Тогда один индексный файл будет описывать ~ 350 000 файлов (максимум). И если структуру индекса сделать примерно как у гугла (dbCache.dat.index), т.е. один квадрат описывать 32-мя байтами, то максимальный размер одного индексного файла будет ~ 10.5 Мб.

В общем, предлагается такая схема:
- несколько индексных файлов, находящихся на строго определённых уровнях зума (а точнее на трёх: 1,11,21);
- имя каждого индексного файла однозначно определяет координаты и уровни зума файлов, которые он описывает (т.е. например, индекс с именем t будет описывать всю Землю с 1 до 10 уровень включительно);
- сами индексные файлы создаются только при наличии картинок в кэше для данной области/уровней зума;
- в индексах не храниться избыточной информации о файлах, отсутствующих в кэше.

Да, мы опять получаем россыпь уже индексных файлов, и порой, эти файлы будут мелкими (несколько килобайт) - из-за слабого заполнения картинками кэша. Но этих файлов будет на несколько порядков меньше, чем было картинок, тем более, что нет нужды таскать за собой индексные файлы - их вполне можно будет получить переиндексировав основной кэш.
А для гурманов, можно сделать опцию: "Один кэш - один индекс" (в ущерб быстродействия поиска), и тогда, если кэш ~ 10 ГБ, то индекс будет ~ 35 МБ.

наличие кодируется простыми битами, чтобы наличие тайла определялось простой битовой операцией "И" а не вычислениями,
их нумерация тоже, поэтому скорость вычислительной обработки будет большой

Тут не очень понятно, как закодировать наличие? Можно пример?

вначале лежит хэш больших квадратов, со смещениям его блока вложенных, и.т.д.

т.е. предполагается упорядоченная структура индекса? Это, по-моему не удобно, проще будет, если описания блоков будут идти "вразнабой", в порядке попадания файлов в кэш. Тогда, чтоб найти описание какого-то блока, нужно будет просканировать "перебором" весь индекс, это конечно, медленнее, но если сканирование выполнять только при уверенности наличия описания блока, и если учесть, что заполнение индекса скорее всего не будет превышать 50-70% - не всё так страшно (предполагается, что наличие описания блока, будет закодировано в шапке индексного файла).