一、简介
最后更新： 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 上成功构建了四个不同的排行榜！根据您的游戏对精确性和速度的需求，您将能够以合理的成本选择适合您的一款。
接下来，查看游戏的学习路径。