[Java] Threadsafe maar toch efficient?

[Verwijderd]

Het threadsafe maken van een applicatie en het toch efficient houden is een moeilijk klusje. Ik zit nu met het volgende probleem:

code:

Hashtable trades;
Hashtable hits;
public Trade getTrade(String id){
return trades.get(id);
}
public void addHit(Hit hit){
hits.add(hit);
}
public void generateAll(){
//loop door de trades en hits structures, verander, verwijder en voeg toe elementen.
}

Nu word 'getTrade' en 'addHit' veel keer per seconden aangeroepen, deze functies zijn en moeten dus efficient blijven. Omdat ze 'alleen data ophalen' hoeven deze niet thread safe te zijn.

Maar 'generateAll()' word 1 keer in het half uur aangeroepen, deze functie manipuleerd de data structures waar 'getTrade' en 'addHit' hun gegevens uit halen. Het kan dus voorkomen dat als 'generateAll' de data structures zit te veranderen 'addHit' of 'getTrade' dezelfde data structures benaderen. Of te wel: een probleem.

Nou kan ik alle 3 methodes voorzien van synchronized keyword:

code:

public synchronized void generateAll(){}

Dan gaat het goed. Maar dat is verre van efficient, want 'getTrade' en 'addHit' en synchronized niet eens nodig, alleen als 'generateAll' word aangeroepen dan komt de synchronized van pas.

Hoe kan ik er tread safe voor zorgen dat 'getTrade' en 'addHit' even wachten als 'generateAll' bezig is met het veranderen/muteren?

[TheNameless]

Kijk eens naar de volgende link: http://java.sun.com/j2se/...rent/locks/Condition.html

Ik denk dat je met behulp van Conditions goed kan oplossen.
IMO krijg je een condition object die aangeeft of er een update gedaan word. Als deze condition waar is, dan moeten de threads die de data willen lezen blocken.

Als de data geupdate is roep je op het Condition object signalAll() aan om aan te geven dat alle threads weer door kunnen gaan met lezen.

Eigenlijk best eenvoudig en logisch

[ Voor 51% gewijzigd door TheNameless op 12-04-2006 14:31 ]

[momania]

Volgens mij kon je dat mooi doen met een tmp lock. (Zoiets als je vaak in threadpool voorbeelden ziet):

Java:

Hashtable trades;
Hashtable hits;

public Trade getTrade(String id){
  return trades.get(id);
}
public void addHit(Hit hit){
  hits.add(hit);
}
public void generateAll(){
  synchonized(trades) {
    synchonized(hits) {
      //loop door de trades en hits structures, verander, verwijder en voeg toe elementen.
    
  }
}

[Soultaker]

@MayaFreak: die Conditions worden gewoon met de object monitor geïmplementeerd dus qua performance win je er niets mee (in tegendeel!).

@momania: dat is net zo unsafe als helemaal geen locking gebruiken (je hoeft ook nooit te wachten want generateAll() is toch de enige methode die ooit probeert te locken). Locking heeft alleen zin als alle functies die een object gebruiken er aan meedoen.

Maar momania's idee om de hashtables afzonderlijk te locken is wel goed; op zo'n manier dus:

Java:

public Trade getTrade(String id){ 
  synchronized(trades) { return trades.get(id); }
} 
public void addHit(Hit hit){ 
  synchronized(hits) { hits.add(hit); }
} 
public void generateAll(){ 
    synchonized(trades) { 
        synchonized(hits) { 
        // ...
        } 
    } 
}

De overhead van het locken blijft dan nog wel bestaan, alleen vertragingen door onnodige contention tussen getTrade() en getHit() worden geëlimineerd. Dat is beter dan op het Trade object locken.

Als je minder overhead wil hebben, moet je in het algemeen minder locken. Dan moet je het locken misschien op een hoger nivo aanpakken, als dat mogelijk is, door bijvoorbeeld meerdere method calls achter elkaar uit te voeren terwijl je de lock vasthoudt. Of dat handig te implementeren is, hangt nogal af van hoe die methoden elders worden aangeroepen; persoonlijk zou ik het niet zo ingewikkeld maken en de kosten van locking gewoon accepteren.

[ Voor 7% gewijzigd door Soultaker op 12-04-2006 15:37 ]

[Infinitive]

Als de generateAll functie nieuwe hashtables maakt (evt. gebaseerd op de oude) en de twee hashtables onafhankelijk zijn (waarbij ik bedoel dat het niet erg is dat een thread een oude ``trades'' ziet, maar wel een nieuwe ``hits''), dan zou je kunnen volstaan met het toevoegen van ``volatile'' bij de declaratie naar de pointers naar je hashtables.

Dit zou correct moeten zijn vanaf jdk1.5 als ik het goed heb

[ Voor 7% gewijzigd door Infinitive op 12-04-2006 15:50 ]

[TheNameless]

@Soultaker: okay, dan heb ik de synchronize keyword verkeerd ingeschat

@Infinitive: Hoeveel is eigenlijk de overhead van het locken? Ben ik wel benieuwd naar.

Er is tegenwoordig ook wel informatie te vinden over Lock-Free programming/Wait-free synchronization te vinden. Dit moet de overhead van locking terug brengen.

Ik heb er verder geen ervaring mee en in hoeverre je dit in JAVA kan toepassen weet ik ook niet.

[makreel]

Eigenlijk wil je een lock op een regel ipv de hele table.
Om op de vraag terug te komen:

"Hoe kan ik er tread safe voor zorgen dat 'getTrade' en 'addHit' even wachten als 'generateAll' bezig is met het veranderen/muteren?"

met wait() en notify().

[ Voor 64% gewijzigd door makreel op 12-04-2006 20:17 ]

[Robtimus]

Of het reader / writer algoritme gebruiken.

Een writer kan de resources aanspreken als er geen readers of writers gebruik maken van de resources (#writers == 0 && #readers == 0).
Een reader kan de resources aanspreken als er geen writers gebruik maken van de resources (#writers == 0).

Je lockt dus niet onnodig andere readers als je alleen maar de data wilt inlezen.

[Alarmnummer]

MayaFreak schreef op woensdag 12 april 2006 @ 14:23:
Kijk eens naar de volgende link: http://java.sun.com/j2se/...rent/locks/Condition.html

Ik denk dat je met behulp van Conditions goed kan oplossen.

Conditions (maken gebruik van wait/notify-event systeem) zijn denk ik overkill aangezien je het in principe af kunt met een mutex. En een oplossing met een condition(variable) zou net zulk slecht concurrent gedrag hebben als de mutex.

[ Voor 10% gewijzigd door Alarmnummer op 13-04-2006 14:34 ]

[Alarmnummer]

Infinitive schreef op woensdag 12 april 2006 @ 15:49:
Als de generateAll functie nieuwe hashtables maakt (evt. gebaseerd op de oude) en de twee hashtables onafhankelijk zijn (waarbij ik bedoel dat het niet erg is dat een thread een oude ``trades'' ziet, maar wel een nieuwe ``hits''), dan zou je kunnen volstaan met het toevoegen van ``volatile'' bij de declaratie naar de pointers naar je hashtables.

Dit zou correct moeten zijn vanaf jdk1.5 als ik het goed heb

Infinitive schreef op woensdag 12 april 2006 @ 15:49:
Als de generateAll functie nieuwe hashtables maakt (evt. gebaseerd op de oude) en de twee hashtables onafhankelijk zijn (waarbij ik bedoel dat het niet erg is dat een thread een oude ``trades'' ziet, maar wel een nieuwe ``hits''), dan zou je kunnen volstaan met het toevoegen van ``volatile'' bij de declaratie naar de pointers naar je hashtables.

Dit is een optie die ik in 1e instantie ook zou kiezen. Je hebt het voordeel dat je dus maar erg kort lockt (dus alleen zo lang je een copy aan het maken bent van de hashmap).

De consequentie van deze aanpak is dat de gecopieerde map eventueel out of sync is met de actuele map. Je moet dus even kijken of dit geen problemen met zich mee gaat brengen.

Een andere oplossing:
incremental generate: dus alleen de wijzigingen binnen het genereer process doorvoeren. Eventueel zou je deze incrementele generates nog op een aparte thread kunnen uitvoeren (zie executors). Hierdoor blokkereer je de addHit dus niet al te lang. De vraag is dus of dit dus mogelijk is.

[ Voor 3% gewijzigd door Alarmnummer op 13-04-2006 14:12 ]

[Alarmnummer]

makreel schreef op woensdag 12 april 2006 @ 19:26:
Eigenlijk wil je een lock op een regel ipv de hele table.
Om op de vraag terug te komen:

"Hoe kan ik er tread safe voor zorgen dat 'getTrade' en 'addHit' even wachten als 'generateAll' bezig is met het veranderen/muteren?"

met wait() en notify().

Wait en notify is alleen handig als je niet weet hoe lang je gaat locken (dus je weet bv niet wanneer de queue weer een plek vrij heeft, of wanneer de verkeerslichten weer op groen staan). Als je wel weet hoe lang je gaat locken (en dat weet je wanneer je een kritieke sectie in gaat) dan moet je gewoon een normale lock gebruiken.

[Alarmnummer]

IceManX schreef op woensdag 12 april 2006 @ 20:19:
Of het reader / writer algoritme gebruiken.

Een writer kan de resources aanspreken als er geen readers of writers gebruik maken van de resources (#writers == 0 && #readers == 0).
Een reader kan de resources aanspreken als er geen writers gebruik maken van de resources (#writers == 0).

Je lockt dus niet onnodig andere readers als je alleen maar de data wilt inlezen.

Een readwritelock heeft alleen maar voordeel als je veel concurrent reads hebt. Op het moment dat er een write komt, moeten alle reads wachten totdat de write klaar is. In applicaties waar de responsetime van de reads heel belangrijk is (bv voor het afhandelen van een webrequest) kon dit wel eens onacceptabel zijn.

[Alarmnummer]

Verder weet ik ook niet genoeg van je probleem af. Wellicht zou je ook naar een database kunnen kijken die multiversioning (Multi Version Concurrency Control) ondersteunt (MySQL + InnoDb, Postgresql, Oracle). Je krijgt dan vanuit de database de garantie dat je een bewerking uitvoert op een consistente set met data tov een bepaald punt in de tijd zonder dat je hiervoor hoeft te locken. In principe kan je de oplossing die Infinitive aandroeg ( copieeren van de hashmaps ) ook vergelijken met multiversioning aangezien je een snapshot maakt van de data. Je data is dan ook consistent (tov een bepaald punt in in de tijd).

[edit]
Je zou ook kunnen kijken naar de ConcurrentHashMap. De reads en de iterator die blokkeren niet terwijl ze wel in een concurrent omgeving gebruikt kunnen worden. Alleen concurrent updates die blokkeren wel. Verder geeft de iterator je ook een consistent beeld tov een bepaald punt in de tijd.

[edit2]
Je kunt ook naar de copy on write structuren kijken. In principe komt dat ook neer op de oplossing waarbij je een copy maakt op het moment dat je die generateAll aanroept.

[ Voor 52% gewijzigd door Alarmnummer op 13-04-2006 14:32 ]

[Verwijderd]

Bedankt voor de replies. Ik gebruik momenteel de methode van soultaker. In de 'generateAll' functie maak ik 2 deepcopies van de 'hits' en 'trade' structures. Zo kan ik mooi het echte en langdurig werk doen met deze deepcopies en kunnen de 'gettrade' en 'addhit' gewoon verder.
Al moet ik zeggen dat ConcurrentHashMap er ook erg goed uitziet, momenteel zit ik nog met jdk1.4 op de server, maar ik zag dat er ook een backport was van de concurrent package van 1.5.
Maar ik zal eerst eens wat stress tests doen, want volgens mij is de code nu een stuk sneller en toch nog steeds veilig.

[Alarmnummer]

Verwijderd schreef op donderdag 13 april 2006 @ 21:34:
Bedankt voor de replies. Ik gebruik momenteel de methode van soultaker. In de 'generateAll' functie maak ik 2 deepcopies van de 'hits' en 'trade' structures. Zo kan ik mooi het echte en langdurig werk doen met deze deepcopies en kunnen de 'gettrade' en 'addhit' gewoon verder.
Al moet ik zeggen dat ConcurrentHashMap er ook erg goed uitziet, momenteel zit ik nog met jdk1.4 op de server, maar ik zag dat er ook een backport was van de concurrent package van 1.5.
Maar ik zal eerst eens wat stress tests doen, want volgens mij is de code nu een stuk sneller en toch nog steeds veilig.

Het probleem aan soultaker zijn aanpak is:
-de structuren zijn volledig geblokkeerd als er een generateAll bezig is (dit kan een behoorlijke inpact hebben op de responsetime van add/getTrade functies).
-concurrent reads zijn niet mogelijk (en dat terwijl concurrent reads dus geen isolation issues met zich meebrengen).

Het is uiteraard een oplossing die correct functioneert, maar je hebt nog steeds veel last van lockcontention (alhoewel wel iets minder dan je oorspronkelijke aanpak). Maar er valt nog heel wat performance winst te halen door andere locking technieken te gebruiken zoals readwrite locks, of snapshots maken van de data (waardoor je nog maar heel erg kort hoeft te locken). En meestal kan het toch niet zo veel kwaad dat je met oudere data werkt, aangezien de uitkomst van de generateAll toch al verouderd is zo gauw er een add word aangeroepen.

[edit]

Bedankt voor de replies. Ik gebruik momenteel de methode van soultaker. In de 'generateAll' functie maak ik 2 deepcopies van de 'hits' en 'trade' structures. Zo kan ik mooi het echte en langdurig werk doen met deze deepcopies en kunnen de 'gettrade' en 'addhit' gewoon verder.

De oplossing van soultaker is locks met verschillende granularities te introduceren. Ik denk dat je de oplossing van Infinitive bedoelt hebt. Mijn commentaar was dus op de aanpak van Soultaker en niet op die van Infinitive.

[edit2]
Waarom maak je een deep copy? Ik snap wel dat je dan geen last hebt van isolation issues, maar soms zijn andere aanpakken wel zo handig (deep copy is imho meestal een teken dat er iets niet goed zit).

[ Voor 57% gewijzigd door Alarmnummer op 14-04-2006 12:29 ]

[Verwijderd]

Ik bedoelde toch de oplossing van soultaker. Dit omdat ik nog steeds met jdk1.4 zit en Infinitive gaf aan dat volatile alleen met 1.5 werkte. Ik heb eens nagekeken wat volatile nu eigenlijk inhoud, maar dat is toch allemaal wat ingewikkeld, dat hele java memory verhaal is niet echt logisch te noemen

Maar laten we ontopic blijven, volatile zorgt er dus voor dat elke thread dezelfde variable ziet, maw de variable in thread memory is altijd dezelfde als in main memory. Als je synchronized gebruikt zorg java ervoor dat alle variabelen in thread memory hetzelfde zijn als in main memory.

Heb ik het dan correct als ik stel dat ik alleen volatile voor m'n hashtables moet zetten en alle synchronized dingen mag verwijderen en dat alles dan goed gaat (dus netzoals als ik synchronized zou gebruiken)?

Tijdens m'n surf tocht zag ik dat volatile niet in alle jdk's word ondersteund, alleen kon ik nergens vinden in welke jdk's wel en niet. Doet volatile het goed in de laatste jdk1.4 van sun (de linux versie)?

Overigens werkt de soultaker oplossing best aardig, ik kan nu minimaal 100 hits per seconden aan (een hit roept meestal gettrade en addhit aan)

Ik maakte overigens een deep copy omdat de generateall functie nogal een tijdrovende functie is die allerlei filters en analyzes op de hashtables uitvoerd. Dus nu lock ik met synchronized de hashtables, maak een deep copy, unlock de hashtables en doe dat de analyzes met de deep copies. Dan kunnen de andere threads vrolijk verder terwijl generateall() nog bezig is met de analyzes.

[ Voor 16% gewijzigd door Verwijderd op 15-04-2006 14:45 ]