Предисловие

Для тех, кто сталкивался с вопросом организации работы фирмы из более чем пары офисов и десятка сотрудников, не секрет, что готовые решения для контроля бизнеса создают огромное количество головной боли как сисадминам, так и владельцам.

Будь то 1С, Битрикс, Мегаплан или тем более самостоятельные решения – они требуют установки специфического софта, налаживания удаленного доступа к серверу через VPN или другие решения, не работают с плохими каналами связи – какие часто встречаются в торговых центрах или удаленных офисах, и уж точно требуют недюжинного умения работников для доступа из дома или командировки.

Отдельно можно сказать о производительности: для меня, как разработчика высоконагруженных систем БД, всегда было странным формирование отчетов не за секунды, а десятками минут, проведение документов занимающее в 1С минуты, и вообще постоянно требующие обновления железа новые версии тех же систем, с баснословными требованиями к серверам. Очевидно было, что такие простейшие операции как посчитать остатки на складе за весь период работы из миллиона документов даже в MySQL займут секунды…

Постановка вопроса

В общем, когда передо мной встала задача поставить систему учета на 5 удаленных магазинов, склад и офис, варианты готовых решений выглядели бледновато. После мыслей об обучении продавцов (хороших продавцов, но не пользователей компьютера) – первый раз видевших мышку, как пользоваться 1С и бесконечных поездках для настройки сети, стало понятно что это не наш вариант…

Хотелось следующего:
• Полностью удаленное пользование с любой операционной системы, с планшета, смартфона
• Нетребовательность к качеству канала связи
• Дружелюбный интерфейс и юзабилити
• Скорость – любые отчеты и документы в течение секунды
• Возможность встраивания продвинутой аналитики

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

Полное содержание и список моих статей по поисковой машине будет обновлятся здесь.

В предыдущих статьях я рассказывал про работу поисковой машины, вот и дошел до сложного технически момента. Напомню что разделяют 2 типа индексов – прямой и обратный. Прямой – сопоставление документу списка слов в нем встреченного. Обратный – слову сопоставляется список документов, в которых оно есть. Логично, что для быстрого поиска лучше всего подходит обратный индекс. Интересный вопрос и про то, в каком порядке в списке хранить документы.

На предыдущем шаге DataFlow от модуля-индексатора мы получили кусочек данных в виде прямого индекса, ссылочной информации и информации о страницах. Обычно у меня он составляет около 200-300mb и содержит примерно 100 тысяч страниц. Со временем я отказался от стратегии хранения цельного прямого индекса, и храню только все эти кусочки + полный обратный индекс в нескольких версиях, чтобы можно было откатиться назад.

Устройство обратного индекса с виду, простое, – храним файл, в нем в начале таблица адресов начала данных по каждому слову, потом собственно данные. Это я утрировано. Так получается самый выгодный для оптимизации скорости поиска формат — не надо прыгать по страницам — как писали Брин и Пейдж, — 1 seek, 1 read. На каждой итерации перестроения, я использую 20-50 кусочков информации описанных выше, очевидно загрузить всю инфу из них в память я не могу, тем более что там полезно хранить еще кучу служебных данных об индексе.

Ну вот одна из самых вкусных частей БД – она хранит миллиарды разных ссылок, и производит доступ к ним в произвольном порядке.

Сначала очевидно можно заметить что все URL сгруппированы в рамках сайта, т.е. все ссылки внутри 1 сайта можно хранить вместе для скорости. Я выделил URL сайта, и стал хранить список сайтов отдельно – сейчас их 600 тыс и отдельная таблица БД описанной раньше легко с ними справляется. В памяти постоянно находится AVL дерево с CRC всех известных сайтов, и проверяя первым делом существование URL я получаю ID сайта ему соответствующего, если он уже есть в базе.

Остальную часть ссылки – кроме названия сайта я отрезаю, и считаю CRC для нее, назовем ее Hash. Таким образом любая ссылка относительно однозначно имеет индекс (ID сайта, Hash). Все ссылки можно отсортировать по Hash в рамках отдельного сайта, и тогда можно легко искать существующую или нет – пробегать по списку все ссылок данного сайта пока не встретим с нужным Hash или не встретим больший Hash – значит ссылки нет. Ускорение не очень большое, но в 2 раза, все таки, в среднем.

Решил немного описать на мой взгляд самую полезную древовидную структуру. AVL дерево это бинарное дерево (у каждой вершины не более 2 сыновей), в котором каждой вершине присвоен идентификатор (как раз его и хранит дерево), идентификаторы подчиняются следующему правилу: ID левого сына<ID родителя<ID правого сына.
Т.е. если обходить дерево рекурсивно слева направо получим отсортированный по возрастанию список ID, справа налево – по убыванию.
Причем дерево максимально сбалансировано: высота левого поддерева отличается от высоты правого максимум на 1.

Интересно в нем то, что тогда на проверку существования элемента в дереве уходит log(N) N – количество ID. Ведь надо пройти от корня вниз, а поскольку дерево максимально симметрично то его высота — log(N)+1
Хорошая новость – нам никто не запрещает прикрепить к вершине еще какие-то полезные данные и тогда выборка произвольных данных по ID будет занимать log(N) времени
Плохая новость – одинаковые ID как следует из определения в нем существовать не могут. Придется делать финт ушами, один способ сделать вместо каждой вершины список вершин с одинаковым ID, другой – изменить алгоритм балансировки.

Без базы данных, даже без нескольких кардинально разных, такой проект невозможен. Поэтому немного посвящу времени этому вопросу.

Итак как минимум будет нужна БД обслуживающая обычные «плоские» («2D») данные – т.е. некоторому идентификатору ID ставится в соответствие поле данных.
Почему поле данных я рассматриваю одно? Потому что:

• выборка производится только по полю ID – поиск по данным не производится. Для этого есть специализированные индексы – иначе с такими количествами информации толку будет мало
• любое количество полей можно упаковать в одно, для этого я «на коленке» создал набор небольших прикладных библиотек, в частности при упаковке сохраняется CRC данных, чтобы не использовать не дай бог битые

Если не задаваться задачей минимизации кол-ва строк кода работы с данными и немного удобством, то почти любую задачу можно свести к той, где эти пункты будут достаточны. И в случае таких высоких требований к оптимальности и скорости, по моему мнению это вполне оправдано.

Вопрос отделения нужного и полезного контента от остальных рюшечек встает довольно часто перед теми, кто занимается сбором той или иной информации в Web.

Думаю нет особой причины останавливаться на алгоритме разбора HTML в дерево, тем более, что в обобщенном виде такие парсеры учат писать курсе на 3-4 ВУЗа. Обычный стек, немного фишечек по пропуску аргументов (кроме тех что потом понадобятся), и выходное дерево как результат разбора. Текст разбивается на слова прямо в процессе разбора, и слова отправляются в отдельный список, где запомнены кроме общей информации и все позиции слова в документе. Понятное дело слова в списке уже в 1-й нормальной форме, про морфологию уже писал, здесь просто скопирую из предыдущей статьи.

В продолжение статьи С чего начинается поисковик, или несколько мыслей про crawler

В предыдущей статье я немного порассказал про эксперименты с интенсивностью загрузки и работой Crawler’а, в общих чертах опишу DataFlow проекта до построения индекса, чтобы было понятно о чем я пишу. Каждый шаг я постараюсь описать подробно в соответствующей статье

Итак, скачанная страница первым делом попадает на выделение ссылок. Новые ссылки с текущего сайта попадают в локальную очередь для загрузки в текущей сессии, а на все другие сайты добавляются в общую очередь Crawler’а. В этой очереди содержаться только главные страницы сайтов.

После сбора достаточного количества страниц одного сайта запускается анализатор, выделяются паттерны, присутствующие на большинстве страниц сайта, и они вырезаются.
На выходе получаем тексты страниц без всего лишнего и сгруппированные по сайтам.

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

Но, к делу: поисковая машина по моему скромному мнению должна уметь находить максимально релевантные результаты по поисковому запросу. В случае текстового поиска, к которому мы все привыкли, поисковый запрос – набор слов, лично я ограничил его длину восемью словами. Ответ – набор ссылок на страницы которые наиболее релевантны поисковому запросу. Ссылки желательно снабдить аннотацией, чтобы человек знал чего ожидать и мог выбрать из результатов нужный – аннотация называется сниппет.

Надо сказать что задача поиска в общем виде не решается – для любого документа имеющего наибольшую релевантность например по слову «работа», можно создать модифицированную копию, которая будет иметь еще лучшую, с точки зрения поисковой машины, релевантность, однако будет полным бредом с точки зрения человека. Вопрос цены и времени, конечно. Из-за обширности Интернета на сегодняшний день таких страниц, мягко говоря, много. Разные системы борются с ними по-разному и с переменным успехом, когда-нибудь искусственный интеллект победит всех нас…

В продолжение начатой темы про собственную поисковую машину

Итак есть несколько крупных задач, которые должна решить система поиска, начнем с того что отдельную страницу надо получить и сохранить.
Тут есть несколько способов, в зависимости от того, какие способы обработки Вы выберете в дальнейшем.

Очевидно, надо иметь очередь страниц, которые надо загрузить из web, хотя бы для того чтобы потом на них смотреть длинными зимними вечерами, если ничего лучшего не придумать. Я предпочитаю иметь очередь сайтов и их главных страниц, и локальную мини очередь того что я буду обрабатывать в данное время. Причина проста – список всех страниц которые я хотел бы загрузить просто за месяц – может существенно превысить объем моего немаленького винчестера :), поэтому я храню только то что действительно необходимо – сайты, их на данный момент 600 тысяч, и их приоритеты и времена загрузки.

Когда-то давно взбрела мне в голову идея: написать свой собственный поисковик. Было это очень давно, тогда я еще учился в ВУЗе, мало чего знал про технологии разработки больших проектов, зато отлично владел парой десятков языков программирования и протоколов, да и сайтов своих к тому времени было понаделано много.

Ну есть у меня тяга к монструозным проектам, да…

В то время про то, как они работают было известно мало. Статьи на английском и очень скудные. Некоторые мои знакомые, которые были тогда в курсе моих поисков, на основе нарытых и мной и ими документов и идей, в том числе тех, которые родились в процессе наших споров, сейчас делают неплохие курсы, придумывают новые технологии поиска, в общем, эта тема дала развитие довольно интересным работам. Эти работы привели в том числе к новым разработкам разных крупных компаний, в том числе Google, но я лично прямого отношения к этому не имею.

На данный момент у меня есть собственный, обучающийся поисковик от и до, со многими нюансами – подсчетом PR, сбором статистик-тематик, обучающейся функцией ранжирования, ноу хау в виде отрезания несущественного контента страницы типа меню и рекламы. Скорость индексации примерно полмиллиона страниц в сутки. Все это крутится на двух моих домашних серверах, и в данный момент я занимаюсь масштабированием системы на примерно 5 свободных серверов, к которым у меня есть доступ.

Действуют они везде – хоть MySQL, хоть Oracle хоть самописная БД. Чем умнее БД – тем больше она старается оптимизировать сама, но лучше ей помочь

1. Разделяй и властвуй, а попросту кластеризация БД – все данные одного типа можно еще разбить на кластеры – отдельные таблицы, в каждую таблицу попадают записи, которые удовлетворяют какому-то простейшему правилу, например в таблицу с индексом I попадают данные у которых ID%N==I, где N – кол-во кластеров. Таким образом очень просто и эффективно делим те данные, которые не надо считывать последовательно – например разбиваем все слова на 100-200-миллион блоков, в каждом блоке только слова у которых ID%N==I. В качестве примера в большой системе, типа социальной сети, можно поделить все данные по признаку принадлежности одному пользователю — например все фото разместить в N таблиц, информация о фото помещается в таблицу K=USER_ID%N

2. Условно — работа с диском. Всегда пиши (вставляй) последовательно, кэшируй и буферизуй запись, читать старайся подряд от начала до конца. Ускорение записи может быть просто фантастическое – много порядков, просто от того что Вы правильно используете запись зная как работает Ваш (или производителя) алгоритм записи на диск. Данные почти всегда можно отсортировать до записи – в памяти ли, разные файлы ли с кускам текста – всегда можно построить индекс или простейший массив, который отсортирован по ID данных и читать-писать их в порядке как в индексе. Как один из вариантов – всегда можно придумать более оптимальную структуру хранения данных. К примеру когда надо вставить кусок таблицы в другую таблицу делать это лучше последовательно от меньшего ID к большему, заодно отключив механизм индексации. И включив его после вставки.