Поисковые технологии или в чем загвоздка написать свой поисковик

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

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

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

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


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

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

    Просто вдумайтесь, Google хранит, по одной из оценок, более 500 миллиардов страниц в индексе. Если бы каждое слово встречалось на 1 странице только 1 раз, и на хранение этого надо было 1 байт – что невозможно, т.к. надо хранить хотя бы id страницы – уже от 4 байт, так вот тогда объем индекса бы был 500гб. В реальности одно слово встречается на странице в среднем до 10 раз, объем информации на вхождение редко когда меньше 30-50 байт, весь индекс увеличивается в тысячи раз… Ну и как прикажите это хранить? А обновлять?

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

    На сегодня объем только индекса, по которому происходит поиск — 57Gb, увеличивается каждый день примерно на 1Gb. Объем сжатых текстов – 25Gb, ну и я храню кучу другой полезной инфы, объем которой очень трудно посчитать из-за ее обилия.

    Вот полный список статей которые относятся к моему проекту и описаны здесь:
    0. Поисковые технологии или в чем загвоздка написать свой поисковик
    1. С чего начинается поисковик, или несколько мыслей про crawler
    2. Общие слова про устройство поиска в Web
    3. Dataflow работы поисковой машины
    4. Про удаление малозначимых частей страниц при индексации сайта
    5. Методы оптимизации производительности приложения при работе с РБД
    6. Немного про проектирование баз данных для поисковой машины
    7. AVL деревья и широта их применения
    8. Работа с URL и их хранение
    9. Построение индекса для поисковой машины

    Similar posts

    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 76

      +2
      А может не нужно хранить 500 миллиардов страниц? Когда в ответе на запрос, я вижу «найдено 100,000,000 страниц» — это угнетает. Сто миллионов или один — неважно. Когда уже количество ответов перейдет в качество?
        +3
        Когда пользователи научаться правильно составлять поисковые запросы. :)
          +2
          … скорее когда интернет будет очищен от мусора.

          В последние дни ищу информацию по одной… негласной тематике (боты для wow), всё мало-мальски полезное — платное или приватное, в публичном поиске 90% — мусор (дорвеи) и копипасты одного и того же на убогих сайтах на юкозе.

          Так вот огромное моё время тратится на анализ всего и этого и отсекание ненужного. Такой аддон как Wot конечно помогает, уже на странице гугла показывая бесполезные сайты, но часто и он не спасает.

          Я бы предпочёл хотя бы, вбивая заведомо «тупиковый» запрос, сразу получить сообщение: «полезной информации нет».
            0
            А зачем вбивать заведомо тупиковый запрос?
              0
              Затем, что информация о том, что он тупиковый, содержится у сервера. У меня перед началом поиска её нет.
              И я, соответственно, хотел бы её получить прямым текстом, а не добывая эмпирическим путём.
                0
                На самом деле, Гугль движется в этом направлении, сопоставляя запросы и переходы по ссылкам из результатов поиска.
              +1
              90% это очень оптимистическая оценка. ИМХО полезного намного меньше.
              +1
              т.е. никогда
              0
              Причем из этих 500 миллиардов можно получить прямой доступ только к первым нескольких сотням. Остальные находятся «в подсознании Google».
                +1
                а ведь всего 7-8 лет назад в поисках стоящих вещей люди перерывали и тысячу страниц выдачи!
                  +1
                  Да ладно? o.O
              +1
              это напрямую связано. понятно что никто не ищет при популярном запросе во всех 100 млн страниц, однако если запрос редкий то придется хранить все-все. или еще интереснее — когда редкое слово с часто встречающимся «этимология слова работа»
                +1
                В прошлом году прошла конференция от Яндекса (YAC), на которой было несколько докладов как раз о том, как работают поисковые машины. Интересующимся темой советую глянуть 2 доклада:
                1. Базовые оптимизации, Петр Попов
                2. Yet Another MapReduce, Александр Дмитриев

                Их можно найти на странице материалов конференции, последние два.
                  +2
                  Надеюсь вы хорошо понимаете в чем разница между послушать конференцию и сделать самостоятельно. Безусловно такие материалы полезны, но вся эта дискуссия напоминает разговор про формат MP3 — все знают что такое битрейт и как примерно он устроен, однако единицы могут реально рассказать где там зашито DCT (их там 3 в отличие от общепринятых «познаний»), и в чем состоит его перемежение (в английском аналоге overlaping)

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

                  Кстати никогда не видел описания как устроена БД которая хранит все url в Яндексе например…
                    +1
                    Буду ждать ваших топиков! :)

                    Ссылку сюда положил исключительно для дополнительной информации. Наверное, спецу в области создания сложных поисковых систем это все мало интересно, но для знакомства с характерными для области задачами сойдет, я думаю. С конкретикой у них там и правда было не очень, — значительную часть вопросов докладчики оставляли без ответов, ссылаясь на NDA.
                      +2
                      Вот про это я и хочу написать. Не претендую на лучшую реализацию, но она хотя бы реально работает, и могу ответить на любой вопрос по теме. Поэтому с удовольствием принимаются вопросы — будет понятно о чем писать. Сегодня выложу порцию конкретики из уже описанного :)
                  +7
                  По моему топик не несет полезной нагрузки, можно было бы начать рассказывать)
                    +1
                    уже есть продолжение :)
                      0
                      Буду ждать, интересная тема :-)
                      0
                      кстати вот этот пост хоть и был моим первым на хабре, имеет прямое отношение к устройству моей БД
                      http://habrahabr.ru/blogs/sql/123670/
                      скоро и про нее выложу пост
                    • UFO just landed and posted this here
                      • UFO just landed and posted this here
                          +2
                          39 килобайт = 0,038085937 Gb
                          вы тут на 3 порядка наврали: 0,000039 Гб
                          • UFO just landed and posted this here
                            • UFO just landed and posted this here
                                0
                                тем более, что 90% из них можно отсеить как копипасту ;-)
                            0
                            Общий ответ:
                            Да, инфы море.
                            Сайтов не 15 млн, это глюки от бесплатных хостингов и умерших доменов. у меня 600 тыс актуальных второго уровня .ru и больше не растет.
                            Хранить все не обязательно, в принципе если я заберу все 600 тыс то сколько-то десятков терабайт моя база займет (одна итерация, я храню минимум 3-4 для инкрементальной работы). Но в таком виде искать по ней на 1 сервере будет нереально. Эти вопросы решить еще предстоит
                              +1
                              Гугл решает просто: www.youtube.com/watch?v=zRwPSFpLX8I
                              • UFO just landed and posted this here
                                  0
                                  Ну вы еще рекламную сеть бегуна и рупоиска возьмите :)
                                  Я рассматриваю только сайты второго уровня + региональные домены немного — у них меньший приоритет
                                  Вы реально думаете что в инете есть контентосодержащих сайтов миллионы? К примеру вычистив promodj.ru третьего уровня я сократил базу в 2 раза. А таких сайтов море. Я их сознательно пока не индексю, с основными то справится бы.
                                  Кроме того ошибки и дубли в эту цифру не входят. Реально проверил из 600 я тысяч 300, которые в индексе больше чем 1-2 страницами
                                  • UFO just landed and posted this here
                                    • UFO just landed and posted this here
                                        0
                                        есть, не спорю. Когда буду запускать полную версию и иметь пару лямов на PR — сделаю чтобы искалось все :)

                                        никак не отсеиваю — в основном пара коэффициентов при поиске — показатели тошноты слов
                                  +4
                                  15000000*255 = 3825000000
                                  3825000000*39 = 149175000000
                                  149175000000/1024/1024/1024 = 138.93
                                  138.93/20 = 6.9465
                                  результат — все сайты рунета занимают приблизительно 7 террабайт.

                                  я хз как вы считали.
                                  • UFO just landed and posted this here
                                    • UFO just landed and posted this here
                                        0
                                        Самая большая ошибка в количестве страниц на сайтах — никто этого не заметил. В среднем у меня не хватает и 1000 страниц лимита, а есть сайты у которых по миллиону ссылок. И не забудьте что на большинстве сайтов есть страницы одинаковые но с разными url — а для того чтобы понять что они одинаковые надо их сначала скачать
                                          0
                                          Да я просто расчеты поправил. Понятия не имею сколько в среднем страниц на сайтах.

                                          Кстати все(основные) поисковики при наличии одинаковых страниц с разными урл — индексируют обе. И еще и в выдаче пессимизируют, за дубликат контена. Интересно, почему так? Раз уж все равно сравнивают — выкидывали бы повторы из индекса, какая никакая но экономия.
                                          • UFO just landed and posted this here
                                            • UFO just landed and posted this here
                                                0
                                                У меня в конце статьи написана динамика, я уже не помню где (слишком много комментов) давал свою оценку — десятки терабайт если иметь в виду объем сопоставимый с яндексом (скорее гуглом) — несколько миллиардов страниц в индексе (у яндекса половина страниц из их миллиардов ищется по ссылкам). короче мне осталось раз в 100-500 вырасти.

                                                Это цифры на одну итерацию — надо хранить несколько чтобы процесс индексации шел непрерывно
                                                0
                                                Интересно как вы избавляетесь от с подчти одинаковой информацие, но просто представленной и отображенной по другому.
                                                Например таблица на несколько страниц, с сортировкой по разным своим колоночкам. В итоге информация вроде разная получается, но по сути дубликаты.
                                                  0
                                                  согласен, проблема. Избавляюсь — если она встречена больше чем на 10% страниц сайта ее не будет в индексе — блоком одной инфы считаются законченый блок тегов — т.е. ряд в таблице подходит.
                                                  Вообще вопрос конечно интересный, но пока что я не встречался с проблемами в выдаче из-за дублей похожих но не одинаковых страниц. Вообще борьба с ними описана у сегаловича — хитрый подсчет нескольких CRC по фрагментам текста.
                                            • UFO just landed and posted this here
                                                0
                                                я Вам минус не ставил — Ваше право высказаться — я просто рассказываю что сделал сам.
                                                  0
                                                  «Писать свои мысли и новую информацию по темам в которых вы разбираетесь», но делать это неаккуратно и в итоге неверно — действительно не стоит.
                                                0
                                                Краулер/индексатор/поиск малая часть современного поисковика. Парсить документы правильно — вот основная проблема для всех поисковиков.
                                                  0
                                                  Парсинг — чисто техническая проблема. Про остальные я еще напишу — тупо не успеваю писать статьи
                                                  0
                                                  Интересно узнать о том, как этот индекс у вас строится и как вы со связностью и рангом слов справились, если такие задачи решались, конечно
                                                    0
                                                    связность — просто, позиции слов и некоторый алгоритм вычисления нескольких расстояний. Все постараюсь описать.
                                                    Ранги — проще — на вход самообучающегося алгоритма ранжирования поступают как взвешенные коэффициенты — как раз ранг по сути, так и абсолютные. Более того есть еще вспомогательные коэффициенты. Сейчас около 56 параметров всего — после большой чистки.
                                                    Остается обучать алгоритм… Над этим и голову ломаю, когда были просто формулы — все руками забивал
                                                      0
                                                      уже становится гораздо интереснее… в свое время застрял на подборе сути параметров и весов для обучающих выборок и оценке того, какой алгоритм лучше с задачей справится…
                                                      тема очень интересная, но ее объем и сложность на первый взгляд, да и на 10й тоже, непросто оценить — удачи вам!
                                                      0
                                                      Да, про индекс естественно подробно опишу
                                                      0
                                                      а где же ссылка на сам поисковик?
                                                        0
                                                        не будет до тех пор пока не доведу до состояния законченного проекта
                                                          0
                                                          Он законченным никогда и не будет, потому что это постоянная разработка. Яндекс — законченный продукт? Такие понятия как «готовый» к динамичным системам надо применять с огласовкой.
                                                            0
                                                            Трудный вопрос. Показывать проект не всегда работающий хотя бы «средне» я не готов — ведь все что вы увидите это результаты поиска, с ними я еще борюсь.
                                                        0
                                                        Вы пляшете от техники, а мне кажется, что нужно плясать от идеи. Ваша реализация — супер, однако хорошая мысль поможет вам избежать часть работы. Поисковики знают, как искать, потому что у них есть данные, ЧТО и КАК народ ищет. У вас есть такие данные, или вы работаете с моделью?

                                                        Правило парето, вероятно, в общем смысле работает и здесь: 80% запросов относятся к 20% объемам информации.

                                                        Если все запросы поделить на категории, то окажется, что несколько миллионов поисков относится к вопросам, ответы на которые не подразумевают какого-либо поиска (всякие энциклопедические, например, дата рождения Пушкина, или самая высокая гора Армении). То есть, возможно, стоит подумать о том, что на часто задаваемые вопросы ответы уже есть, и искать их не нужно.

                                                        Мне намного интереснее бы было почитать о том, как вы смотрите на логику запросов, на семантику, и вообще философски на то, какая должна быть поисковая система, а вы, к сожалению, сваливаетесь в описание баз данных, индексов и прочего — конечно, это тоже интересно, однако лишь «технической» публике (которой, кстати, на хабре, меньше, чем «мыслительско-предпринимательской»).
                                                          0
                                                          Ну согласитесь, что искать по энциклопедиям, умея искать по огромному кол-ву разных документов, будет намного проще. Меня просто на все не хватит. Первоначально я занимался параллельным поиском и по файлам в файловых хостингом, и в новостях, и в торрентах, и в вакансиях — благо многие базы у меня есть и обновляются самостоятельно, но меня просто на все не хватило. Я выделил наиболее интересный кусок для себя.

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

                                                          Я обязательно раскрою предложенную Вами тему, но пока мне жаль, что она остается только в моей голове.
                                                          Одно из уже реализованных, но пока не оптимизированных под нормальную быструю работу в связке с поиском — кластеризация результатов — то что делает clusty.com и nigma.ru. Только в отличие от последней, я могу это делать по всему массиву документов, а не по 400 сниппетам. И я не успел тогда прикрутить это раньше нигмы — они меня опередили наверное месяца на 4-5
                                                            0
                                                            Я логику на базе молекулярной сетки строил, что то между нейронной и семантической сетью оперирующей связями на основе большого словаря (для него 3 года назад и начал делать паука).
                                                            0
                                                            Ну согласитесь, что искать по энциклопедиям, умея искать по огромному кол-ву разных документов, будет намного проще. Меня просто на все не хватит. Первоначально я занимался параллельным поиском и по файлам в файловых хостингом, и в новостях, и в торрентах, и в вакансиях — благо многие базы у меня есть и обновляются самостоятельно, но меня просто на все не хватило. Я выделил наиболее интересный кусок для себя.

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

                                                            Я обязательно раскрою предложенную Вами тему, но пока мне жаль, что она остается только в моей голове.
                                                            Одно из уже реализованных, но пока не оптимизированных под нормальную быструю работу в связке с поиском — кластеризация результатов — то что делает clusty.com и nigma.ru. Только в отличие от последней, я могу это делать по всему массиву документов, а не по 400 сниппетам. И я не успел тогда прикрутить это раньше нигмы — они меня опередили наверное месяца на 4-5

                                                              0
                                                              Уважаемый автор, все пишете очень здорово! Могли бы вы поделиться своими мыслями насчет задержек в апдейтах яндекса в последнее время. Как то:
                                                              1) редко считают ссылочное
                                                              2) уже давно не пересчитывали тиц
                                                              3) актуальность текстового индекса иногда отстает на 2-3 недели, да есть быстробот, но он не спасает.
                                                              4) в сегодняшний ап порезало кучу страниц у нормальных сайтов, это что, кривые руки яндексоидов или как?
                                                              вот СДЛ сайт, не мой, просто пример:
                                                              anseo.ru/sites/?url=avtotochki.ru
                                                              страниц в индексе:
                                                              Яндекс: 178
                                                              Google: 581,000

                                                              Что вообще происходит в яндексе, нехватка ресурсов, серверов, людей, косяки в планировании или руки из одного места?

                                                              Спасибо.
                                                                0
                                                                Хоть я и работаю в Web и имею много сайтов и много хостов но комментировать здесь Яндекс не буду, был бы Сегаловичем — может бы ответил, а так смогу отвечать только про своий поисковик если он будет когда-нибудь в открытом доступе
                                                                0
                                                                > зато отлично владел парой десятков языков программирования и протоколов
                                                                Вы в универе знали 20 языков программирования? o_O
                                                                  –1
                                                                  В 11 классе я знал 3 и сдавал в качестве экзамена проект проигрывателя wav файлов типа winamp тогдашнего только под Dos
                                                                  На втором курсе, когда у меня уже были свои проекты, для обучения я владел Pascal/C/Basic и для работы Shell(да, это язык программирования)/Perl/PHP/JS/VBScript/ASP/SVG (если его можно считать)/AJAX (тогда слова такого не было) ну и кучу всякого типа XML/HTML/SQL/SOAP и тд
                                                                  На третьем курсе мы сдавали проект компилятора C++ в качестве курсовой, а для себя я писал mp3 плеер и кодек (вернее декодек), соответственно я в владел(ю) MS Visual C++/Assembler

                                                                  Думаю продолжать не стоит, когда есть опыт владения несколькими принципиально разными языками типа C++/Java Perl Shell или Python то изучение нового превращается в странное занятие по написанию программ «не знаю как, но работает»
                                                                  0
                                                                  У меня тоже свой поисковик :), тоже работаю над ним с переменным успехом (когда есть время) третий год.

                                                                  Рекламу и меню отсекаю на основе алгоритма похожего на поиск спама. На основании подобного алгоритма пытаюсь определить похожесть страниц для вычистки дублей. Если вычищать дубли и разделить сайты на большие и среднии, то окажется, что 90% интернет сайтов (без дублей) занимают очень мало места.
                                                                    +1
                                                                    Да, у меня похожий подход, я выделяю паттерны. Все опишу

                                                                    Здорово что я не один такой на голову :)
                                                                      0
                                                                      Да нас много таких. Когда я говорю что это всё работает на Lazarus (FreePascal) + Firebird, народ начинает вращать глазами и читать мантры ;).
                                                                        0
                                                                        Не, я предпочитаю феншуй. Обработка пары десятков(а то и сотен) гигов за час глубоко оптимизированая — не верю я в Паскаль
                                                                          0
                                                                          Тут вопрос религии ;).

                                                                          FreePascal немного медленнее, но зато памяти в два раза меньше кушает в синтетических тестах. На деле же получается солянка из кучи библиотек и кто сверху будет рулить ими C++ или FreePascal не имеет значения. Я просто где нужно быстрее, так же использую C++ (запаковываю в библиотеки), а некоторые вещи сделаны с использованием LUA — так как там важна гибкость и от использования языков более низкого уровня выигрыш минимален.
                                                                        0
                                                                        Простите, а что Вы называете в данном случае паттерном: сам алгоритм выделения блоков на странице или алгоритм анализа (выделенного) блока на предмет рекламы или навигации?
                                                                        Вы используете, как и Infanty, лексический анализ блока для того, чтобы определить является он рекламой или контентом?
                                                                          0
                                                                          нет все намного проще — рабиваю по законченным кускам html от мелких до крупных и считаю количество повторов. потом уже исходя из количества и размера блока делаю вывод надо это убирать из всех страниц или нет. уже дописываю статью про это
                                                                            0
                                                                            Ага, то есть если я правильно понимаю, у Вас на входе N страниц, каждую из которых вы разбиваете на блоки и потом ранжируете эти блоки по их повторяемости. Более-менее очевидные повторы, близкие к N Вы вырезаете с каждой страницы. Так?
                                                                            Тут самый ключевой момент — как правильно резать по блокам. Что Вы называете «законченным куском html»?
                                                                            Заранее спасибо за статью, будет интересно почитать!
                                                                        0
                                                                        А, если не секрет, что за алгоритм «похожи на поиск спама» Вы используете? Какой-то само-обучающийся фильтр или что-то вроде TF-IDF для текстовых блоков?
                                                                          0
                                                                          не самообучающийся, и не для текстовых блоков, а для кусков HTML — с тегами включительно
                                                                          в результате получаю простейшую и довольно хорошо работающую систему. см выше коммент
                                                                            0
                                                                            HTML помогает разбить контент на логические блоки, а потом проверка текста на повторение на соседних страницах + учёт длины текста + чуть чуть ручных правил фильтрации.
                                                                              0
                                                                              Все вопросы мне, шлите в личку :).

                                                                          Only users with full accounts can post comments. Log in, please.