Voor .NET 4.0, als we de Dictionary-klasse in een multithreaded omgeving moesten gebruiken, hadden we geen andere keuze dan zelf thread-synchronisatie te implementeren om de threads veilig te houden.
Veel ontwikkelaars hebben zeker een vergelijkbare thread-veilige oplossing geïmplementeerd, hetzij door een geheel nieuw thread-veilig woordenboektype te creëren, hetzij door simpelweg een Dictionary-object in een klasse te encapsuleren en een vergrendelingsmechanisme toe te voegen aan alle methoden, wat we "Dictionary + Locks" noemen.
Maar nu hebben we ConcurrentDictionary. De thread-safe beschrijving van de Dictionary-klasse documentatie op MSDN stelt dat als je een thread-veilige implementatie nodig hebt, je ConcurrentDictionary moet gebruiken.
Nu we een thread-veilige woordenboekklasse hebben, hoeven we die niet meer zelf te implementeren. Geweldig, nietwaar?
Oorsprong van het probleem
Sterker nog, ik heb CocurrentDictionary maar één keer eerder gebruikt, in mijn test om de responsiviteit te testen. Omdat het goed presteerde in de toetsen, heb ik het meteen vervangen door mijn klas, wat tests gedaan, en toen ging er iets mis.
Dus, wat ging er mis? Zei je niet draadveilig?
Na meer testen vond ik de oorzaak van het probleem. Maar om de een of andere reden bevat MSDN versie 4.0 geen beschrijving van de GetOrAdd-methodehandtekening die vereist dat je een delegate-typeparameter moet doorgeven. Na het bekijken van versie 4.5 vond ik deze notitie:
Als je GetOrAdd gelijktijdig aanroept op verschillende threads, kan addValueFactory meerdere keren worden aangeroepen, maar het sleutel/waarde-paar wordt mogelijk niet bij elke aanroep aan het dictionary toegevoegd.
Dat is het probleem waar ik tegenaan liep. Omdat het niet eerder in de documentatie werd beschreven, moest ik meer testen om het probleem te bevestigen. Natuurlijk heeft het probleem waar ik tegenaan loop te maken met mijn gebruik; over het algemeen gebruik ik het woordenboektype om wat data te cachen:
Deze data is erg traag om te genereren;
Deze data kan slechts één keer worden aangemaakt, omdat de tweede creatie een uitzondering zal veroorzaken, of meerdere creaties kunnen leiden tot bronlek, enzovoort;
Ik had een probleem met de tweede aandoening. Als beide threads ontdekken dat een stuk data niet bestaat, wordt het één keer aangemaakt, maar slechts één resultaat wordt succesvol opgeslagen. En de andere dan?
Als het proces dat je aanmaakt een uitzondering geeft, kun je try: Catch (niet elegant genoeg, maar het lost het probleem op). Maar wat als een grondstof wordt gecreëerd en niet wordt gerecycled?
Je zou kunnen zeggen dat een object wordt aangemaakt en als garbage collected wordt opgenomen als het er niet meer naar verwezen wordt. Overweeg echter wat er zou gebeuren als de hieronder beschreven situatie zich voordoet:
Genereer code dynamisch met Emit. Ik heb deze aanpak gebruikt in een Remote-framework en alle implementaties in een assembly geplaatst die niet gerecycled kon worden. Als een type twee keer wordt gemaakt, zal het tweede altijd bestaan, zelfs als het nooit is gebruikt.
Maak direct of indirect een thread aan. We moeten bijvoorbeeld een component bouwen die een propriëtaire thread gebruikt om asynchrone berichten te verwerken en afhankelijk is van de volgorde waarin ze worden ontvangen. Wanneer de component wordt geïnstantieerd, wordt er een thread aangemaakt. Wanneer deze componentinstantie wordt vernietigd, wordt de thread ook beëindigd. Maar als we de verwijzing naar het object verwijderen nadat we de component hebben vernietigd, eindigt de thread om de een of andere reden niet en houdt de referentie naar het object vast. Als de draad dan niet sterft, wordt het object ook niet gerecycled.
Voer een P/Invoke-operatie uit. Eis dat het aantal gesloten tijden voor het ontvangen handvat gelijk moet zijn aan het aantal openingen.
Zeker, er zijn veel vergelijkbare situaties. Bijvoorbeeld, een dictionary-object houdt een verbinding met een service op een externe server vast, die slechts één keer kan worden opgevraagd, en als deze een tweede keer wordt opgevraagd, zal de andere service denken dat er een fout is opgetreden en dit in het logboek loggen. (Bij een bedrijf waar ik werkte, waren er enkele wettelijke sancties voor deze aandoening.) ）
Het is dus makkelijk te zien dat Dictionary + Locks niet overhaast vervangen kan worden door ConcurrentDictionary, zelfs als de documentatie zegt dat het thread-veilig is.
Analyseer het probleem
Begrijp je het nog steeds niet?
Het is waar dat dit probleem mogelijk niet ontstaat onder de Dictionary + Locks-benadering. Aangezien dit afhangt van de specifieke implementatie, laten we dit eenvoudige voorbeeld bekijken:
In de bovenstaande code houden we de vergrendeling op het woordenboek vast voordat we beginnen met het opvragen van de sleutelwaarde. Als het gespecificeerde sleutel-waardepaar niet bestaat, wordt het direct aangemaakt. Tegelijkertijd, omdat we al een lock op dat woordenboek hebben, kunnen we sleutel-waarde paren direct aan het woordenboek toevoegen. Vervolgens wordt de woordenboekvergrendeling losgemaakt en het resultaat teruggegeven. Als twee threads tegelijkertijd dezelfde sleutelwaarde opvragen, voltooit de eerste thread die de dictionary lock krijgt de creatie van het object, en wacht de andere thread op de voltooiing van deze creatie en krijgt na het krijgen van de dictionary lock het resultaat van de gecreëerde sleutelwaarde.
Dat is goed, toch?
Echt niet! Ik denk niet dat het parallel maken van een object zoals dit, waarbij uiteindelijk maar één wordt gebruikt, niet het probleem veroorzaakt dat ik heb beschreven.
De situatie en het probleem dat ik probeer uit te leggen, zijn niet altijd reproduceerbaar; in een parallelle omgeving kunnen we simpelweg twee objecten maken en er één weggooien. Dus, hoe vergelijken we precies Dictionary + Locks en ConcurrentDictionary?
Het antwoord is: het hangt af van de slotgebruiksstrategie en hoe het woordenboek wordt gebruikt.
Spel 1: Tegelijkertijd hetzelfde object creëren
Laten we eerst aannemen dat een object twee keer kan worden aangemaakt, dus wat gebeurt er als twee threads dit object tegelijkertijd aanmaken?
Ten tweede, hoe lang besteden we aan soortgelijke creaties?
We kunnen simpelweg een voorbeeld maken waarbij het instantieren van een object 10 seconden duurt. Wanneer de eerste thread het object 5 seconden later aanmaakt, probeert de tweede implementatie de GetOrAdd-methode aan te roepen om het object te krijgen, en omdat het object nog steeds niet bestaat, begint het ook het object te maken.
In deze situatie werken 2 CPU's parallel gedurende 5 seconden, en wanneer de eerste thread klaar is, moet de tweede thread nog 5 seconden blijven draaien om de constructie van het object te voltooien. Wanneer de tweede thread het object heeft gebouwd, ontdekt deze dat een object al bestaat en kiest het ervoor het bestaande object te gebruiken en het nieuw aangemaakte object direct weg te gooien.
Als de tweede thread gewoon wacht en de tweede CPU doet ander werk (andere threads of applicaties draaien, wat energie besparen), krijgt hij het gewenste object na 5 seconden in plaats van 10 seconden.
Dus, onder deze omstandigheden wint Dictionary + Locks een klein spel.
Spel 2: Bezoek verschillende objecten parallel
Nee, de situatie die je noemde is helemaal niet waar!
Nou, het bovenstaande voorbeeld is wat eigenaardig, maar het beschrijft het probleem, alleen is dit gebruik extremer. Dus stel je voor wat er gebeurt als de eerste thread een object aanmaakt, en de tweede thread moet toegang krijgen tot een ander key-value object, en dat key-value object bestaat al?
In ConcurrentDictionary maakt het lock-free ontwerp het lezen erg snel omdat er geen lock op het lezen is. In het geval van Dictionary + Locks zal de leesoperatie wederzijds exclusief zijn, zelfs als het een totaal andere sleutel is, wat de leesoperatie uiteraard vertraagt.
Op deze manier trok ConcurrentDictionary een spel terug.
Opmerking: Hier denk ik dat je verschillende concepten begrijpt, zoals Bucket/Node/Entry in de woordenboekklasse; zo niet, dan wordt aanbevolen om Ofir Makmal's artikel "Understanding Generic Dictionary in-depth" te lezen, waarin deze concepten goed worden uitgelegd.
Het derde spel van het spel: lees meer en schrijf single
Wat gebeurt er als je Multiple Readers en Single Writer gebruikt in plaats van een volledige lock op het woordenboek in Dictionary + Locks?
Als een thread een object aanmaakt en een upgradebare lock vasthoudt totdat het object is aangemaakt, wordt de lock geüpgraded naar een schrijflock, waarna de leesoperatie parallel kan worden uitgevoerd.
We kunnen het probleem ook oplossen door een leesoperatie 10 seconden ongebruikt te laten. Maar als er veel meer lezingen dan schrijfacties zijn, zullen we merken dat ConcurrentDictionary nog steeds snel is omdat het reads zonder vergrendeling toepast.
Het gebruik van ReaderWriterLockSlim voor woordenboeken maakt het lezen erger, en het wordt over het algemeen aanbevolen om Full Lock voor woordenboeken te gebruiken in plaats van ReaderWriterLockSlim.
Dus, onder deze omstandigheden, won ConcurrentDictionary weer een spel.
Opmerking: ik heb de YieldReaderWriterLock- en YieldReaderWriterLockSlim-klassen in eerdere artikelen behandeld. Door gebruik te maken van deze lees-schrijfvergrendeling is de snelheid aanzienlijk verbeterd (nu geëvolueerd tot SpinReaderWriterLockSlim) en kunnen meerdere lezingen parallel worden uitgevoerd met weinig tot geen effect. Hoewel ik deze methode nog steeds gebruik, zou een lockless ConcurrentDictionary natuurlijk sneller zijn.
Spel 4: Voeg meerdere sleutel-waarde paren toe
De confrontatie is nog niet voorbij.
Wat als we meerdere sleutelwaarden moeten optellen, en ze botsen niet allemaal en in verschillende buckets worden toegewezen?
In het begin was deze vraag vreemd, maar ik deed een test die niet helemaal paste. Ik gebruikte een woordenboek van het type <int, int> en de constructiefabriek van het object gaf direct een negatief resultaat als sleutel terug.
Ik verwachtte dat ConcurrentDictionary het snelst zou zijn, maar het bleek het langzaamst. Dictionary + Locks daarentegen presteert sneller. Waarom is dat?
Dit komt doordat ConcurrentDictionary knooppunten toewijst en in verschillende buckets plaatst, wat geoptimaliseerd is om te voldoen aan het lock-free ontwerp voor leesoperaties. Bij het toevoegen van key-value-items wordt het proces van het creëren van een node echter duur.
Zelfs onder parallelle omstandigheden kost het toewijzen van een Node-lock nog steeds meer tijd dan het gebruik van een volledige lock.
Dus, Dictionary + Locks wint dit spel.
Het vijfde spel spelen: De frequentie van leesoperaties is hoger
Eerlijk gezegd, als we een afgevaardigde hadden die snel objecten kon instantiëren, hadden we geen woordenboek nodig. We kunnen de afgevaardigde direct bellen om het object op te halen, toch?
In feite is het antwoord ook dat het afhangt van de situatie.
Stel je voor dat het sleuteltype een string is en padkaarten bevat voor verschillende pagina's in de webserver, en de bijbehorende waarde is een objecttype dat het record bevat van de huidige gebruikers die de pagina benaderen en het aantal bezoeken aan de pagina sinds de server is gestart.
Het creëren van zo'n object gebeurt bijna onmiddellijk. En daarna hoef je geen nieuw object meer aan te maken, alleen de opgeslagen waarden te wijzigen. Het is dus mogelijk om het maken van een weg twee keer toe te staan totdat slechts één instantie wordt gebruikt. Omdat ConcurrentDictionary echter langzamer Node-bronnen toewijst, zal het gebruik van Dictionary + Locks leiden tot snellere aanmaaktijden.
Dus, met dit voorbeeld is het heel bijzonder, we zien ook dat Dictionary + Locks beter presteert onder deze omstandigheden, omdat het minder tijd kost.
Hoewel de node allocatie in ConcurrentDictionary langzamer is, heb ik niet geprobeerd 100 miljoen data-items erin te stoppen om de tijd te testen. Want dat kost natuurlijk veel tijd.
Maar in de meeste gevallen wordt een data-item, zodra het is aangemaakt, altijd gelezen. Hoe de inhoud van het data-item verandert is een ander verhaal. Het maakt dus niet uit hoeveel milliseconden het duurt om een data-item te maken, want reads zijn sneller (slechts een paar milliseconden sneller), maar reads gebeuren vaker.
Dus, ConcurrentDictionary won het spel.
Spel 6: Maak objecten die verschillende tijden verbruiken
Wat gebeurt er als de tijd die het kost om verschillende data-items te maken varieert?
Maak meerdere data-items die verschillende tijden verbruiken en voeg ze parallel toe aan het woordenboek. Dit is het sterkste punt van ConcurrentDictionary.
ConcurrentDictionary gebruikt verschillende vergrendelingsmechanismen om data-items gelijktijdig toe te voegen, maar logica zoals beslissen welk slot je gebruikt, een slot aanvragen om de grootte van de emmer te veranderen, enzovoort, helpt niet. De snelheid waarmee data-items in een bak worden gedaan is machinesnel. Wat ConcurrentDictionary echt doet winnen, is het vermogen om objecten parallel te maken.
Maar we kunnen eigenlijk hetzelfde doen. Als het ons niet uitmaakt of we objecten parallel maken, of dat sommige zijn verwijderd, kunnen we een slot toevoegen om te detecteren of het data-item al bestaat, dan het slot losmaken, het data-item aanmaken, erop drukken om het slot te krijgen, opnieuw controleren of het data-item bestaat, en als dat niet zo is, het data-item toevoegen. De code zou er ongeveer zo uit kunnen zien:
* Let op: ik gebruik een woordenboek van het type <int, int>.
In de eenvoudige structuur hierboven presteert Dictionary + Locks bijna even goed als ConcurrentDictionary bij het creëren en toevoegen van data-items in parallelle omstandigheden. Maar er is ook hetzelfde probleem, waarbij sommige waarden gegenereerd kunnen worden maar nooit worden gebruikt.
conclusie
Dus, is er een conclusie?
Op dit moment zijn er nog enkele:
Alle woordenboeklessen zijn erg snel. Ook al heb ik miljoenen data gemaakt, het gaat nog steeds snel. Normaal maken we maar een klein aantal data-items, en er zijn tijdsintervallen tussen reads, waardoor we de tijds-overhead van het lezen van data-items meestal niet merken.
Als hetzelfde object niet twee keer kan worden aangemaakt, gebruik dan ConcurrentDictionary niet.
Als je je echt zorgen maakt over de prestaties, kan Dictionary + Locks nog steeds een goede oplossing zijn. Een belangrijke factor is het aantal data-items dat is toegevoegd en verwijderd. Maar als er veel leesoperaties zijn, is het langzamer dan ConcurrentDictionary.
Hoewel ik het niet heb geïntroduceerd, is er eigenlijk meer vrijheid om het Dictionary + Locks-schema te gebruiken. Je kunt bijvoorbeeld één keer vergrendelen, meerdere data-items toevoegen, meerdere data-items verwijderen, of meerdere keren een query zoeken, enzovoort, en dan de vergrendeling losmaken.
Vermijd in het algemeen ReaderWriterLockSlim als er veel meer lezingen dan geschreven zijn. Woordenboektypen zijn al veel sneller dan het krijgen van een read lock in een read-write lock. Natuurlijk hangt dit ook af van de tijd die wordt verbruikt om een object in een lock te maken.
Dus, ik denk dat de gegeven voorbeelden wat extreem zijn, maar ze laten zien dat het gebruik van ConcurrentDictionary niet altijd de beste oplossing is.
Voel het verschil
Ik heb dit artikel geschreven met de intentie een betere oplossing te zoeken.
Ik probeer al een dieper begrip te krijgen van hoe een specifiek woordenboekvak werkt (nu heb ik het gevoel dat ik heel duidelijk ben).
Je zou kunnen stellen dat Bucket en Node in ConcurrentDictionary heel eenvoudig zijn. Ik deed iets soortgelijks toen ik probeerde een woordenboekles te maken. De reguliere woordenboekklasse lijkt misschien eenvoudiger, maar in feite is het complexer.
In ConcurrentDictionary is elke Node een complete klasse. In de Dictionary-klasse wordt Node geïmplementeerd met een waardetype, en worden alle nodes in een enorme array bewaard, terwijl Bucket wordt gebruikt om in de array te indexeren. Het wordt ook gebruikt in plaats van de eenvoudige verwijzing van een Node naar zijn volgende Node (want als Node van een structtype kan het geen Node van een structtype bevatten).
Bij het toevoegen en verwijderen van een woordenboek kan de Dictionary-klasse niet simpelweg een nieuwe node aanmaken; deze moet controleren of er een index is die een node markeert die is verwijderd, en deze vervolgens hergebruiken. Of "Count" wordt gebruikt om de positie van de nieuwe Node in de array te bepalen. Sterker nog, wanneer de array vol is, dwingt de Dictionary-klasse een groottewijziging af.
Voor ConcurrentDictionary kan een Node worden gezien als een nieuw object. Het verwijderen van een Node is simpelweg het verwijderen van zijn referentie. Het toevoegen van een nieuwe Node kan eenvoudig een nieuwe Node-instantie aanmaken. Het veranderen van de grootte is alleen om conflicten te vermijden, maar het is niet verplicht.
Dus, als de Dictionary-klasse bewust complexere algoritmen gebruikt om ermee om te gaan, hoe zorgt ConcurrentDictionary er dan voor dat het beter presteert in een multithreaded omgeving?
De waarheid is: alle knooppunten in één array plaatsen is de snelste manier om toe te wijzen en te lezen, zelfs als we een andere array nodig hebben om bij te houden waar die data-items gevonden worden. Het lijkt erop dat hetzelfde aantal buckets meer geheugen gebruikt, maar de nieuwe data-items hoeven niet opnieuw toegewezen te worden, er zijn geen nieuwe object-synchronisaties nodig en er vindt geen nieuwe garbage collection plaats. Omdat alles al geregeld is.
Het vervangen van inhoud in een Node is echter geen atomaire bewerking, wat een van de factoren is die de thread onveilig maakt. Omdat knooppunten allemaal objecten zijn, wordt er aanvankelijk een knoop aangemaakt, waarna een aparte referentie wordt bijgewerkt om ernaar te wijzen (atomaire bewerking hier). Dus, de leesdraad kan de woordenboekinhoud lezen zonder lock, en de read moet een van de oude en nieuwe waarden zijn, en er is geen kans om een onvolledige waarde te lezen.
Dus, de waarheid is: als je geen lock nodig hebt, is de Dictionary-klasse sneller bij reads, omdat het de lock is die het lezen vertraagt.
Dit artikel is vertaald uit Paulo Zemeks artikel "Dictionary + Locking versus ConcurrentDictionary" op CodeProject, en sommige statements zullen worden aangepast om begripsredenen.
|
Geplaatst op 13-09-2016 13:33:04
|
|
|
Huisbaas|
Geplaatst op 13-09-2016 13:33:15
|
