一、簡介
最後更新： 2023-01-27
建立排行榜需要什麼？
從本質上講，排行榜只是帶有一個複雜因素的分數表：讀取任何給定分數的排名需要以某種順序了解所有其他分數。此外，如果您的遊戲取得成功，您的排行榜將會變得越來越大，並且會被頻繁讀取和寫入。為了建立一個成功的排行榜，它需要能夠快速處理這個排名操作。
你將建構什麼
在此 Codelab 中，您將實現各種不同的排行榜，每種排行榜適用於不同的場景。
你將學到什麼
您將學習如何實現四種不同的排行榜：
- 使用簡單的記錄計數來確定排名的簡單實現
- 一個便宜的、定期更新的排行榜
- 帶有一些樹廢話的即時排行榜
- 用於對非常大的玩家群進行近似排名的隨機（機率）排行榜
你需要什麼
- 最新版本的 Chrome（107 或更高版本）
- Node.js 16 或更高版本（如果您使用 nvm，請執行
nvm --version查看版本號） - 付費 Firebase Blaze 方案（可選）
- Firebase CLI v11.16.0 或更高版本
若要安裝 CLI，您可以執行npm install -g firebase-tools或參閱CLI 文件以取得更多安裝選項。 - 了解 JavaScript、Cloud Firestore、Cloud Function 和Chrome DevTools
2. 設定
取得程式碼
我們已將此項目所需的所有內容放入 Git 儲存庫中。首先，您需要取得程式碼並在您最喜歡的開發環境中開啟它。在本 Codelab 中，我們使用了 VS Code，但任何文字編輯器都可以。
或者，克隆到您選擇的目錄中：
git clone https://github.com/FirebaseExtended/firestore-leaderboards-codelab.git
我們的出發點是什麼？
我們的專案目前是一張白紙，有一些空函數：
-
index.html包含一些黏合腳本，讓我們可以從開發控制台呼叫函數並查看它們的輸出。我們將使用它與後端交互並查看函數呼叫的結果。在現實場景中，您可以直接從遊戲中進行這些後端調用 - 我們在此 Codelab 中不使用遊戲，因為每次您想要將分數添加到排行榜時，玩遊戲都會花費太長時間。 -
functions/index.js包含我們所有的雲端函數。您將看到一些實用函數，例如addScores和deleteScores，以及我們將在此 Codelab 中實現的函數，這些函數呼叫另一個檔案中的輔助函數。 -
functions/functions-helpers.js包含我們將實現的空函數。對於每個排行榜，我們將實現讀取、創建和更新功能，您將看到我們選擇的實現如何影響實現的複雜性及其擴展性能。 -
functions/utils.js包含更多實用函數。我們不會在此 Codelab 中觸及此文件。
建立並配置 Firebase 項目
- 在Firebase 控制台中，按一下新增項目。
- 若要建立新項目，請輸入所需的項目名稱。
這也將根據項目名稱將項目 ID（顯示在項目名稱下方）設定為某些內容。您可以選擇單擊項目 ID 上的編輯圖示以進一步自訂它。 - 如果出現提示，請查看並接受Firebase 條款。
- 單擊繼續。
- 選擇為此項目啟用 Google Analytics選項，然後按一下繼續。
- 選擇要使用的現有 Google Analytics 帳戶，或選擇建立新帳戶來建立新帳戶。
- 點選建立項目。
- 建立項目後，按一下「繼續」 。
- 從「建置」功能表中，按一下「功能」 ，如果出現提示，請升級您的專案以使用 Blaze 計費計劃。
- 從「建置」功能表中，按一下Firestore 資料庫。
- 在出現的「建立資料庫」對話方塊中，選擇「以測試模式啟動」 ，然後按一下「下一步」 。
- 從Cloud Firestore 位置下拉清單中選擇一個區域，然後按一下「啟用」 。
配置並運行您的排行榜
- 在終端機中，導航到專案根目錄並運行
firebase use --add。選擇您剛剛建立的 Firebase 專案。 - 在專案的根目錄中，運行
firebase emulators:start --only hosting。 - 在瀏覽器中，導覽至
localhost:5000。 - 開啟 Chrome DevTools 的 JavaScript 控制台並匯入
leaderboard.js：const leaderboard = await import("http://localhost:5000/scripts/leaderboard.js"); - 運行
leaderboard.codelab();在控制台中。如果您看到歡迎訊息，則表示一切就緒！如果沒有，請關閉模擬器並重新執行步驟 2-4。
讓我們進入第一個排行榜的實現。
3. 實現一個簡單的排行榜
在本節結束時，我們將能夠在排行榜上添加分數並讓它告訴我們我們的排名。
在我們開始之前，讓我們解釋一下這個排行榜的實現是如何運作的：所有玩家都儲存在一個集合中，透過檢索該集合併計算領先於他們的玩家數量來獲取玩家的排名。這使得插入和更新樂譜變得容易。要插入新分數，我們只需將其附加到集合中，並更新它，我們過濾當前用戶，然後更新結果文件。讓我們看看程式碼是什麼樣的。
在functions/functions-helper.js中，實作createScore函數，函數非常簡單：
async function createScore(score, playerID, firestore) {
return firestore.collection("scores").doc().create({
user: playerID,
score: score,
});
}
對於更新分數，我們只需要添加錯誤檢查以確保正在更新的分數已經存在：
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,
});
}
最後，我們簡單但可擴展性較差的排名函數：
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}`);
}
讓我們來測試一下吧！透過在終端機中執行以下命令來部署您的功能：
firebase deploy --only functions
然後，在 Chrome 的 JS 控制台中，添加一些其他分數，以便我們可以看到我們在其他玩家中的排名。
leaderboard.addScores(); // Results may take some time to appear.
現在我們可以將自己的分數加入組合中：
leaderboard.addScore(999, 11); // You can make up a score (second argument) here.
寫入完成後，您應該在控制台中看到一條回應，顯示「分數已建立」。看到錯誤了嗎？透過 Firebase 控制台開啟 Functions 日誌以查看出了什麼問題。
最後，我們可以獲得並更新我們的分數。
leaderboard.getRank(999);
leaderboard.updateScore(999, 0);
leaderboard.getRank(999); // we should be last place now (11)
然而，這種實現給我們帶來了不良的線性時間和記憶體需求來獲取給定分數的排名。由於函數執行時間和記憶體都是有限的，這不僅意味著我們的獲取變得越來越慢，而且在將足夠的分數添加到排行榜後，我們的函數將在返回結果之前超時或崩潰。顯然，如果我們要擴展到少數玩家之外，我們將需要更好的東西。
如果您是 Firestore 愛好者，您可能會知道COUNT 聚合查詢，這將使此排行榜的效能更高。你是對的！透過 COUNT 查詢，其規模遠低於一百萬左右的用戶，儘管其效能仍然是線性的。
但是等等，你可能會想，如果我們要枚舉集合中的所有文檔，我們可以為每個文檔分配一個排名，然後當我們需要獲取它時，我們的獲取將是 O(1)時間和記憶！這引導我們採取下一種方法，即定期更新排行榜。
4. 實施定期更新的排行榜
這種方法的關鍵是將排名儲存在文件本身中，因此獲取它即可為我們提供排名，而無需添加任何工作。為了實現這一目標，我們需要一種新的函數。
在index.js中，加入以下內容：
// 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;
});
現在我們的讀取、更新和寫入操作都非常簡單。寫入和更新均未更改，但讀取變為（在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"),
};
}
不幸的是，如果不在專案中新增計費帳戶，您將無法部署和測試它。如果您確實有計費帳戶，請縮短預定功能的時間間隔，並觀看您的功能神奇地為您的排行榜分數分配排名。
如果沒有，則刪除預定的函數並跳到下一個實作。
繼續並透過點擊分數集合旁邊的 3 個點來刪除 Firestore 資料庫中的分數，為下一部分做好準備。
5. 實現即時樹排行榜
這種方法的工作原理是將搜尋資料儲存在資料庫集合本身。我們的目標不是擁有統一的集合，而是將所有內容儲存在樹中，我們可以透過移動文件來遍歷該樹。這使我們能夠對給定分數的排名執行二元（或 n 元）搜尋。那會是什麼樣子呢？
首先，我們希望能夠將分數分佈到大致均勻的桶中，這需要對使用者記錄的分數值有一定的了解；例如，如果您正在為競技遊戲中的技能評級建立排行榜，使用者的技能評級幾乎總是呈常態分佈。我們的隨機分數產生函數使用 JavaScript 的Math.random() ，這會產生近似均勻的分佈，因此我們將均勻地劃分我們的儲存桶。
在此範例中，為簡單起見，我們將使用3 個儲存桶，但您可能會發現，如果在實際應用程式中使用此實現，更多儲存桶將產生更快的結果- 較淺的樹平均意味著更少的集合獲取和更少的鎖爭用。
玩家的排名是由得分較高的玩家人數加上玩家本身的分數得出的。 scores下的每個集合將儲存三個文檔，每個文檔都有一個範圍，每個範圍下的文檔數量，然後是三個相應的子集合。為了讀取排名，我們將遍歷這棵樹來搜尋分數並追蹤較大分數的總和。當我們找到分數時，我們也會得到正確的總和。
寫作要複雜得多。首先，我們需要在一個事務中進行所有寫入，以防止同時發生多個寫入或讀取時出現資料不一致。當我們遍歷樹來編寫新文件時，我們還需要維護上面描述的所有條件。最後，由於我們擁有這種新方法的所有樹複雜性，並且需要儲存所有原始文檔，因此我們的儲存成本將略有增加（但仍然是線性的）。
在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,
});
});
});
}
這肯定比我們上一個實作更複雜，上一個實作是一個方法調用，只有六行程式碼。實現此方法後，嘗試在資料庫中添加一些分數並觀察生成的樹的結構。在你的 JS 控制台中：
leaderboard.addScores();
產生的資料庫結構應如下所示，樹結構清晰可見，樹的葉子代表各個分數。
scores
- document
range: 0-333.33
count: 2
scores:
- document
exact:
score: 18
user: 1
- document
exact:
score: 22
user: 2
現在我們已經解決了最困難的部分，我們可以透過前面描述的遍歷樹來讀取分數。
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,
};
}
更新作為額外的練習。嘗試使用leaderboard.addScore(id, score)和leaderboard.getRank(id)方法在 JS 控制台中新增和取得分數，並查看 Firebase 控制台中的排行榜如何變化。
然而，透過這種實現，我們為實現對數性能而增加的複雜性是有代價的。
- 首先，此排行榜實作可能會遇到鎖爭用問題，因為事務需要鎖定對文件的讀取和寫入以確保它們保持一致。
- 其次，Firestore 施加了100 的子集合深度限制，這意味著您需要避免在 100 個並列分數之後建立子樹，而此實作則不然。
- 最後，該排行榜僅在樹平衡的理想情況下以對數方式縮放 - 如果樹不平衡，則該排行榜的最壞情況性能將再次呈線性。
完成後，透過 Firebase 控制台刪除scores和players集合，我們將繼續執行最後一個排行榜實作。
6. 實現隨機（機率）排行榜
執行插入程式碼時，您可能會注意到，如果並行運行太多次，您的函數將開始失敗，並顯示與事務鎖爭用相關的錯誤訊息。我們不會在本 Codelab 中探索解決這個問題的方法，但如果您不需要精確的排名，您可以放棄先前方法的所有複雜性，以獲得更簡單、更快的方法。讓我們來看看如何返回玩家得分的估計排名而不是準確排名，以及這如何改變我們的資料庫邏輯。
對於這種方法，我們將排行榜分成 100 個部分，每個部分大約代表我們期望收到的分數的百分之一。即使不知道我們的分數分佈，這種方法也可以工作，在這種情況下，我們無法保證整個儲存桶中分數的大致均勻分佈，但如果我們確實知道我們的分數將如何分佈，我們將在近似值中獲得更高的精度。
我們的方法是這樣的：像以前一樣，每個桶儲存其內分數的數量和分數的範圍。插入新分數時，我們將找到該分數的儲存桶並增加其計數。當獲取排名時，我們只需將其前面的儲存桶相加，然後在我們的儲存桶內進行近似，而不是進一步搜尋。這為我們提供了非常好的恆定時間查找和插入，並且需要更少的程式碼。
一、插入：
// 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();
}
}
}
您會注意到此插入程式碼有一些邏輯用於在頂部初始化資料庫狀態，並警告不要在生產中執行此類操作。初始化程式碼根本沒有針對競爭條件的保護，因此如果您要這樣做，多個並發寫入會透過給您一堆重複的儲存桶來損壞您的資料庫。
繼續部署您的函數，然後執行插入以初始化計數為零的所有儲存桶。它會傳回一個錯誤，您可以安全地忽略該錯誤。
leaderboard.addScore(999, 0); // The params aren't important here.
現在資料庫已正確初始化，我們可以運行addScores並在 Firebase 控制台中查看資料的結構。儘管表面上很相似，但最終的結構比我們上次的實現要扁平得多。
leaderboard.addScores();
現在，讀取分數：
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,
};
}
由於我們已經使addScores函數產生均勻分佈的分數，並且我們在存儲桶內使用線性插值，因此我們將獲得非常準確的結果，隨著用戶數量的增加，排行榜的性能不會降低，並且在更新計數時我們不必擔心鎖爭用（同樣多）。
7. 附錄：作弊
等一下，您可能會想，如果我透過瀏覽器標籤的 JS 控制台將值寫入我的 Codelab，我的任何玩家難道不能對排行榜撒謊並說他們獲得了高分嗎？公平地實現？
是的他們可以。如果您想防止作弊，最可靠的方法是透過安全規則停用客戶端寫入資料庫，保護對雲端功能的訪問，以便客戶端無法直接呼叫它們，然後在您的伺服器上驗證遊戲內操作。將分數更新發送到排行榜。
值得注意的是，這種策略並不是對抗作弊的靈丹妙藥——只要有足夠大的激勵，作弊者就可以找到繞過伺服器端驗證的方法，並且許多大型成功的視頻遊戲不斷地與作弊者玩貓捉老鼠的遊戲來識別作弊者。新的作弊行為並阻止它們擴散。這種現象的一個困難後果是，每個遊戲的伺服器端驗證本質上都是客製化的；儘管 Firebase 提供了 App Check 等反濫用工具，可以防止用戶透過簡單的腳本用戶端複製您的遊戲，但 Firebase 並沒有提供任何相當於整體反作弊的服務。
對於足夠流行的遊戲或足夠低的作弊障礙，任何缺乏伺服器端驗證的行為都會導致排行榜上的最高值都是作弊者。
8. 恭喜
恭喜您，您已在 Firebase 上成功建立了四個不同的排行榜！根據您的遊戲對精確性和速度的需求，您將能夠以合理的成本選擇適合您的一款。
接下來，查看遊戲的學習路徑。