|
Задавайте вопросы, мы ответим
Вы не зашли.
Коллеги,
хочу порассуждать насчет решения одной задачи и посоветоваться. Заранее прошу прощения за путанное изложение.
Задача состоит в учёте траффика с поисковых систем. Обслуживается не один сайт, а несколько тысяч, поэтому поток посетителей - порядка миллиона в день (и постепенно растёт).
Основная сложность - это хранение и обработка поисковых фраз.
По началу я решил задачу "в лоб", записывая все фразы в словарь (id, word). Сейчас я думаю, что это было ошибкой, потому что словарь растёт (за несколько месяцев там скопилось уже более 20 млн. фраз - это как раз про него была тема) и будет продолжать расти (поскольку вариантов фраз может быть очень много). Уже при настоящем объеме работа с ним оказывается слишком низкопроизводительной - если нужно выбрать больше тысячи записей (именно самих значений фраз), это может занимать больше минуты (что для работы сервиса неприемлемо).
Поэтому я решил поменять механизм работы и мне пришел в голову следующий алгоритм (сразу скажу, что с подобным я сталкиваюсь впервые, поэтому строго не судите).
1. Непосредственно текстовую информацию, т.е. сами слова, из которых состоит фраза,
Фразу разбивать на отдельные слова и в виде текста хранить только их, а не фразы целиком. Русских слов порядка 70 тыс. Плюс еще английские, плюс всякая бессмысленная дребедень, которую вводят, в общем, получается не больше 200 тыс., я думаю. Такой словарь будет гораздо меньше по размеру, плюс будет меньше длина текстового поля.
2. Сами фразы как комбинации слов хранить в другой таблице
Текст фразы хранить в виде числа, в котором хранятся комбинации id слов, занимая по три байта каждое (забыл, как это грамотно называется).
Например, "мама мыла раму". В таблице с отдельными словами id (мама) = 123; мыла = 660, раму = 4900.
В словосочетании три слова, на каждое слово по три байта (думаю, количество отдельных слов не превысит 16 млн., поэтому можно обойтись MEDIUMINT, а не INT). Значит, понадобится 3*3 = 9 байт. Первые три байта хранят число 123, следующие три - 660, третьи - 4900 (т.е. число равно 123*2^(8*6) + 660*2^(8*3) + 4900, хотя это не важно).
3. Для быстрой проверки, есть ли уже такая фраза, для каждой фразы хранить MD5 и повесить составной ключ на первые четыре байта (думаю, четыре байта хватит, т.к. это уже 4 млрд. вариантов) и на id (чтобы, если нашлось - быстро выдавала id из индекса, а не лезла в таблицу).
Тем не менее, количество поисковых фраз останется тем же, и таблица все равно будет длинная.
Но при такой схеме я, по крайней мере, кое-что выигрываю.
Средняя длина слова - никак не меньше четырех букв. Плюс разделитель слов. Итого на каждое слово минимум пять байт вместо трёх плюс невозможность использовать всякие злые числовые операции типа побитовых сдвигов, поскольку длина слов непостоянная.
В общем, в результате вместо одной очень большой таблицы я получаю одну среднюю и одну такую же большую, но со строками в два-три раза короче, с которыми ещё и можно обращаться как с числами.
4. Чего при этой схеме все-таки не удаётся.
Не удаётся решить задачу типа "найти все фразы, где встречается такое-то слово". Как при старой, так и при новой схеме это полный скан таблицы, только при старой - вообще LIKE, а при новой что-то похитрее с битами, но все равно индекс одинаково не будет использоваться ни там, ни там.
(Честно говоря, я вообще не знаю, как такая задача нормально решается. Кто знает - поделитесь, пожалуйста)
Если кто осилил до конца - буду признателен, если выскажетесь.
Неактивен
Зачем хранить и MD5 и id? MD5 заменяет собой id.
Я бы оптимизировал иначе - хранил бы не все фразы, а только частые. Структура такая.
Две таблицы:
phrases (md5, phrase, expire timestamp)
newbies (md5, phrase, expire timestamp)
Появилась фраза - ищешь ее в phrases и в newbies. Если она есть во phrases, то добавляешь в expire 1 день. Если есть в newbies, добавляешь к expire 1 день и переносишь в phrases. Если нет нигде, добавляешь в newbies с expire = now() + 1 DAY;
Таблицу newbies ни к чему не привязывать и в статистику эту инфу не выдавать, так мы избавимся от 99% запросов. Фразы, время хранения которых истекло (expire<now()) удалять. Если с newbies удаление будет трудоемким, то сделать newbies_odd, newbiew_even - записывать по четным и нечетным дням, а удалять опустошением таблицы.
1ого числа создал newbies_odd, наполняю
2ого числа создал newbies_even наполняю (а повторы ищу и в newbies_even и в newbies_odd)
3ого числа очистил newbiews_odd (truncate), наполняю (повторы ищу в newbies_odd и во вчерашнем newbies_even)
Неактивен
Миш, а изначальная задача какая? Научиться строить индекс по фразам и
отвечать на вопрос «найди все фразы, где»? Это умеет делать sphinx, например.
Неактивен
Зачем хранить и MD5 и id? MD5 заменяет собой id.
Потому что бывает задача проверить, есть ли уже в таблице такая фраза, имея только текст фразы.
При хранении фразы в исходном строковом виде ключ на строку хуже, чем ключ на MD5. У буквы алфавита CARDINALITY где-то 30. + английские и цифры получается где-то 60-70. В MD5 же весь диапазон байта используется, поэтому CARDINALITY 256, т.е. в 4 раза выше. На 4 байта это уже 4^4 = 256, т.е. на 2,5 порядка выше. По-моему, существенно.
При такой схеме, как я описал в головном сообщении, без MD5 вообще никак, т.к. иначе придется строить фразу. Это можно, когда её пользователю показываешь (относительно нечастое событие), но когда это надо делать по 20 раз в секунду - не пойдёт. А MD5 позволяет быстро проверить.
===
Я бы оптимизировал иначе - хранил бы не все фразы, а только частые
Оригинальная схема, но имеет два недостатка.
1.
Таблицу newbies ни к чему не привязывать и в статистику эту инфу не выдавать
Тогда придется сделать "мёртвый" период, в который статистика не показывается. С точки зрения пользователя выглядит странно.
2.
так мы избавимся от 99% запросов
Вот это ключевой момент. Не хочется лишаться 99%. Т.к. пользователь тогда вообще не будет представлять, с каких запросов на него с поисковиков попадают. 99% потери траффика - это много. Соответственно, чем меньше будет цифра потерь, тем меньше будут иметь смысл две таблицы.
Можно сказать, что, дескать, зачем пользователю знать про запросы, которые не повторяются (т.е. случайные, фактически). Но это не user-friendly.
Вообще я приму к сведению, конечно. Надо будет пособирать статистику частоты использования фраз.
Неактивен
Миш, а изначальная задача какая? Научиться строить индекс по фразам и
отвечать на вопрос «найди все фразы, где»? Это умеет делать sphinx, например.
Всё сложнее...
Сфинкс read-only, а мне надо динамику с временем обновления (желательно) несколько минут.
Хотя, если что - да. Про sphinx я как-то не подумал. Взял на заметку, спасибо.
Неактивен
я написал:
4. Чего при этой схеме все-таки не удаётся.
Не удаётся решить задачу типа "найти все фразы, где встречается такое-то слово". Как при старой, так и при новой схеме это полный скан таблицы, только при старой - вообще LIKE, а при новой что-то похитрее с битами, но все равно индекс одинаково не будет использоваться ни там, ни там.
Придумал насчет этого кое-что (это пришло мне в голову еще при написании головного поста, но я решил, что это слишком ресурсоёмкое решение).
Можно сделать таблицу с двумя колонками - word_id и phrase_id. Соответственно, для каждого слова хранить список фраз, где оно встречается (ну, или, говоря по-другому, хранить для каждой фразы список составляющих её слов в нормализованной форме).
К сожалению, для хранения полной информации о фразе это не подходит (т.к. нельзя задать порядок слов), но для быстрого поиска фраз, содержащих слово, сойдет.
Средняя длина фразы, думаю, не превышает трёх слов. Если 20 млн. фраз, то 60 млн. строк. 2 колонки MEDIUMINT => 6 байт на запись, итого 360 Мб. Не так и много. Правда, это всё придется загнать в индекс, который будет где-то около 500 Мб (а то и больше), чтобы по id слова можно было получать id фраз из индекса, а не копаться потом по диску. И, возможно, еще один индекс, такой же, только в обратную сторону (чтобы уж сразу и по id фразы из индекса выдавал id слов - будет тоже полезно).
P.S. Что-то я тут нафлудил и навыдумывал, что мне одному только полезно, по-моему 
Неактивен
Зачем md5 понятно, непонятно зачем иметь id, если есть md5.
От 99% запросов по уникальности, но не по числу посещений. А мертвый период будет только для редких запросов (для частых его не будет) - посмотри на liveinternet, мне всегда казалось, что он не все запросы показывает (может и не прав).
Может и правильно конечно иметь id ради гарантированной уникальности
Неактивен
непонятно зачем иметь id, если есть md5
Т.к. id будет 3 байта, а MD5 - 16. id должен входить в другие таблицы, в т.ч. в состав индексов, поэтому длина важна.
Неактивен
id - 4 байта (3 байтовых не знаю), md5 можно до половины обрезать - будет 8 байт. Все конечно зависит от других таблиц
Неактивен
md5 можно до половины обрезать - будет 8 байт
8^8 = 16 млн. Маловато.. Учитывая, что где-то столько записей и будет, а заполняется он случайно (вставлять наудачу впадлу, пусть даже и с проверкой, т.к. с приближением к 16 миллионам удача будет все реже). Лучше уж автоинкремент..
Плюс, действительно, другие таблицы.
В общем, мне кажется, проще таки не изобретать велосипед и оставить и MD5, и id 
Неактивен
Не 8^8, а 256^8 или 2^(8*8) = 2^64 = 16*2^60 ~ 16*1000^6 = 1.6e19 (все-таки не 16 млн)
Неактивен
[забыл]
id - 4 байта (3 байтовых не знаю)
id может быть хоть один байт.
Я собираюсь использовать MEDIUMINT, который 3 байта.
Неактивен
Не 8^8, а 256^8 или 2^(8*8) = 2^64 = 16*2^60 ~ 16*1000^6 = 1.6e19 (все-таки не 16 млн)
А, ну да
Но всё равно велосипед не хочу
Неактивен
Слушайте..
А как, собственно, взять сколько-то байт из MD5?.
Как вообще взять первые сколько-то байт (или последние) из строки по-человечески?
(будет хорошо, если кто-нибудь напишет, как это делается, в частности, в PHP).
Неактивен
Вопросы по PHP задаются на webew.ru 
$a = $a & 0xFFFF; — последние 2 байта.
Неактивен
Вопросы по PHP задаются на webew.ru
Ну тут просто в тему пришлось...
$a = $a & 0xFFFF; — последние 2 байта.
Это если с числом. А MD5 - это ж шестнадцатеричная строка
Поэтому с ней надо так: pack('H4', MD5('что-то'))
Правда, это так будут первые два байта, но мне не принципиально..
Неактивен
Не изобретай очередной велосипед.
Залезь в клиентское API сфинкса.
Посмотри как он отдает строки. Ну и хранит слова соответственно.
Для примера в PHP использует pack.
И ложи в базу binary длиной равной количеству символов.
Неактивен
Ну pack и binary - по-моему, и без сфинкса понятно
(вроде работает)
Хотя сфинкс для разнообразия надо будет как-нибудь посмотреть.
Неактивен
LazY написал:
Хотя сфинкс для разнообразия надо будет как-нибудь посмотреть.
Да его и не для разнообразия стоит посмотреть :-)
Неактивен
