понедельник, 23 мая 2016 г.

Веб поиск на Go. Краулер. Как не хранить лишнее

В предыдущей статье, я написал, как можно на этапе скачивания отбросить лишние страницы до непосредственной загрузки. Оставшиеся приходится хранить. Несмотря на большие и дешёвые диски, объёмы получаются существенными. Например, у меня сейчас в БД загружено 12 тыс страниц. И чистый HTML без картинок и прочего весит 900 МБ. Это неприемлемо много, поскольку для одного только habrahabr в очереди на скачивание осталось 20 тыс. страниц, в действительности их больше, т.е. только один сайт займёт более 2 ГБ на диске. Нужно как-то решать проблему.

 

Сжатие

Это очевидная и простая оптимизация.

Для Go много готовых архиваторов, различающихся по эффективности сжатия и скорости работы. Я протестировал три самых популярных:
  • zlib - входит в стандартную библиотеку Go.
  • gzip - тоже входит в стандартную библиотеку.
  • lzma - взял одну из обёрток вокруг C библиотеки реализующей LZMA, приводить ссылку не буду, т.к. их десятки, а какая лучшая - не знаю.
Первое, что я проверил - насколько меньше займёт текст с разными уровнями сжатия (для тестирования брал набор html размером в 240 МБ):
Level lzma zlib gzip
0 43 MB 240 MB 240 MB
1 41 MB 53 MB 53 MB
2 40 MB 51 MB 51 MB
3 40 MB 49 MB 49 MB
4 39 MB 47 MB 47 MB
5 38 MB 45 MB 45 MB
6 38 MB 44 MB 44 MB
7 38 MB 44 MB 44 MB
8 38 MB 44 MB 44 MB
9 38 MB 44 MB 44 MB

Тут "level" - уровень сжатия. А цифры в столбце показывают какой размер я получил после сжатия.

Как видно, тут zlib и gzip показывают одинаковые результаты, а вот lzma - гораздо эффективнее по степени сжатия.

Так же я замерил время работы при сжатии:
Level lzma zlib gzip
0 13.3s 676.2ms 826.3ms
1 17.0s 7.3s 7.5s
2 18.7s 7.5s 7.7s
3 22.6s 8.1s 8.3s
4 45.3s 10.7s 10.9s
5 1m0.7s 13.5s 13.7s
6 1m12.9s 17.1s 17.3s
7 1m28.1s 19.3s 19.4s
8 1m58.1s 22.6s 22.6s
9 1m55.2s 25.8s 25.8s

Тут опять же zlib и gzip отличаются на уровне погрешности (правда в пользу zlib). А lzma сильно проигрывает.
Потом проверил скорость разархивации:
Level lzma zlib gzip
0 4.1s 735.3ms 950.7ms
1 3.8s 2.9s 3.1s
2 3.7s 2.8s 3.0s
3 3.7s 2.7s 2.9s
4 3.7s 2.6s 2.9s
5 3.6s 2.5s 2.8s
6 3.6s 2.5s 2.7s
7 3.6s 2.5s 2.7s
8 6.7s 2.5s 2.7s
9 6.5s 2.5s 2.7s

zlib опять лидер, gzip не сильно хуже, а вот lzma - отстаёт, иногда до 2 раз.
Конечно хорошо было бы замерить потребление памяти и нагрузку на CPU, но я пока ни в то, ни в другое не упираюсь.

Если интересно можно посмотреть на аналоги. Snappy: сжала текст до 57 MB за 2 секунды, скорость конечно высокая, но степень сжатия мне не подходит. Ещё есть lzw из стандартной библиотеки - сжал до 106 MB за 5.1s - слишком слабо, как по мне. Кстати, есть проект который реализует lzma на нативном Go, правда сжимает он почему-то до 122 MB за 3m59.2s, да и сам автор говорит, что его работа далека от завершения. Вообще алгоритмов сжатия - десятки, если не сотни и можно провести не один день исследуя их, но похоже разница в результатах сжатия при сопоставимом времени работы в современных архиваторах - минимальна.

В итоге для себя - я выбрал zlib с уровнем сжатия "6", дальнейшее увеличение уровня почти не уменьшает размер сжатых данных, а вот время заметно увеличивается. lzma хоть и даёт результат лучше примерно на 10%, работает до трех раз медленнее, плюс требует C-библиотеку, что мне особенно не нравится.

 

Поиск дубликатов

Как бы я не старался заниматься нормализацией ссылок, обработкой редиректов и т.п. Всё равно 0.6% скачанных страниц - дубликаты. А это лишние мегабайты на диске и мусор в БД.

Избавиться от дубликатов легко. Что бы не сравнивать большие куски HTML - сохраняйте вместе с данными ещё и хеш страницы. Поиск по хешу - почти не занимает времени (главное помнить про коллизии). Хеш ещё крайне полезен для проверки целостности данных. Будет обидно работать с данными у которых БД или архиватор случайно потеряет пару байт.

 

Чистка HTML

HTML такой нехороший формат, который мешает извлекать текст из страницы. А значит нужно привести скачанную страницу к подмножеству HTML, почистив "мусор". Что бы делать это системно - нужно вооружиться каким-нибудь справочником по тегам.

Первое, что я сделал - вырезал теги, вместе с содержимым, которые меня не интересуют. Это "input", "button", "br", "audio" и им подобные.

Потом пришёл черёд строчных тегов. Нужно конечно смотреть на каждый тег по отдельности, но в большинстве случаев их нужно "раскрывать".
Например при вот такой вёрстке:
<div>При<b>в</b>ет</div>
После парсинга "в лоб" можно получить три слова "При", "в" и "ет", хотя на самом деле там только одно "привет". А если строчный тег "b" удалить, оставив его содержимое получим правильное:
<div>Привет</div>
Тут нужно действовать аккуратно, часть тегов содержит полезную информацию в своих атрибутах. Например тег "abbr" в атрибуте "title" хранит текст, который я бы хотел сохранить, поэтому я добавляю его к тексту внутри тега, а сам тег - удаляю.

В атрибутах можно найти полезную мета информации, которую не хочется хранить рядом с текстом. Поэтому я отдельным шагом - извлекаю её и сохраняю отдельно. Примером могут служить ссылки, заголовок страницы и т.п. А вот например кодировку страницы даже отдельно хранить не нужно - сразу конвертируем текст в UTF-8. Затем на этапе чистки HTML такие атрибуты удаляются.

Блочные элементы, в основном, я преобразовывал в тег "div", как наиболее универсальный.

Конечно по каждому тегу решение принимается отдельно, в зависимости от задачи. У меня в итоге после преобразования не осталось ничего кроме тегов "div" и текста. Кто-то наоборот оставляет максимальное количество тегов и применяет эвристические алгоритмы для анализа. Например для рекламных блоков характерна ситуация, когда разметки больше чем собственно самого текста, а значит его нужно отбросить. Можно уйти в другую крайность и удалить вообще все теги оставив только текст. Но я планирую в дальнейшем использовать информацию о том, как текст разбит на блоки.

Ещё отмечу, что в современном вебе, невозможно правильно извлечь текст из страницы только анализируя теги. Как минимум нужно ещё смотреть на CSS, а в идеале и выполнять JS код. Но для этого нужны слишком сложные алгоритмы.

Этот шаг сократил размер несжатого HTML в 4 раза. Очень хороший результат, правда долгий в реализации.

 

Минимизация текста

Если возможно ужать теги, то почему нельзя то же сделать и с текстом? Например всевозможные звёздочки, стрелочки, сердечки и т.п. - лишние. Впрочем, и знакомые с детства точки, запятые и скобки несут сомнительную ценность. Я поступил просто: оставил символы русского и английского алфавита, цифры и десяток символов (вроде '&', '-'…), а остальные заменил на пробелы. Потом убрал лишние пробелы между словами, что бы уменьшить размер. Дальше осталось только удалить ставшие пустыми теги.

Результат, я привёл к нижнему регистру - анализировать потом проще, да и коэффициент сжатия лучше будет. В итоге по отношению к предыдущему шагу получил сжатие в 1.2 раза.

 

Результаты

Напомню, что исходный размер HTML - 900 МБ, после чистки HTML, минимизации текста и сжатия размер сократился в 16.4 раза и стал 54 МБ.

Комментариев нет:

Отправить комментарий