Bestenlisten mit Firestore erstellen

1. Einführung

Zuletzt aktualisiert: 27.01.2023

Was ist erforderlich, um eine Bestenliste zu erstellen?

Im Grunde sind Bestenlisten nur Tabellen mit Ergebnissen. Allerdings ist es etwas komplizierter, einen Rang für ein bestimmtes Ergebnis zu ermitteln, da dazu alle anderen Ergebnisse in einer bestimmten Reihenfolge bekannt sein müssen. Wenn Ihr Spiel an Beliebtheit gewinnt, werden Ihre Bestenlisten immer größer und es wird häufig auf sie zugegriffen. Damit eine Bestenliste erfolgreich erstellt werden kann, muss sie diese Ranking-Operation schnell ausführen können.

Aufgaben

In diesem Codelab implementieren Sie verschiedene Bestenlisten, die jeweils für ein anderes Szenario geeignet sind.

Lerninhalte

Sie erfahren, wie Sie vier verschiedene Bestenlisten implementieren:

• Eine einfache Implementierung, bei der der Rang durch einfaches Zählen von Datensätzen bestimmt wird
• Eine kostengünstige, regelmäßig aktualisierte Bestenliste
• Eine Echtzeit-Bestenliste mit einigen Baum-Unsinnigkeiten
• Eine stochastische (probabilistische) Bestenliste für die ungefähre Rangfolge sehr großer Spielerzahlen

Voraussetzungen

• Eine aktuelle Version von Chrome (ab Version 107)
• Node.js 16 oder höher (führen Sie nvm --version aus, um Ihre Versionsnummer zu sehen, wenn Sie nvm verwenden)
• Ein kostenpflichtiger Firebase-Tarif „Blaze“ (optional)
• Firebase CLI v11.16.0 oder höher
  Wenn Sie die CLI installieren möchten, können Sie npm install -g firebase-tools ausführen. Weitere Installationsoptionen finden Sie in der CLI-Dokumentation.
• Kenntnisse in JavaScript, Cloud Firestore, Cloud Functions und den Chrome-Entwicklertools

2. Einrichtung

Code abrufen

Wir haben alles, was Sie für dieses Projekt benötigen, in ein Git-Repository gepackt. Als Erstes müssen Sie den Code abrufen und in Ihrer bevorzugten Entwicklungsumgebung öffnen. Für dieses Codelab haben wir VS Code verwendet, aber jeder Texteditor ist geeignet.

file_downloadQuellcode herunterladen und die heruntergeladene ZIP-Datei entpacken.

Oder klonen Sie das Repository in ein Verzeichnis Ihrer Wahl:

git clone https://github.com/FirebaseExtended/firestore-leaderboards-codelab.git

Was ist unser Ausgangspunkt?

Unser Projekt ist derzeit noch leer und enthält nur einige leere Funktionen:

• index.html enthält einige Glue-Skripts, mit denen wir Funktionen über die Entwicklerkonsole aufrufen und ihre Ausgaben sehen können. Wir verwenden sie, um mit unserem Backend zu interagieren und die Ergebnisse unserer Funktionsaufrufe zu sehen. In der Praxis würden Sie diese Backend-Aufrufe direkt aus Ihrem Spiel heraus ausführen. In diesem Codelab verwenden wir kein Spiel, da es zu lange dauern würde, jedes Mal ein Spiel zu spielen, wenn Sie der Bestenliste einen Wert hinzufügen möchten.
• functions/index.js enthält alle unsere Cloud Functions. Sie sehen einige Dienstfunktionen wie addScores und deleteScores sowie die Funktionen, die wir in diesem Codelab implementieren. Diese rufen Hilfsfunktionen in einer anderen Datei auf.
• functions/functions-helpers.js enthält die leeren Funktionen, die wir implementieren werden. Für jede Bestenliste implementieren wir Lese-, Erstellungs- und Aktualisierungsfunktionen. Sie sehen, wie sich unsere Implementierung auf die Komplexität und die Skalierungsleistung auswirkt.
• functions/utils.js enthält weitere Dienstprogrammfunktionen. In diesem Codelab wird diese Datei nicht bearbeitet.

Firebase-Projekt erstellen und einrichten

Neues Firebase-Projekt erstellen

1. Melden Sie sich mit Ihrem Google-Konto in der Firebase Console an.
2. Klicken Sie auf die Schaltfläche, um ein neues Projekt zu erstellen, und geben Sie dann einen Projektnamen ein (z. B. Leaderboards Codelab).
   
3. Klicken Sie auf Weiter.
4. Lesen und akzeptieren Sie bei Aufforderung die Firebase-Nutzungsbedingungen und klicken Sie dann auf Weiter.
5. (Optional) Aktivieren Sie die KI-Unterstützung in der Firebase Console (als „Gemini in Firebase“ bezeichnet).
6. Für dieses Codelab benötigen Sie kein Google Analytics. Deaktivieren Sie daher die Google Analytics-Option.
7. Klicken Sie auf Projekt erstellen, warten Sie, bis Ihr Projekt bereitgestellt wurde, und klicken Sie dann auf Weiter.

Firebase-Produkte einrichten

1. Klicken Sie im Menü Build auf Functions und führen Sie bei Aufforderung ein Upgrade Ihres Projekts auf den Blaze-Tarif durch.
2. Klicken Sie im Menü Build auf Firestore-Datenbank.
3. Wählen Sie im angezeigten Dialogfeld Datenbank erstellen die Option Im Testmodus starten aus und klicken Sie dann auf Weiter.
4. Wählen Sie im Drop-down-Menü Cloud Firestore-Standort eine Region aus und klicken Sie dann auf Aktivieren.

Bestenliste konfigurieren und ausführen

1. Wechseln Sie in einem Terminal zum Stammverzeichnis des Projekts und führen Sie firebase use --add aus. Wählen Sie das Firebase-Projekt aus, das Sie gerade erstellt haben.
2. Führen Sie im Stammverzeichnis des Projekts firebase emulators:start --only hosting aus.
3. Rufen Sie in Ihrem Browser localhost:5000 auf.
4. Öffnen Sie die JavaScript-Konsole der Chrome-Entwicklertools und importieren Sie leaderboard.js:

   const leaderboard = await import("http://localhost:5000/scripts/leaderboard.js");
   

5. Führen Sie leaderboard.codelab(); in der Console aus. Wenn Sie eine Willkommensnachricht sehen, ist alles in Ordnung. Falls nicht, schließen Sie den Emulator und wiederholen Sie die Schritte 2 bis 4.

Sehen wir uns die erste Bestenlistenimplementierung an.

3. Einfache Bestenliste implementieren

Am Ende dieses Abschnitts können wir der Bestenliste eine Punktzahl hinzufügen und uns unseren Rang anzeigen lassen.

Bevor wir loslegen, möchten wir kurz erklären, wie diese Bestenliste funktioniert: Alle Spieler werden in einer einzigen Sammlung gespeichert. Der Rang eines Spielers wird ermittelt, indem die Sammlung abgerufen und gezählt wird, wie viele Spieler vor ihm liegen. So lässt sich ganz einfach eine Punktzahl einfügen und aktualisieren. Um einen neuen Wert einzufügen, hängen wir ihn einfach an die Sammlung an. Um ihn zu aktualisieren, filtern wir nach dem aktuellen Nutzer und aktualisieren dann das resultierende Dokument. Sehen wir uns an, wie das im Code aussieht.

Implementieren Sie in functions/functions-helper.js die createScore-Funktion, die denkbar einfach ist:

async function createScore(score, playerID, firestore) {
  return firestore.collection("scores").doc().create({
    user: playerID,
    score: score,
  });
}

Für das Aktualisieren von Ergebnissen müssen wir nur eine Fehlerprüfung hinzufügen, um sicherzustellen, dass das zu aktualisierende Ergebnis bereits vorhanden ist:

async function updateScore(playerID, newScore, firestore) {
  const playerSnapshot = await firestore.collection("scores")
      .where("user", "==", playerID).get();
  if (playerSnapshot.size !== 1) {
    throw Error(`User not found in leaderboard: ${playerID}`);
  }
  const player = playerSnapshot.docs[0];
  const doc = firestore.doc(player.id);
  return doc.update({
    score: newScore,
  });
}

Und schließlich unsere einfache, aber weniger skalierbare Rank-Funktion:

async function readRank(playerID, firestore) {
  const scores = await firestore.collection("scores")
      .orderBy("score", "desc").get();
  const player = `${playerID}`;
  let rank = 1;
  for (const doc of scores.docs) {
    const user = `${doc.get("user")}`;
    if (user === player) {
      return {
        user: player,
        rank: rank,
        score: doc.get("score"),
      };
    }
    rank++;
  }
  // No user found
  throw Error(`User not found in leaderboard: ${playerID}`);
}

Probieren wir es aus! Stellen Sie die Funktionen bereit, indem Sie im Terminal Folgendes ausführen:

firebase deploy --only functions

Fügen Sie dann in der JS-Konsole von Chrome einige weitere Ergebnisse hinzu, damit wir sehen können, wie wir im Vergleich zu anderen Spielern abschneiden.

leaderboard.addScores(); // Results may take some time to appear.

Jetzt können wir unseren eigenen Score hinzufügen:

leaderboard.addScore(999, 11); // You can make up a score (second argument) here.

Wenn der Schreibvorgang abgeschlossen ist, sollte in der Konsole die Meldung „Score created“ (Punktzahl erstellt) angezeigt werden. Wird stattdessen ein Fehler angezeigt? Öffnen Sie die Funktionslogs über die Firebase Console, um zu sehen, was schiefgelaufen ist.

Schließlich können wir unseren Score abrufen und aktualisieren.

leaderboard.getRank(999);
leaderboard.updateScore(999, 0);
leaderboard.getRank(999); // we should be last place now (11)

Diese Implementierung führt jedoch zu unerwünschten linearen Zeit- und Speicheranforderungen für das Abrufen des Rangs einer bestimmten Punktzahl. Da sowohl die Ausführungszeit als auch der Arbeitsspeicher von Funktionen begrenzt sind, werden unsere Abrufe nicht nur immer langsamer, sondern die Funktionen werden nach einer bestimmten Anzahl von hinzugefügten Ergebnissen in der Bestenliste auch Zeitüberschreitungen oder Abstürze verursachen, bevor sie ein Ergebnis zurückgeben können. Offensichtlich brauchen wir etwas Besseres, wenn wir mehr als nur eine Handvoll Spieler haben wollen.

Wenn Sie sich mit Firestore auskennen, wissen Sie vielleicht, dass sich mit COUNT-Aggregationsabfragen die Leistung dieses Leaderboards deutlich verbessern lässt. Und du hättest recht! Bei COUNT-Abfragen lässt sich dies gut auf bis zu etwa eine Million Nutzer skalieren, die Leistung ist jedoch weiterhin linear.

Aber Moment mal, denken Sie vielleicht, wenn wir sowieso alle Dokumente in der Sammlung aufzählen, können wir jedem Dokument einen Rang zuweisen. Wenn wir es dann abrufen müssen, sind unsere Abrufe O(1) in Bezug auf Zeit und Arbeitsspeicher. Das führt uns zu unserem nächsten Ansatz, der regelmäßig aktualisierten Bestenliste.

4. Bestenliste mit regelmäßigen Aktualisierungen implementieren

Der Schlüssel zu diesem Ansatz besteht darin, den Rang im Dokument selbst zu speichern. Wenn wir ihn abrufen, erhalten wir also den Rang ohne zusätzlichen Aufwand. Dazu benötigen wir eine neue Art von Funktion.

Fügen Sie in index.js Folgendes hinzu:

// Also add this to the top of your file
const admin = require("firebase-admin");

exports.scheduledFunctionCrontab = functions.pubsub.schedule("0 2 * * *")
    // Schedule this when most of your users are offline to avoid
    // database spikiness.
    .timeZone("America/Los_Angeles")
    .onRun((context) => {
      const scores = admin.firestore().collection("scores");
      scores.orderBy("score", "desc").get().then((snapshot) => {
        let rank = 1;
        const writes = [];
        for (const docSnapshot of snapshot.docs) {
          const docReference = scores.doc(docSnapshot.id);
          writes.push(docReference.set({rank: rank}, admin.firestore.SetOptions.merge()));
          rank++;
        }
        Promise.all(writes).then((result) => {
          console.log(`Writes completed with results: ${result}`);
        });
      });
      return null;
    });

Unsere Lese-, Aktualisierungs- und Schreibvorgänge sind jetzt ganz einfach. „Write“ und „Update“ bleiben unverändert, „Read“ wird jedoch (in functions-helpers.js):

async function readRank(playerID, firestore) {
  const scores = firestore.collection("scores");
  const playerSnapshot = await scores
      .where("user", "==", playerID).get();
  if (playerSnapshot.size === 0) {
    throw Error(`User not found in leaderboard: ${playerID}`);
  }

  const player = playerSnapshot.docs[0];
  if (player.get("rank") === undefined) {
    // This score was added before our scheduled function could run,
    // but this shouldn't be treated as an error
    return {
    user: playerID,
    rank: null,
    score: player.get("score"),
  };
  }

  return {
    user: playerID,
    rank: player.get("rank"),
    score: player.get("score"),
  };
}

Leider können Sie die Funktion nicht bereitstellen und testen, ohne Ihrem Projekt ein Rechnungskonto hinzuzufügen. Wenn Sie ein Abrechnungskonto haben, verkürzen Sie das Intervall für die geplante Funktion. Die Funktion weist dann auf magische Weise Ränge für die Ergebnisse in Ihrer Bestenliste zu.

Falls nicht, löschen Sie die geplante Funktion und fahren Sie mit der nächsten Implementierung fort.

Löschen Sie die Ergebnisse in Ihrer Firestore-Datenbank, indem Sie neben der Sammlung „scores“ auf die drei Punkte klicken, um sich auf den nächsten Abschnitt vorzubereiten.

5. Echtzeit-Bestenliste für Bäume implementieren

Bei diesem Ansatz werden Suchdaten in der Datenbank-Collection selbst gespeichert. Anstatt eine einheitliche Sammlung zu haben, möchten wir alles in einem Baum speichern, den wir durchlaufen können, indem wir uns durch Dokumente bewegen. So können wir eine binäre (oder n-äre) Suche nach dem Rang einer bestimmten Punktzahl durchführen. Wie könnte das aussehen?

Zuerst müssen wir die Werte in ungefähr gleichmäßige Gruppen aufteilen. Dazu benötigen wir einige Informationen zu den Werten der von unseren Nutzern protokollierten Ergebnisse. Wenn Sie beispielsweise eine Bestenliste für die Fähigkeitsbewertung in einem kompetitiven Spiel erstellen, sind die Fähigkeitsbewertungen Ihrer Nutzer fast immer normalverteilt. Unsere Funktion zum Generieren von Zufalls-Scores verwendet Math.random() von JavaScript, was zu einer ungefähr gleichmäßigen Verteilung führt. Daher teilen wir unsere Buckets gleichmäßig auf.

In diesem Beispiel verwenden wir der Einfachheit halber drei Buckets. Wenn Sie diese Implementierung in einer echten App verwenden, werden Sie jedoch wahrscheinlich feststellen, dass mehr Buckets zu schnelleren Ergebnissen führen. Ein flacherer Baum bedeutet im Durchschnitt weniger Abrufe von Sammlungen und weniger Konflikte bei der Sperrung.

Der Rang eines Spielers ergibt sich aus der Summe der Anzahl der Spieler mit höheren Scores plus eins für den Spieler selbst. In jeder Sammlung unter scores werden drei Dokumente gespeichert, die jeweils einen Bereich, die Anzahl der Dokumente in jedem Bereich und dann drei entsprechende Untersammlungen enthalten. Um einen Rang zu ermitteln, durchlaufen wir diesen Baum auf der Suche nach einer Punktzahl und verfolgen die Summe der höheren Punktzahlen. Wenn wir die Punktzahl kennen, wissen wir auch die richtige Summe.

Das Schreiben ist deutlich komplizierter. Zuerst müssen wir alle Schreibvorgänge in einer Transaktion ausführen, um Dateninkonsistenzen zu vermeiden, wenn mehrere Schreib- oder Lesevorgänge gleichzeitig erfolgen. Außerdem müssen wir alle oben beschriebenen Bedingungen beibehalten, während wir den Baum durchlaufen, um unsere neuen Dokumente zu schreiben. Da wir die gesamte Baumkomplexität dieses neuen Ansatzes in Kombination mit der Notwendigkeit, alle unsere Originaldokumente zu speichern, haben, werden unsere Speicherkosten leicht steigen (aber immer noch linear sein).

In functions-helpers.js:

async function createScore(playerID, score, firestore) {
  /**
   * This function assumes a minimum score of 0 and that value
   * is between min and max.
   * Returns the expected size of a bucket for a given score
   * so that bucket sizes stay constant, to avoid expensive
   * re-bucketing.
   * @param {number} value The new score.
   * @param {number} min The min of the previous range.
   * @param {number} max The max of the previous range. Must be greater than
   *     min.
   * @return {Object<string, number>} Returns an object containing the new min
   *     and max.
   */
  function bucket(value, min, max) {
    const bucketSize = (max - min) / 3;
    const bucketMin = Math.floor(value / bucketSize) * bucketSize;
    const bucketMax = bucketMin + bucketSize;
    return {min: bucketMin, max: bucketMax};
  }

  /**
   * A function used to store pending writes until all reads within a
   * transaction have completed.
   *
   * @callback PendingWrite
   * @param {admin.firestore.Transaction} transaction The transaction
   *     to be used for writes.
   * @return {void}
   */

  /**
   * Recursively searches for the node to write the score to,
   * then writes the score and updates any counters along the way.
   * @param {number} id The user associated with the score.
   * @param {number} value The new score.
   * @param {admin.firestore.CollectionReference} coll The collection this
   *     value should be written to.
   * @param {Object<string, number>} range An object with properties min and
   *     max defining the range this score should be in. Ranges cannot overlap
   *     without causing problems. Use the bucket function above to determine a
   *     root range from constant values to ensure consistency.
   * @param {admin.firestore.Transaction} transaction The transaction used to
   *     ensure consistency during tree updates.
   * @param {Array<PendingWrite>} pendingWrites A series of writes that should
   *     occur once all reads within a transaction have completed.
   * @return {void} Write error/success is handled via the transaction object.
   */
  async function writeScoreToCollection(
      id, value, coll, range, transaction, pendingWrites) {
    const snapshot = await transaction.get(coll);
    if (snapshot.empty) {
      // This is the first score to be inserted into this node.
      for (const write of pendingWrites) {
        write(transaction);
      }
      const docRef = coll.doc();
      transaction.create(docRef, {exact: {score: value, user: id}});
      return;
    }

    const min = range.min;
    const max = range.max;

    for (const node of snapshot.docs) {
      const data = node.data();
      if (data.exact !== undefined) {
        // This node held an exact score.
        const newRange = bucket(value, min, max);
        const tempRange = bucket(data.exact.score, min, max);

        if (newRange.min === tempRange.min &&
          newRange.max === tempRange.max) {
          // The scores belong in the same range, so we need to "demote" both
          // to a lower level of the tree and convert this node to a range.
          const rangeData = {
            range: newRange,
            count: 2,
          };
          for (const write of pendingWrites) {
            write(transaction);
          }
          const docReference = node.ref;
          transaction.set(docReference, rangeData);
          transaction.create(docReference.collection("scores").doc(), data);
          transaction.create(
              docReference.collection("scores").doc(),
              {exact: {score: value, user: id}},
          );
          return;
        } else {
          // The scores are in different ranges. Continue and try to find a
          // range that fits this score.
          continue;
        }
      }

      if (data.range.min <= value && data.range.max > value) {
        // The score belongs to this range that may have subvalues.
        // Increment the range's count in pendingWrites, since
        // subsequent recursion may incur more reads.
        const docReference = node.ref;
        const newCount = node.get("count") + 1;
        pendingWrites.push((t) => {
          t.update(docReference, {count: newCount});
        });
        const newRange = bucket(value, min, max);
        return writeScoreToCollection(
            id,
            value,
            docReference.collection("scores"),
            newRange,
            transaction,
            pendingWrites,
        );
      }
    }

    // No appropriate range was found, create an `exact` value.
    transaction.create(coll.doc(), {exact: {score: value, user: id}});
  }

  const scores = firestore.collection("scores");
  const players = firestore.collection("players");
  return firestore.runTransaction((transaction) => {
    return writeScoreToCollection(
        playerID, score, scores, {min: 0, max: 1000}, transaction, [],
    ).then(() => {
      transaction.create(players.doc(), {
        user: playerID,
        score: score,
      });
    });
  });
}

Das ist sicherlich komplizierter als unsere letzte Implementierung, die nur einen Methodenaufruf und sechs Codezeilen umfasste. Nachdem Sie diese Methode implementiert haben, fügen Sie der Datenbank einige Werte hinzu und beobachten Sie die Struktur des resultierenden Baums. In der JS-Konsole:

leaderboard.addScores();

Die resultierende Datenbankstruktur sollte in etwa so aussehen. Die Baumstruktur ist deutlich zu sehen und die Blätter des Baums stellen einzelne Werte dar.

scores
  - document
    range: 0-333.33
    count: 2
    scores:
      - document
        exact:
          score: 18
          user: 1
      - document
        exact:
          score: 22
          user: 2

Nachdem wir das Schwierigste hinter uns haben, können wir die Werte lesen, indem wir den Baum wie zuvor beschrieben durchlaufen.

async function readRank(playerID, firestore) {
  const players = await firestore.collection("players")
      .where("user", "==", playerID).get();
  if (players.empty) {
    throw Error(`Player not found in leaderboard: ${playerID}`);
  }
  if (players.size > 1) {
    console.info(`Multiple scores with player ${playerID}, fetching first`);
  }
  const player = players.docs[0].data();
  const score = player.score;

  const scores = firestore.collection("scores");

  /**
   * Recursively finds a player score in a collection.
   * @param {string} id The player's ID, since some players may be tied.
   * @param {number} value The player's score.
   * @param {admin.firestore.CollectionReference} coll The collection to
   *     search.
   * @param {number} currentCount The current count of players ahead of the
   *     player.
   * @return {Promise<number>} The rank of the player (the number of players
   *     ahead of them plus one).
   */
  async function findPlayerScoreInCollection(id, value, coll, currentCount) {
    const snapshot = await coll.get();
    for (const doc of snapshot.docs) {
      if (doc.get("exact") !== undefined) {
        // This is an exact score. If it matches the score we're looking
        // for, return. Otherwise, check if it should be counted.
        const exact = doc.data().exact;
        if (exact.score === value) {
          if (exact.user === id) {
            // Score found.
            return currentCount + 1;
          } else {
            // The player is tied with another. In this case, don't increment
            // the count.
            continue;
          }
        } else if (exact.score > value) {
          // Increment count
          currentCount++;
          continue;
        } else {
          // Do nothing
          continue;
        }
      } else {
        // This is a range. If it matches the score we're looking for,
        // search the range recursively, otherwise, check if it should be
        // counted.
        const range = doc.data().range;
        const count = doc.get("count");
        if (range.min > value) {
          // The range is greater than the score, so add it to the rank
          // count.
          currentCount += count;
          continue;
        } else if (range.max <= value) {
          // do nothing
          continue;
        } else {
          const subcollection = doc.ref.collection("scores");
          return findPlayerScoreInCollection(
              id,
              value,
              subcollection,
              currentCount,
          );
        }
      }
    }
    // There was no range containing the score.
    throw Error(`Range not found for score: ${value}`);
  }

  const rank = await findPlayerScoreInCollection(playerID, score, scores, 0);
  return {
    user: playerID,
    rank: rank,
    score: score,
  };
}

Updates sind Teil einer anderen Übung. Versuchen Sie, in Ihrer JS-Konsole mit den Methoden leaderboard.addScore(id, score) und leaderboard.getRank(id) Punktzahlen hinzuzufügen und abzurufen, und sehen Sie sich an, wie sich die Bestenliste in der Firebase Console ändert.

Diese Implementierung hat jedoch ihren Preis: Die Komplexität, die wir hinzugefügt haben, um eine logarithmische Leistung zu erzielen.

• Erstens kann es bei dieser Bestenlistenimplementierung zu Problemen mit der Sperrenkonkurrenz kommen, da für Transaktionen das Sperren von Lese- und Schreibvorgängen für Dokumente erforderlich ist, um sicherzustellen, dass sie konsistent bleiben.
• Zweitens gilt in Firestore ein Limit für die Tiefe von Untersammlungen von 100. Das bedeutet, dass Sie vermeiden müssen, Unterstrukturen nach 100 gleichwertigen Ergebnissen zu erstellen. Das ist in dieser Implementierung nicht der Fall.
• Schließlich wird diese Bestenliste nur im Idealfall, in dem der Baum ausgeglichen ist, logarithmisch skaliert. Wenn der Baum nicht ausgeglichen ist, ist die Leistung dieser Bestenliste im schlimmsten Fall wieder linear.

Wenn Sie fertig sind, löschen Sie die Sammlungen scores und players über die Firebase Console. Wir fahren dann mit der letzten Bestenlistenimplementierung fort.

6. Stochastische (probabilistische) Bestenliste implementieren

Wenn Sie den Einfügungscode ausführen, stellen Sie möglicherweise fest, dass Ihre Funktionen bei zu vielen parallelen Ausführungen mit einer Fehlermeldung zu Konflikten bei Transaktionssperren fehlschlagen. Es gibt Möglichkeiten, dies zu umgehen, die wir in diesem Codelab nicht näher erläutern. Wenn Sie jedoch kein genaues Ranking benötigen, können Sie die gesamte Komplexität des vorherigen Ansatzes durch etwas Einfacheres und Schnelleres ersetzen. Sehen wir uns an, wie wir anstelle einer genauen Rangfolge eine geschätzte Rangfolge für die Ergebnisse unserer Spieler zurückgeben können und wie sich dadurch unsere Datenbanklogik ändert.

Bei diesem Ansatz teilen wir die Bestenliste in 100 Buckets auf, die jeweils etwa ein Prozent der erwarteten Ergebnisse repräsentieren. Dieser Ansatz funktioniert auch ohne Kenntnis unserer Score-Verteilung. In diesem Fall können wir keine ungefähr gleichmäßige Verteilung der Scores im gesamten Bucket garantieren. Wenn wir jedoch wissen, wie unsere Scores verteilt werden, können wir genauere Schätzungen vornehmen.

Unser Ansatz ist wie folgt: Wie zuvor wird in jedem Bucket die Anzahl der Scores innerhalb des Bereichs und der Bereich der Scores gespeichert. Wenn ein neuer Wert eingefügt wird, wird das entsprechende Bucket gesucht und die Anzahl erhöht. Wenn wir einen Rang abrufen, summieren wir einfach die Buckets davor und schätzen dann innerhalb unseres Buckets, anstatt weiter zu suchen. Dadurch erhalten wir sehr gute Lookups und Einfügungen in konstanter Zeit und es ist viel weniger Code erforderlich.

Zuerst das Einfügen:

// Add this line to the top of your file.
const admin = require("firebase-admin");

// Implement this method (again).
async function createScore(playerID, score, firestore) {
  const scores = await firestore.collection("scores").get();
  if (scores.empty) {
    // Create the buckets since they don't exist yet.
    // In a real app, don't do this in your write function. Do it once
    // manually and then keep the buckets in your database forever.
    for (let i = 0; i < 10; i++) {
      const min = i * 100;
      const max = (i + 1) * 100;
      const data = {
        range: {
          min: min,
          max: max,
        },
        count: 0,
      };
      await firestore.collection("scores").doc().create(data);
    }
    throw Error("Database not initialized");
  }

  const buckets = await firestore.collection("scores")
      .where("range.min", "<=", score).get();
  for (const bucket of buckets.docs) {
    const range = bucket.get("range");
    if (score < range.max) {
      const writeBatch = firestore.batch();
      const playerDoc = firestore.collection("players").doc();
      writeBatch.create(playerDoc, {
        user: playerID,
        score: score,
      });
      writeBatch.update(
          bucket.ref,
          {count: admin.firestore.FieldValue.increment(1)},
      );
      const scoreDoc = bucket.ref.collection("scores").doc();
      writeBatch.create(scoreDoc, {
        user: playerID,
        score: score,
      });
      return writeBatch.commit();
    }
  }
}

Dieser Einfügecode enthält oben eine Logik zum Initialisieren des Datenbankstatus mit einer Warnung, dass dies nicht in der Produktion erfolgen sollte. Der Code für die Initialisierung ist überhaupt nicht vor Race Conditions geschützt. Wenn Sie dies also tun würden, würden mehrere gleichzeitige Schreibvorgänge Ihre Datenbank beschädigen, indem sie eine Reihe von doppelten Buckets erzeugen.

Stellen Sie Ihre Funktionen bereit und führen Sie dann eine Einfügung aus, um alle Buckets mit dem Wert „0“ zu initialisieren. Es wird ein Fehler zurückgegeben, den Sie ignorieren können.

leaderboard.addScore(999, 0); // The params aren't important here.

Nachdem die Datenbank korrekt initialisiert wurde, können wir addScores ausführen und die Struktur unserer Daten in der Firebase Console ansehen. Die resultierende Struktur ist viel flacher als bei unserer letzten Implementierung, obwohl sie oberflächlich ähnlich sind.

leaderboard.addScores();

So lesen Sie die Ergebnisse:

async function readRank(playerID, firestore) {
  const players = await firestore.collection("players")
      .where("user", "==", playerID).get();
  if (players.empty) {
    throw Error(`Player not found in leaderboard: ${playerID}`);
  }
  if (players.size > 1) {
    console.info(`Multiple scores with player ${playerID}, fetching first`);
  }
  const player = players.docs[0].data();
  const score = player.score;

  const scores = await firestore.collection("scores").get();
  let currentCount = 1; // Player is rank 1 if there's 0 better players.
  let interp = -1;
  for (const bucket of scores.docs) {
    const range = bucket.get("range");
    const count = bucket.get("count");
    if (score < range.min) {
      currentCount += count;
    } else if (score >= range.max) {
      // do nothing
    } else {
      // interpolate where the user is in this bucket based on their score.
      const relativePosition = (score - range.min) / (range.max - range.min);
      interp = Math.round(count - (count * relativePosition));
    }
  }

  if (interp === -1) {
    // Didn't find a correct bucket
    throw Error(`Score out of bounds: ${score}`);
  }

  return {
    user: playerID,
    rank: currentCount + interp,
    score: score,
  };
}

Da wir die Funktion addScores so konfiguriert haben, dass sie eine einheitliche Verteilung von Ergebnissen generiert, und wir die lineare Interpolation innerhalb der Gruppen verwenden, erhalten wir sehr genaue Ergebnisse. Die Leistung unserer Bestenliste wird nicht beeinträchtigt, wenn wir die Anzahl der Nutzer erhöhen, und wir müssen uns (nicht so sehr) um Konflikte bei der Sperrung kümmern, wenn wir Zählungen aktualisieren.

7. Anhang: Betrug

Wenn ich Werte über die JS-Konsole eines Browser-Tabs in mein Codelab schreibe, können meine Spieler dann nicht einfach das Leaderboard manipulieren und behaupten, sie hätten einen Highscore erzielt, den sie nicht auf faire Weise erreicht haben?

Ja, das ist möglich. Wenn Sie Betrug verhindern möchten, ist es am besten, Client-Schreibvorgänge in Ihrer Datenbank über Sicherheitsregeln zu deaktivieren, den Zugriff auf Ihre Cloud Functions zu sichern, damit Clients sie nicht direkt aufrufen können, und dann Aktionen im Spiel auf Ihrem Server zu validieren, bevor Sie Punkteaktualisierungen an die Bestenliste senden.

Diese Strategie ist jedoch kein Allheilmittel gegen Cheating. Bei einem ausreichend großen Anreiz können Cheater Wege finden, serverseitige Validierungen zu umgehen. Viele große, erfolgreiche Videospiele spielen ständig Katz und Maus mit ihren Cheatern, um neue Cheats zu identifizieren und zu verhindern, dass sie sich ausbreiten. Eine schwierige Folge dieses Phänomens ist, dass die serverseitige Validierung für jedes Spiel von Natur aus maßgeschneidert ist. Firebase bietet zwar Tools gegen Missbrauch wie App Check, die verhindern, dass ein Nutzer Ihr Spiel über einen einfachen Script-Client kopiert, aber Firebase bietet keinen Dienst, der einem ganzheitlichen Anti-Cheat entspricht.

Wenn Sie keine serverseitige Validierung verwenden, werden in Bestenlisten beliebter Spiele oder bei geringen Hürden für Cheating die Spitzenwerte von Cheatern belegt.

8. Glückwunsch

Herzlichen Glückwunsch! Sie haben erfolgreich vier verschiedene Bestenlisten in Firebase erstellt. Je nach den Anforderungen Ihres Spiels an Genauigkeit und Geschwindigkeit können Sie eine auswählen, die für Sie zu einem angemessenen Preis funktioniert.

Als Nächstes kannst du dir die Lernpfade für Spiele ansehen.