1. Giới thiệu
Lần cập nhật gần đây nhất: ngày 27 tháng 01 năm 2023
Cần những gì để tạo bảng xếp hạng?
Về cơ bản, bảng xếp hạng chỉ là các bảng điểm có một yếu tố phức tạp: việc đọc thứ hạng cho một điểm số nhất định bất kỳ yêu cầu bạn phải biết tất cả các điểm số khác theo thứ tự nào đó. Ngoài ra, nếu trò chơi của bạn được phát hành, bảng xếp hạng của bạn sẽ phát triển lớn hơn và được đọc và ghi thường xuyên. Để xây dựng được một bảng xếp hạng thành công, ứng dụng cần phải xử lý nhanh thao tác xếp hạng này.
Sản phẩm bạn sẽ tạo ra
Trong lớp học lập trình này, bạn sẽ triển khai nhiều bảng xếp hạng, mỗi bảng xếp hạng phù hợp với một tình huống riêng.
Kiến thức bạn sẽ học được
Bạn sẽ tìm hiểu cách triển khai 4 bảng xếp hạng:
- Cách triển khai đơn giản bằng cách đếm bản ghi đơn giản để xác định thứ hạng
- Một bảng xếp hạng rẻ, được cập nhật định kỳ
- Một bảng xếp hạng theo thời gian thực với một số thông tin vô nghĩa
- Bảng xếp hạng ngẫu nhiên (xác suất) để xếp hạng gần đúng số lượng người chơi rất lớn
Bạn cần có
- Phiên bản Chrome gần đây (107 trở lên)
- Node.js 16 trở lên (chạy
nvm --versionđể xem số phiên bản của bạn nếu bạn đang sử dụng nvm) - Gói Firebase Blaze có tính phí (không bắt buộc)
- Firebase CLI phiên bản 11.16.0 trở lên
Để cài đặt CLI, bạn có thể chạynpm install -g firebase-toolshoặc tham khảo tài liệu về CLI để biết thêm các cách cài đặt khác. - Có kiến thức về JavaScript, Cloud Firestore, Cloud Functions và Công cụ của Chrome cho nhà phát triển
2. Thiết lập
Lấy mã
Chúng tôi đã đặt mọi thứ bạn cần cho dự án này vào kho lưu trữ Git. Để bắt đầu, bạn cần lấy mã và mở mã đó trong môi trường nhà phát triển yêu thích của bạn. Đối với lớp học lập trình này, chúng ta đã sử dụng VS Code, nhưng bất kỳ trình soạn thảo văn bản nào cũng sử dụng được.
rồi giải nén tệp zip đã tải xuống.
Hoặc sao chép vào thư mục bạn chọn:
git clone https://github.com/FirebaseExtended/firestore-leaderboards-codelab.git
Điểm xuất phát của chúng ta là gì?
Dự án của chúng tôi hiện là một phương tiện chặn trống với một số hàm trống:
index.htmlchứa một số tập lệnh keo cho phép chúng ta gọi các hàm từ bảng điều khiển dành cho nhà phát triển và xem kết quả của các hàm đó. Chúng ta sẽ sử dụng hàm này để giao tiếp với phần phụ trợ và xem kết quả của lệnh gọi hàm. Trong tình huống thực tế, bạn sẽ trực tiếp thực hiện những lệnh gọi phụ trợ này từ trò chơi của mình. Chúng ta sẽ không sử dụng trò chơi trong lớp học lập trình này vì sẽ mất quá nhiều thời gian để chơi một trò chơi mỗi khi bạn muốn thêm điểm số vào bảng xếp hạng.functions/index.jschứa tất cả Cloud Functions của chúng tôi. Bạn sẽ thấy một số hàm hiệu dụng nhưaddScoresvàdeleteScores, cũng như các hàm chúng ta sẽ triển khai trong lớp học lập trình này. Các hàm này sẽ gọi các hàm trợ giúp trong một tệp khác.functions/functions-helpers.jschứa các hàm trống mà chúng ta sẽ triển khai. Đối với mỗi bảng xếp hạng, chúng ta sẽ triển khai các chức năng đọc, tạo và cập nhật. Bạn sẽ thấy lựa chọn triển khai của chúng tôi ảnh hưởng như thế nào đến sự phức tạp của việc triển khai cũng như hiệu suất mở rộng của việc triển khai.functions/utils.jschứa nhiều hàm hiệu dụng hơn. Chúng ta sẽ không đề cập đến tệp này trong lớp học lập trình này.
Tạo và định cấu hình dự án Firebase
- Trong bảng điều khiển của Firebase, hãy nhấp vào Thêm dự án.
- Để tạo một dự án mới, hãy nhập tên dự án mà bạn muốn.
Thao tác này cũng sẽ thiết lập mã dự án (hiển thị bên dưới tên dự án) thành một giá trị nào đó dựa trên tên dự án. Bạn có thể nhấp vào biểu tượng chỉnh sửa trên mã dự án để tuỳ chỉnh thêm (không bắt buộc). - Nếu được nhắc, hãy xem xét và chấp nhận các điều khoản của Firebase.
- Nhấp vào Tiếp tục.
- Chọn mục Bật Google Analytics cho dự án này, rồi nhấp vào Tiếp tục.
- Chọn tài khoản Google Analytics hiện có để sử dụng hoặc chọn Tạo tài khoản mới để tạo tài khoản mới.
- Nhấp vào Tạo dự án.
- Sau khi tạo dự án, hãy nhấp vào Tiếp tục.
- Trên trình đơn Tạo, hãy nhấp vào Chức năng. Nếu được nhắc, hãy nâng cấp dự án của bạn để sử dụng Gói thanh toán linh hoạt.
- Trên trình đơn Build (Tạo), hãy nhấp vào Firestore cơ sở dữ liệu.
- Trong hộp thoại Tạo cơ sở dữ liệu vừa xuất hiện, hãy chọn Bắt đầu ở chế độ thử nghiệm, rồi nhấp vào Tiếp theo.
- Chọn một khu vực trong trình đơn thả xuống vị trí Cloud Firestore, sau đó nhấp vào Bật.
Định cấu hình và chạy bảng xếp hạng
- Trong dòng lệnh, hãy chuyển đến thư mục gốc của dự án rồi chạy
firebase use --add. Chọn dự án Firebase mà bạn vừa tạo. - Trong gốc của dự án, hãy chạy
firebase emulators:start --only hosting. - Trong trình duyệt, hãy chuyển đến
localhost:5000. - Mở bảng điều khiển JavaScript trong Công cụ của Chrome cho nhà phát triển rồi nhập
leaderboard.js:const leaderboard = await import("http://localhost:5000/scripts/leaderboard.js"); - Chạy
leaderboard.codelab();trong bảng điều khiển. Nếu thấy thông báo chào mừng thì tức là bạn đã hoàn tất! Nếu không, hãy tắt trình mô phỏng và chạy lại các bước 2-4.
Hãy bắt đầu triển khai bảng xếp hạng đầu tiên.
3. Triển khai một bảng xếp hạng đơn giản
Kết thúc phần này, chúng ta có thể thêm một điểm số vào bảng xếp hạng và yêu cầu điểm số đó cho biết thứ hạng của chúng ta.
Trước khi bắt đầu, hãy cùng tìm hiểu cách triển khai bảng xếp hạng này: Tất cả người chơi được lưu trữ trong một bộ sưu tập duy nhất. Việc tìm nạp thứ hạng của người chơi được thực hiện bằng cách truy xuất bộ sưu tập và đếm xem có bao nhiêu người chơi đang dẫn trước họ. Điều này giúp chèn và cập nhật điểm số dễ dàng. Để chèn một điểm số mới, chúng ta chỉ cần thêm điểm số đó vào bộ sưu tập. Để cập nhật điểm này, chúng ta lọc theo người dùng hiện tại rồi cập nhật tài liệu thu được. Hãy xem thành quả trông như thế nào trong mã.
Trong functions/functions-helper.js, hãy triển khai hàm createScore. Hàm này khá đơn giản:
async function createScore(score, playerID, firestore) {
return firestore.collection("scores").doc().create({
user: playerID,
score: score,
});
}
Để cập nhật điểm số, chúng tôi chỉ cần thêm chế độ kiểm tra lỗi để đảm bảo điểm số đang được cập nhật đã tồn tại:
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,
});
}
Cuối cùng là hàm xếp hạng đơn giản nhưng ít mở rộng của chúng tôi:
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}`);
}
Chúng ta hãy thử xem! Triển khai các hàm bằng cách chạy dòng sau trong thiết bị đầu cuối:
firebase deploy --only functions
Sau đó, trong bảng điều khiển JS của Chrome, hãy thêm một số điểm số khác để chúng ta có thể thấy thứ hạng của mình so với những người chơi khác.
leaderboard.addScores(); // Results may take some time to appear.
Bây giờ, chúng ta có thể thêm điểm số của riêng mình vào danh sách kết hợp:
leaderboard.addScore(999, 11); // You can make up a score (second argument) here.
Khi quá trình ghi hoàn tất, bạn sẽ thấy phản hồi trong bảng điều khiển có nội dung "Đã tạo điểm số". Bạn thấy lỗi? Mở nhật ký Hàm thông qua bảng điều khiển của Firebase để xem đã xảy ra lỗi gì.
Cuối cùng, chúng ta có thể tìm nạp và cập nhật điểm số.
leaderboard.getRank(999);
leaderboard.updateScore(999, 0);
leaderboard.getRank(999); // we should be last place now (11)
Tuy nhiên, cách triển khai này đòi hỏi chúng tôi đáp ứng những yêu cầu không mong muốn về thời gian và bộ nhớ cho tuyến tính để tìm nạp thứ hạng của một điểm số nhất định. Do thời gian thực thi hàm và bộ nhớ đều bị giới hạn, nên điều này không chỉ có nghĩa là các lần tìm nạp của chúng ta sẽ ngày càng chậm lại, mà sau khi chúng ta thêm đủ điểm số vào bảng xếp hạng, các hàm của chúng ta sẽ hết thời gian chờ hoặc gặp sự cố trước khi có thể trả về kết quả. Rõ ràng là chúng tôi cần cải thiện hơn nữa nếu có thể mở rộng ra ngoài một số ít người chơi.
Nếu là người say mê Firestore, bạn có thể sẽ biết đến COUNT truy vấn tổng hợp, giúp bảng xếp hạng này hoạt động hiệu quả hơn rất nhiều. Đúng vậy! Với COUNT truy vấn, con số này sẽ giảm xuống dưới một triệu người dùng hoặc hơn một triệu người dùng, mặc dù hiệu suất của truy vấn vẫn là tuyến tính.
Nhưng chờ một chút, có thể bạn sẽ tự nhủ, nếu chúng ta định liệt kê tất cả tài liệu trong tập hợp, chúng ta có thể gán thứ hạng cho mỗi tài liệu và khi cần tìm nạp, chúng ta sẽ mất O(1) thời gian và bộ nhớ! Việc này dẫn đến phương pháp tiếp theo của mình, đó là bảng xếp hạng cập nhật định kỳ.
4. Triển khai bảng xếp hạng được cập nhật định kỳ
Yếu tố quan trọng của phương pháp này là lưu trữ thứ hạng trong chính tài liệu, vì vậy, việc tìm nạp thứ hạng giúp chúng ta có được thứ hạng mà không cần phải làm gì thêm. Để làm được điều này, chúng ta cần một loại hàm mới.
Trong index.js, hãy thêm đoạn mã sau:
// 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;
});
Giờ đây, các thao tác đọc, cập nhật và ghi của chúng ta đều đẹp và đơn giản. Hoạt động ghi và cập nhật đều không thay đổi, nhưng quyền đọc sẽ trở thành (trong 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"),
};
}
Rất tiếc, bạn sẽ không thể triển khai và thử nghiệm tính năng này nếu không thêm tài khoản thanh toán vào dự án của mình. Nếu bạn có tài khoản thanh toán, hãy rút ngắn khoảng thời gian trên hàm đã lên lịch và xem chức năng của bạn tự động chỉ định thứ hạng cho điểm số trên bảng xếp hạng của bạn.
Nếu không, hãy xoá hàm đã lên lịch rồi chuyển sang lần triển khai tiếp theo.
Hãy tiếp tục và xoá điểm số trong cơ sở dữ liệu Firestore của bạn bằng cách nhấp vào biểu tượng 3 dấu chấm bên cạnh tập hợp điểm để chuẩn bị cho phần tiếp theo.
5. Triển khai bảng xếp hạng cây theo thời gian thực
Phương pháp này hoạt động bằng cách lưu trữ dữ liệu tìm kiếm trong chính tập hợp cơ sở dữ liệu. Thay vì có một bộ sưu tập đồng nhất, mục tiêu của chúng ta là lưu trữ mọi thứ trong một cây mà chúng ta có thể di chuyển qua bằng cách di chuyển qua các tài liệu. Điều này cho phép chúng ta thực hiện tìm kiếm nhị phân (hoặc n-ary) để tìm thứ hạng của một điểm số đã cho. Thông tin đó trông như thế nào?
Để bắt đầu, chúng tôi muốn có thể chia điểm số của mình thành các nhóm gần như bằng nhau. Việc này đòi hỏi một số kiến thức về giá trị của các điểm mà người dùng của chúng tôi đang ghi nhật ký; ví dụ: nếu bạn đang xây dựng bảng xếp hạng về xếp hạng kỹ năng trong một trò chơi cạnh tranh, mức phân loại kỹ năng hầu như sẽ luôn được phân bổ bình thường. Hàm tạo điểm số ngẫu nhiên của chúng tôi sử dụng Math.random() của JavaScript, nhờ đó, chúng ta sẽ phân phối gần như đồng đều. Vì vậy, chúng ta sẽ chia đều các nhóm.
Trong ví dụ này, chúng tôi sẽ sử dụng 3 nhóm để đơn giản hoá, nhưng bạn có thể thấy rằng nếu sử dụng cách triển khai này trong ứng dụng thực tế thì nhiều nhóm hơn sẽ mang lại kết quả nhanh hơn. Cây càng nông hơn có nghĩa là trung bình ít tìm nạp tập hợp hơn và ít tranh chấp khoá hơn.
Thứ hạng của một người chơi được tính bằng tổng của số người chơi có điểm cao hơn cộng với 1 của chính người chơi đó. Mỗi tập hợp trong scores sẽ lưu trữ 3 tài liệu, mỗi tập hợp có một phạm vi, số lượng tài liệu trong mỗi dải ô và 3 tập hợp con tương ứng. Để đọc thứ hạng, chúng ta sẽ di chuyển qua cây này để tìm một điểm số và theo dõi tổng điểm của các điểm số lớn hơn. Khi tìm được điểm, chúng ta cũng sẽ có tổng chính xác.
Việc viết sẽ phức tạp hơn nhiều. Trước tiên, chúng ta cần thực hiện tất cả các lượt ghi trong một giao dịch để ngăn chặn việc dữ liệu không nhất quán khi có nhiều lượt ghi hoặc đọc xảy ra cùng lúc. Chúng ta cũng cần duy trì tất cả các điều kiện đã mô tả ở trên khi di chuyển qua cây để viết tài liệu mới. Và cuối cùng, do chúng ta có tất cả sự phức tạp dạng cây của phương pháp mới này kết hợp với nhu cầu lưu trữ tất cả tài liệu gốc, nên chi phí lưu trữ sẽ tăng một chút (nhưng vẫn là tuyến tính).
Sau 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,
});
});
});
}
Bước này chắc chắn phức tạp hơn so với cách triển khai gần đây nhất của chúng ta, đó là một lệnh gọi phương thức duy nhất và chỉ có 6 dòng mã. Sau khi triển khai phương pháp này, hãy thử thêm một vài điểm số vào cơ sở dữ liệu rồi quan sát cấu trúc của cây thu được. Trong bảng điều khiển JS:
leaderboard.addScores();
Cấu trúc cơ sở dữ liệu thu được sẽ có dạng như sau, với cấu trúc cây rõ ràng và các lá của cây đại diện cho từng điểm số.
scores
- document
range: 0-333.33
count: 2
scores:
- document
exact:
score: 18
user: 1
- document
exact:
score: 22
user: 2
Bây giờ, chúng ta đã thực hiện xong phần khó khăn, chúng ta có thể đọc điểm số bằng cách đi qua cây như được mô tả trước đó.
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,
};
}
Nội dung cập nhật được giữ lại là một bài tập bổ sung. Hãy thử thêm và tìm nạp điểm số trong bảng điều khiển JS bằng phương thức leaderboard.addScore(id, score) và leaderboard.getRank(id) và xem bảng xếp hạng của bạn thay đổi như thế nào trong bảng điều khiển của Firebase.
Tuy nhiên, với cách triển khai này, cái giá phải trả là độ phức tạp mà chúng tôi đã thêm vào để đạt được hiệu suất lôgarit.
- Thứ nhất, việc triển khai bảng xếp hạng này có thể gặp vấn đề tranh chấp khoá vì các giao dịch yêu cầu phải khoá chức năng đọc và ghi vào tài liệu để đảm bảo tính nhất quán.
- Thứ hai, Firestore áp dụng giới hạn chiều sâu của bộ sưu tập phụ là 100, nghĩa là bạn sẽ cần tránh tạo các cây con sau 100 điểm số được ràng buộc, trong khi cách triển khai này không áp dụng được.
- Cuối cùng, bảng xếp hạng này chỉ chia tỷ lệ theo lôgarit trong trường hợp lý tưởng khi cây đang cân bằng. Nếu cây không cân bằng thì hiệu suất xấu nhất của bảng xếp hạng này lại là tuyến tính.
Sau khi hoàn tất, hãy xoá các bộ sưu tập scores và players qua bảng điều khiển của Firebase và chúng ta sẽ chuyển sang bước triển khai bảng xếp hạng gần đây nhất.
6. Triển khai bảng xếp hạng ngẫu nhiên (xác suất)
Khi chạy mã chèn, bạn có thể nhận thấy rằng nếu chạy mã quá nhiều lần song song, các hàm của bạn sẽ bắt đầu không thành công kèm theo thông báo lỗi liên quan đến tranh chấp khoá giao dịch. Có những cách xoay quanh vấn đề này mà chúng ta sẽ không khám phá trong lớp học lập trình này, nhưng nếu không cần thứ hạng chính xác, bạn có thể loại bỏ tất cả những gì phức tạp của phương pháp trước đó để tìm ra phương pháp vừa đơn giản hơn vừa nhanh hơn. Hãy cùng xem cách chúng ta có thể trả về thứ hạng ước tính cho người chơi thay vì một thứ hạng chính xác và cách điều đó làm thay đổi logic cơ sở dữ liệu của chúng tôi.
Đối với phương pháp này, chúng tôi sẽ chia bảng xếp hạng thành 100 nhóm, mỗi nhóm đại diện cho khoảng 1 phần trăm số điểm mà chúng tôi dự kiến sẽ nhận được. Phương pháp này hoạt động ngay cả khi chúng tôi không biết về cách phân phối điểm. Trong trường hợp đó, chúng tôi không có cách nào để đảm bảo phân phối điểm gần như đồng đều trong toàn bộ nhóm, nhưng chúng tôi sẽ đạt được độ chính xác cao hơn trong kết quả ước tính nếu biết cách phân phối điểm.
Cách tiếp cận của chúng tôi như sau: giống như trước đây, mỗi nhóm lưu trữ số lượng điểm trong phạm vi và phạm vi điểm số. Khi chèn một điểm số mới, chúng ta sẽ tìm nhóm điểm số và tăng số lượng của điểm số đó. Khi tìm nạp thứ hạng, chúng ta sẽ chỉ tổng hợp các nhóm đứng trước nó rồi ước chừng trong nhóm thay vì tìm kiếm thêm. Điều này cho phép chúng ta tra cứu và chèn thời gian liên tục rất tốt và yêu cầu ít mã hơn nhiều.
Đầu tiên, chèn:
// 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();
}
}
}
Bạn sẽ nhận thấy mã chèn này có một số logic để khởi tạo trạng thái cơ sở dữ liệu ở trên cùng kèm theo cảnh báo không được làm tương tự như vậy trong phiên bản chính thức. Mã để khởi tạo hoàn toàn không được bảo vệ trước các điều kiện tranh đấu, vì vậy nếu bạn làm điều này, nhiều lần ghi đồng thời sẽ làm hỏng cơ sở dữ liệu của bạn bằng cách cung cấp cho bạn một loạt các bộ chứa trùng lặp.
Hãy tiếp tục và triển khai các hàm rồi chạy thao tác chèn để khởi tạo tất cả các nhóm có số lượng bằng 0. Thao tác này sẽ trả về lỗi mà bạn có thể yên tâm bỏ qua.
leaderboard.addScore(999, 0); // The params aren't important here.
Bây giờ, cơ sở dữ liệu đã được khởi chạy đúng cách, chúng ta có thể chạy addScores và xem cấu trúc dữ liệu trong bảng điều khiển của Firebase. Cấu trúc thu được phẳng hơn nhiều so với cách triển khai gần đây nhất của chúng ta, mặc dù chúng khá giống nhau.
leaderboard.addScores();
Và bây giờ là cách đọc điểm số:
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,
};
}
Vì chúng ta đã làm cho hàm addScores tạo phân phối điểm số đồng nhất và sử dụng nội suy tuyến tính trong các nhóm, nên chúng ta sẽ nhận được kết quả rất chính xác, hiệu suất của bảng xếp hạng sẽ không suy giảm khi chúng ta tăng số lượng người dùng và chúng ta không phải lo lắng về tranh chấp khoá (nhiều) khi cập nhật số lượng.
7. Phụ lục: Hành vi gian lận
Đợi một chút, có thể bạn đang nghĩ rằng nếu tôi viết các giá trị vào lớp học lập trình của mình thông qua bảng điều khiển JS của thẻ trình duyệt, liệu có ai trong số những người chơi của tôi lại nói dối trên bảng xếp hạng và nói rằng họ đạt điểm cao mà họ không đạt được một cách công bằng phải không?
Có, chúng có thể. Nếu muốn ngăn chặn hành vi gian lận, cách hiệu quả nhất là vô hiệu hoá hoạt động ghi máy khách vào cơ sở dữ liệu của bạn thông qua quy tắc bảo mật, quyền truy cập bảo mật vào Cloud Functions để các ứng dụng không thể gọi trực tiếp cho họ, sau đó xác thực các hành động trong trò chơi trên máy chủ của bạn trước khi gửi thông tin cập nhật điểm số tới bảng xếp hạng.
Điều quan trọng cần lưu ý là chiến lược này không phải là thuốc chữa bệnh gian lận – với một động lực đủ lớn, những kẻ gian lận có thể tìm ra cách né tránh các hoạt động xác thực phía máy chủ và nhiều trò chơi điện tử thành công và lớn liên tục chơi trò lừa đảo với những hành vi gian lận để xác định các trò gian lận mới và ngăn chặn chúng sinh sôi nảy nở. Một hệ quả khó khăn của hiện tượng này là việc xác thực phía máy chủ cho mọi trò chơi vốn được thiết kế riêng; Mặc dù Firebase cung cấp các công cụ chống hành vi sai trái như tính năng Kiểm tra ứng dụng để ngăn người dùng sao chép trò chơi thông qua một ứng dụng được viết tập lệnh đơn giản, nhưng Firebase không cung cấp bất kỳ dịch vụ nào như là biện pháp chống gian lận toàn diện.
Bất cứ điều gì thiếu khả năng xác thực phía máy chủ, đối với một trò chơi đủ phổ biến hoặc rào cản đủ thấp để gian lận, sẽ dẫn đến bảng xếp hạng mà tất cả các giá trị cao nhất đều là những kẻ gian lận.
8. Xin chúc mừng
Xin chúc mừng! Bạn đã tạo thành công 4 bảng xếp hạng trên Firebase! Tuỳ thuộc vào nhu cầu về độ chính xác và tốc độ của trò chơi, bạn có thể chọn một lối chơi phù hợp với mình với mức chi phí hợp lý.
Tiếp theo, hãy xem lộ trình học tập về trò chơi.