Недавно я рассматривал алгоритмы ранжирования, особенно те, которые используются Reddit и Hacker News. Сами алгоритмы достаточно просты, но я не совсем понимаю, как они используются.
Одна вещь, которую я мог бы сделать, это реализовать алгоритм прямо в SQL, так что каждый раз, когда пользователь переходит на страницу, отображающую ранжированные сообщения, что-то вроде этого будет работать:
SELECT thing1, thing2 FROM table ORDER BY ranking_algorithm DESC LIMIT page*20, 20 Существует несколько аналогичных вопросов по SO, но единственный ответ – поставить алгоритм ранжирования внутри SQL-запроса. Затем нить умирает …
Включение алгоритма в SQL-запрос в меньшем масштабе, но что, если на веб-сайте большое количество пользователей и очень большое количество сообщений? Это означает, что каждый раз, когда любой пользователь открывает страницу, на которой отображаются ранжированные сообщения, этот запрос будет запущен. Это не может быть очень эффективным.
Теперь Reddit и Hacker News не запускают свои алгоритмы ранжирования в виде SQL-запросов, а в python и ark соответственно. Итак, как и когда именно они используются?
Одним из возможных решений является получение всей необходимой информации из каждого сообщения и сохранение ее в некоторой структуре данных на веб-сервере. Затем ранжируйте и сортируйте эту структуру данных.
Каждый раз, когда кто-то открывает страницу, на которой отображаются ранжированные сообщения, вы просто переходите к структуре данных, извлекаете правильный диапазон сообщений и показываете их.
Затем каждые полчаса вы получаете самую последнюю информацию с сервера, оцениваете ее, сортируете и обновляете структуру данных.
Другие менее дорогостоящие запросы, такие как извлечение и отображение всей информации с определенной должности или отображение новейших сообщений (в отличие от лучших результатов), могут выполняться в SQL каждый раз, когда открывается соответствующая страница.
Преимущество заключается в том, что ваша база данных попадает (для дорогого запроса на ранжирование) только один раз каждые полчаса. Недостатком является то, что вам нужно иметь дубликат большого фрагмента вашей базы данных.
Reddit использует Pyrex, алгоритм сортировки – расширение Python C для повышения производительности.
Таким образом, вы можете сделать то же самое в SQL, когда запись будет обновлена, pex: когда вверх или вниз проголосовали.
Псевдокод, который вы должны перевести на синтаксис SQL-синтаксиса:
function hot(ups, downs, date){ score = ups - downs; order = log(max(abs(score), 1), 10); if (score>0){ sign = 1; } else { if (score<0){ sign = -1; } else { sign = 0; } } td = date - datetime(1970,1,1); seconds = td.days * 86400 + td.seconds + (float(td.microseconds) / 1000000) - 1134028003; return round(order + sign * seconds / 45000, 7); }
Таким образом, вы должны сохранить в столбе столбец вверх, вниз, дату и результат горячей функции. И тогда вы можете сделать сортировку в горячей колонке.
Исходный код Reddit можно посмотреть здесь: http://code.reddit.com/
Я применил SQL-версию алгоритма ранжирования Reddit для агрегатора видео:
SELECT id, title FROM videos ORDER BY LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total) + (UNIX_TIMESTAMP(created_at) / 300000) DESC LIMIT 50
cached_votes_total обновляется триггером при каждом новом голосовании. Он работает достаточно быстро на нашем текущем сайте, но я планирую добавить столбец ранжирования и обновить его с помощью того же триггера, что и столбец cached_votes_total . После этой оптимизации он должен быть достаточно быстрым для большинства сайтов любого размера.
edit: Дополнительная информация в алгоритме HotDride Reddit в SQL