[JAVA] Eindeutiger Hashcode

Ich habe bei mir im Spiel das ganze Datenbankframework aus Interesse daran wie sowas eigentlich geht selber programmiert (hätte auch Hibernate verwenden können :D).

Funktioniert auch recht flott, ich hätte doch für sehr oft durchgeführte Abfragen gerne einen Cache. Jetzt habe ich natürlich das Problem das ich bei 2 eigenständigen Abfragen herausfinden muss, ob diese nur equivalent sind oder nicht. Dabei spielt bei mir das "QueryKey" Objekt die entscheidende Rolle. Das Objekt besitzt eine Liste mit jeweils folgendem Eintrag für ein Feld:

"feldname" "wert"

und läuft logischerweise jeweils auf eine bestimmte Tabelle. Der Cache weiss also bereits auf welche Tabelle die Abfrage geht.

Ich habe jetzt mal versucht equals zu überschreiben und einen eindeutigen hash dadurch zu erreichen .. das ich die einzelnen feldnamen und werte in einem String zusammenschreibe und mir dann den String Hash geben lasse.

Beispiel:

"id"+"1"+"type"+"4" = "id1type4" (<- und von dem nacher den hashcode)

Ist sicherlich eine etwas naive Vorgehensweise und hat dementsprechend zwar für 95% funktioniert, aber in den restlichen Fällen, leider falsche Daten aus dem Cache zurückgegeben.

Hat vielleicht jemand eine Idee wie man hier eine eindeutige Identifzierung von Queries erreichen könnte?

Entweder du hast ein Attribut für den Primärschlüssel vergessen - oder du hast in dem Ansatz (ich weiß dein Beispiel gerade nicht richtig im Stack einzuordnen) die kleine, aber nicht unscheinbare Tatsache vergessen, dass der Cache nur den Hashcode, sondern auch den Entitätentyp speichern muss. Entitätentyp + Primärschlüssel müssen eindeutig sind.

Ok ich glaub ich hab mich etwas missverständlich ausgedrückt, am Primärschlüssel kanns nicht liegen, weil ich mich nur darauf beziehe mit welcher WHERE Bedingung auf die Tabelle abgefragt wurde. Also das QueryKeySet (QKS) beinhaltet nur die Felder der Where Bedingung, man kann davon ausgehen das es keine JOIN's gibt nur simple abfragen auf eine Tabelle.

Hier das Objekt das eine Abfrage auf eine Tabelle definiert (dies ist das qks Objekt das dann weiter unten verwendet wird):

Java:

    @Override
    public int hashCode() {
       int hashCode = 0;
        // Build hasCode from QueryKey 
       String hashStr = "";
       for (QueryKey qk : keys) {
           hashStr += qk.getFieldName();
           hashStr += qk.getFieldValue();
       }
       return hashStr.hashCode();
    }
    @Override
    public boolean equals(Object obj) {
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final QueryKeySet other = (QueryKeySet)obj;
        if (other.hashCode() != this.hashCode()) {
            return false;
        }
        return true;
    }

Im Framework werden die gecachten Ergebnisse hier gespeichert:

Java:

private HashMap> buffer = new HashMap>();

Und hier wie ich dann überprüfe ob eine Abfrage bereits im Cache durchgeführt wurde

        if (buffer.containsKey(qks.hashCode())) {
            // System.out.println("Retrieve from Buffered Results ("+qks.hashCode()+")");
            return buffer.get(qks.hashCode());
        }

Wenn ich dich richtig verstehe cachest du ganze ResultSets (in Objektrepsäsentation) anhand eines Hashes. Dieser Hash besteht bei dir aber nur aus den Parametern der Abfrage.

Select * from user where state='ACTIVE' hat also eine HashKollision mit

Select * from user where state!='ACTIVE', weil du deine Operatoren nicht mit in das Hashverfahren einbeziehst.

Knalli bezog sich glaube ich nur auf das Cachen von einzelnen Entitäten...da sollte der Objekttyp plus ID für ein eindeutiges Hash reichen....bis auf Hashkollisionen durch das eigentliche Hashverfahren, die aber eher mathematisch interesseant sind, meist aber nicht praktisch relevant.

Wenn ich das richtrig sehe, dass du einen globalen Cache für Ergebnisse jeglicher Art haben willst, dann müsstest du für dein Hash folgendes mit einbeziehen:

• Objekttyp class.getName()
• Parameter des Aufrufs
• Operatoren in korrekter Reihenfolge relativ zu den verwendeten Parametern

So long...

Maxx

EDIT: Falls du Spring verwendest empfehle ich dir (wenn du genug hast mit lernen) die @Cacheable Annotation von spring zu verwenden. @Cacheable baut dir um deine Klasse einen Proxy, der vor dem Aufruf deiner eigentlichen Methode überprüft, ob es im Cache bereits einen Eintrag gibt (mit dem Hash aus den benutzten Parametern). Gibt es diesen, so bedient der Cache direkt. Gibt es ihn nicht, so wird die Methode ausgeführt. Beim verlassen der Methode sorgt der Proxy noch dafür, dass das Ergebnis im Cache abgelegt wird. Eigentlich recht simpel von der Implementierung her.

Dadurch, dass es hier vom Konzept her einen Cache pro Methode gibt, muss weder Objekttyp noch Operanden mit in die Identifikation der Elemente im Cache einbezogen werden.

Kurzes HowTo zu dieser Annotation: http://www.rowellbelen.com/content/declarative-caching-using-spring-ehcache-and-java-5-annotations

Offensichtlich hab ich irgendwo was verbockt, ich habe jetzt gerade mal für alle Queries hashCode und WhereString in ein CSV geschreiben und in Excel gefiltert, gab nirgends eine Kollision.

Wenn sich was neues ergibt sag ichs dann :)

Ich frage mich generell warum du überhaupt so einen Cache neu implementierst. Im Endeffekt simulierst du damit nur einen Querycache der in der Form bereits in der Datenbank existiert. Vom Dateisystemcache des Betriebssystems mal abgesehen. Zudem hat deine Implementierung ein Problem: sie cacht nur auf Basis des Querystrings. Dadurch kann ein Objekt doppelt, bedingt durch zwei verschiedene gecachte Resultsets, im Cache liegen. Änderst du eine Version davon kann die zweite als gecachtes Objekt trotzdem noch weiterverwendet werden. Womit deine Anwendung mit ungültigen Daten arbeitet. Nachdem dein Cache offenbar keinerlei Einsicht in die Struktur und Beziehungen der gecachten Objekte hat, kannst du zur Abhilfe nur den kompletten Cache einer Tabelle leeren, nachdem ein Query mit potentiellen Änderungen aufgetreten ist. Damit hast du dann aber auch nur die Funktionalität eines gewöhnlichen Querycaches wie er in der Datenbank schon vorhanden ist dupliziert und effektiv wenig gewonnen. Den Performancegewinn durch den eingesparten IO mit der Datenbank kannst du vernachlässigen. Reine Abfragen, vorallem wenn sie offensichtlich nichtmal mit komplexen Joins arbeiten, sind nicht dein Performanceproblem (solange du keine Indexe vergisst ;)). Was dir im Zweifelsfall die Datenbank killt sind eher hohe Updateraten und Parallelitätsprobleme (dead locks, race conditions, etc.pp.).

Wenn du statische/unveränderliche Daten in der Datenbank hast, so würde ich die einmal zum Start der Anwendung in eine geeignete Datenstruktur einlesen und danach überhaupt nicht mehr über einen ORM-Layer darauf zugreifen. In allen anderen Fällen würde ich vorerst auf eigene Caches verzichten und eher an der Optimierung der Datenbank arbeiten. Da kann man auch ohne Programmieraufwand viel rausholen. Solltest du dennoch eines Tages mit deinem Spiel so erfolgreich sein, dass du sämtliche bezahlbare Hardware mit deiner Datenbank auslastest, kannst du dir immer noch über Caching Gedanken machen. Vorallem hast du dann wesentlich mehr Wissen über die Bottlenecks deiner Anwendung und kannst selektiv die Performance verbessern.

Was du da gerade treibst ist im Augenblick verschwendete Liebsmüh ;)

Danke für den ausführlichen Beitrag, da hast du wohl recht.

Wir hatten früher in unserer Anwendung ja das Prinzip das wir spezifische Cache für statische Daten hatten, die auf ihren jeweiligen Zweck optimiert waren. Das selbsterstellte ORM Layer dient jetzt praktisch dazu diese ganzen Einzelcaches in einer generischen allgemeingültigen Variante zugänglich zu machen und gleichzeitig zu ermöglichen ebenfalls Daten zu cachen die 99% Lese und 1% Schreibzugriffe haben und beim update dieses Caches die Daten in der Datenbank ebenfalls automatisch zu aktualisieren.

Grundsätzlich gings uns ja nur darum das Programm, das vorher ein unübersichtlicher Saustall mit SQL Statements an jeder Ecke war, etwas freundlicher zu gestalten. Da bei uns zum Teil sogar in JSP Seiten Spiellogik drin stand. Ein über Jahre gewachsener Moloch sozusagen :D

Das Zeug da oben mit dem Abfragecache ist auch eher eine Spielerei von mir, wenn ich mal keine Lust habe nur am Spiel zu proggen und ne programmtechnische Herausforderung brauch :)

Edit: Wir haben auch mit 30 Spielern soviel Spass, das sich der Aufwand lohnt :)

Ich habe das jetzt richtig verstanden:

a) du willst aus Teufel komm raus sogar einen eigenen Second-Level-Cache bauen

b) und besitzt dann auch noch die Güte, den Cache auch auf die Where-Klausel auszuweiten?

Wow. Gesetz den Fall, das habe ich jetzt richtig verstanden, so kann ich deinen Cache mit folgender Situation sofort knallen lassen:

1. "get user where name = 'peter'"
2. => cache mit hash(user, name)
3. "get user where id = 4711
4. => cache mit hash(user, id)
5. update user where id = 4711 (etwa neue Mailadresse)
6. wird wohl den cache mit hash(user, id) invalidieren
7. und was ist mit "get user where name = 'peter'"? zufälligerweise der gleiche datensatz.. weiß nur die o.g. Logik nicht.

Will heißen: Es hat keinen Sinn, nicht über Primärschlüssel (zusammengesetzt oder künstlich) zu cachen, weil es schlichtweg unvollständig ist (warum sollte es sonst einen Primärschlüssel geben).

Ganz im Ernst, sowas muss man nicht selber bauen.

@MrMaxx 

Wo ist der Unterschied zu den (praktische) Hibernate-Annotationen? 

Original von knalli

Ich habe das jetzt richtig verstanden:

a) du willst aus Teufel komm raus sogar einen eigenen Second-Level-Cache bauen

Neeeein, nur so experimentell neben her, wenns nicht klappt halb so schlimm, das momentan Framework das mit Primärschlüssen und Index arbeitet ist auch sehr schnell. Aber es wäre ein Second-Level-Cache in der Tat.

Wobei ich anmerken muss, das der Cache für bereits first-level gecachte Daten (langsam wirds verwirrend) eher nicht so wichtig ist, hauptsächlich wäre der Cache dafür gedacht, das ich Anfragen die nicht durch den First-Level-Cache gedeckt werden und somit sofort an die Datenbank gehen, in diesem Cache zwischenspeichere.

b) und besitzt dann auch noch die Güte, den Cache auch auf die Where-Klausel auszuweiten?

Wow. Gesetz den Fall, das habe ich jetzt richtig verstanden, so kann ich deinen Cache mit folgender Situation sofort knallen lassen:

1. "get user where name = 'peter'"
2. => cache mit hash(user, name)
3. "get user where id = 4711
4. => cache mit hash(user, id)
5. update user where id = 4711 (etwa neue Mailadresse)
6. wird wohl den cache mit hash(user, id) invalidieren
7. und was ist mit "get user where name = 'peter'"? zufälligerweise der gleiche datensatz.. weiß nur die o.g. Logik nicht.

pfff ... Vorausgesetzt ich verstehe dich richtig, nehme ich an du hast mich nicht richtig verstanden. Exe hat das bereits sehr treffend in seinem Post beschrieben, der Vorgang wäre folgender:

1. "get user where name = 'peter'"
2. => cache mit ([[name='peter']], Ergebnis)
3. "get user where id = 4711"
4. => cache mit ([[id=4711]], Ergebnis) <--- wobei das absolut kein Sinn macht, weil Primärschlüssel so schnell gefunden wird das es egal ist
5. update user where id = 4711 (naja siehe 4. macht kein Sinn, aber theoretisch würd ich dann wie exe gesagt hat, den ganze cache ins Klo werfen)
Somit 6. => cache ins Klo
7. back to 1.

Aber danke für eure Kritik und Anregungen, ich werds mit dem Cache wohl eher lassen ;)

Jetzt zitier ich mich schon selber ....

Hihi.. aber ja, exec hatte das tatsächlich schon angesprochen. Diese Ergebnis(in)validitäten meinte ich. Du würdest die Arbeit vom DBMS nochmal machen => Fehlinvestition. Falls also dein DBMS keinen guten Querycache anbietet und die Datenbank daran auch wirklich zu grunde geht, tja.. dann gibts nur 2 Möglichkeiten: DBMS-Wahl überdenken oder besser konfigurieren. Tatsächlich kann man doch Second-Level-Cache nur für Dinge nutzen, die sich nicht dauernd ändern.. weil sonst bringt der Cache nichts. Benutzerstammdaten könnten sicherlich so ein Fall sein, da darf natürlich dann keine Information a la "letzter Zugriff" stehen.

Und mal ganz allgemein, zum ersten Post, letztes Beispiel: Schon mal die generierten HashCode-Methoden von Eclipse gesehen?