Je suis élaboré sur un problème qui me semble difficile et je ne m'attends pas à une solution simple, mais peut-être qu'il y a des pratiques éprouvées ou une lecture supplémentaire qui pourrait rendre cela plus facile. Je suis sûr que le problème général apparaît dans de nombreuses applications (par exemple, la collecte des ordures ou des bases de données transactionnelles).
Mon application a un graphique (un DAG si cela compte) qui est traversé simultanément par plusieurs threads. Certaines d'entre elles essaient simplement de trouver certains nœuds ou de récupérer un sous-graphique, d'autres peuvent changer la structure du graphique.
La stratégie que je veux implémenter est qu'un thread de lecture effectuera toute sa opération sur un "instantané" du graphique, i. e. Voir la structure comme il était à un moment donné.
Mon plan actuel consiste à configurer quelque chose de similaire à la version de rangée dans les DBS transactionnels, i. e. Un fil de lecture obtient d'abord un numéro de version actuel, puis ne visite que des nœuds et des bords de graphes qui ont ce numéro de version ou plus tôt. Les threads d'écriture mettraient alors un numéro de version incrémenté sur les nouveaux éléments (les éléments modifiés seraient clonés en premier), ce qui les rend invisibles pour les lecteurs en cours d'exécution. Un fil d'écriture peut alors "commettre" sa nouvelle version lorsqu'il a terminé avec succès et que les lecteurs "libèrent" leur numéro de version, faisant des éléments supprimés éligibles à la suppression.
Cette stratégie est toujours sommaire et présente un certain nombre de problèmes non résolus tels que l'accès à l'écriture simultanée, mais cela semble généralement être une route viable à aller.
3 Réponses :
Une alternative utiliserait Ils sont comme un fichier journal, la version modifiée est toujours appendend la dernière les rendant immuables, car leurs opérations ne mettent pas (visiblement) la structure en place, mais cédez toujours une nouvelle structure mise à jour. Langages de programmation tels que Clojure récemment polarisé cette approche (du moins pour moi).
@DFA, +1 Je pense que c'est ce qu'il obtient avec les révisions du nœud. L'incorporation de nombreux ensembles de nœuds / révisions constituant la totalité de la structure à une révision globale donnée constituerait un bon point de départ pour une révision complète de la structure.
Merci, cela semble très intéressant. Je n'ai pas compris tout cela, encore (par exemple, qu'en est-il des suppressions?), Mais je vais juste travailler à travers elle. Cela ressemble parfaitement à ce que je tire. PS: Ajout d'un lien vers l'article Wikipedia
Votre approche semble être sonore pour moi ...
Qu'est-ce que vous pourriez avoir des problèmes avec cependant, c'est assurer Si un écrivain modifie le sous-script A et un autre écrivain modifie un sous-script distinct B, mais d'autres opérations de lecture / écriture se produisent sur le sous-programme C où A et B sont en C, alors vous devez vous assurer que la version du sous-graphique C aligne correctement avec les versions. de b et a.
Je suggérerais un schéma de verrouillage dans le DAG qui intègre le verrouillage sous-graphique pour une lecture multiple / une seule écriture unique d'une racine donnée. Vous aurez besoin de grep le graphique des dépendances cycliques cependant pour vous assurer de ne pas entrer dans un état de famine / impasse dans le graphique.
Si votre graphique est distribué ou votre accès simultané a latence alors votre système de transaction sera plus difficile à mettre en œuvre et nécessitera probablement des garanties supplémentaires.
Votre approche de versions sonne bien à condition que vos dispositions de verrouillage garantissent, dans tous les cas qu'un ensemble de révisions pour les nœuds à tout moment, il représente un état intégral du graphique. L'ensemble de nœuds et de révisions à T = {N0, N1, N2, N3} et une cyclature de révision simultanée des sous-graphes poseront les maux de tête pour maintenir l'ensemble des révisions et des nœuds à T Integral.
Merci pour tous les conseils utiles!
Eh bien, je pensais que je serais intelligent et Google plusieurs mots-clés, pour trouver une littérature. Le premier résultat ... Cette question était-elle.
Donc, il n'y a pas trop sur ce sujet! Intéressant. Je pensais juste que je partagerais.
Aiden Bell et DFA ont toutes deux des réponses très approfondies, je ne vais donc pas essayer de les toper. :) Mais je ferai une observation sur la qualité du DAG du graphique et de l'accès en écriture simultanée. Cela vous aurait peut-être déjà eu lieu, mais bon. :)
Vous pouvez autoriser des threads simultanés sans avoir à vous soucier d'un écrivant d'une nouvelle modification d'un autre en supposant simplement que, à tout moment, le nœud habité par un fil d'écriture et tous les enfants de ce nœud, sont "verrouillés". par ce fil d'écriture particulier . Je trouve plus facile à visualiser cela avec un arbre (qui est également un dag, évidemment). Tout fil d'écriture a essentiellement verrouillé un sous-arbre particulier, mais également, nous pouvons maintenant dire que des arbres froids, ou des nœuds ancêtres, sont joyeusement écrits.
Un dag plus complexe (où un nœud peut avoir plusieurs parents, en particulier) aura, en effet, beaucoup de sous-arbres qui se chevauchent, et il ne peut donc pas y avoir tellement de liberté, mais la règle s'applique toujours: tout Le nœud qui n'est pas habité, ni l'enfant d'un nœud habitée par un filetage en écriture, peut être considéré comme en écriture.
Évidemment, il pourrait y avoir beaucoup de facteurs pourquoi l'idée ci-dessus n'est pas utile, mais si plusieurs threads d'écriture se dirigent souvent dans des directions "différentes", il peut alléer certaines des exigences nécessaires pour le faire filer-sécurité. < / p>
J'espère que cela vous aide!
-agor
Oui, cette stratégie de verrouillage est quelque chose que j'ai déjà eu à l'esprit et que Aiden Bell lui a également suggéré. Cependant, la mise en œuvre n'est pas vraiment triviale. Je dois laisser des threads travailler sous un nœud verrouillé qu'ils ne peuvent pas écrire. Il y aurait plusieurs façons de le faire, mais tout ce que je pouvais penser à impliquer de monter ou de descendre le graphique, de propager la serrure ou de la vérification d'une. Cela signifie que je reçois un nouvel ensemble de problèmes de concurrence. E. g., Si je monte sur le graphique du nœud, je veux écrire à, vérifier les serrures, je dois m'assurer qu'un verrou n'est pas défini quand je viens de passer, mais avant que j'écris.
Je viens de noter que, comme je posais cette question, il sera difficile d'accepter toute réponse. Désolé mon mauvais. Je vais voir ce qui arrive et accepte juste l'un des postes les plus utiles.
Cependant, c'est une question très intéressante: +1
Le graphique a-t-il un nœud racine? Est-ce un arbre? Est le répertoire comme?