stockage optimale de la structure de données pour la recherche rapide et la persistance

Question

Scénario

Je les méthodes suivantes:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Dans un premier temps, je pense stockage sur le formulaire:

itemId -> userId, userId, userId

et

userId -> itemId, itemId, itemId

AddItemSecurity est basé sur la façon dont je reçois les données d'une API tiers, GetValidItemIds comment je veux l'utiliser lors de l'exécution.

Il y a potentiellement 2000 utilisateurs et 10 millions d'articles. id article de sont sur la pour la forme:. 2007123456, 2010001234 (10 chiffres où quatre premiers représentent l'année)

AddItemSecurity ne pas effectuer super rapide, mais GetValidIds doit être la seconde. En outre, si une mise à jour sur une itemId existante je dois supprimer cette itemId pour les utilisateurs ne sont plus dans la liste.

Je suis en train de réfléchir à la façon dont je devrais stocker cette façon optimale. De préférence sur le disque (avec la mise en cache), mais je veux que le code maintenable et propre.

Si l'ID de poste avaient commencé de à 0, je pensais à la création d'un tableau d'octets la longueur de MaxItemId / 8 pour chaque utilisateur, et définir un vrai / faux bits si l'élément était présent ou non. Cela limiterait la longueur du tableau à un peu plus de 1 Mo par utilisateur et donner ainsi rapidement lookups comme un moyen facile de mettre à jour la liste par utilisateur. En persistant cela comme mémoire mappée fichiers avec le framework .Net 4 Je pense que je recevrais la mise en cache décent bien (si la machine a assez de RAM) sans me mettre en œuvre une logique de mise en cache. L'id Parsing, le décapage de l'année, et de stocker un tableau par an pourrait être une solution.

Le ItemId -> UserId [] liste peut être sérialisé directement sur le disque et en lecture / écriture avec une FileStream normale afin de persister dans la liste et diff quand il y a des changements

.

Chaque fois qu'un nouvel utilisateur est ajouté toutes les listes doivent également mises à jour, mais cela peut être fait tous les soirs.

Question

Dois-je continuer à essayer cette approche, ou y at-il d'autres voies qui devraient être étudiés aussi bien? Je pense serveur SQL ne fonctionnera pas assez vite, et ce serait donner une tête (au moins s'il est hébergé sur un autre serveur), mais mes hypothèses peut-être tort. Toute pensée ou des idées sur la question est appréciée. Et je veux essayer de le résoudre sans ajouter trop de matériel:)

[Mise à jour 2010-03-31]

Je l'ai maintenant testé avec SQL Server 2008 dans les conditions suivantes.

• Table avec deux colonnes (USERID itemid) les deux sont Int
• index en cluster sur les deux colonnes
• Ajout ~ 180 articles pour 800,000 utilisateurs - Total de 144 millions de lignes
• ram Numéroté 4gb pour le serveur SQL
• ordinateur portable Dual Core 2,66 GHz
• disque SSD
• Utilisez un SqlDataReader pour lire tous de itemid dans une liste
• Boucle sur tous les utilisateurs

Si je lance un fil il est en moyenne sur 0,2 seconde. Lorsque j'ajoute un second fil il va jusqu'à 0,4 secondes, ce qui est toujours ok. A partir de là les résultats sont en baisse. L'ajout d'un troisième fil apporte beaucoup de requêtes jusqu'à 2 seonds. Un quatrième fil, jusqu'à 4 secondes, une cinquième pointes certaines des requêtes jusqu'à 50 secondes.

La CPU est toiture alors que ce qui se passe, même sur un fil. Mon application de test prend certains en raison de la boucle rapide et sql le reste.

Ce qui me conduit à la conclusion qu'il ne sera pas l'échelle très bien. Au moins pas sur mon matériel testé. Y at-il des moyens d'optimiser la base de données, le stockage dire un tableau de int années par utilisateur au lieu d'un enregistrement par article. Mais ce qui rend plus difficile de supprimer des éléments.

[Mise à jour 2010-03-31 # 2]

Je l'ai fait un test rapide avec les mêmes données mettant sous forme de bits dans les fichiers de mémoire mappées. Il est bien meilleur. Six fils rendements temps d'accès entre 0,02 s et 0.06s. Purement mémoire liée. Les fichiers mis en correspondance ont été mis en correspondance par un processus, et accessibles par six autres simultanément. Et comme la base sql a 4gb, les fichiers sur le disque ont 23Mo.

Answer 1

Après beaucoup de tests je me suis retrouvé à l'aide de la mémoire mappée fichiers, en les marquant avec le bit clairsemé (NTFS), en utilisant le code NTFS Sparse fichiers avec C # .

Wikipedia a une explication sur un clairsemée est.

Les avantages de l'utilisation d'un fichier rares est que je n'ai pas se soucier de ce que vont mes numéros d'identification sont. Si je n'écris que ids entre 2006000000 et 2010999999, le fichier n'attribuera 625.000 octets de 250.750.000 décalage dans le fichier . Tout l'espace jusqu'à ce décalage est non alloué dans le système de fichiers. Chaque id est stocké comme un bit de jeu dans le fichier. Sorte d'traité comme un tableau de bits. Et si la séquence id change brusquement, il attribuera dans une autre partie du fichier.

Afin de récupérer l'ID de sont définies, je peux effectuer un appel d'OS pour obtenir les parties affectées du fichier clairsemé, puis-je vérifier chaque bit dans ces séquences. vérifier si un identifiant aussi particulier est défini est très rapide. Si elle tombe en dehors des blocs attribués, alors il est pas là, si elle tombe à l'intérieur, il est simplement un octet lu et un chèque de masque de bits pour voir si le bit correct est réglé.

Donc, pour le scénario particulier où vous avez beaucoup d'id que vous voulez vérifier avec autant de vitesse que possible, c'est la façon la plus optimale que j'ai trouvé à ce jour.

Et la bonne nouvelle est que les fichiers de mémoire mappée peuvent être partagées avec Java et (ce qui est avéré être quelque chose nécessaire). Java supporte également la mémoire mappée fichiers sous Windows, et mettre en œuvre la logique de lecture / écriture est assez trivial.

Answer 2

Je pense vraiment que vous devriez essayer une base de données bien avant de prendre votre décision. Quelque chose comme ce sera difficile de maintenir à long terme. Votre base d'utilisateurs est en fait assez petit. SQL Server doit être capable de gérer ce dont vous avez besoin sans aucun problème.

Answer 3

2000 utilisateurs est pas trop mal, mais avec 10 mil articles connexes, vous devriez vraiment envisager de mettre cela dans une base de données. BDs font tout le stockage, la persistance, l'indexation, la mise en cache, etc. que vous avez besoin et ils fonctionnent très bien.

Ils permettent également une meilleure évolutivité dans l'avenir. Si vous avez besoin soudainement faire face à deux millions d'utilisateurs et des milliards de paramètres ayant une bonne db en place fera une mise à l'échelle non-question.