Database Isolation Level; onzichtbaar maken?

[Tieske[82]]

Ik ben bezig in MySQL(InnoDB)/PHP een systeem te bouwen waarmee je met meerdere gebruikers iets kan kopen, maar loop tegen een schaalbaarheidsissue aan wat me maar niet lukt om te tackelen.

Het concept is een spel, waarbij er huizen gebouwd kunnen worden. Een huis kost altijd 100, en bestaat uit hout/glas/steen. Een huis wordt gevormd als de som van alle grondstoffen 100 is. Dus als dit de biedingen zijn:

1. Speler 1 biedt 50 hout,
2. Speler 2 biedt 30 glas,
3. Speler 3 biedt 20 steen,

Dan vormen ze samen een huis (want 50+30+20=100). Wat het script nu doet is het volgende:

1. De hele table locken,
2. Transactie starten,
3. Kijken wat de hoogste biedingen zijn op hout, glas en steen,
4. Als die samen 100 zijn, deze biedingen op 'afgehandeld' zetten, en verplaatsen naar een andere tabel
5. Transactie beëindigen
6. Table vrijgeven

Deze constructie betekend m.i. wel dat optimale/parallele uitvoering eigenlijk onmogelijk is.
De reden waarom ik de tabel lock voor de transactie (1), is omdat ik wil voorkomen dat een andere transactie (2) dmv een SELECT query ook de "50 hout" te zien krijgt en daarmee gaat rekenen of er ook 100 gevormd kan worden, terwijl die eventueel aan het eind van transactie (1) niet meer aanwezig hoeft te zijn.

Ik wil dit graag ombouwen naar een constructie waarbij de table lock achterwege kan blijven. Daarvoor is het (denk ik) noodzakelijk om de rijen die in de transactie (1) worden gebruikt (mbv SELECT/DELETE), überhaupt niet zichtbaar te maken voor transactie (2), ook niet voor SELECT queries.

Volgens mij kan ik dit niet oplossen met een ander Isolation Level, omdat READs (SELECTs) altijd mogelijk blijven.

Is er een methode om dit slimmer/anders te doen, begrijp ik MySQL niet helemaal goed, of zie ik iets over het hoofd?

[Armageddon_2k]

Denk dat je er niet onderuit komt om een een-of-ander lock mechanisme te gaan gebruiken.
En of je dat nou zelf maakt of dat je een table lock gebruikt. Dat maakt niet zoveel uit.
Je kan ook vrolijk een kolom bij maken "CantTouchThis". Zodat de tweede transactie hier nooit mee gaat rekenen. Maar dan bestaat de kans dat je er alsnog telaat pas er achterkomt.

[Voutloos]

Hoe groot is de kans dat een rij voor meerdere transacties geldig lijkt? KISS en introduceer dan geen eigen locks of CantTouchThis kolommen. Voeg where clauses toe bij het doorvoeren van de betalingen. Zodra query faalt (geen affected rows) doe je een rollback en klaar.

[Tieske[82]]

De biedingen zullen oplopen, totdat 100 gevormd kan worden. Een speler biedt dan 40, een volgende 45, daarna iemand 50, totdat de grondstoffen voldoende zijn om een huis te bouwen.

De kans is dus groot dat de transactie dezelfde rij eruit vist, omdat de query de maximale biedingen ophaalt. Dus als MAX(hout), MAX(glas), MAX(steen) groter dan/gelijk is aan 100, dan kan er een huis gebouwd worden.

Een extra kolom werkt denk ik ook lastig, aangezien je voor elke SELECT ook een UPDATE moet doen die de kolom "CantTouchThis" op "yes" zet oid. Om dit voor andere transacties zichtbaar te krijgen, moet je dus een READ UNCOMMITTED level kiezen, maar dat is juist wat je wil voorkomen lijkt me?

[ACM]

Is dit niet op te lossen met SELECT ... FOR UPDATE eventueel nog in combinatie met het SERIALIZABLE locking-level? Of je schaalbaarheid daar echt beter van wordt weet ik alleen niet

Dan krijg je iets als:

SQL:

SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
START TRANSACTION;
-- Voor elk van je resources:
-- plaats een write lock op het record met de hoogste bieding
SELECT id, amount FROM biedingen ORDER BY id DESC LIMIT 1 FOR UPDATE;

-- Klopt de som van je amounts nog steeds en kreeg je drie records? Zoja:
-- Je afhandelingsprocedure van de drie biedingen
COMMIT;

Het kan zijn dat je in bovenstaande procedure een deadlock krijgt. Dan moet je waarschijnlijk alle pogingen die daarbij betrokken waren opnieuw starten. Als je nog meer voorbeelden wilt, kan je kijken naar voorbeelden waarbij met bankrekeningen wordt gewerkt. Die hebben tenslotte min of meer hetzelfde probleem en worden vaak als voorbeeld gebruikt bij dit soort problemen.

[MSalters]

Heb je een index liggen op de biedingen? Zo ja, dan is de hele "selecteer hoogste bieding" een simpele lookup die nauwelijks te versnellen is met parallelisatie.

Kijk, normaal gesproken zou je zoiets oplossen in twee stappen: buiten een transactie zoek je de kandidaat rows, en binnen een transactie controleer je of de rows nog steeds aan de eisen voldoen om vervolgens de wijziging uit te voeren.

Het idee is dat je met deze opzet het grootste deel van het zoekwerk al gedaan hebt buiten de transactie. Maar hier is de zoekactie schijnbaar zo simpel dat er geen winst te halen is aan zo'n voorselectie.

[jbdeiman]

- Hoeveel spelers doen gelijktijdig mee aan een bieding, voor 1 object (lees: huis)
- Zitten deze spelers mogelijk in teams/ groepen, of kan elke losse speler op een object bieden?

of beter gezegd, kan je uitleggen hoe die biedingen precies zijn opgezet, daarop is het ws ook beter mogelijk om een duidelijk antwoord te geven hoe je dit aan kan pakken. Als we de uiteindelijke werking niet kennen, moeten we uitgaan dat wat je nu hebt een oplossing is die prima is, maar misschien niet handig.

Wellicht heb je te ingewikkeld gedacht?

[Tieske[82]]

Iedere speler biedt tegelijkertijd op een huis, het aantal huizen dat gemaakt kan worden is onbeperkt en er wordt er telkens één gebouwd.

De biedingen per grondstof zullen dus telkens oplopen totdat de drie samen 100 vormen -> die 3 biedingen worden dan verwijderd en de spelers van die 3 biedingen krijgen een deel van het huis.

Dan zitten daaronder nog wel de openstaande biedingen van de andere spelers. Die kunnen op dat moment bv samen 98 vormen. Die biedingen worden vervolgens weer verhoogd totdat ze weer samen 100 vormen, enz. enz.

De spelers zitten niet in teams/groepen, alle spelers brengen een bod uit, en de verschillenden biedingen van alle spelers worden met elkaar vergeleken om te zien of er 100 gevormd kan worden.

Betekend een SELECT ... FOR UPDATE overigens dat die regel op dat moment niet leesbaar is voor een andere transactie?

[Varienaja]

Je bouwt nu alles in de DB, maar je zei dat je ook PHP gebruikt. Dus.. waarom niet in PHP programmeren ipv SQL?

Gewoon in 1 of ander loopje de laatste biedingen aflopen totdat je 100 hebt, met die biedingen dat huis bouwen, en de DB updaten. Dan kan je ook ineens allerlei spannende dingen doen als parallelisatie en andere degelijke optimalisaties

[Voutloos]

Eh nee. Locking/transacties/mutexes bouw je niet zomaar ff in userspace na en ik vraag me uberhaupt af hoe je erbij komt dat het dan wel parallel kan.

[Tieske[82]]

Het grootste gedeelte gebeurd ook al in PHP. Die vuurt een aantal SELECT MAX queries af (voor hout, glas en steen). In PHP worden alle resultaten verwerkt, dus als de som van de 3 queries groter of gelijk aan 100 is, dan volgen er 3 UPDATE queries waarbij een kolom 'Bod_afgehandeld" een "1" krijgt.

Na elk geplaatst bod draait dit script. Daar zit inderdaad een loop in die zichzelf herhaalt. Als er een huis gebouwd kan worden, begint hij nog eens van voor af aan met de SELECT queries. Zodra de drie grondstoffen geen 100 of meer vormen, en er dus geen huis gebouwd kan worden, stopt de loop. Een volgende gebruiker kan dan een bod plaatsen en het script in werking stellen; zonder nieuw bod zal er namelijk nooit een nieuw huis gebouwd kunnen worden.

Waar ik tegenaan loop is nu dat 'het script' uitvoeren een bepaalde tijd kost. Op de huidige manier loopt alles dus serieel: als een gebruiker een bod plaatst, loopt het script en start de loop. Het volgende bod kan pas verwerkt worden als het hele script voor gebruiker 1 is afgelopen. Er zit dus een beperking in het aantal 'biedingen' die het script per seconde kan verwerken, en dus een limiet in het aantal gebruikers.

Het helpt in dit geval volgens mij ook niet om meerdere (PHP of database) servers in te schakelen, omdat het script nog steeds moet wachten tot de vorige klaar is.

Aan die beperking in schaalbaarheid (meer servers heeft geen zin volgens mij) wil ik graag iets doen. Maar ik kom zelf helaas niet verder

[Xudonax]

Moet dit realtime gebeuren? Als het niet erg is als het eventjes duurt voordat het besluit genomen word om een huis te bouwen kun je een queue gebruiken (asynchroon alles erin gooien) welke iedere x minuten geleegd word door een cronjob oid. Op deze manier blijft je spel doorlopen, maar duurt het wel even voordat de bouw-een-huis logica uitgevoerd word.

[ACM]

Tieske\[82] schreef op donderdag 19 mei 2011 @ 17:22:
Betekend een SELECT ... FOR UPDATE overigens dat die regel op dat moment niet leesbaar is voor een andere transactie?

Nee, dat als je die gelockte records probeert te lezen, dat je dan in een wachtrij gezet wordt tot de records vrij zijn. Wat dus kan betekenen dat de records daarna een andere waarde hebben of zelfs verwijderd zijn.

[Voutloos]

Gewoon lostrekken maakt het al een stuk eenvoudiger. Dus een langlopend script cq. script welke steeds herstart wordt, waarvan maar 1 instantie draait. De requests waar gebruikers op wachten zijn dan eerder klaar, en dat specifieke script kan een paar mooie aannames doen.

Maar ik vraag me eerlijk gezegd af of je écht al tegen een probleem aan loopt, en of je goed gemeten hebt dat dit het probleem is, want wat je tijdens de lock (critical region) doet is eerlijk gezegd bepaald geen rocket science.

[ReenL]

In mijn ogen ziet het er naar uit dat je een queue nodig hebt waarin je de boden gooit. Als je vervolgens maar 1 script maakt die de queue afloopt, dan is er niets aan de hand, maar dit is niet parallel te doen omdat je te maken hebt met meerdere threads die dezelfde data aan willen spreken.

Ik vind het ook niet netjes om dit in een cron te doen, want dan weet je niet wie het huis verdient heeft, het kan namelijk zijn dat iemand al een 100+ bod gedaan heeft, maar dat het script niet runde en dat hij vervolgens overboden werd.

Een queue maken die netjes afgehandeld wordt kun je doen met Gearman. Als je maar 1 worker draait zullen alle jobs netjes fifo uitgevoerd worden. Zo komt iedereen ook netjes aan de beurt.

[Voutloos]

Een cron kan het net zo goed op volgorde van Biedingen.Id kunnen doen, maar het is wel handig om een keer van Gearman gehoord te hebben.

edit:
Tja als je bij ivm 1 enkele ORDER BY clause, welke praktisch bij elke query aanwezig moet zijn al bang bent om de fout in te gaan...

[Voor 33% gewijzigd door Voutloos op 21-05-2011 12:54]

[ReenL]

Als je de beidingen al geïnsert hebt wordt dat lastig. Je moet ze wel chronologisch aflopen. En een cron doet dit niet gelijk, maar pas als hij gescheduled is. Maar het is inderdaad niet onmogelijk, je gaat alleen sneller de fout in.

[Tieske[82]]

Realtime is noodzakelijk, de gebruiker moet na het plaatsen van een bod directe feedback krijgen. Nou ja, realtime, als de cron elke (halve) seconde loopt is dat genoeg bij benadering. Maar het lijkt mij een onelegante oplossing.

Mbv de queue is het lees ik hierboven ook niet mogelijk om zaken parallel af te wikkelen. Ik kan dit probleem maar niet naast me neerleggen, hoe kan zoiets nu wel schaalbaar gemaakt worden? Heeft iemand een idee hoe beurssoftware dat oplost, daar wordt toch ook continu de hoogste vraagprijs met de laagste verkoopprijs gematcht oid, dan geld daar toch hetzelfde probleem?

[Voutloos]

Tieske\[82] schreef op zaterdag 21 mei 2011 @ 12:29:
Ik kan dit probleem maar niet naast me neerleggen, hoe kan zoiets nu wel schaalbaar gemaakt worden?

Voutloos schreef op donderdag 19 mei 2011 @ 22:28:
Maar ik vraag me eerlijk gezegd af of je écht al tegen een probleem aan loopt, en of je goed gemeten hebt dat dit het probleem is, want wat je tijdens de lock (critical region) doet is eerlijk gezegd bepaald geen rocket science.

[Tieske[82]]

Er zijn over de huidige 'engine' wel wat statistieken beschikbaar. Dat lijkt er uiteindelijk op neer te komen dat er ongeveer 20 acties per seconde verwerkt kunnen worden. Dit vertaald zich uiteindelijk wel naar ong. 5000 gebruikers, aangezien gebleken is dat het aantal acties/seconde/gebruiker beperkt is.

Voorlopig is dat ook wel ok, maar als ik in mijn achterhoofd hou dat deze oplossing vanwege het seriële karakter (het hard locken van de tables), weet ik dat groei maar beperkt haalbaar is. Het bijplaatsen van een server heeft namelijk naar mijn idee geen enkel nut.

Dus ja, ik ben er dus vrij zeker van dát ik tegen een probleem ga aanlopen in de toekomst, en ben dus op zoek naar wat tips/pointers/advies om hier wel een oplossing voor te bieden.

[ReenL]

Het is simpelweg niet mogelijk om dit parallel af te handelen omdat elke "run" dezelfde resources nodig heeft.

Als je meer gebruikers aan wilt kunnen heb je verschillende mogelijkheden:
(pick one of maak een mooie combinatie)
- Queues opdelen, en alle beidingen load balancen tussen die queues;
- Alle biedingen in memcached het geheugen bijhouden (verhoogt je aantal transacties waarschijnlijk aanzienlijk) dmv een message queue of iets dergelijks;
- Een ander systeem verzinnen;
- Een server applicatie maken waar je de transacties inschiet.

[Edit]
Net even snel een testje in java geschreven. ongeveer 2666 5000 transacties per seconde (wel op een i7 processor).

Ik heb een klein servertje geschreven, je kan een socket openen en playerid, resourceid en amount meegeven. Je krijgt een "1" terug op het moment dat alles goed gaat en een "2" op het moment dat er een huis gebouwd kan worden inclusief alle playerid, resourceid en amounts die daarbij horen. Dit kun je vervolgens naar de database schrijven.

Het servertje gebruikt alleen memory, dus bij een crash ben je alle transacties kwijt. De performance zal nog iets omlaag gaan omdat je ook de resources van de player moet verlagen.

Ook zul je het script om moeten bouwen zodat je de waardes met php makkelijker uit kan lezen.

Java:

/**
 * © ReenL
 * 
 * http://gathering.tweakers.net/forum/list_messages/1458238
 */

package queue;

import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.IOException;
import java.net.ServerSocket;
import java.net.Socket;
import java.util.ArrayList;
import java.util.PriorityQueue;

public class ResourceQueueServer implements Runnable
{
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args)
    {
        // Define the port to run on
        int port = 1789;
        if (args.length > 0) {
            try {
                port = Integer.parseInt(args[1]);
            } catch (NumberFormatException ex) {
                System.err.println("[ERROR] Argument should be an integer.");
            }
        }

        // Run the server in a new thread.
        try {
            new Thread(new ResourceQueueServer(port)).start();
        } catch (IOException ex) {
            System.err.println("[ERROR] Socket error: " + ex.getMessage());
            System.err.println("\tTrying a different port might help.");
        }
    }

    protected ServerSocket ss;
    private PriorityQueue<Offer> queue;
    private int collected = 0;

    public static final int AMOUNT_TO_COLLECT = 100;
    
    public ResourceQueueServer(int port) throws IOException
    {
        ss = new ServerSocket(port);
        // We know that the queue can't get bigger than 100.
        queue = new PriorityQueue<Offer>(AMOUNT_TO_COLLECT);
    }

    public void run()
    {
        while ( true ) {
            Socket s = null;
            try {
                s = ss.accept();
                handle(s);
            } catch (IOException ex) {
                // Some error handling.
            } finally {
                try {
                    s.close();
                } catch (IOException ex) {
                }
            }
        }
    }

    private void handle(Socket s) throws IOException
    {
        /*
         * You might want to increase or decrease this value.
         * The client should send data within 10 miliseconds else te request
         * will be ignored.
         *
         * This is required because we have only 1 Thread users block eachother.
         */
        s.setSoTimeout(10);

        DataInputStream in = new DataInputStream(s.getInputStream());
        DataOutputStream out = new DataOutputStream(s.getOutputStream());

        // Fetch the data from the socket
        int player   = in.readInt();
        int resource = in.readInt();
        int amount   = in.readInt();

        // Lets not allow something to be in the queue for ever :)
        if ( amount < 1 ) {
            // Return 0 to the client
            out.writeInt(0);
            out.flush();
            // And get the hell out of here
            return;
        }

        // No exceptions so far, add the offer
        add(new Offer(player, resource, amount));

        // How much did we collect so far?
        collected += amount;

        // Did we collect enough?
        if ( collected > AMOUNT_TO_COLLECT ) {
            // Jup, lets get the highest offers.
            ArrayList<Offer> offers = new ArrayList<Offer>();

            // We need the total amount gathered so far.
            int gathered = 0;
            while ( gathered < AMOUNT_TO_COLLECT ) {
                Offer offer = queue.poll();
                if ( offer == null ) {
                    // This should never happen :)
                    System.err.println("Null offer");
                    break;
                }
                // We got an offer, add it to the list.
                gathered += offer.getAmount();
                offers.add(offer);
                System.out.println(offer.getAmount());
            }
            // We have to remove the gathered resources from the collected
            collected -= gathered;

            // We have a house to build
            out.writeInt(2);

            // Report the amount of offers for the house.
            out.writeInt(offers.size());

            // Now report the offers.
            for ( Offer offer : offers ) {
                out.writeInt(offer.getPlayer());
                out.writeInt(offer.getResource());
                out.writeInt(offer.getAmount());
            }
        } else {
            // Everything went fine, just not enough resources
            out.writeInt(1);
        }
        // Make sure the client is able to receive data now.
        out.flush();
    }

    private void add(Offer offer)
    {
        queue.add(offer);
    }

    /**
     * Little helper class to keep track of the offers.
     *
     * PriorityQueue uses compareTo to define the order.
     *
     */
    private class Offer implements Comparable
    {
        private final int player;
        private final int resource;
        private final int amount;

        public Offer(int player, int resource, int amount)
        {
            this.player = player;
            this.resource = resource;
            this.amount = amount;
        }

        public int getAmount()
        {
            return amount;
        }

        public int compareTo(Object o)
        {
            return compareTo((Offer)o);
        }

        public int compareTo(Offer o)
        {
            if ( amount < o.amount ) {
                return 1;
            }

            if ( amount > o.amount ) {
                return -1;
            }

            return 0;
        }

        public int getPlayer()
        {
            return player;
        }

        public int getResource()
        {
            return resource;
        }
    }
}

[Voor 86% gewijzigd door ReenL op 23-05-2011 19:31]

[Tieske[82]]

ReenL, hier wil ik wel iets meer over weten. Ik heb je net een DM gestuurd iig!

[ACM]

ReenL schreef op zondag 22 mei 2011 @ 11:53:
Als je meer gebruikers aan wilt kunnen heb je verschillende mogelijkheden:
(pick one of maak een mooie combinatie)
- Queues opdelen, en alle beidingen load balancen tussen die queues;
- Alle biedingen in memcached bijhouden (verhoogt je aantal transacties waarschijnlijk aanzienlijk);
- Een ander systeem verzinnen;
- Een server applicatie maken waar je de transacties inschiet.

Memcached is geen opslagsysteem, maar een cache. Het geeft geen enkele garantie dat data die jij er in stopt later ook nog bestaat.

[ReenL]

Je hebt gelijk, mijn punt was meer dat het in memory moest gebeuren, bij deze een kleine edit .

Gelijk even een de transacties per seconden updaten, blijken er meer te zijn. +/- 5000/sec

[Voutloos]

Tieske\[82] schreef op zaterdag 21 mei 2011 @ 15:23:
Dat lijkt er uiteindelijk op neer te komen dat er ongeveer 20 acties per seconde verwerkt kunnen worden.

Maar hoeveel tijd zit er nou in dit specifieke deel? Want als dat 50ms (1s/20 ) is voor deze eenvoudige logica^* heb je sowieso nog wat laaghangend fruit. Of een server uit 1999, maar dan weet je ook wat je moet doen.

^*: Ik ga er eigenlijk van uit dat je heel wat details weglaat, anders mis ik het tactische element in je spel.

[Voor 13% gewijzigd door Voutloos op 23-05-2011 21:00]