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

Question

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

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

Answer 1

Я реализовал 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

Answer 2

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/