1. Giới thiệu
Cập nhật lần cuối: 27-01-2023
Xây dựng bảng xếp hạng cần những gì?
Về cốt lõi, bảng xếp hạng chỉ là các bảng điểm với một yếu tố phức tạp: việc đọc thứ hạng cho bất kỳ điểm số nhất định nào đều yêu cầu kiến thức về tất cả các điểm số khác theo một thứ tự nào đó. Ngoài ra, nếu trò chơi của bạn thành công, bảng xếp hạng của bạn sẽ ngày càng lớn và được đọc và ghi thường xuyên. Để xây dựng một bảng xếp hạng thành công, nó cần có khả năng xử lý hoạt động xếp hạng này một cách nhanh chóng.
Những gì bạn sẽ xây dựng
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 khác nhau, mỗi bảng xếp hạng phù hợp với một tình huống khác nhau.
Bạn sẽ học được gì
Bạn sẽ tìm hiểu cách triển khai bốn bảng xếp hạng khác nhau:
- Một cách triển khai đơn giản sử dụng cách đếm bản ghi đơn giản để xác định thứ hạng
- Bảng xếp hạng giá rẻ, cập nhật định kỳ
- Bảng xếp hạng thời gian thực với một số thứ vô nghĩa về cây
- 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
Những gì bạn cần
- 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 trả phí (tùy chọn)
- Firebase CLI v11.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 CLI để có thêm tùy chọn cài đặt. - Kiến thức về JavaScript, Cloud Firestore, Cloud Function và Chrome DevTools
2. Bắt đầu thiết lập
Lấy mã
Chúng tôi đã đưa 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ở nó trong môi trường nhà phát triển yêu thích của mình. Đối với lớp học lập trình này, chúng tôi đã sử dụng VS Code nhưng bất kỳ trình soạn thảo văn bản nào cũng được.
và 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 khởi đầu của chúng ta là gì?
Dự án của chúng tôi hiện là một bản trống với một số chức năng trống:
-
index.htmlchứa một số tập lệnh kết nối 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ả đầu ra của chúng. Chúng tôi sẽ sử dụng điều này để giao tiếp với phần phụ trợ của chúng tôi và xem kết quả của việc gọi hàm của chúng tôi. Trong trường hợp thực tế, bạn sẽ trực tiếp thực hiện các lệnh gọi phụ trợ này từ trò chơi của mình—chúng tôi 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 trò chơi mỗi khi bạn muốn thêm điểm vào bảng xếp hạng . -
functions/index.jschứa tất cả các Hàm đám mây của chúng tôi. Bạn sẽ thấy một số hàm tiện ích, 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 để 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 tôi sẽ triển khai. Đối với mỗi bảng xếp hạng, chúng tôi sẽ triển khai các chức năng đọc, tạo và cập nhật, đồng thời 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 cả mức độ phức tạp trong quá trình triển khai cũng như hiệu suất mở rộng quy mô của nó. -
functions/utils.jschứa nhiều hàm tiện ích hơn. Chúng ta sẽ không chạm vào 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 Firebase , nhấp vào Thêm dự án .
- Để tạo một dự án mới, hãy nhập tên dự án mong muốn.
Điều này cũng sẽ đặt ID dự án (hiển thị bên dưới tên dự án) thành giá trị nào đó dựa trên tên dự án. Bạn có thể tùy ý nhấp vào biểu tượng chỉnh sửa trên ID dự án để tùy chỉnh thêm. - Nếu được nhắc, hãy xem lại và chấp nhận các điều khoản của Firebase .
- Nhấp vào Tiếp tục .
- Chọn tùy chọn 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 .
- Khi dự án đã được tạo, hãy nhấp vào Tiếp tục .
- Từ menu Xây dựng , nhấp vào Chức năng và 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 Blaze.
- Từ menu Xây dựng , nhấp vào Cơ sở dữ liệu Firestore .
- Trong hộp thoại Tạo cơ sở dữ liệu xuất hiện, chọn Bắt đầu ở chế độ thử nghiệm , sau đó nhấp vào Tiếp theo .
- Chọn một khu vực từ 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 của bạn
- Trong một thiết bị đầu cuối, điều hướng đến thư mục gốc của dự án và chạy
firebase use --add. Chọn dự án Firebase bạn vừa tạo. - Trong thư mục gốc của dự án, hãy chạy
firebase emulators:start --only hosting. - Trong trình duyệt của bạn, điều hướng đến
localhost:5000. - Mở bảng điều khiển JavaScript của Chrome DevTools và 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 bạn nhìn thấy thông báo chào mừng, 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 bảng xếp hạng đơn giản
Đến cuối phần này, chúng ta sẽ có thể thêm điểm vào bảng xếp hạng và để nó cho chúng ta biết thứ hạng của mình.
Trước khi bắt đầu, hãy giải thích cách hoạt động của việc 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 và 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 dẫn trước họ. Điều này làm cho việc chèn và cập nhật điểm trở nên dễ dàng. Để chèn điểm mới, chúng tôi chỉ cần thêm điểm đó vào bộ sưu tập và để cập nhật điểm, chúng tôi lọc theo người dùng hiện tại rồi cập nhật tài liệu kết quả. Hãy xem nó trông như thế nào trong mã.
Trong functions/functions-helper.js , hãy triển khai hàm createScore , việc này gần như đơn giản như sau:
async function createScore(score, playerID, firestore) {
return firestore.collection("scores").doc().create({
user: playerID,
score: score,
});
}
Để cập nhật điểm, chúng ta chỉ cần thêm kiểm tra lỗi để đảm bảo điểm đ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,
});
}
Và cuối cùng, hàm xếp hạng đơn giản nhưng ít mở rộng hơn 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}`);
}
Hãy đưa nó vào thử nghiệm! Triển khai các chức năng của bạn bằng cách chạy lệnh sau trong terminal:
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 khác để chúng tôi có thể xem 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 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". Thay vào đó, bạn nhìn thấy lỗi? Mở nhật ký Chức năng thông qua bảng điều khiển Firebase để xem điều gì đã xảy ra.
Và cuối cùng, chúng ta có thể tìm nạp và cập nhật điểm của mình.
leaderboard.getRank(999);
leaderboard.updateScore(999, 0);
leaderboard.getRank(999); // we should be last place now (11)
Tuy nhiên, việc triển khai này mang lại cho chúng ta những yêu cầu về thời gian và bộ nhớ tuyến tính không mong muốn để tìm nạp thứ hạng của một điểm nhất định. Vì cả thời gian thực thi hàm và bộ nhớ đều bị giới hạn, điều này không chỉ có nghĩa là quá trình tìm nạp của chúng tôi ngày càng trở nên chậm hơn mà sau khi đủ điểm được thêm vào bảng xếp hạng, các hàm của chúng tôi sẽ hết thời gian chờ hoặc gặp sự cố trước khi chúng có thể trả về kết quả. Rõ ràng, chúng tôi sẽ cần thứ gì đó tốt hơn nếu muốn mở rộng quy mô ra ngoài một số ít người chơi.
Nếu bạn là người đam mê Firestore, bạn có thể biết COUNT truy vấn tổng hợp , điều này sẽ làm cho bảng xếp hạng này hoạt động hiệu quả hơn nhiều. Và bạn đã đúng! Với COUNT truy vấn, tỷ lệ này rất nhỏ dưới một triệu người dùng, mặc dù hiệu suất của nó vẫn tuyến tính.
Nhưng chờ đã, bạn có thể tự nghĩ, nếu chúng ta định liệt kê tất cả các tài liệu trong bộ sưu tập, chúng ta có thể gán cho mỗi tài liệu một thứ hạng và sau đó khi chúng ta cần tìm nạp nó, các lần tìm nạp của chúng ta sẽ là O(1) thời gian và nỗi nhớ! Điều này dẫn chúng ta đến cách tiếp cận tiếp theo, bảng xếp hạng được cập nhật định kỳ.
4. Triển khai bảng xếp hạng cập nhật định kỳ
Chìa khóa 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 nó sẽ cung cấp cho chúng ta thứ hạng mà không cần phải làm thêm gì. Để đạt được điều này, chúng ta sẽ cần một loại chức năng mới.
Trong index.js , thêm phần 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 tôi đều rất hay và đơn giản. Viết và cập nhật đều không thay đổi, nhưng đọc 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 thực hiện chức năng đã lên lịch và xem chức năng của bạn gán thứ hạng một cách kỳ diệu cho điểm số trên bảng xếp hạng của bạn.
Nếu không, hãy xóa chức năng đã lên lịch và chuyển sang bước triển khai tiếp theo.
Hãy tiếp tục và xóa điểm trong cơ sở dữ liệu Firestore của bạn bằng cách nhấp vào 3 dấu chấm bên cạnh bộ sưu tập điểm để chuẩn bị cho phần tiếp theo.
5. Triển khai bảng xếp hạng dạng cây theo thời gian thực
Cách tiếp cận này hoạt động bằng cách lưu trữ dữ liệu tìm kiếm trong chính bộ sưu tập cơ sở dữ liệu. Thay vì có một bộ sưu tập thố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ể duyệt qua bằng cách di chuyển qua các tài liệu. Điều này cho phép chúng tôi thực hiện tìm kiếm nhị phân (hoặc n-ary) cho thứ hạng của một điểm nhất định. Điều đó có thể trông như thế nào?
Để bắt đầu, chúng tôi muốn có thể phân phối điểm số của mình thành các nhóm gần như đồng đều, điều này đòi hỏi một số kiến thức về giá trị của điểm số mà người dùng của chúng tôi đang ghi lại; ví dụ: nếu bạn đang xây dựng bảng xếp hạng để xếp hạng kỹ năng trong một trò chơi cạnh tranh thì xếp hạng kỹ năng của người dùng hầu như sẽ luôn có phân phối chuẩn. Hàm tạo điểm ngẫu nhiên của chúng tôi sử dụng Math.random() của JavaScript, dẫn đến sự phân phối gần như đồng đều, vì vậy chúng tôi sẽ chia đều các nhóm của mình.
Trong ví dụ này, chúng tôi sẽ sử dụng 3 nhóm để đơn giản hóa, nhưng bạn có thể thấy rằng nếu bạn sử dụng cách triển khai này trong một ứng dụng thực, thì nhiều nhóm hơn sẽ mang lại kết quả nhanh hơn–cây nông hơn có nghĩa là trung bình ít lần tìm nạp bộ sưu tập hơn và ít tranh chấp khóa hơn.
Thứ hạng của một người chơi được tính bằng tổng số người chơi có điểm cao hơn, cộng thêm một cho chính người chơi đó. Mỗi bộ sưu tập theo scores sẽ lưu trữ ba tài liệu, mỗi tài liệu có một phạm vi, số lượng tài liệu trong mỗi phạm vi và sau đó là ba bộ sưu tập con tương ứng. Để đọc thứ hạng, chúng ta sẽ duyệt qua cây này để tìm kiếm điểm số và theo dõi tổng của các điểm lớn hơn. Khi tìm được điểm của mình, chúng ta cũng sẽ có số tiền chính xác.
Viết phức tạp hơn đáng kể. Trước tiên, chúng ta cần thực hiện tất cả các thao tác ghi trong một giao dịch để tránh tình trạng dữ liệu không nhất quán khi xảy ra nhiều thao tác ghi hoặc đọc cùng một 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 duyệt qua cây để viết các tài liệu mới. Và cuối cùng, vì chúng tôi có tất cả sự phức tạp của 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ữ của chúng tôi sẽ tăng nhẹ (nhưng vẫn tuyến tính).
Trong 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,
});
});
});
}
Điều này chắc chắn phức tạp hơn so với lần triển khai gần đây nhất của chúng tôi, đó là một lệnh gọi phương thức duy nhất và chỉ có sáu dòng mã. Khi bạn đã triển khai phương pháp này, hãy thử thêm một vài điểm vào cơ sở dữ liệu và quan sát cấu trúc của cây kết quả. Trong bảng điều khiển JS của bạn:
leaderboard.addScores();
Cấu trúc cơ sở dữ liệu thu được sẽ trông giống như thế này, với cấu trúc cây hiển thị rõ ràng và các lá của cây biểu thị từng điểm số riêng lẻ.
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 đã giải quyết xong phần khó khăn, chúng ta có thể đọc điểm bằng cách duyệt qua cây như đã mô tả trước đây.
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,
};
}
Cập nhật được để lại như một bài tập bổ sung. Hãy thử thêm và tìm nạp điểm trong bảng điều khiển JS của bạn bằng các 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 Firebase.
Tuy nhiên, với việc triển khai này, độ phức tạp mà chúng tôi đã thêm vào để đạt được hiệu suất logarit sẽ phải trả giá.
- Đầu tiên, việc triển khai bảng xếp hạng này có thể gặp phải các vấn đề tranh chấp khóa vì các giao dịch yêu cầu khóa đọc và ghi vào tài liệu để đảm bảo chúng luôn nhất quán.
- Thứ hai, Firestore áp đặt giới hạn độ sâu bộ sưu tập con là 100 , nghĩa là bạn sẽ cần tránh tạo cây con sau 100 điểm bằng nhau, điều mà việc triển khai này không làm được.
- Và cuối cùng, bảng xếp hạng này chỉ chia tỷ lệ theo logarit trong trường hợp lý tưởng khi cây cân bằng–nếu nó không cân bằng thì hiệu suất trong trường hợp xấu nhất của bảng xếp hạng này lại một lần nữa là tuyến tính.
Sau khi bạn hoàn tất, hãy xóa scores và bộ sưu tập players thông qua bảng điều khiển Firebase và chúng ta sẽ chuyển sang bước triển khai bảng xếp hạng cuối cùng của mình.
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 song song quá nhiều lần thì các chức năng của bạn sẽ bắt đầu bị lỗi kèm theo thông báo lỗi liên quan đến tranh chấp khóa giao dịch. Có nhiều cách giải quyết 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 xếp hạng chính xác, bạn có thể loại bỏ tất cả sự phức tạp của phương pháp trước đó để thực hiện một phương pháp vừa đơn giản vừa nhanh hơn. Chúng ta hãy xem cách chúng tôi có thể trả về thứ hạng ước tính cho điểm số của người chơi thay vì thứ hạng chính xác và điều đó thay đổi logic cơ sở dữ liệu của chúng tôi như thế nào.
Đối với phương pháp này, chúng tôi sẽ chia bảng xếp hạng của mình thành 100 nhóm, mỗi nhóm đại diện cho khoảng 1% số điểm mà chúng tôi mong đợi nhận được. Cách tiếp cận này hoạt động ngay cả khi không biết về phân phối điểm của chúng tôi, 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 các phép tính gần đúng nếu chúng tôi biết điểm của mình sẽ được phân phối như thế nào .
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 bên trong và phạm vi điểm. Khi chèn điểm mới, chúng ta sẽ tìm nhóm điểm và tăng số lượng của nó. Khi tìm nạp thứ hạng, chúng tôi sẽ chỉ tính tổng các nhóm phía trước nó rồi ước chừng trong nhóm của chúng tôi thay vì tìm kiếm thêm. Điều này mang lại cho chúng tôi khả năng 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 của bạn ở trên cùng kèm theo cảnh báo không thực hiện những việc như thế này trong quá trình sản xuất. Mã khởi tạo hoàn toàn không được bảo vệ trước các điều kiện tương tranh, 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 nhóm trùng lặp.
Hãy tiếp tục và triển khai các hàm của bạn, sau đó chạy phần chèn để khởi tạo tất cả các nhóm có số lượng bằng 0. Nó sẽ trả về một 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 tạo chính xác, chúng ta có thể chạy addScores và xem cấu trúc dữ liệu của mình trong bảng điều khiển Firebase. Cấu trúc kết quả phẳng hơn nhiều so với lần triển khai gần đây nhất của chúng tôi, mặc dù bề ngoài chúng giống nhau.
leaderboard.addScores();
Và bây giờ, để đọc điểm:
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 tôi đã tạo ra hàm addScores tạo ra sự phân bổ điểm số đồng đều và chúng tôi đang sử dụng phép nội suy tuyến tính trong các nhóm nên chúng tôi 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 giảm khi chúng tôi tăng số lượng người dùng, và chúng tôi không phải lo lắng về việc tranh chấp khóa (nhiều) khi cập nhật số lượng.
7. Phụ lục: Gian lận
Đợi đã, bạn có thể đang nghĩ, nếu tôi đang 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 tab trình duyệt, thì không lẽ bất kỳ người chơi nào của tôi cũng có thể nói dối bảng xếp hạng và nói rằng họ đạt điểm cao mà thực ra họ không làm được đạt được một cách công bằng?
Vâng, họ có thể. Nếu bạn muốn ngăn chặn gian lận, cách mạnh mẽ nhất để làm như vậy là vô hiệu hóa khả năng ghi của ứng dụng khách vào cơ sở dữ liệu của bạn thông qua các quy tắc bảo mật , quyền truy cập an toàn vào Chức năng đám mây của bạn để ứng dụng khách 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 đó gửi thông tin cập nhật về điểm số lên 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ách bệnh chống gian lận–với động cơ đủ lớn, những kẻ gian lận có thể tìm cách phá vỡ quá trình xác thực phía máy chủ và nhiều trò chơi điện tử lớn, thành công liên tục chơi trò mèo vờn chuột với những kẻ gian lận để xác định danh tính của họ. những mánh gian lận mới và ngăn chặn chúng sinh sôi nảy nở. Một hậu 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 đặt riêng; mặc dù Firebase cung cấp các công cụ chống lạm dụng như Kiểm tra ứng dụng sẽ ngăn người dùng sao chép trò chơi của bạn thông qua một ứng dụng khách có tập lệnh đơn giản, Firebase không cung cấp bất kỳ dịch vụ nào có chức năng chống gian lận toàn diện.
Bất cứ điều gì thiếu 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 gian lận đủ thấp, sẽ dẫn đến một bảng xếp hạng trong đó 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 đã xây dựng thành công bốn bảng xếp hạng khác nhau trên Firebase! Tùy thuộc vào nhu cầu về độ chính xác và tốc độ của trò chơi, bạn sẽ có thể chọn một trò chơi phù hợp với mình với chi phí hợp lý.
Tiếp theo, hãy xem lộ trình học tập dành cho trò chơi.