Cartography

Cartography -- распределенная система для обработки и хранения данных в парадигме MapReduce.

Запуск мастера:

./cartography master <work_dir>

Запуск ноды:

./cartography node <node_name> <master_host> <work_dir>

Implementation details

Данные и метаданные

Формат метаданных - json-документ:

{
    "name": "directory1/my_table",
    "records_count": 1024,
    "size": 172742,
    "sorted": false,

    // master only items
    "nodes": [ "gemini-1" ]
}

Формат таблицы - текстовый файл Строки - записи таблицы (json-документы)

• Мастер:

Директория METADATA, где хранятся общие метаданные:

METADATA/directory1/my_table.meta
METADATA/directory2/directory3/my_table2.meta

• Нода:

Директория METADATA, где хранятся метаданные для частей таблиц:

METADATA/directory1/my_table.meta
METADATA/directory2/directory3/my_table2.meta

Директория DATA, где хранятся сами части таблиц:

DATA/directory1/my_table
DATA/directory2/directory3/my_table2

Операция MAP:

На каждой ноде, где хранится часть таблицы, запускается маппер и результаты складываются прямо по месту. В итоге, степень распределенности выходной таблицы == степени распределенности старой таблицы.

Операция SORT:

С каждой ноды берется случайная выборка (1% от имеющихся записей), все вместе сортируется, берется n-1 медиан (где n - количество доступных нод). По полученным медианам составляется таблица:

ключ | -inf < k <= e1 | e1 < k <= e2 | ... | en-1 < k <= +inf |
нода |        1       |      2       | ... |        n         |

На каждой ноде запускается процесс, который, используя таблицу, распределяет имеющиеся у него данные по нодам (во временную таблицу). После данные на каждой локально сортируются. В итоге имеем сортированную таблицу.

Список нод в "nodes" теперь имеет значение: это будут ноды 1 .. n из таблицы.