Всем привет!
Недавно мне показали в DC++ сети пользователя с шарой 350 Tb! (рис 1)
6.5 миллиона файлов 259 тыс каталогов -
Файл лист в сжатом bz2 виде занимает 197 мб - после декомпрессии получается xml в 733 мб
Флалинк парсит этот список на моем i7 компе 60 сек!
Теперь рассмотрим алгоритм обслуживания поисковых запросов в DC++
для случае если такой жирный пользователь сидит на большом кол-ве хабов.
Если открыть окно CMD отладчика то можно увидеть, что клиент ежесекундно
получает пачку поисковых запросов
(на моем компе активно около 30 хабов случае это около 40-80 штук)
Запросы делятся на 2 вида:
1. Точный запрос поиска по TTH вида
$Search Hub:Indie F?T?0?9?TTH:KEWX74O4YGFIT3WGE3LYK43QXMVYORJPWVLUWUA
2. Поиск по подстроке(клиенты ищут файлы без учета регистра)
$Search Hub:UserDDD_1313 F?T?0?7?Unforgettable
Первый вид запросов практически не напрягает программу т.к. вся шара пользователя загружена в оперативную память в хеш таблицу (std::unordered_map) где ключом является TTHValue - 24 байта
если пренебрегать возможными коллизиями хеш-функции поиск идет мгновенно вот в этом месте:
https://github.com/pavel-pimenov/flylinkdc-r5xx/blob/e92a7f560a19bb3122106efe6d25721ee00fb770/client/ShareManager.cpp#L2144
Второй запрос немного сложнее и тут выполняется 2 шага.
2.1 Полученную подстроку подают на вход bloom-фильтра который быстро отвечает на вопрос - стоит ли искать ее в шаре или нет.
2.2 Если bloom сказал, что вероятно объект с таким именем у вас в шаре имеется то стартует самая последняя и тяжелая ветка алгоритма - рекурсивный обход всего дерева каталогов и файлов шары:
https://github.com/pavel-pimenov/flylinkdc-r5xx/blob/e92a7f560a19bb3122106efe6d25721ee00fb770/client/ShareManager.cpp#L2205
В результате обхода собирается ответ из 5 или 10 первых совпадений и возвращает результат назад запросившему пользователю.
- Если запросивший пользователь активный, то ему посылается UDP пакет на указанный порт (собственно поэтому если юзер думает что он активный и UDP порт закрыт - не работает поиск)
- Если запросивший юзер пассивный, то ответ идет по TCP на хаб с указанием ника кому форварднуть ответ о том, что по его запросу найдены файлы.
Проблема не эффективного потребления CPU в DC++ клиентах возникает когда владелец толстой шары сидит на более чем 1 хабе.
Возьмем наш лог из CMD отладчика (FlylinkDC++ недавно научился его сохранять в файл по галке в настройках)
и выберем строки где идет поиск по подстроке Unforgettable
Обратите внимание на временные метки и адреса хабов с которых приходили запросы.
Получается что за секунду прилетело 7 одинаковых(!) запросов от одного юзера
совместно с вами сидящем на разных хабах (рис 2)
По текущему алгоритм клиент получив эти запросы в разных потоках обслуживающих эти хабы
по очереди обращается к менеджеру шары и постоянно ищет одно и то-же.
Если bloom фильтр не отрубает эту подстроку на входе, то затраты на поиск возрастают пропорционально кол-ву файлов и каталогов в шаре.
я внес мелкое исправление
https://code.google.com/p/flylinkdc/source/detail?r=17886#
в менеджер шары флайлинка где попытался убрать эту лишнюю нагрузку
с помощью заведение дополнительной хеш-таблицы.
Алгоритм работы такой:
1. Получаем запрос на поиск подстроки от клиента-1 и выполняем рекурсивный поиск. Если не находим ее в шаре сохраняем строку в хеш-таблице.
2. С большой вероятностью в течении секунды к нам в менеджер шары прилетает еще таких-же запросов от клиентов 2-N
перед тяжелым рекурсивным обходом дерева - мы смотрим в нашу промежуточную табличку по ключу - подстрока поиска если находим ее там - сразу уходим т.к. в нашей шаре такого объекта не нашлось и мы это определили на шаге (1)
3. Если в вашу шару добавляются файлы - деваться некуда чистим эту временную мапу
4. На минутном таймере смотрим размер этой таблицы и если он больше 1000 - тоже чистим
число 1000 выбрал с потолка - на выходных потестю подробнее но лимит нужен чтобы не утекала память при большом кол-ве разных запросов.
Новой бетки с этими изменениями пока нет - появится вечером.
Желающие могут покритиковать-улучшить алгоритм т.к. возможно я что-то не учел.
не хочется сломать ключевую функцию клиента - поиск который и так из за NAT-работает не очень :-)
Сообщения
