пятница, 21 ноября 2014 г.

Проблемка DC++ если шарятся очень большие коллекции файлов

Всем привет!
Недавно мне показали в 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-работает не очень :-)

 

воскресенье, 16 ноября 2014 г.

FlylinkDC++ и Visual C++ 2013

Планирую перейти на VC++2013
в автообновление пока не помещал - просьба протестировать новый билд и отписать о результатах
http://www.fly-server.ru/install/r5xx/src-bin/r503-vc2013
в Favorites.xml 483 - хаба  - ввизуально стартует быстрее и памяти немного меньше кушает

Размер FlylinkDC_x64.exe 12407968 (VC++2010)

RAM - 333 Mb











Размер FlylinkDC_x64.exe 11805856 (VC++2013)
RAM -  318 Mb

 

пятница, 7 ноября 2014 г.

Автоматический переход в пассивный режим.

Привет.
В последней бетке реализован автоматический _временный_ переход в пассивный режим если не смогли скачать в активном.
для теста можете авто обновиться или забрать бинарники 
тут http://www.fly-server.ru/install/r5xx/src-bin/

Алгоритм работы:
* Если клиент настроен как "активный" а по факту порты закрыты (мешает NAT, программный фаервол) 
   при попытке подключиться к пользователю по команде $ConnectToMe - клиент бесконечно висел в ожидании.
   неподготовленный пользователь в этом случае - сносил FlylinkDC++ :)
* Сейчас после 60 секунд ожидания клиент переходит в пассивный режим и повторяет попытку подключения 
  через команду $RevConnectToMe
* Если попытка удалась - происходит скачка контента при этом в прогрессе рисуется "кирпичная стенка"
* После завершения операции клиент возвращается в активный режим.
Кто разбирается в протоколе - подскажите какие проблемы вы видите в этом случае.
Пока пришлось выполнять посылку команды $MyINFO сообщающей хабу
что мы перешли в пассив - это сделано для Verlihub хотя другие хабы 
в частности PtokaX не требуют этой посылки и принимают команду $RevConnectToMe 
даже если клиент ранее сообщил что он активный.
мне это не совсем нравится т.к .приводит к лишнему спаму MyINFO туда-сюда...
что может привести к блокировке юзера на хабе напичканы хитрыми скриптами...
обычно нельзя часто слать MyINFO - от спама даже в клиенте есть защита на 2 минут.
пишите в комментарии или подрубайтесь к хабу dchub://dc.fly-server.ru
там можно анонимно пообщаться :)