Распределённая система хранения метаданных23.04.2018 15:36

Назовём её DMSS (Distributed Metadata Storage System). Ну и картинка конечно — куда ж без этого:

Последние успехи в борьбе с интернетом (в странах с авторитарными режимами) и с распространением информации (руками правоторговцев в странах с режимами покультурнее) наверно многих наводят на мысль, что нужен способ децентрализованно хранить метаданные одного типа. Примеры таких каталогов с метаданными:

Либрусек. Порядка 300–400 тыс. книг.
Архив. Порядка 1.5 млн. статей.
Скихаб. Порядка 65 млн. статей.
Флибуста. Порядка 400 тыс. книг.
PirateBay. Никак не могу найти сколько там всего торрентов. Как будто скрывают. Видел только, что сжатый дамп с magnet ссылками весит 100 МБ. Но учитывая, что magnet ссылка это по сути SHA-1 (20 байт) и такие хеши несжимаемы, то выходит, что всего там 100 МБ / 20 байт = 5 млн ссылок.
IMDB. Порядка 500 тыс. фильмов.
Spotify. Порядка 30 млн. файлов.

Сами файлы (книги, статьи, аудио, видео) хранить в этой системе не надо: торренты с сид-боксами и VPN и так хорошо справляются с этой задачей. Каталог подобных сайтов хотя никаких разумных законов не нарушает (PirateBay например это просто список SHA-1 хешей — самих файлов там нет), будет так или иначе заблокирован силами правоторговцев даже в странах первого мира. Просто потому что такой каталог больно наступает им на яй доходы.

Прежде всего никто, даже разработчики этой системы, не должны иметь возможности разводить там цензуру. Даже если им предложат вагон золотых слитков и паяльник кипятильник на выбор. Никаких суперадминов.
Возможность добавить каталог. Допустим он будет идентифицироваться своим SHA-1. У нового каталога возможно будут даже модераторы которые смогут разводить цензуру и самоуправство, но во первых будет возможность создавать каталоги без модераторов (то есть даже создатель каталога будет лишь обычным юзером), а во вторых всегда можно будет создать новый каталог и переманить аудиторию, если старые модераторы надоели (идея взята с д3).
Возможность найти каталог по его SHA-1. Метаданные (имя каталога например или его описание) там хранить не обязательно, потому что всегда можно завести каталог каталогов.
Возможность подписаться на каталог. В этом случае участник выделяет немного места для хранения части этого каталога. Какой именно части участник знать не будет. Таким образом участник будет знать, что он хранит часть, скажем статей по химии, но никаким боком не связан с фотографиями котиков или чем то подобным.
Возможность отписаться от каталога. Значит фрагменты данных каталога должны быть промаркированы.
Возможность добавить новую запись в каталог. Запись по сути будет списком пар ключ-значение и всё вместе вполне может помещаться в 4 КБ. Одним из полей записи может быть magnet ссылка на файл или например ссылка на запись в каталоге комментариев. Максимальный размер записи и её тип будет в свойствах каталога (кажется придётся хранить метаданные каталога в нём самом). Тип записи это довольно общая штука которая вполне может проверятся самописным скриптом: идея в том, чтобы в каталоге с книгами не допускать гигабайтные файлы с байтами явно не из ASCII таблицы. Если в каталоге есть модераторы, то у них должна быть возможность одобрить или отклонить запись. Возможно нужно что то вроде ACL в NTFS.
Возможности удалить запись вроде бы быть не должно, но что если есть модераторы? Думаю, что не будет ничего плохого в том, чтобы разрешить удаление. Если не хочется, чтобы кто то всё удалил, то нужно не создавать модераторов с правом удаления.
Редактирование мне кажется тоже лишь усложнит систему не дав ничего взамен. Даже комментарии к записи (которые могут хранится в отдельном каталоге где каждый комментарий это обычная запись) редактировать смысла нет. Мы ведь когда email-ы посылаем не жалуемся, что возможности отредактировать их нет?
Поиск. Хотя бы нужно уметь находить все записи с заданной подстрокой или лучше с подстрокой с пропусками (как например сделан поиск файлов в гитхабе). Результат должен быть отсортирован хотя бы по времени. Сложность здесь в том, что мало кто будет хранить полную копию каталога и чтобы что-то найти надо будет фактически сделать поиск в ширину. Как-то не очень эффективно выглядит.

Вроде бы всё?

Связность графа peer-to-peer сети. Эту проблему кажется решил телеграм своими push notifications (надо бы почитать про это). Это проблема исключительно авторитарных стран. В странах где сильны правоторговцы проблем с скачиваением метаданных не будет, а проблема скачивания файлов решается торрентами и сид боксами оплаченными биткоинами (на самом деле можно просто торрентами — посмотрите карту юзеров piratebay), но если уж параноить, то сид бокс сделать не сложно.
Флуд. Когда связность сети нарушить не получится, в дело пойдёт флуд. Враг будет загружать много легитимно выглядящих записей. Идея в том, чтобы в каталоге было 99% хлама и пользоваться им было нельзя. Как эту проблему решить я ещё не придумал. Возможно увеличивать задержку после каждой отклонённой записи (если есть модераторы).

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

Некоторые ноды вполне могут быть чем-то вроде сид-боксов в Эквадоре и они могут хранить почти весь каталог. По этой причине хотелось бы придумать как скрестить такую систему с биткоинами, чтобы мотивировать людей создавать такие сид-боксы. Может быть можно добавить в протокол возможность брать плату за скачивание. Минус: система может оказаться в ситуации когда без биткоинов скачать вообще ничего будет нельзя — 99% юзеров отвалятся сразу. С другой стороны одна нода может скачать мегабайт по цене X, а потом невозбранно раздавать её же по цене X/2 и в итоге цены упадут до цен на трафик в Эквадоре.

Добавление записи

Хочется, чтобы каждая запись была разбита на нечитабельные фрагменты раскиданные по случайным местам. Можно попробовать сделать так:

Запись как правило будет небольшая: меньше мегабайта. Вычислим её хеш (например SHA-1) и зашифруем (например AES-CBC) этим хешем всю запись.
Зашифрованную запись разобьём на маленькие блоки B[1], B[2], …, B[N]. Идея в том, что каждый из блоков окажется на нескольких случайных нодах. У каждого блока есть его идентификатор — это его хеш.
У клиента есть список соседей — IP адреса клиентов которые он каким-то образом получил. Через те же push notifications или другими способами. Каждый из блоков B[i] рассылаем на несколько случайно выбранных соседей. Теперь каждому блоку соответствует список IP адресов где есть этот блок.
Строим что-то вроде дерева на основе этих блоков. Для простоты будем строить бинарное дерево. Диапазон B[1..N] разобьём на B[1..N/2] и B[N/2+1..N] и два этих диапазона назовём фрагментами F[1] и F[2]. У каждого фрагмента есть идентификатор — это его хеш. Затем разобём эти фрагменты пополам и так далее. В итоге у нас получится, что есть фрагменты нижнего уровня, которые представляют из себя несколько рядом стоящих блоков, например F[23] = B[4..7]. Есть фрагменты котрые объединяют другие фрагменты, например F[8] = F[23..26]. И так далее до самого верхнего фрагмента F[0] который представляет собой всю запись. По сути мы получили список фрагментов F[1..M] где каждый фрагмент имеет id (некий хеш) и представляет из себя список фрагментов из которых он состоит и при определённой нумерации этот список будет без пропусков: F[i] = F[j..k].
Каждый фрагмент F[i] рассылаем нескольким случайно выбранным соседям. Содержимое посылки будет по сути хешем фрагмента F[i] и списком хешей фрагментов из которых он состоит. В дополнение к этому к каждому хешу фрагмента мы отправим список адресов где он есть (чтобы потом было понятно где их искать). Пример «посылки» будет выглядеть как-то так:

POST /fragments
X-Catalogue: 2bc..332
X-Fragment: 3bc..5ee

23e..443 (11.21.32.44, 23.2.3.1, 44.3.4.5)
e3e..55f (3.3.4.2, 2.11.32.123)
22e..44b (1.2.3.4)

Кстати, предварительно всю запись можно пропустить через т.н. Burrows Wheeler Transform (делается за линейное время), чтобы одинаковые символы в среднем оказывались рядом — тогда будет больше одинаковых блоков и разные записи смогут использовать одни и те же блоки.

Допустим, что какие то из соседей — вражеские серверы которые ловят распространителей «запрещённой» информации. Все эти запросы нельзя проверить на содержание чего бы то ни было. Можно например сначала отправлять фрагменты с адресами, а потом отправлять блоки. Блоки по отдельности расшифровать нельзя (AES-CBC не позволяет расшифровать произвольный кусок в середине). Единственный способ узнать, что находится в записи это взять верхний фрагмент F[0](надо ещё как то догадаться, что это верхний фрагмент), собрать всё это дерево и расшифровать всю запись (хеш её известен).

Если в каталоге есть модераторы, то надо как-то придумать, чтобы сначала запись шла им, они ставили подпись (не ручкой конечно), и дальше все запросы шли с заголовком вроде X-Signature, чтобы ноды могли проверить валидность подписи.

Получение записи по её хешу

Хеш записи это верхний фрагмент F[0]. Нам надо восстановить дерево:

Спрашиваем некоторых соседей есть ли у них такой хеш. Если его нет, то повторяем запрос, но уже с заголовком X-SearchDepth: 2 чтобы они спросили своих соседей (возможно не всех). И так далее пока не найдём или не надоест искать. Если в процессе хеш нашёлся, то нода которая нашла хеш может его закешировать и возможно удалить старые записи — место на диске не резиновое. Ответом будет список хешей фрагментов и адреса где они хранятся (по сути тот POST выше, только в виде ответа 200).
Для каждого фрагмента мы получили список адресов где он лежит. Случайным образом выбираем по одному адресу и идём туда. Повторяем этот процесс пока не построим всё дерево и не дойдём до хешей блоков B[1..N].
Скачиваем все блоки. Собираем их в кучу. Расшифровываем.

Здесь надо напомнить, что скачали мы всего лишь метаданные фильма (например), а не сам фильм. Даже в авторитарных странах это ещё не преступление. Но даже если кому-то очень захочется поймать скачивателя метаданных конкретного фильма, то и это будет непросто: скачивание например списка F[0] это ведь не вся запись, а просто её описание. Придётся сделать так, чтобы клиент был окружён вражескими серверами которые могли скоординированно раздать все фрагменты и блоки и с достаточной уверенностью сказать, что этот клиент скачал содержимое всей записи.

Поиск

Здесь каких то интересный идей у меня ещё нет. Ну кроме разве что опроса соседей с строкой поиска, те опрашивают своих соседей и так далее.

Хотелось бы, чтобы поиск выглядел как перемещение по дереву поиска или дереву суффиксов (этакое распределённое дерево поиска), плюс дерево это как-то само обновляется и т.д. При этом без чрезмерного усложения протокола.

Статья должна была получится маленькая, потому что идея очень простая, но как это обычно бывает — описание даже простой идеи раздувается до небольшого RFC. Интересно узнать, что думает публика и не придумываю ли я велосипед (судя по тому, что даже безобидный каталог книг — либрусек — был захвачен, велосипеда таки нет). Если в этой идее есть смысл, то дальше надо сделать репозиторий на гитхабе и продумать все детали.