Ну вот одна из самых вкусных частей БД – она хранит миллиарды разных ссылок, и производит доступ к ним в произвольном порядке.
Сначала очевидно можно заметить что все URL сгруппированы в рамках сайта, т.е. все ссылки внутри 1 сайта можно хранить вместе для скорости. Я выделил URL сайта, и стал хранить список сайтов отдельно – сейчас их 600 тыс и отдельная таблица БД описанной раньше легко с ними справляется. В памяти постоянно находится AVL дерево с CRC всех известных сайтов, и проверяя первым делом существование URL я получаю ID сайта ему соответствующего, если он уже есть в базе.
Остальную часть ссылки – кроме названия сайта я отрезаю, и считаю CRC для нее, назовем ее Hash. Таким образом любая ссылка относительно однозначно имеет индекс (ID сайта, Hash). Все ссылки можно отсортировать по Hash в рамках отдельного сайта, и тогда можно легко искать существующую или нет – пробегать по списку все ссылок данного сайта пока не встретим с нужным Hash или не встретим больший Hash – значит ссылки нет. Ускорение не очень большое, но в 2 раза, все таки, в среднем.
Надо сказать, что каждой ссылке у меня присвоен ID для того чтобы меньше места занимал в индексе – 4 байта вместо 2*4. Отдельная таблица содержит данные ID – (ID сайта, Hash) для быстрой выборки.
Теперь немного про то как же хранить списки по миллиону ссылок да еще и отсортировано для 600 тысяч сайтов. Для этого реализован еще один тип таблицы – с двумерным индексом, т.е. сначала по ID1 мы получаем доступ к списку данных отсортированных по ID2 причем специально ID2 не обязан быть от 1 до N, как делается в большинстве случаев. Такая таблица применялась у меня и для хранения обратного индекса, но сейчас там работает более эффективное решение. Сама таблица реализована так, чтобы добавление в список ID2 сохраняло отсортированность списка.
Все данные об URL'ах разбиты на 64 части по ID1, в таблице K содержаться записи о сайтах ID сайта%64=K, каждая таблица разбита на сегменты, выделенные под каждый конкретный ID1. Когда нужен доступ к конкретному списку записей – по ID1, все они уже лежат подряд на диске, и сразу известна позиция, куда сделать seek и откуда начать буферизовано читать. Читаем ровно до момента, когда встретим нужный Hash
Вставка в такую таблицу дело не очень быстрое, с другой стороны большой кеш и небольшой объем одной записи позволяет довольно быстро вставлять пакетом. Пакет обновлений накапливается — сейчас примерно 32000 ссылок для каждой таблицы, потом вставляется за 1 проход — делается временная копия таблицы в которую сливаются данные из кеша и старой таблицы.
URL с www и без учитываются как одинаковые – в зависимости от того на какой из них была первая ссылка тот и считается основным – он будет добавлен в базу, а все остальные ссылки приклеятся к нему. Это позволяет избежать бездумного отрезания или не отрезания www – ведь сайт может не работать без www, однако не полностью решает все проблемы связанные с тем что по адресам с www и без могут быть разные сайты
Самая кропотливая работа была в разрешении относительных ссылок – пример:
на странице “site.ru/index” есть ссылка “./” тогда она должна разрешится в “site.ru/” однако если к первой ссылке приписать слеш: “site.ru/index/” и хотя это может быть все та же страница на сайте, разрешенная ссылка будет «site.ru/index/» поэтому нельзя отрезать слеш на конце, нельзя отрезать аргументы ссылки, и названия файла исполняемого.
В целом я делю ссылку на части: протокол, сайт, путь, имя файла, аргументы, именованная ссылка (все что после #)
Из двух ссылок, так порезанных я собираю новую проходя по списку и подставляя пропущенные элементы (если надо) в результат.
Потом надо не забыть что бывают конструкции вида “./././././” и их надо убрать, а также “../../../”, ну и потом удаляются либо подставляются “#”,”?”
В целом процесс не долгий, но очень муторный в придумывании тестов и способов обработки всех возможных сочетаний. Зато когда написал – уже все работает как надо
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
Сначала очевидно можно заметить что все URL сгруппированы в рамках сайта, т.е. все ссылки внутри 1 сайта можно хранить вместе для скорости. Я выделил URL сайта, и стал хранить список сайтов отдельно – сейчас их 600 тыс и отдельная таблица БД описанной раньше легко с ними справляется. В памяти постоянно находится AVL дерево с CRC всех известных сайтов, и проверяя первым делом существование URL я получаю ID сайта ему соответствующего, если он уже есть в базе.
Остальную часть ссылки – кроме названия сайта я отрезаю, и считаю CRC для нее, назовем ее Hash. Таким образом любая ссылка относительно однозначно имеет индекс (ID сайта, Hash). Все ссылки можно отсортировать по Hash в рамках отдельного сайта, и тогда можно легко искать существующую или нет – пробегать по списку все ссылок данного сайта пока не встретим с нужным Hash или не встретим больший Hash – значит ссылки нет. Ускорение не очень большое, но в 2 раза, все таки, в среднем.
Надо сказать, что каждой ссылке у меня присвоен ID для того чтобы меньше места занимал в индексе – 4 байта вместо 2*4. Отдельная таблица содержит данные ID – (ID сайта, Hash) для быстрой выборки.
Теперь немного про то как же хранить списки по миллиону ссылок да еще и отсортировано для 600 тысяч сайтов. Для этого реализован еще один тип таблицы – с двумерным индексом, т.е. сначала по ID1 мы получаем доступ к списку данных отсортированных по ID2 причем специально ID2 не обязан быть от 1 до N, как делается в большинстве случаев. Такая таблица применялась у меня и для хранения обратного индекса, но сейчас там работает более эффективное решение. Сама таблица реализована так, чтобы добавление в список ID2 сохраняло отсортированность списка.
Все данные об URL'ах разбиты на 64 части по ID1, в таблице K содержаться записи о сайтах ID сайта%64=K, каждая таблица разбита на сегменты, выделенные под каждый конкретный ID1. Когда нужен доступ к конкретному списку записей – по ID1, все они уже лежат подряд на диске, и сразу известна позиция, куда сделать seek и откуда начать буферизовано читать. Читаем ровно до момента, когда встретим нужный Hash
Вставка в такую таблицу дело не очень быстрое, с другой стороны большой кеш и небольшой объем одной записи позволяет довольно быстро вставлять пакетом. Пакет обновлений накапливается — сейчас примерно 32000 ссылок для каждой таблицы, потом вставляется за 1 проход — делается временная копия таблицы в которую сливаются данные из кеша и старой таблицы.
URL с www и без учитываются как одинаковые – в зависимости от того на какой из них была первая ссылка тот и считается основным – он будет добавлен в базу, а все остальные ссылки приклеятся к нему. Это позволяет избежать бездумного отрезания или не отрезания www – ведь сайт может не работать без www, однако не полностью решает все проблемы связанные с тем что по адресам с www и без могут быть разные сайты
Самая кропотливая работа была в разрешении относительных ссылок – пример:
на странице “site.ru/index” есть ссылка “./” тогда она должна разрешится в “site.ru/” однако если к первой ссылке приписать слеш: “site.ru/index/” и хотя это может быть все та же страница на сайте, разрешенная ссылка будет «site.ru/index/» поэтому нельзя отрезать слеш на конце, нельзя отрезать аргументы ссылки, и названия файла исполняемого.
В целом я делю ссылку на части: протокол, сайт, путь, имя файла, аргументы, именованная ссылка (все что после #)
Из двух ссылок, так порезанных я собираю новую проходя по списку и подставляя пропущенные элементы (если надо) в результат.
Потом надо не забыть что бывают конструкции вида “./././././” и их надо убрать, а также “../../../”, ну и потом удаляются либо подставляются “#”,”?”
В целом процесс не долгий, но очень муторный в придумывании тестов и способов обработки всех возможных сочетаний. Зато когда написал – уже все работает как надо
Полное содержание и список моих статей по поисковой машине будет обновлятся вот здесь: http://habrahabr.ru/blogs/search_engines/123671/
