ПРИМЕЧАНИЕ: Далее приводится обсуждение истории реализации netDb и не является актуальной информацией. См. основную страницу netDb для актуальной документации.
История
netDb распространяется с помощью простой техники под названием “floodfill”. Давно netDb также использовала Kademlia DHT в качестве резервного алгоритма. Однако она плохо работала в нашем приложении и была полностью отключена в версии 0.6.1.20.
(Адаптировано из поста jrandom в старом Syndie, 26 ноября 2005 г.)
Floodfill netDb — это действительно простая и, возможно, временная мера, использующая максимально простой алгоритм — отправить данные peer’у в floodfill netDb, подождать 10 секунд, выбрать случайного peer’а в netDb и попросить его о записи, которую нужно отправить, проверяя её правильную вставку/распространение. Если проверяющий peer не отвечает или у него нет записи, отправитель повторяет процесс. Когда peer в floodfill netDb получает netDb store от peer’а, который не находится в floodfill netDb, он отправляет её всем peer’ам в floodfill netDb.
В какой-то момент функциональность поиска/хранения Kademlia всё ещё была на месте. Узлы считали floodfill узлы всегда «ближе» к любому ключу, чем любой узел, не участвующий в netDb. Мы возвращались к Kademlia netDb, если floodfill узлы по какой-либо причине не работали. Однако затем Kademlia была полностью отключена (см. ниже).
Позднее Kademlia была частично возвращена в конце 2009 года как способ ограничить размер netDb, который должен хранить каждый floodfill router.
Введение алгоритма Floodfill
Floodfill был введён в релизе 0.6.0.4, оставив Kademlia в качестве резервного алгоритма.
(Адаптировано из постов jrandom в старом Syndie, 26 ноября 2005 г.)
Как я часто говорил, я не особенно привязан к какой-либо конкретной технологии - для меня важно то, что даст результат. Пока я работал над различными идеями netDb в течение последних нескольких лет, проблемы, с которыми мы столкнулись в последние несколько недель, обострили некоторые из них. В живой сети, с коэффициентом избыточности netDb установленным в 4 узла (что означает, что мы продолжаем отправлять запись новым узлам, пока 4 из них не подтвердят, что они её получили) и таймаутом на узел, установленным в 4 раза больше среднего времени ответа этого узла, мы всё ещё получаем в среднем 40-60 узлов, которым отправляем, прежде чем 4 подтвердят сохранение. Это означает отправку в 36-56 раз больше сообщений, чем должно отправляться, каждое из которых использует туннели и тем самым пересекает 2-4 соединения. Более того, это значение сильно искажено, поскольку среднее количество узлов, которым отправлялось в “неудачном” сохранении (означающем, что менее 4 человек подтвердили сообщение после 60 секунд отправки сообщений), было в диапазоне 130-160 узлов.
Это безумие, особенно для сети всего лишь с примерно 250 узлами.
Самый простой ответ - сказать “ну, очевидно же, jrandom, это сломано. почини это”, но это не совсем добирается до сути проблемы. В соответствии с другим текущим усилием, вероятно, у нас есть значительное количество сетевых проблем из-за ограниченных маршрутов - узлов, которые не могут общаться с некоторыми другими узлами, часто из-за проблем с NAT или firewall. Если, скажем, K узлов, ближайших к определенной записи netDb, находятся за “ограниченным маршрутом” таким образом, что сообщение netDb store может достичь их, но сообщение netDb lookup от какого-то другого узла не может, эта запись будет по сути недоступной. Продолжая эту линию рассуждений немного дальше и принимая во внимание тот факт, что некоторые ограниченные маршруты будут создаваться с враждебными намерениями, ясно, что нам придется более внимательно изучить долгосрочное решение для netDb.
Существует несколько альтернатив, но две из них заслуживают особого упоминания. Первая заключается в том, чтобы просто запустить netDb как Kademlia DHT, используя подмножество полной сети, где все эти узлы доступны извне. Узлы, которые не участвуют в netDb, по-прежнему запрашивают эти узлы, но не получают незапрошенные сообщения хранения или поиска netDb. Участие в netDb было бы как самостоятельным выбором, так и исключением пользователем - router’ы выбирали бы, публиковать ли флаг в своем routerInfo, указывающий, хотят ли они участвовать, в то время как каждый router выбирает, какие узлы он хочет рассматривать как часть netDb (узлы, которые публикуют этот флаг, но никогда не предоставляют полезных данных, игнорировались бы, фактически исключая их из netDb).
Другой альтернативой является возврат к прошлому, к менталитету DTSTTCPW (Do The Simplest Thing That Could Possibly Work) - floodfill netDb, но, как и в альтернативе выше, использующий только подмножество полной сети. Когда пользователь хочет опубликовать запись в floodfill netDb, он просто отправляет её одному из участвующих router-ов, ждёт ACK, а затем через 30 секунд запрашивает другого случайного участника в floodfill netDb для проверки правильности распределения. Если всё в порядке - отлично, а если нет - просто повторяет процесс. Когда floodfill router получает netDb store, он немедленно отправляет ACK и ставит в очередь netDb store для всех своих известных netDb peer-ов. Когда floodfill router получает netDb lookup, если у него есть данные, он отвечает ими, но если их нет, он отвечает хешами, скажем, 20 других peer-ов в floodfill netDb.
Рассматривая это с точки зрения сетевой экономики, floodfill netDb весьма похожа на оригинальную широковещательную netDb, за исключением того, что стоимость публикации записи в основном несут узлы в netDb, а не издатель. Развивая эту мысль дальше и рассматривая netDb как чёрный ящик, мы можем увидеть, что общая пропускная способность, требуемая netDb, составляет:
recvKBps = N * (L + 1) * (1 + F) * (1 + R) * S / T
где:
N = number of routers in the entire network
L = average number of client destinations on each router
(+1 for the routerInfo)
F = tunnel failure percentage
R = tunnel rebuild period, as a fraction of the tunnel lifetime
S = average netDb entry size
T = tunnel lifetime
Подставляя несколько значений:
recvKBps = 1000 * (5 + 1) * (1 + 0.05) * (1 + 0.2) * 2KB / 10m
= 25.2KBps
Это, в свою очередь, масштабируется линейно с N (при 100 000 узлов netDb должна быть способна обрабатывать сообщения netDb store общим объемом 2,5 МБ/с, или при 300 узлах — 7,6 КБ/с).
Хотя floodfill netDb предполагает, что каждый участник netDb получает напрямую только небольшую часть netDb записей, генерируемых клиентами, в конечном итоге они все получат все записи, поэтому все их каналы связи должны быть способны обрабатывать полный recvKBps. В свою очередь, им всем потребуется отправлять (recvKBps/sizeof(netDb)) * (sizeof(netDb)-1) для поддержания синхронизации с другими узлами.
Floodfill netDb не потребует ни маршрутизации туннелей для работы netDb, ни какого-либо специального выбора того, на какие записи можно “безопасно” отвечать, поскольку базовое предположение заключается в том, что все они хранят всё. И что касается требуемого использования дискового пространства netDb, это всё ещё довольно незначительно для любой современной машины, требуя около 11МБ на каждые 1000 пиров (N * (L + 1) * S).
Kademlia netDb сократила бы эти числа, в идеале приведя их к K над M от их значения, где K = коэффициент избыточности, а M = количество router’ов в netDb (например, 5/100, что даёт recvKBps 126KBps и 536MB при 100,000 router’ов). Недостатком Kademlia netDb является повышенная сложность безопасной работы во враждебной среде.
То, о чём я сейчас думаю, это просто реализовать и развернуть floodfill netDb в нашей существующей живой сети, позволив узлам, которые хотят её использовать, выбирать других узлов, помеченных как участники, и запрашивать их вместо запроса традиционных Kademlia netDb узлов. Требования к пропускной способности и дисковому пространству на этом этапе достаточно незначительны (7.6 КБ/с и 3 МБ дискового пространства), и это полностью исключит netDb из плана отладки - проблемы, которые останется решить, будут вызваны чем-то, не связанным с netDb.
Как будут выбираться пиры для публикации флага, указывающего, что они являются частью floodfill netDb? В начале это может делаться вручную как расширенная опция конфигурации (игнорируется, если router не может проверить свою внешнюю достижимость). Если слишком много пиров установят этот флаг, как участники netDb выберут, кого исключить? Опять же, в начале это может делаться вручную как расширенная опция конфигурации (после отбрасывания недостижимых пиров). Как избежать разделения netDb? Путём проверки router’ами того, что netDb правильно выполняет flood fill, запрашивая K случайных netDb пиров. Как router’ы, не участвующие в netDb, обнаруживают новые router’ы для туннелирования? Возможно, это можно сделать, отправив специальный netDb lookup, чтобы netDb router ответил не пирами в netDb, а случайными пирами вне netDb.
netDb в I2P очень отличается от традиционных нагруженных DHT - она содержит только метаданные сети, а не фактическую полезную нагрузку, поэтому даже netDb, использующая алгоритм floodfill, сможет выдержать произвольное количество данных I2P-сайтов/IRC/bt/почты/syndie/и т.д. Мы даже можем провести некоторые оптимизации по мере роста I2P, чтобы немного больше распределить эту нагрузку (возможно, передавая фильтры Блума между участниками netDb, чтобы видеть, чем им нужно поделиться), но кажется, что пока мы можем обойтись гораздо более простым решением.
Один факт стоит изучить подробнее - не все leaseSet нужно публиковать в netDb! На самом деле, большинство из них не нужно публиковать - только те, которые предназначены для получателей, которые будут принимать непрошеные сообщения (то есть серверы). Это связано с тем, что сообщения garlic encryption, отправляемые от одного получателя к другому, уже содержат leaseSet отправителя, поэтому любая последующая отправка/получение между этими двумя получателями (в течение короткого периода времени) работает без какой-либо активности netDb.
Итак, возвращаясь к этим уравнениям, мы можем изменить L с 5 на что-то вроде 0.1 (предполагая, что только 1 из каждых 50 назначений является сервером). Предыдущие уравнения также не учитывали сетевую нагрузку, необходимую для ответа на запросы от клиентов, но хотя она крайне изменчива (в зависимости от активности пользователей), она также весьма вероятно будет довольно незначительной по сравнению с частотой публикации.
В любом случае, по-прежнему никакой магии, но приятное сокращение почти на 1/5 требуемой пропускной способности/дискового пространства (возможно, больше позже, в зависимости от того, будет ли распространение routerInfo происходить напрямую как часть установления соединения с узлом или только через netDb).
Отключение алгоритма Kademlia
Kademlia была полностью отключена в релизе 0.6.1.20.
(Адаптировано из IRC-беседы с jrandom 11/07)
Kademlia требует минимальный уровень сервиса, который базовая конфигурация не могла предоставить (пропускная способность, процессор), даже после добавления уровней (чистая kad абсурдна в этом отношении). Kademlia просто не работала бы. Это была хорошая идея, но не для враждебной и изменчивой среды.
Текущий статус
netDb играет очень специфическую роль в сети I2P, и алгоритмы были настроены под наши потребности. Это также означает, что они не были настроены для решения потребностей, с которыми нам еще предстоит столкнуться. I2P в настоящее время довольно мала (несколько сотен router’ов). Были проведены расчеты, показывающие, что 3-5 floodfill router’ов должны справиться с 10 000 узлов в сети. Реализация netDb более чем адекватно удовлетворяет наши текущие потребности, но вероятно потребуется дальнейшая настройка и исправление ошибок по мере роста сети.
Обновление расчетов 03-2008
Текущие числа:
recvKBps = N * (L + 1) * (1 + F) * (1 + R) * S / T
где:
N = number of routers in the entire network
L = average number of client destinations on each router
(+1 for the routerInfo)
F = tunnel failure percentage
R = tunnel rebuild period, as a fraction of the tunnel lifetime
S = average netDb entry size
T = tunnel lifetime
Изменения в предположениях:
- L теперь составляет около 0.5, по сравнению с 0.1 выше, из-за популярности i2psnark и других приложений.
- F составляет около 0.33, но баги в тестировании tunnel исправлены в 0.6.1.33, поэтому станет намного лучше.
- Поскольку netDb состоит примерно на 2/3 из routerInfo размером 5K и на 1/3 из leaseSet размером 2K, S = 4K. Размер RouterInfo уменьшается в 0.6.1.32 и 0.6.1.33, поскольку мы удаляем ненужную статистику.
- R = период построения tunnel: 0.2 было очень низким значением - возможно, было 0.7 - но улучшения алгоритма построения в 0.6.1.32 должны снизить его примерно до 0.2 по мере обновления сети. Назовем это 0.5 сейчас, когда половина сети на версии .30 или ранее.
recvKBps = 700 * (0.5 + 1) * (1 + 0.33) * (1 + 0.5) * 4KB / 10m
~= 28KBps
Это касается только хранилищ - а что насчет запросов?
Возвращение алгоритма Kademlia?
(Адаптировано из материалов встречи I2P от 2 января 2007 г.)
Kademlia netDb просто не работала должным образом. Она мертва навсегда или вернется? Если она вернется, то узлы в Kademlia netDb будут очень ограниченным подмножеством router’ов в сети (по сути расширенным числом floodfill узлов, если/когда floodfill узлы не смогут справиться с нагрузкой). Но пока floodfill узлы могут справляться с нагрузкой (и можно добавить другие узлы, которые смогут), это не нужно.
Будущее Floodfill
(Адаптировано из IRC-беседы с jrandom 11/07)
Вот предложение: класс пропускной способности O автоматически становится floodfill. Хм. Если мы не уверены, то можем получить изощренный способ DDoS-атаки на все роутеры класса O. Ситуация довольно такая: мы хотим убедиться, что количество floodfill как можно меньше, при этом обеспечивая достаточную доступность. Если/когда запросы netDb терпят неудачу, тогда нам нужно увеличить количество floodfill узлов, но на данный момент я не знаю о проблемах с получением netDb. По моим записям, есть 33 узла класса “O”. 33 - это /очень/ много для floodfill.
Значит, floodfill работает лучше всего, когда количество узлов в этом пуле строго ограничено? И размер пула floodfill не должен сильно расти, даже если сама сеть постепенно будет расширяться? 3-5 floodfill узлов могут обработать 10K роутеров, если я правильно помню (я публиковал кучу цифр с объяснением деталей в старом syndie). Звучит как сложное требование для выполнения с автоматическим добровольным участием, особенно если узлы, подключающиеся к этому, не могут доверять данным от других. например “давайте посмотрим, вхожу ли я в топ-5”, и могут доверять только данным о себе (например “я определенно класса O, и пропускаю 150 КБ/с, и работаю уже 123 дня”). И топ-5 тоже враждебно. В основном, это то же самое, что и серверы каталогов tor - выбираемые доверенными людьми (то есть разработчиками). Да, сейчас это можно эксплуатировать через добровольное участие, но это было бы тривиально обнаружить и устранить. Кажется, в итоге нам может понадобиться что-то более полезное, чем Kademlia, и пусть только достаточно способные узлы присоединяются к этой схеме. Класс N и выше должен быть достаточно большим количеством для подавления риска того, что противник вызовет отказ в обслуживании, надеюсь. Но тогда это должно было бы отличаться от floodfill в том смысле, что не вызывало бы огромный трафик. Большое количество? Для основанного на DHT netDb? Не обязательно основанного на DHT.
Список задач Floodfill
ПРИМЕЧАНИЕ: Следующая информация не является актуальной. См. главную страницу netDb для получения текущего статуса и списка планируемых работ.
Сеть была сведена к единственному floodfill на пару часов 13 марта 2008 года (приблизительно 18:00 - 20:00 UTC), и это вызвало множество проблем.
Два изменения, реализованные в версии 0.6.1.33, должны уменьшить нарушения, вызванные удалением или ротацией floodfill узлов:
- Рандомизировать floodfill-узлы, используемые для поиска каждый раз. Это позволит в конечном итоге обойти неисправные узлы. Это изменение также исправило неприятную ошибку, которая иногда приводила код поиска ff в бешенство.
- Отдавать предпочтение floodfill-узлам, которые работают. Код теперь избегает узлов, которые находятся в черном списке, неисправны или от которых не было сигналов в течение получаса, если это возможно.
Одним из преимуществ является более быстрый первый контакт с I2P-сайтом (т.е. когда вам сначала нужно получить leaseset). Тайм-аут поиска составляет 10 секунд, поэтому если вы не начнёте с запроса к недоступному узлу, вы можете сэкономить 10 секунд.
В этих изменениях могут быть последствия для анонимности. Например, в коде store floodfill есть комментарии о том, что узлы из черного списка не избегаются, поскольку узел может быть “плохим” и затем посмотреть, что произойдет. Поиски гораздо менее уязвимы, чем сохранения - они происходят гораздо реже и раскрывают меньше информации. Так что, возможно, нам не стоит об этом беспокоиться? Но если мы хотим подкорректировать изменения, было бы легко отправлять узлу, помеченному как “недоступный” или находящемуся в черном списке, просто не считать его частью тех 2 узлов, которым мы отправляем (поскольку мы на самом деле не ожидаем ответа).
Существует несколько мест, где выбирается floodfill-узел - данное исправление затрагивает только одно - от кого обычный узел выполняет поиск [по 2 за раз]. Другие места, где должен быть реализован лучший выбор floodfill-узлов:
- У кого обычный узел хранит данные [по 1 за раз] (случайно - нужно добавить квалификацию, потому что таймауты длительные)
- У кого обычный узел выполняет поиск для проверки хранения [по 1 за раз] (случайно - нужно добавить квалификацию, потому что таймауты длительные)
- Кого floodfill узел отправляет в ответ на неудачный поиск (3 ближайших к поиску)
- Кому floodfill узел передает данные (всем другим floodfill узлам)
- Список floodfill узлов, отправляемый в NTCP каждые 6 часов “whisper” (хотя это может быть больше не нужно из-за других улучшений floodfill)
Многое еще можно и нужно сделать:
- Использовать статистику “dbHistory” для лучшей оценки интеграции floodfill узла
- Использовать статистику “dbHistory” для немедленного реагирования на floodfill узлы, которые не отвечают
- Быть умнее с повторными попытками - повторные попытки обрабатываются верхним уровнем, а не в FloodOnlySearchJob, поэтому он выполняет еще одну случайную сортировку и пробует снова, вместо целенаправленного пропуска ff узлов, которые мы только что попробовали.
- Больше улучшить статистику интеграции
- Фактически использовать статистику интеграции, а не только индикацию floodfill в netDb
- Использовать также статистику задержки?
- Больше улучшений в распознавании неисправных floodfill узлов
Недавно завершено:
- [В релизе 0.6.3] Реализовать автоматическое подключение к floodfill для некоторого процента узлов класса O, основываясь на анализе сети.
- [В релизе 0.6.3] Продолжить уменьшение размера записей netDb для снижения трафика floodfill - мы достигли минимального количества статистики, необходимой для мониторинга сети.
- [В релизе 0.6.3] Ручной список floodfill-узлов для исключения (блок-листы по идентификатору router)
- [В релизе 0.6.3] Лучший выбор floodfill-узлов для хранения: Избегать узлы с устаревшей netDb, или с недавней неудачной попыткой сохранения, или навсегда занесенные в черный список.
- [В релизе 0.6.4] Предпочитать уже подключенные floodfill-узлы для хранения RouterInfo, чтобы уменьшить количество прямых соединений с floodfill-узлами.
- [В релизе 0.6.5] Узлы, которые больше не являются floodfill, отправляют свой routerInfo в ответ на запрос, чтобы router, выполняющий запрос, знал, что он больше не является floodfill.
- [В релизе 0.6.5] Дальнейшая настройка требований для автоматического становления floodfill
- [В релизе 0.6.5] Исправить профилирование времени отклика в подготовке к предпочтению быстрых floodfill
- [В релизе 0.6.5] Улучшить блокировку
- [В релизе 0.7] Исправить исследование netDb
- [В релизе 0.7] Включить блокировку по умолчанию, заблокировать известных нарушителей
- [Несколько улучшений в последних релизах, продолжающиеся усилия] Снизить требования к ресурсам на высокопропускных и floodfill router’ах
Это длинный список, но потребуется именно столько работы, чтобы создать сеть, устойчивую к DOS-атакам от множества узлов, которые включают и выключают переключатель floodfill. Или притворяются floodfill router. Ничего из этого не было проблемой, когда у нас было только два ff router, и они оба работали 24/7. Опять же, отсутствие jrandom указало нам на места, которые нуждаются в улучшении.
Для содействия этим усилиям, дополнительные данные профиля для floodfill-узлов теперь (начиная с версии 0.6.1.33) отображаются на странице “Профили” в консоли router. Мы будем использовать эти данные для анализа того, какая информация подходит для оценки floodfill-узлов.
Сеть в настоящее время довольно устойчива, однако мы продолжим совершенствовать наши алгоритмы для измерения и реагирования на производительность и надежность floodfill-узлов. Хотя мы в данный момент не полностью защищены от потенциальных угроз со стороны вредоносных floodfill-узлов или DDOS-атак на floodfill, большая часть инфраструктуры уже создана, и мы находимся в хорошем положении для быстрого реагирования в случае необходимости.