¿Cómo se usan los algoritmos de clasificación de Reddit y Hacker News?

He estado buscando algoritmos de clasificación recientemente, específicamente aquellos usados ​​por Reddit y Hacker News. Los algoritmos en sí son bastante simples, pero no entiendo cómo se usan.

Una cosa que podría hacer es implementar el algoritmo directamente en SQL, para que cada vez que un usuario vaya a una página que muestra publicaciones clasificadas, se ejecute algo como esto:

SELECT thing1, thing2 FROM table ORDER BY ranking_algorithm DESC LIMIT page*20, 20 

Hay varias preguntas similares en SO, pero la única respuesta dada es poner el algoritmo de clasificación dentro de la consulta SQL. Entonces el hilo muere …

Poner el algoritmo en la consulta SQL bien en una escala más pequeña, pero ¿y si el sitio web tiene una gran cantidad de usuarios y una gran cantidad de publicaciones? Esto significa que cada vez que un usuario abre una página que muestra publicaciones clasificadas, esa consulta se ejecutará. Eso no puede ser muy eficiente.

Ahora, Reddit y Hacker News no ejecutan sus algoritmos de clasificación en consultas SQL, sino en python y ark, respectivamente. Entonces, ¿cómo y cuándo se usan exactamente?

Una posible solución es tomar toda la información relevante de cada publicación y almacenarla en alguna estructura de datos en el servidor web. Luego clasifique y clasifique esta estructura de datos.

Cada vez que alguien abre una página que muestra las publicaciones clasificadas, simplemente vaya a la estructura de datos, recupere el rango correcto de publicaciones y muéstrelas.

Luego, cada media hora más o menos, recupera la información más actualizada del servidor, la clasifica, clasifica y actualiza la estructura de datos.

Otras consultas menos costosas, como la recuperación y visualización de toda la información de una publicación específica, o la visualización de las publicaciones más recientes (en lugar de la mejor puntuada) podrían realizarse en SQL cada vez que se abra la página correspondiente.

La ventaja es que su base de datos se ve afectada (por la costosa consulta de clasificación) solo una vez cada media hora. La desventaja es que necesita tener un duplicado de una gran parte de su base de datos.

Reddit usa Pyrex, el algoritmo de ordenamiento es una extensión Python C para mejorar el rendimiento.

Por lo tanto, puede hacer lo mismo en SQL cuando se actualice el registro, pex: cuándo se votó hacia arriba o hacia abajo.

El pseudocódigo que debe traducir a la syntax de su motor 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); } 

Por lo tanto, debe almacenar en la tabla de publicaciones los altibajos, la fecha y el resultado de la función de encendido. Y luego puedes hacer una especie en la columna caliente.

Puede ver el código fuente de Reddit aquí: http://code.reddit.com/

Implementé una versión SQL del algoritmo de clasificación de Reddit para un agregador de video como ese:

 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 se actualiza mediante un desencadenador cada vez que se lanza una nueva votación. Se ejecuta lo suficientemente rápido en nuestro sitio actual, pero estoy planeando agregar una columna de valor de clasificación y actualizarla con el mismo activador que la columna cached_votes_total . Después de esa optimización, debe ser lo suficientemente rápido para la mayoría de los sitios de cualquier tamaño.

editar: Más información en Reddit Hotness Algorithm en SQL