Если вы хотите получить подробный ответ, взгляните на раздел 3.8 этого документа , в котором описан тест на просмотр URL современного скребка:
В курсепри извлечении ссылок любой веб-сканер встретит несколько ссылок на один и тот же документ.Чтобы не загружать и не обрабатывать документ несколько раз, перед каждой извлеченной ссылкой необходимо выполнить проверку URL-адреса перед добавлением его к границе URL-адреса.(В качестве альтернативы можно было бы вместо этого выполнить проверку URL-адреса при удалении URL-адреса с границы, но такой подход привел бы к гораздо большей границе.)
Чтобы выполнить тест с просмотром URL-адреса, мыхранить все URL-адреса, которые Mercator просматривает в канонической форме, в большой таблице, называемой набором URL-адресов.Опять же, слишком много записей, чтобы все они поместились в памяти, поэтому, как и набор отпечатков документов, набор URL хранится в основном на диске.
Чтобы сэкономить место, мы не храним текстовое представление каждого URL-адреса в наборе URL-адресов, а используем контрольную сумму фиксированного размера.В отличие от отпечатков пальцев, представленных в наборе отпечатков документов в тесте с просмотром содержимого, поток URL-адресов, проверенных по набору URL-адресов, имеет нетривиальную локальность.Поэтому, чтобы уменьшить количество операций с файлом резервного диска, мы храним в памяти кеш популярных URL-адресов.Интуиция для этого кэша заключается в том, что ссылки на некоторые URL-адреса довольно распространены, поэтому кэширование популярных в памяти приведет к высокой частоте обращений в памяти.
Фактически, используя кэш в памяти из 2 ^ 18 записей и политику замены тактового генератора, подобную LRU, мы достигаем общего коэффициента попадания в кэш в памяти в 66,2% и коэффициента попадания в9,5% в таблице недавно добавленных URL, чистая доля попаданий составляет 75,7%.Более того, из 24,3% запросов, которые отсутствуют как в кеше популярных URL-адресов, так и в таблице недавно добавленных URL-адресов, около 1 = 3 производят попадания в буфер в нашей реализации файла произвольного доступа, которая также находится в пользовательском пространстве.Конечным результатом всей этой буферизации является то, что каждый тест членства, который мы выполняем на наборе URL, приводит в среднем к 0,16 запросам поиска и 0,17 вызовам ядра чтения (некоторая часть которых обслуживается из буферов файловой системы ядра).Таким образом, каждый тест на членство в наборе URL-адресов вызывает в шесть раз больше вызовов ядра, чем тест на членство в наборе отпечатков документов.Эта экономия обусловлена исключительно количеством локальных URL-адресов (т. Е. Повторением популярных URL-адресов), присущих потоку URL-адресов, встречающемуся во время сканирования.
В основном они хешируют все URL-адреса с помощью функции хешированияэто гарантирует уникальные хеши для каждого URL-адреса и из-за локальности URL-адресов становится очень легко найти URL-адреса.Google даже открыл свою функцию хеширования: CityHash
ПРЕДУПРЕЖДЕНИЕ!
Они также могут говорить о ловушках ботов !!!Ловушка для бота - это раздел страницы, который продолжает генерировать новые ссылки с уникальными URL-адресами, и вы по сути попадете в «бесконечный цикл», перейдя по ссылкам, которые обслуживаются этой страницей.Это не совсем цикл, потому что цикл будет результатом посещения одного и того же URL-адреса, но это бесконечная цепочка URL-адресов, которые следует избегать сканирования.
Обновление 12/13/2012 -на следующий день после того, как мир должен был закончиться:)
За комментарий Fr0zenFyr: если кто-то использует алгоритм AOPIC для выбора страниц, тогда довольно легко избежать ловушекбесконечный циклВот краткая информация о том, как работает AOPIC:
- Получите набор из N начальных страниц.
- Выделите X сумму кредита для каждой страницы, чтобы каждая страница имела кредит X / N(т. е. равная сумма кредита) до начала сканирования.
- Выберите страницу P, где P имеет наибольшую сумму кредита (или, если все страницы имеют одинаковую сумму кредита, просканируйте случайную страницу).
- Страница сканирования C (допустим, что при сканировании у P было 100 кредитов).
- Извлеките все ссылки со страницы P (допустим, их 10).
- Установите для кредитов P значение 0.
- Возьмите «налог» в размере 10% и разместите его на лямбда-странице.
- Выделите равное количество кредитов для каждой ссылки, найденной на странице P, из исходного кредита P - налога: так (100 (P кредитов) - 10 (10% налога)) / 10 (ссылок) = 9 кредитов на каждую ссылку.
- Повторите с шага 3.
Поскольку страница Lambda непрерывно собирает налог, в конечном итоге это будет страница с наибольшей суммой кредита, и нам придется ее "сканировать". Я говорю «сканировать» в кавычках, потому что мы на самом деле не делаем HTTP-запрос для лямбда-страницы, мы просто берем ее кредиты и распределяем их поровну по всем страницам в нашей базе данных.
Поскольку ловушки для ботов дают кредиты только по внутренним ссылкам и редко получают кредиты извне, они будут постоянно пропускать кредиты (от налогообложения) на страницу Lambda. Лямбда-страница будет равномерно распределять кредиты по всем страницам в базе данных, и при каждом цикле страница ловушки ботов будет терять все больше и больше кредитов, пока у нее не будет так мало кредитов, что она почти никогда не будет сканироваться снова. Это не случится с хорошими страницами, потому что они часто получают кредиты от обратных ссылок, найденных на других страницах. Это также приводит к динамическому рангу страниц, и вы заметите, что каждый раз, когда вы делаете снимок своей базы данных, упорядочиваете страницы по количеству кредитов, которые они имеют, тогда они, скорее всего, будут упорядочены примерно в соответствии с их истинный рейтинг страницы .
Это позволяет избежать только ловушек для ботов типа бесконечного цикла, но есть много других ловушек для ботов , на которые следует обратить внимание, и есть способы их обойти.