50 Mio Datensätze Zuordnung, Abfragen, Performance

[Rolf b]

Es sind nicht 500.000 User, sondern lt. Google Play 10.000.000 bis 50.000.000. Und das ist nur Android, mit iOS und Windows Phone kommen sicher noch etliche Milliönchen dazu. Nehmen wir einfach mal 50 Mio User an. Die sind natürlich nicht alle aktiv, aber es werden auch etliche hochaktive Spieler dabei sein.

Wenn Du Dir eine Tabelle vorstellst, wo pro gespielter Kombination Frage/User ein Eintrag steht, dann hast du im Worstcase 500 Milliarden Rows. Ich weiß nicht was die durchschnittliche Anzahl gespielter Fragen pro User ist. Nehmen wir mal 200 an? Also durchschnittlich 200 Rows pro Spieler. Jede Row enthält 32 Bit für die Userid und 16 Bit für die Frage-ID, das sind 6 Bytes pro Row oder 1200 Bytes pro Spieler (wovon 800 Bytes für das hundertfache Speichern seiner User-ID draufgehen). Die Tabelle belegt mit 10 Milliarden Rows 60GB Nettospeicher, es kommt noch Verwaltungsspeicher pro Row und der Index hinzu. Vermutlich brutto 100GB-120GB.

Das ist sicherlich handhabbar. Aber bei bei Vielspielern wird es zum Problem, bei jedem Spiel die für sie relevanten Rows zu laden. Hat der Spieler schon 5000 Fragen gespielt, muss man für ihn 5000 Rows laden. Bei Verwendung eines Cluster-Index stehen die zwar beisammen, aber dafür hast Du den Aufwand des Clusterns. Des weiteren sind 2/3 des zu lesenden Volumens (db-intern) keine Fragenummer, sondern die Usernummer. Für Wenigspieler mag das eine sinnvolle Lösung sein, bei Vielspielern würde ich das nicht tun.

Die gespielten Fragen als langen String zu speichern, wo die Fragenummern durch Komma getrennt sind, ist Platzverschwendung. Eine Frage belegt dann typischerweise 6 Bytes. Zumindest sollte man da die Fragenummern base-64 in 3 Bytes codieren, das speichert bis $$2^{18}$$ Fragen pro Triplet, auf die Kommas verzichten und einfach alle gespielten Triplets hintereinanderhängen. Dann muss man keine Kommas parsen, und eine base-64 decodierung ist auch nicht langsamer als das Parsen eines int-Wertes. Der Durchschnittsspieler belegt dann ca 600 Bytes, aber das kann die DB nicht so optimal speichern weil es ein varchar oder varbinary String ist, die brauchen Reserven. Und ein Vielspieler mit 2000 gespielten Fragen belegt 6K.

Ich würde es anders realisieren. Ich würde bei 10000 Fragen einen Bitvektor der Länge 10000 anlegen. Der belegt 1250 Bytes und kann z.B. in einer BLOB Spalte abgelegt werden. Sowas hab ich mit PHP noch nicht verarbeitet, würde aber vermuten, dass es geht (mysqli_stmt::bind_param Datentyp 'b' und pack/unpack). Aber es gibt ja auch eine Welt jenseits von PHP und ich würde eine solche Komponente vermutlich eher mit einer Sprache realisieren, die maschinennahe Operationen besser abbildet.

Jedes Bit im Vektor entspricht dann einer Frage. Freie Fragen zu finden hängt dann von der Implementierung ab. In PHP macht man erstmal mit $vec = unpack("I4") aus dem Blob ein Array aus 32-bit Integers (jajaja, geht bei 1250 Byte nicht auf) und sucht dann einen Eintrag, der nicht -1 ist (0xffffffff). Und darin dann ein ungesetztes Bit. Ist in PHP etwas frickelig, aber sicherlich möglich. Aber wie gesagt, es gibt dafür elegantere Sprachen. C++, Java, C#, irgendwas mit hinreichend low-level Funktionalität.

Wenn der Fragenkatalog erweitert wird, erweitere ich z.B. den Bitvektor. Ein BLOB kann bis 65535 Bytes lang werden. Man muss sich hier aber genau anschauen, wie die aktuell verwendete DB und DB-Engine BLOBs speichert, um zu wissen, ob man bei mehr Fragen eher den BLOB verlängert oder ob man mehrere kleine BLOBs verwendet. Man muss auch die Packet-Size des DBMS beachten. Das sind ein paar technische Details, die bei der Programmierung zu beachten sind. Eventuell merkt man dann, dass BLOBs nicht effizient sind, und verwendet statt dessen eine base64-codierung in VARCHAR-Feldern. Das sind aber alles Fragen, die sich darum drehen, wie man die Bitmap in die DB bringt, sie ändern nichts an der Grundidee, eine Bitmap für die verwendeten Fragen zu nutzen. Die Bitmap wird erst dann unpraktisch, wenn der Fragenkatalog soweit anwächst, dass die Bitmaps nicht mehr effizient verarbeitet werden können. Wann diese Grenze erreicht ist, hängt von der Hardware ab, die ich zu bezahlen bereit bin :)

Auf diese Weise ist das pro User zu ladende Datenvolumen nicht sonderlich groß und der Aufwand zum Durchsuchen ist begrenzt. Der Nachteil ist, dass man für Wenigspieler genausoviel Platz braucht wie für Vielspieler. Bei 1250 Bytes für 10000 Fragen sind es 62GB an BLOB-Volumen. Das entspricht der relationalen Durchschnittsangabe vom Anfang - aber dafür ist es gleichzeitig die Obergrenze des belegten Volumens. Weiterer Nachteil ist, dass es keine einfache Query gibt, um festzustellen, welche Fragen wie oft gespielt wurden. Dafür muss man dann alle Blobs einmal Laden und decodieren. Um festzustellen, ob das akzeptabel ist, muss man alle Anforderungen an die DB sammeln (nicht nur aus Sicht der Spieler, sondern auch aus Sicht des Herstellers).

Rolf