1.简介
上次更新日期:2023 年 1 月 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 Functions 和 Chrome 开发者工具
2. 准备工作
获取代码
我们已将您完成此项目所需的一切都放入一个 Git 代码库中。首先,您需要获取代码,并在您喜爱的开发环境中将其打开。在此 Codelab 中,我们使用的是 VS Code,但任何文本编辑器都可以执行此操作。
或者,将其克隆到您选择的目录中:
git clone https://github.com/FirebaseExtended/firestore-leaderboards-codelab.git
我们从何处入手?
目前,我们的项目是一个空白函数,其中包含一些空函数:
index.html
包含一些粘合脚本,可让我们从开发者控制台调用函数并查看其输出。我们将使用它与后端交互,并查看函数调用的结果。在实际场景中,您需要直接从游戏中进行这些后端调用。我们在此 Codelab 中并未使用游戏,因为每次您想要在排行榜中添加得分时,玩游戏所需的时间会太长。functions/index.js
包含我们所有的 Cloud Functions 函数。您将看到一些实用函数(如addScores
和deleteScores
),以及我们将在此 Codelab 中实现的函数,这些函数会在另一个文件中调用辅助函数。functions/functions-helpers.js
包含我们要实现的空函数。对于每个排行榜,我们将实现读取、创建和更新函数,您将了解我们的实现选择如何影响实现复杂性和扩缩性能。functions/utils.js
包含更多实用函数。在本 Codelab 中,我们不会涉及该文件。
创建和配置 Firebase 项目
- 在 Firebase 控制台中,点击添加项目。
- 如需创建新项目,请输入要使用的项目名称。
此操作还会根据项目名称将项目 ID(显示在项目名称下方)设置为某个值。您可以选择点击项目 ID 上的修改图标,以进一步对其进行自定义。 - 如果看到相关提示,请查看并接受 Firebase 条款。
- 点击继续。
- 选择为此项目启用 Google Analytics 选项,然后点击继续。
- 选择要使用的现有 Google Analytics 账号,或选择创建新账号来创建新账号。
- 点击 Create project。
- 项目创建完毕后,点击继续。
- 在 Build(构建)菜单中,点击 Functions(函数),如果系统提示,请升级您的项目以使用 Blaze 结算方案。
- 在构建菜单中,点击 Firestore 数据库。
- 在显示的创建数据库对话框中,选择以测试模式开始,然后点击下一步。
- 从 Cloud Firestore 位置下拉列表中选择一个区域,然后点击启用。
配置和运行排行榜
- 在终端中,转到项目根目录并运行
firebase use --add
。选择您刚刚创建的 Firebase 项目。 - 在项目的根目录中,运行
firebase emulators:start --only hosting
。 - 在浏览器中,前往
localhost:5000
。 - 打开 Chrome 开发者工具的 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.
写入完成后,您应该会在控制台中看到一条响应,显示“Score created”(已创建得分)。还是看到了错误?通过 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 写入值,难道我的任何玩家都会对排行榜撒谎,说自己获得了高分,但他们的得分并不公平?
是的,可以。如果您想防止作弊,最可靠的方式是通过安全规则禁止客户端向数据库写入数据,并禁止对 Cloud Functions 函数进行安全访问,以便客户端无法直接调用它们,然后在将得分更新发送到排行榜之前在服务器上验证游戏内操作。
请务必注意,这种策略并不是打击作弊的灵丹妙药,有了足够大的激励,作弊者可以想方设法规避服务器端验证,并且许多成功的大型视频游戏经常与作弊者进行猫鼠游戏,以发现新的作弊并阻止它们的扩散。这种现象的一个严重后果是,每款游戏的服务器端验证本质上都是定制的;虽然 Firebase 提供了 App Check 等反滥用工具,可防止用户通过简单的脚本客户端复制您的游戏,但 Firebase 不提供任何整体反作弊的服务。
如果不进行服务器端验证,那么对于热门程度足够高或作弊门槛足够低的游戏,排行榜中的前列玩家全都是作弊者。
8. 恭喜
恭喜,您已成功在 Firebase 上构建了四个不同的排行榜!您可以根据游戏对精确性和速度的需求,选择适合您的方案,价格合理。
接下来,请查看游戏的学习路线。