Mise à jour en temps réel du classement relatif pour chaque utilisateur entre amis

Question

J'ai travaillé sur une fonctionnalité de mon application pour implémenter un classement - en gros pile utilisateurs classement en fonction de leur score. Im actuellement suivi le score sur une base individuelle. Ma pensée est que ce classement devrait être relatif au lieu de l'absolu c.-à-d. Au lieu d'avoir le top 10 des meilleurs utilisateurs de notation sur le site, son top 10 parmi le réseau d'amis d'un utilisateur. Cela semble mieux parce que tout le monde a la chance d'être numéro 1 dans leur réseau et il y a une forme de concurrence amicale pour ceux qui sont intéressés par ce genre de chose. Je stocke déjà le score pour chaque utilisateur de sorte que le défi est de savoir comment calculer le classement de ce score en temps réel de manière efficace. Im en utilisant Google App Engine donc il les requêtes sont des avantages et des limites (par exemple, IN [tableau]) effectuent une sous-requête pour chaque élément du tableau et sont également limités à 30 éléments par déclaration

Par exemple

1er Jack 100

2 John 50

Voici les approches que je suis venu avec, mais ils semblent tous être inefficaces et je pensais que cette communauté pourrait venir avec quelque chose de plus élégant. Mon sentiment est que toute solution sera probablement fait avec un Cron et que je stocke un rang par jour et pour la liste afin d'optimiser les opérations de lecture, mais ce serait cool s'il y a quelque chose de plus léger et en temps réel

1. Tirez le liste de tous les utilisateurs du site classés par score. Pour chaque utilisateur, sélectionnez ses amis dans cette liste et créez de nouveaux classements. Stockez le classement et l'ordre des listes. Mise à jour quotidienne. Inconvénients - Si j'obtiens beaucoup d'utilisateurs cela prendra une éternité

2a. Pour chaque utilisateur, choisissez leurs amis et pour chaque ami, choisissez un score. Triez cette liste. Stockez le classement et l'ordre des listes. Mise à jour quotidienne. Enregistrer la dernière position de chaque utilisateur afin que la liste préexistante puisse être utilisée pour la réorganisation de la prochaine mise à jour afin de la rendre plus efficace (peut économiser du temps de tri)

2b. Idem que ci-dessus excepté calculer seulement le rang et l'ordre de liste pour les personnes dont les profils ont été consultés au dernier jour Contre - le rang est seulement à jour pour la 2ème personne qui voit le profil

Answer 1

Si les écritures sont très rares par rapport à lit (une hypothèse clé dans la plupart des magasins de valeur-clé, et pas seulement dans ceux-ci ;-), alors vous préférerez peut-être prendre un coup de temps lorsque vous avez besoin de mettre à jour les scores plutôt que d'obtenir les classements relatifs.). Plus précisément, lorsque le score d'un utilisateur change, mettez en file d'attente des tâches pour chacun de ses amis pour mettre à jour leurs "classements relatifs" et conserver ces classements en tant qu'attributs de liste (qui gardent l'ordre!) Correctement triés (oui, une dénormalisation souvent nécessaire pour dénormaliser, c'est-à-dire, dupliquer les informations de manière appropriée, pour exploiter au mieux les magasins à valeur-clé!

Bien sûr, vous allez également mettre à jour les classements relatifs lorsqu'une amitié (connexion utilisateur à utilisateur) disparaît ou apparaît, mais ceux-ci devraient être plus rares que les mises à jour de score ;-). Si les écritures sont assez fréquentes, puisque vous n'avez pas besoin d'informations de dernière minute parfaitement précises (c'est-à-dire, ce n'est pas financier/comptabilité ;-), vous avez encore de nombreuses approches viables à essayer.

E.g., les gros changements de score (plus rares) peuvent déclencher le recalcul des classements relatifs, tandis que les plus petits (plus fréquents) sont stockés et ne sont appliqués qu'une fois de temps en temps "quand vous vous en approchez". Il est difficile d'être plus précis sans chiffres approximatifs sur la fréquence des mises à jour de différentes amplitudes, les tailles de cluster réseau-amitié typiques, etc. Je sais, comme tout le monde, que vous voulez une approche parfaite, quelle que soit la taille et la fréquence en question ... mais, vous ne pourrez pas trouver un -)

Answer 2

Il y a une bibliothèque python disponible pour les classements stockage:

http://code.google.com/p/google-app-engine-ranklist/