Как используются алгоритмы ранжирования Reddit и Hacker News?

Я недавно изучал алгоритмы ранжирования, особенно те, которые используются 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 каждый раз, когда открывается соответствующая страница.

Преимущество заключается в том, что ваша база данных попадает (для дорогого запроса на ранжирование) только один раз каждые полчаса. Недостатком является то, что вам нужно иметь дубликат большого фрагмента вашей базы данных.

Ответ 1

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/

Ответ 2

Я внедрил 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: Дополнительная информация на Алгоритм Reddit Hotness в SQL