[c++] Conception de structure de données simultanée



Answers

Les listes liées sont définitivement la réponse ici. Insertion et suppression dans O (1), itération d'un nœud à l'autre dans O (1) et stabilité à travers les opérations. std::list garantit tout cela, y compris que tous les itérateurs sont valides sauf si l'élément est retiré de la liste (ceci inclut les pointeurs et les références aux éléments). Pour le verrouillage, vous pouvez simplement envelopper la liste dans une classe de verrouillage, ou vous pouvez écrire votre propre classe de liste (vous ne pourrez pas utiliser std::list dans ce cas qui supporte le verrouillage basé sur un nœud - par exemple vous pouvez verrouiller Certaines zones de la liste peuvent être utilisées pendant que d'autres threads effectuent des opérations sur des zones différentes.Cependant vous dépendez largement du type d'accès simultané auquel vous vous attendez - si plusieurs opérations sur différentes parties de la liste sont vraiment communes, écrivez les vôtres, mais rappelez-vous que vous allez mettre un objet mutex dans chaque nœud, ce qui n'est pas efficace dans l'espace.

Question

J'essaie de trouver la meilleure structure de données pour un serveur C ++ à haut débit. La structure de données sera utilisée pour stocker n'importe quoi, de quelques à plusieurs millions d'objets, et aucun tri n'est requis (bien qu'une clé de tri unique puisse être fournie à un coût très bas).

Les exigences sont les suivantes: insertion efficace, idéalement O (1), retrait modérément efficace et traversée efficace. Il n'a pas besoin de supporter une opération de recherche (autre que ce qui pourrait être nécessaire pour la suppression).

La torsion est qu'il doit être thread safe par rapport aux modifications tandis que d'autres threads sont en train d'énumérer la structure de données. Cela signifie qu'un simple arbre rouge-noir ne fonctionne pas, car un thread ne peut pas insérer un élément (et effectuer les rotations d'arbre nécessaires) sans gâcher les curseurs détenus par d'autres threads.

Il n'est pas acceptable d'utiliser un verrou de lecture / écriture et différer les opérations d'écriture jusqu'à ce que tous les lecteurs aient terminé, car les opérations de lecture peuvent avoir une longue durée de vie. Peu importe si les insertions qui se produisent pendant qu'il y a un lecteur sont visibles ou non pour ce lecteur.

L'empreinte de la mémoire est également très importante, et la petite est évidemment meilleure!

Quelles suggestions sont là?

Réponse aux commentaires:

Merci pour les réponses.

Non, les insertions ne peuvent pas invalider les itérateurs existants. Les itérateurs peuvent ou non voir la nouvelle insertion, mais ils doivent voir tout ce qu'ils auraient vu si l'insertion n'avait pas eu lieu.

La suppression est nécessaire, mais en raison de règles de niveau supérieur, je peux garantir qu'un itérateur ne sera jamais arrêté sur un élément qui peut être supprimé.

Le verrouillage par nœud pour un curseur aurait un impact trop important sur les performances. Il peut y avoir un certain nombre de threads à lire en même temps, et n'importe quel type de point mémoire que plusieurs threads utilisent dans un verrou tue la bande passante de la mémoire (comme nous l'avons découvert à la dure!). Même un nombre simple de lecteurs avec plusieurs threads appelant InterlockedIncrement échoue à l'échelle proprement.

Je suis d'accord qu'une liste chaînée est probablement la meilleure approche. Les suppressions sont rares, donc payer la pénalité de mémoire pour les pointeurs arrière pour supporter O (1) delete est coûteux et nous pouvons les calculer séparément à la demande et puisque les suppressions ont tendance à être des opérations par lots.

Heureusement, l'insertion dans une liste liée ne nécessite aucun verrouillage pour les lecteurs, tant que les pointeurs sont mis à jour dans le nœud inséré avant que le pointeur de tête ne soit modifié.

L'idée de verrouillage-copie-déverrouillage est intéressante. La quantité de données impliquées est trop importante pour que cela fonctionne par défaut pour les lecteurs, mais elle pourrait être utilisée pour les écrivains lorsqu'ils entrent en collision avec les lecteurs. Un verrou de lecture / écriture protégerait la structure entière, et l'écriture clonerait la structure de données si elle entre en collision avec un lecteur. Les écritures sont beaucoup plus rares que les lectures.




FWIW, c'est trivial à résoudre si vous avez un garbage collector. En F #, par exemple, vous pouvez simplement utiliser une référence mutable à une liste chaînée ou à une carte purement fonctionnelle (arbre binaire équilibré) sans aucun verrou. Cela fonctionne parce que les structures de données sont immuables et l'écriture d'une référence (pour mettre à jour après une écriture) est atomique afin que les lecteurs simultanés soient assurés de voir l'ancienne ou la nouvelle structure de données mais jamais la corruption. Si vous avez plusieurs écrivains, vous pouvez les sérialiser.

Cependant, c'est beaucoup plus difficile à résoudre en C ++ ...




Je pense que la liste liée devrait répondre à vos besoins. Notez que vous ne pouvez verrouiller que les nœuds qui sont en cours de modification (supprimés / ajoutés) afin que les lecteurs puissent travailler en parallèle avec les rédacteurs. Cette approche nécessite un verrou par noeud de liste lié, mais ce n'est pas un must. Vous pouvez avoir un nombre limité de verrous, puis plusieurs nœuds seront affectés au même verrou. C'est-à-dire, ayant un tableau de N verrous et des noeuds numérotés 0..M, vous pouvez utiliser le verrou (NodeId% N) pour verrouiller ce noeud. Ceux-ci peuvent être des verrous en lecture-écriture, et en contrôlant le nombre de verrous, vous pouvez contrôler la quantité de parallélisme.




Je ne suis pas sûr que quelqu'un l'ait mentionné, mais je m'inspirerais du ConcurrentHashMap de Java. Il offre la traversée, la récupération et l'insertion sans verrouillage ni attente. Le seul verrou se produit une fois que vous avez trouvé un ensemble de données correspondant à la clé de hachage et que vous traversez ce compartiment (c'est-à-dire que vous verrouillez SEULEMENT le compartiment et non la carte de hachage). "Au lieu d'un seul verrou de collection, ConcurrentHashMap utilise un pool fixe de verrous qui forment une partition sur la collection de compartiments."

Vous pouvez trouver plus de détails sur la mise en œuvre réelle ici . Je crois que toutes les choses montrées dans l'implémentation peuvent être aussi facilement faites avec C ++.

Alors passons par votre liste d'exigences:

1. High throughput. CHECK
2. Thread safe. CHECK
3. Efficient inserts happen in O(1). CHECK
4. Efficient removal (with no data races or locks). CHECK
5. VERY efficient traversal. CHECK
6. Does not lock or wait. CHECK
7. Easy on the memory. CHECK
8. It is scalable (just increase the lock pool). CHECK

Voici un exemple d'entrée de carte:

protected static class Entry implements Map.Entry {
    protected final Object key;
    protected volatile Object value;
    protected final int hash;
    protected final Entry next;
    ...
}

Notez que la valeur est volatile, donc lorsque nous supprimons une entrée, nous définissons la valeur sur NULL, qui est automatiquement visible par tout autre thread qui tente de lire la valeur.




Vous avez 3 types de tâches:

  1. itération (lente)
  2. insertion (rapide)
  3. suppression (rapide)

Si la cohérence est suffisante, gardez une trace du nombre de tâches d'itération actives.

Si les tâches d'itération sont actives et qu'une nouvelle tâche d'insertion ou de suppression arrive en file d'attente, ces tâches seront traitées ultérieurement (mais vous pouvez renvoyer l'appelant immédiatement)

Dès la dernière itération si le processus terminé est en file d'attente, insère et supprime.

Si une requête d'itération intervient alors que des insertions ou des suppressions sont en attente, mettez-la en file d'attente.

Si une requête d'itération arrive alors qu'il n'y a que des itérations en cours, faites la passer et itérez.

Vous devez toujours écrire l'itération pour être aussi rapide que possible en faisant une copie des données que vous itérez et ensuite traiter ces données dans le client si le traitement des données prend beaucoup plus de temps que l'itération elle-même.

J'implémenterais la collection principale avec une hashtable ou stl: map pourrait même être assez rapide. Les demandes d'insertion / suppression peuvent être mises en file d'attente dans une liste.




Links