SMB Search

Общее устройство

Всю систему можно условно разделить на 4 относительно независимые части:

Храние данных

Общая структура данных

Вся информация, накопленная в результате проверок компьютеров и сканиования сети, хранится в двух местах: поисковом сервере (fsearch) и SQL-сервере.

Одно из основных назначений поискового сервера - хранить информацию о файлах. Также он хранит часть информации о хостах, поскольку она нужна ему для некоторых целей (например, для возможности сортировки результатов поиска по состоянию компьютера). Вся информация обо всех файлах лежит в памяти одновременно. Как следствие, поисковый сервер составляет наиболее "тяжелую" часть системы, которая потребляет основную долю процессорного времени и памяти.

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

Информация о сети и о хостах

О каждом индексируемом компьютере хранится следующая информация (центральная таблица hosts):

В таблице workgroups хранится информация о рабочих группах в сети: ее имя и идентификатор.

Также имеется ряд вспомогательных таблиц: counter - для подсчета числа посещения различных страниц; stat - для быстрого доступа к статистике по различным компьютерам и типам ресурсов.

Информация о файлах

Информация о файлах хранится в поисковом сервер в виде структур, в которых имеется следующие поля:

Тип ресурса введен для возможности быстрого поиска только в определенном типе файлов. На данный момент выделены такие типы: фильмы, клипы, музыка, картинки, документация, файлы Unix, образы дисков. Тип файла представляет из себя число, 0 означает некласифицированный файл, положительное число означает определенный тип. Список типов можно легко изменить или расширить, поисковый сервер воспринимает тип ресурса лишь как произвольное целое число (аналог вычислимого поля в SQL-таблицах). Файлы делятся на типа по их расширению и размеру. Поисковый сервер содержит внутри себя классификатор, который проставляет тип ресурса при загрузке списка файлов с диска.

Host checker

Checker представляет из себя скрипт, запускающий по расписанию (при помощи cron) и определяющий какие компьютеры включены и выключены. Получив свежую информацию, он заполняет таблицу hosts в SQL-сервере, а также синхронизирует данные о компьютерах в поисковом сервере.

Для определения включенных компьютеров checker использует утилиту nmap. Он запускает ее, передавая различные подсети, указанные в конфигурационных файлах. Для проверки включенности компьютера использует TCP scan на 139 порт. Все ответившие на этот запрос считаются включенными.

После этого определяется статус компьютеров. Выключенный компьютер сразу получается статус offline. Компьютер, который раньше был выключен, а сейчас стал включенным (только что включился) получает статус unchecked. Если компьютер был включен, и по-прежнему остается включен, то проверяется время его последнего сканирования. Если компьютер недавно просканирован, его состояние не меняется. Если последний раз компьютеры был просканирован давно, то ему тоже ставится статус unchecked. Устанавливая статус unchecked checker выбирает компьютеры, которые в ближаший запуск будут сканироваться сканером.

Сканнер

Сканер тоже запускается по расписанию но реже (например, раз в 15 минут). Сканер выбирает из списка компов имеющие статус unchecked, то есть те, которые включены и данные о которых устарели, и начинает их сканировать.

Для сканирования используется патченный smbclient, который отличается от обычного тем, что выводит информацию не в stdout в виде удобном для пользователя, а в файл, указанный в командной строке, и и в специальном формате, удобном для чтения из поискового сервера. Сначала получается список расшаренных каталогов, а затем они сканируются по порядку (вся информация дописывается в один список файлов). Если сканирование окончилось неуспешно (smbclient вернул ошибку), то компьютеру ставится статус error. Если компьютер был успешно просканирован, то сканер отправляет список файлов поисковому серверу (указывая запрос на обновление). Поисковый сервер читает список файлов в память, делая различные проверки, строя индексы, классифицируя файлы и обновляя статистику.

Во избежание различных конфликтов, сканер при запуске создает специальный .lock-файлы, чтобы не запустились 2 экземпляра сканера одновременно.

Поисковый сервер

Общее устройство

Поисковый сервер (fsearch) представляет собой наиболее технически сложный компонент всей системы. Он написан на C++ в виде демона, который запускается и находится в памяти все время в течение работы. При перезапуске чекера, сканера, web-сервера его перезапускать не нужно. При разработке поискового сервера использовался valgrind и другие средства с целью уничтожения всех утечек памяти и обеспечения стабильной работы. В целом можно сказать что эта цель достигнута.

Все общение с поисковым сервером происходит через сокет. Может использоваться любой тип сокета (UNIX, TCP/IP, другие), никаких специфичных функций не используется. В данный момент применяется UNIX-сокет по причине своей простоты. Если вдруг возникнет необходимость для доступа к нему по сети (например, поисковый сервер и web-сервер может быть на разных машинах), то легко добавить TCP/IP-сокет.

Через сокет сервер принимает запросы и делает соответствующие действия. Если запрос подразумевает некоторый ответ, то сервер выдает ответ прямо в этот сокет же. Все команды передаются по строчкам, разделителем является символ конца строки \n. Запросы можно условно разделить на несколько типов:

Поисковые запросы

Поисковые запросы содержат в себе тест, или фильтр которое указывает какие файлы интересуют пользователя. Условие есть выражение, которое строится из базовых тестов и различных логических операций. Базовые тесты включают в себя следующие:

Для сложных поисков применяются различные логические операторы (AND, NOT, OR, XOR) и скобки. Например, запрос, который ищет музыкальный файлы Pink Floyd размера не менее 10 Mb может выглядеть так:

	(SUBSTR "Pink Floyd") AND (RESTYPE 2) AND (MINSIZE 10000000)

Для реализации тестов были применены методы объектно-ориентированного программирования. Каждый тест реализован классом, унаследованным от базового абстрактного теста. Это позволяет очень просто создавать новые тесты: достаточно объявить новый класс и перегрузить в нем виртуальную функцию test.

Синтаксис запросов

Все поисковые запросы обрабатываемые сервером имеет следующий вид:

SEARCH min max [SHORT|FULL] hostfilter query

Где:

Запросы с просмотром пути

Для более полных возможностей поиска были реализованы так называемые запросы с обходом полного пути. При типичном поиске рассматривается только имя файла, имя каталогов, содержащих файл не учитывается. Довольно типичны такие ситуации: \\HOST\share\music\Artist\Album\Song.mp3 При этом пользователи ищут слова Artist Album Song. Никаких файлов при этом не находится, так как имя файла Song.mp3 содержит только ключевое слово Song. Для преодоления этого был введен специальный режим, который позволяет просматривать имена родительских каталогов.

Дело в том, что информация о файлах сама по себе уже занимает достаточно много места, поэтому хранить полный путь невозможно (это будет требовать гигабайты оперативной памяти). По этой причине, полный путь всегда конструируется на лету. Необходимо обеспечить чтобы поиск при этом не сильно замедлялся. Для решения этой задачи были придуманы фильтры с состояниями (state filters). Обычный фильтр является двоичным, его функция проверки возвращает true или false в зависимости от того, подходит файл или нет. State filter устроен более тонко - он имеет состояние, которое показывает какая часть фильтра уже была найдена. При этом функция добавочной проверки, которая добавляет новое слово (элемент пути) и обновляет состояние. Изначально фильтр инициализируется пустым состоянием. Если по окончании он будет в состоянии, когда все его условия удовлетворены (полное состояние), то его функция проверки возвращает true. Применение функций состояния позволяет не проверять заново весь пусть, а запоминать состояние родителя и затем только добавлять имя конечного файла. Это дает очень существенный выигрыш в скорости. Замеры показывают, что накладные расходы при таком способе минимальны.

Был реализован специальный path match filter который используя метод состояний позволяе проверять заданные тесты по полному пути. Состояние реализуется в виде битовой маски (до 32-х тестов). Для его использования используется следующий синтаксис:

PATHMATCH(TEST1, TEST2, ..., TESTN)

Например для вышеописанной ситуации можно использовать тест PATHMATCH(SUBSTR "Artist", SUBSTR "Album", SUBSTR "Song")

Оптимизация запросов с помощью индексов

Вначале общее количество файлов было мало и простой проверка всех файлов подряд работала вполне быстро (0.2 с). По мере увеличения числа хостов и роста базы такой метод становился все медленнее и медленнее. Для решения этой проблемы было принято решение об использовании индексов.

Основная трудность в такого рода системах - как правильно строить индексы. Для размера, даты, типа файла индексы строятся очевидным способом. Но строки не являются строго упорядоченными, поэтому отсортировать их в порядке возрастания невозможно. Для поиска по строкам применяются специальные структуры данных - суффиксные деревья, trie, PATRICIA-деревья и тп. Основная проблема состоит в том, что эти структуры занимают очень много места в памяти, или очень долго строятся. Особенность поиска в локальной сети состоит в том, процесс пересканирования идет постоянно (в среднем 1 хост в минуту), что накладывает требования на очень быстрое обновление индекса.

Чтобы удовлетворить всем требованиям - маленький объем памяти и быстрое обновление был применен метод индексирования по словам. Для этого каждое имя файла разбивается на слова. Затем строится список какие слова содержатся в каких файлах. Подсчеты показывают, что часто используемые слова (the, on, of) составляют более 50% индекса что сильно увеличивает расход памяти. Поскольку поиск по ним обычно бессмысленен то, индекс для них просто не строится.

В отличии от настоящего индекса, который содержит точную информацию, здесь индекс дает лишь приблизительную. Например, буквосочетание "pink floyd" дробится на слова pink floyd. Однако не всякое имя, содержащие cлова pink и floyd обязательно содержит "pink floyd" (например floyd pink). Поэтому вместо термина индекс здесь применяется понятие подсказки (hint). Подсказка - подмножество файлов, гарантированно содержащее все файлы, удовлетворяющие некоторому условию, но возможно также содержащее еще какие-то лишние ненужные файлы. При поиске теста сначала строится hint, а затем тест проверяется только внутри него. При поиске подстрок используется метод разбиения на слова. В момент реализации использование hint-ов ускорило поиск в 8-9 раз (основное время теперь тратится на проверку слов).

Использование памяти

Один из наиболее важных моментов состоит в том, что почти все данные которые находятся в памяти поискового сервера постоянно используются. Когда свободной физической памяти становится недостаточно и сервер весь не влезает в память, работать с ним просто невозможно. Это не есть проблема неправильно написанного сервера, для поиска действительно необходимо одновременно работать с большим числом данных. При установке поискового сервера это обстоятельство нужно учитывать и не пытаться ставить его на машину с недостаточным объемом памяти.

Память расходуется в основном на 2 большие структуры данных. Первая из - непосредственно сама информация о файлах. Для каждого файла нужно 28 байт + имя файла. Средняя длина имени файла - 12.8 (+1 байт на закрывющий нуль). Всего получается около 32 байта на файл. В используемой конфигурации наблюдается на данный момент около 12 миллионов файлов, что дает 400 Мб.

Второй источник высокого потребления памяти - индексы и хэш слов. Размер индекса равен примерно 8 байта x общее количество слов. В среднем в одном файле попадается 1.5 слова, что дает еще 12 байт на файл. Хэш слов также занимает большой объем, но в отличии от предыдущих этот объем почти не растет с увеличением количества файлов. При увеличении количества файлов с 10 миллионов до 17 миллионов количество слов выросло на проценты и сейчас составляет около 600 тысяч. Можно считать, что эта часть занимает фиксированный объем.

Суммарное использование памяти сервером можно узнать при помощи команды SERVERSTAT или скрипта serverstat.pl при работе с Web-интерфейсом

Web-интерфейс

Web-интерфейс представляет собой набор CGI-скриптов, взаимодействующих с web-сервером Apache и поисковым сервером FSearch. Основная их задача обработатка параметров, которые ввел пользователь, проверка их правильности, составление запроса к поисковому серверу и затем красивый вывод результатов в виде html. Для обращения к поисковому серверу используется обычный UNIX-сокет, для интерфейса к web-серверу - модуль CGI.pm, который входит в поставку Perl.

Для ускорения работы используется mod_perl, который позволяет запускать perl-скрипты прямо внутри Apache, без дополнительных fork/exec. При этом сам скрипт представляется в виде процедуры, которую можно запускать много раз без инициализации самого perl (что весьма длительная процедура).

Для повышения быстродействия используется Apache 2, который позволяет запускать различные обработчики в виде различных тредов, что ускоряет переключение задач и уменьшает расход памяти. Переход с Apache 1.3 на Apache 2.0 дал ощутимый прирост скорости.


SMB Search is written by Sasha, write to alex@sectorb.msk.ru