Показаны сообщения с ярлыком оптимизация. Показать все сообщения
Показаны сообщения с ярлыком оптимизация. Показать все сообщения

пятница, 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 байта
если пренебрегать возможными коллизиями хеш-функции поиск идет мгновенно вот в этом месте:
http://github.com/pavel-pimenov/flylinkdc-r5xx/blob/e92a7f560a19bb3122106efe6d25721ee00fb770/client/ShareManager.cpp#L2144

Второй запрос немного сложнее и тут выполняется 2 шага.
2.1 Полученную подстроку подают на вход bloom-фильтра который быстро отвечает на вопрос - стоит ли искать ее в шаре или нет.
2.2 Если bloom сказал, что вероятно объект с таким именем у вас в шаре имеется то стартует самая последняя и тяжелая ветка алгоритма - рекурсивный обход всего дерева каталогов и файлов шары:
http://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 фильтр не отрубает эту подстроку на входе, то затраты на поиск возрастают пропорционально кол-ву файлов и каталогов в шаре.
 










я внес мелкое исправление http://code.google.com/p/flylinkdc/source/detail?r=17886#
в менеджер шары флайлинка где попытался убрать эту лишнюю нагрузку
с помощью заведение дополнительной хеш-таблицы.

Алгоритм работы такой:
1. Получаем запрос на поиск подстроки от клиента-1 и выполняем рекурсивный поиск. Если не находим ее в шаре сохраняем строку  в хеш-таблице.
2. С большой вероятностью в течении секунды к нам в менеджер шары прилетает еще таких-же запросов от клиентов 2-N
перед тяжелым рекурсивным обходом дерева - мы смотрим в нашу промежуточную табличку по ключу - подстрока поиска если находим ее там - сразу уходим т.к. в нашей шаре такого объекта не нашлось и мы это определили на шаге (1)
3. Если в вашу шару добавляются файлы - деваться некуда чистим эту временную мапу
4. На минутном таймере смотрим размер этой таблицы и если он больше 1000 - тоже чистим
    число 1000 выбрал с потолка - на выходных потестю подробнее но лимит нужен чтобы не утекала память при большом кол-ве разных запросов.

Новой бетки с этими изменениями пока нет - появится вечером.
Желающие могут покритиковать-улучшить алгоритм т.к. возможно я что-то не учел.
не хочется сломать ключевую функцию клиента - поиск который и так из за NAT-работает не очень :-)

 

суббота, 28 июня 2014 г.

SQLite - оптимизация выборки страны по IP (GeoIP)

Всем привет.
Нашел статью проверил на sqlite, действительно быстрее.
c ревизии  r17333 в ветке r5xx ускорена выборка флага страны
данный запрос выполняется при первой отрисовке флага страны в колонке "расположение"
а также выполняется для всех записей если по этой колонке делают сортировку.








Тестовая база данных и запросы тут http://yadi.sk/d/l6ovbUUDV4iKQ
Изменения (было - стало)



Результат:
 

понедельник, 21 апреля 2014 г.

Кушаем CPU при большой очереди закачек

Привет
Часто жаловались на тормоза флая на слабых компах если в очереди много закачек. 
Нашел в коде несколько моментов:
1. При работ клиента в активном режиме на него постоянно приходит несколько десятков запросов в секунду
на поиск различных TTH.




















2. Если флай не находя данные TTH у себя в шаре (там выполняется быстрый поиск через unordered_map)
выполняет дополнительный запрос к менеджеру закачек 
в этом месте к сожалению идет линейный поиск по контейнеру т.к. ключом в мапе является имя файла а не TTH
http://github.com/pavel-pimenov/flylinkdc-r5xx/blob/f8157019835b79ab9000134444cd9a9982020ff3/client/QueueManager.cpp#L3044
http://github.com/pavel-pimenov/flylinkdc-r5xx/blob/f8157019835b79ab9000134444cd9a9982020ff3/client/QueueManager.cpp#L210
у некоторых пользователей в очереди закачек висят тысячи файлов постоянный и очень частый линейный просмотр такого 
контейнера кушает CPU в холостую т.к. вероятнее всего в очереди так-же нет файлов с такими ТТХ
тут я пока планирую завести дополнительный контейнер unordered_set где буду отслеживать наличие  TTH в очереди..
или может есть более оптимальный вариант?

3. Если TTH находится в очереди (это бывает когда вы качаете что-то популярное и большое которые одновременно все ищут) 
то выполняется создание UDP сокета
формирование информации какие части файла есть уже есть в клиенте через функцию SearchManager::toPSR
и передача UDP пакета в того кто ищет этот файл.
при этом выполняются команды разбора URL адреса на части 
в строках Util::decodeUrl(aSeeker, proto, ip, port, file, query, fragment);
а также дополнительный Socket::resolve(ip) перед посылкой UDP
пока не понял зачем делается эта операция тогда как по описанию команды в Search
в то место может попасть только IP:Port
аналогичный код   находится и в StrongDC++ в AirDC++ его немного оптимизировали
сделав UDP-Socket не временным а как мембер менеджера - он создается один раз.
Кто знает/тестировал насколько создание и разрушение UDP сокета затратная операция - наверно стоит сделать аналогично.?
другие мысли можете высказать если есть идеи в этом месте.
 

среда, 20 февраля 2013 г.

fly-server + mediainfo + json- оптимизация

Анализ файлов показал избыточное хранение информации предоставляемой mediainfo

1. В случаях когда в файле Audio больще 2-х атрибуты для всех блоков 0,1,2, - N как правило совпадают









2. Выполнил слияние дубликатных атрибутов в общую групп







 


3. Экономия на размере JSON пакета ~ 1Кб




Изменения попадут в следующий билд серой сборки.
и завтра постараюсь выпустить публичную бетку.
Всем спасибо за тестирование и конструктивные баг-репорты!


четверг, 17 января 2013 г.

Оптимизируем загрузку GeoIP

Всем привет.
Пост для программистов! 
Возможно кто-то из вас в свободное время "копает" исходный код FlylinkDC++ в академических целях
и если вдруг вы заметили элементы говно-кода обязательно сообщите об этом!
Пример использования профайлера для поиска хот поинтов по нагрузке на CPU
Шаг 1   - под профайлером запускаем флайлинк и после завершения процесса студия показывает нам стек вызова "горячей" функции.














Шаг 2 - находим тормозной кусок в коде и , где выполняется заполнение массива стран и провайдеров через использование 
линейного поиска по std::vector. данный вызов выполняется ~180 тысяч раз
при этом в результирующем векрторе набирается всего ~2900 названий стран и провайдеров.

Шаг 3 - заводим дополнительную хэш таблицу std::unordered_map
через которую пробрасываем наши 180 тысяч записей. и после индексации всего массива чистим.









Шаг 4 - Сравниваем скорость загрузки GeoIP старой и новой версии:












среда, 6 июля 2011 г.

Расчет TTH - CUDA, OpenCL

Привет,
Год назад мне пришло письмо:
"Хотел попробовать реализовать хеширование файлов с помощью технологии CUDA. это может дать очень большое ускорение."

К сожалению разработчик больше не откликался..

Кто хорошо знает технологию (CUDA, OpenCL) и сможет реализовать расчет TTH (Tiger Tree Hashing) 
с помощью видеокарт  приглашается к нам в FlylinkDC++ Team и за успешную реализацию... получает подарок.

четверг, 12 августа 2010 г.

Оптимизация обработки поисковых запросов (часть 2)

Инсталлятор x86
Исходный текст (С++)
ZIP-Архив x86

------------------------------------------------------------------------
r4395 | pavel.pimenov | 2010-08-12 20:44:19 +0400 (Чт, 12 авг 2010) | 2 lines
* Оптимизация обработки поисковых запросов (часть 2) исключаем постоянный вызов функции Text::toLower к именам файлов вашей шары при поступлении запросов из сети.
Цена оптимизации: дополнительно храним в памяти имена всех файлов в нижнем регистре и обновляем их только в случаях изменениях шары или запуска.
------------------------------------------------------------------------
r4394 | pavel.pimenov | 2010-08-12 20:35:12 +0400 (Чт, 12 авг 2010) | 1 line
* Добавлена опция в ком-строке FlylinkDC.exe /nowine (запустить флая в эмуляторе wine без  "обрезания" функций - возможны падения под старыми версиями wine)
------------------------------------------------------------------------
r4384 | tret2003 | 2010-08-11 09:05:02 +0400 (Ср, 11 авг 2010) | 2 lines
* (Closes issue #104) : Пункты меню "Копировать..." убрал "в буфер обмена"
------------------------------------------------------------------------
r4381 | pavel.pimenov | 2010-08-09 22:47:45 +0400 (Пн, 09 авг 2010) | 1 line
* Отключил загрузку CustomLocations.bmp под wine (http://flylinkdc.blogspot.com/2010/08/customlocationsbmp-wine.html)
------------------------------------------------------------------------
r4378 | pavel.pimenov | 2010-08-09 22:40:40 +0400 (Пн, 09 авг 2010) | 1 line
* Привел конфигурацию GDIOle к общему виду "Debug LIB" заменил на "Debug"

среда, 11 августа 2010 г.

Оптимизация обработки поисковых запросов (часть 1)

Всем привет.
DC++ клиенты(с открытым кодом) под профайлером показывают в топе функцию Text::toLower



















DC++ в процессе работы получает запросы и ищет файлы в своей шаре вот этим методом



















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

Первая часть исправления: поменял местами несколько строк (подозрительно просто)
...может я что-то не учел?












Вторая часть: сделаю завтра.