c++ corrigé - Conception de structure de données simultanée





corrigés année (10)


La seule façon de le faire est de faire appel à un protocole de concomitance multiversion utilisé dans des bases de données telles qu'oracle / postgresql etc. Cela garantit que les lecteurs ne bloquent pas les lecteurs, les rédacteurs ne bloquent pas les lecteurs, mais les rédacteurs ne bloquent que ceux qui mettre à jour le même morceau de données. Cette propriété des auteurs bloquant le ou les auteurs qui mettent à jour le même élément de données est importante dans le monde de la programmation concurrente, sinon des incohérences entre les données et le système sont possibles. Pour chaque opération d'écriture sur la structure de données, vous prenez un instantané de la structure de données ou au moins la partie des nœuds de structure de données affectée par l'opération d'écriture vers un emplacement différent dans la mémoire avant d'écrire. Ainsi, lorsque l'écriture est en cours, un thread de lecture demande de lire une partie des données de la partie writer, vous vous référez toujours à l'instantané le plus récent et parcourez cet instantané, fournissant ainsi une vue cohérente des données à tous les lecteurs. Les instantanés sont coûteux car ils consomment plus de mémoire, mais oui pour votre exigence donnée, cette technique est la bonne à suivre. Et oui, utilisez des verrous (mutex / sémaphore / spinlock) pour protéger l'opération d'écriture des autres threads d'écriture / processus ayant besoin de mettre à jour la même donnée.

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.




Eh bien, pour être sûr, vous allez devoir verrouiller quelque chose à un moment donné. Une chose importante est de s'assurer que les objets dans votre référentiel peuvent être verrouillés séparément de la structure du dépôt elle-même: c'est-à-dire ne pas avoir un lien _next ou quoi que ce soit dans les données que vous stockez. De cette façon, les opérations de lecture peuvent verrouiller le contenu des objets sans bloquer la structure du référentiel.

L'insertion efficace est facile: liste liée, tableaux non triés, hashtables tout fonctionne bien. La suppression efficace est plus difficile car cela implique de trouver la chose supprimée dans le dépôt. Howerver, pour la simplicité et la rapidité, une liste liée est un bon choix. Les suppressions peuvent-elles être reportées pour les périodes non occupées et les éléments simplement marqués comme "inactifs"? Alors le coût de trouver / supprimer n'est pas si limitant.

Vous allez quand même avoir des problèmes avec traversal. Tout ce que vous pouvez faire est de verrouiller et de prendre un instantané de ce qui doit être traversé, puis vérifier les changements après que l'instantané a été regardé. Problème difficile ...




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.




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.




Personnellement, j'aime beaucoup les structures de données immuables et persistantes dans des situations très concurrentes. Je n'en connais pas spécialement pour C ++, mais Rich Hickey a créé d'excellentes structures de données immuables (et incroyablement rapides) en Java pour Clojure . Spécifiquement: vecteur, hashtable et hashset. Ils ne sont pas trop difficiles à mettre en communication, alors vous pouvez envisager l'un d'entre eux.

Pour élaborer un peu plus, les structures de données immuables persistantes résolvent vraiment beaucoup de problèmes associés à la concurrence. Parce que la structure de données elle-même est immuable, il n'y a pas de problème avec plusieurs threads en lecture / itération simultanément (tant qu'il s'agit d'un const itérateur). "Ecrire" peut aussi être asynchrone car il n'écrit pas vraiment à la structure existante mais plutôt crée une nouvelle version de cette structure qui inclut le nouvel élément. Cette opération est rendue efficace ( O (1) dans toutes les structures de Hickey) par le fait que vous ne copiez pas tout. Chaque nouvelle version partage la majeure partie de sa structure avec l'ancienne version. Cela rend les choses plus efficaces sur le plan de la mémoire, tout en améliorant considérablement les performances par rapport à la simple technique de copie à l'écriture.

Avec des structures de données immuables, le seul moment où vous avez réellement besoin de synchroniser consiste à écrire réellement dans une cellule de référence. Puisque l'accès à la mémoire est atomique, même celui-ci peut généralement être verrouillé. Le seul inconvénient ici est que vous pourriez perdre des données entre les threads (conditions de course). La structure de données ne sera jamais corrompue en raison de la simultanéité, mais cela ne signifie pas que des résultats incohérents sont impossibles dans les situations où deux threads créent une nouvelle version de la structure basée sur un seul ancien et tentent d'écrire leurs résultats. "gagner" et les changements de l'autre seront perdus). Pour résoudre ce problème, vous devez avoir un verrou pour les "opérations d'écriture", ou utiliser une sorte de STM . J'aime la deuxième approche pour la facilité d'utilisation et le débit dans les systèmes à faible collision (les écritures sont idéalement non bloquantes et les lectures ne bloquent jamais ), mais l'une fonctionnera.

Vous avez posé une question difficile, pour laquelle il n'y a pas vraiment de bonne réponse. Les structures de données à accès simultané sont difficiles à écrire, en particulier lorsqu'elles doivent être modifiables. Les architectures totalement sans verrou sont prouvées impossibles en présence d'un état partagé, vous pouvez donc vouloir abandonner cette exigence. Le mieux que vous pouvez faire est de minimiser le verrouillage requis, d'où les structures de données immuables.




Je suis un peu en retard à la fête. Mais si quelqu'un est toujours à la recherche d'une solution pratique à ce problème et qu'ils n'ont pas encore décidé sur un serveur, permettez-moi de suggérer Google App Engine . Leur magasin de données est optimisé pour ce type d'exigences.




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.




Toutes mes excuses pour la double réponse ...

Puisque les écritures sont assez rares, vous devriez vraiment envisager d'utiliser STM au lieu de verrouiller. STM est une forme de verrouillage optimiste, ce qui signifie qu'il est fortement biaisé dans les performances vers des systèmes sans collision (moins d'écritures). En revanche, le verrouillage pessimiste (verrouillage-écriture-déverrouillage) est optimisé pour les systèmes à collision lourde (c'est-à-dire beaucoup d'écritures). Le seul problème avec STM est qu'il exige presque que vous utilisiez des structures de données immuables dans les cellules TVar, sinon l'ensemble du système tombe en panne. Personnellement, je ne pense pas que ce soit un problème car une structure de données immuable décente va être aussi rapide qu'une structure mutable (voir mon autre réponse), mais cela vaut la peine d'être considérée.




J'aime le discours de Rob Pike: La simultanéité n'est pas le parallélisme (c'est mieux!) (slides) (talk)

Rob parle habituellement de Go et aborde généralement la question de la concurrence et du parallélisme dans une explication visuelle et intuitive! Voici un bref résumé:

Tâche: Brûlons une pile de manuels de langues obsolètes! Un à la fois!

Concurrence: Il y a beaucoup de décompositions simultanées de la tâche! Un exemple:

Parallélisme: La configuration précédente se produit en parallèle s'il y a au moins 2 spermophiles travaillant en même temps ou non.





c++ data-structures concurrency