在 Datastore 中快速穩定地進行排名

排名:單純卻難以解決的問題

Applibot 的 App Engine 首席工程師 Tomoaki Suzuki (圖 1) 一直在努力設法解決每個大型遊戲服務都會面臨的常見難題:排名

圖 1:Applibot, Inc. 的 App Engine 首席工程師 Tomoaki Suzuki。

Applibot 是日本一大社交應用軟體供應商,這間公司的獨到之處在於,他們具有豐富的相關知識及經驗,能夠在 Google 所提供的平台式服務 (PaaS) Google App Engine 上建置可高度擴充的社交遊戲服務。Applibot 善用這個平台的強大功能,抓住了社交遊戲市場的龐大商機,不僅在日本獲得成功,在美國的業務也蒸蒸日上,取得了無庸置疑的的亮眼成就。他們其中一項主打遊戲 Legend of the Cryptids (圖 2),於 2012 年 10 月在 Apple AppStore 北美地區的遊戲類別中搶下了冠軍寶座;Legend 系列遊戲的下載次數累計共有 470 萬次。另外一項遊戲 Gang Road 則在 2012 年 12 月於 AppStore 日本地區的總銷量排名中獲得了第 1 名的佳績。

圖 2:2012 年 10 月 Apple AppStore 排名第 1 的遊戲 Legend of the Criptids。

這些遊戲都能夠順利擴充所需要的處理資源,以因應大幅上升的流量。Applibot 從來不必為了建置複雜的虛擬伺服器或是資料分割資料庫叢集而傷腦筋;他們將 App Engine 的強大功能駕馭自如,因此能夠有效達成所需的擴充性及可用性。

但提供即時更新的玩家排名就不是這麼容易解決的問題了;對 Tomoaki 而言,甚至對任何開發人員來說這都相當棘手,尤其是針對規模如此龐大的遊戲。他們的要求很簡單:

  • 滿足遊戲中的數十萬名玩家,甚至更多!
  • 每當玩家與敵人戰鬥或執行其他活動時,讓分數隨之變更。
  • 在入口網站頁面中向玩家顯示他們的最新排名。

如何計算排名?

圖 3:每位玩家都有一個分數,該如何計算他們的排名?

如果不需顧及擴充性和速度,要取得排名其實很簡單,例如您可以執行下列查詢:

SELECT count(key) FROM Players WHERE Score > YourScore

這項查詢會計算所有分數比您高的玩家人數 (圖 4),但是對入口網頁的每項要求執行這項查詢合乎實際需求嗎?如果遊戲有上百萬名玩家,這種做法得花費多少時間?

Tomoaki 一開始是採用這種做法,但是每次都要等上幾秒才能取得回應,不但速度緩慢,成本又高昂,而且執行效能會隨著規模擴大而逐漸衰減。

圖 4:最簡單的做法是掃描所有玩家。

接著,Tomoaki 又嘗試在 Memcache 中維護排名資料。這種做法雖然快速,但不穩定,因為 Memcache 項目隨時會遭到撤銷,而且有時候根本無法使用 Memcache 服務。由於這種排名服務完全倚賴記憶體內部鍵/值,因此很難維持一致性和可用性。

為了暫時解決這項問題,Tomoaki 決定將服務等級降級。他不再為每項要求計算排名,而是改為設定排程工作,每小時掃描並更新每位玩家的排名一次。透過這種方式,入口網頁的要求就能立即取得玩家排名,但是排名資料最多可能延遲一個小時。

Tomoaki 想要尋找的終極解決方法,是能夠永久持續、具備交易性的可擴充快速排名實作方式;這種方式要能夠每秒接受 300 項分數更新要求,並在數百毫秒之內取得每位玩家的排名。為了找到完美的解決方案,Tomoaki 轉而向 Kaz Sato 尋求協助;他是我們根據進階支援合約指派給 Applibot 的 Google Cloud Platform 小組解決方案架構師 (SA) 暨技術支援帳戶經理 (TAM)。

解決問題的捷徑

許多 Google Cloud Platform 大客戶或是合作夥伴 (像是 Applibot),都簽訂了進階支援合約;有了這份支援合約,不但可以享有全年無休的雲端客戶服務小組支援服務以及雲端銷售小組企業支援服務,Google 還會為每位客戶指派一名技術支援帳戶經理 (TAM)。

TAM 會代表客戶和負責建置實際雲端基礎架構的 Google 工程部門溝通,因此對於客戶的系統及架構都瞭若指掌。一旦發生重大問題,他們就會以駐公司 Google 工程部門代表的身分,運用自己的知識和人脈網路替公司解決問題,也會將問題向上呈報給小組中的解決方案架構師,或是 Cloud Platform 小組中的軟體工程師。簡而言之,進階支援合約就是透過 Google Cloud Platform 尋找解決方案的快捷管道。

負責支援 Applibot 的 TAM Kaz 知道,對於所有可擴充分佈式服務而言,排名是非解決不可的常見麻煩問題。他開始檢閱 Google Cloud Datastore 和其他 NoSQL 資料庫中的已知排名實作方式,以尋找符合 Applibot 要求的解決方案。

尋找 O(log n) 演算法

比較簡單的查詢解決方案必須掃描所有比查詢玩家得分更高的其他玩家,才能計算出排名。這個演算法的時間複雜性為 O(n),換句話說,執行查詢所需的時間會與玩家人數成正比;從實際執行的層面來看,即代表這個演算法無法擴充。因此需要 O(log n) 或是更為快速的演算法,確保查詢時間僅會隨著玩家人數的成長以對數方式增加。

如果您曾經上過電腦科學課,可能還記得二元樹狀圖、紅-黑樹狀圖或 B 樹狀圖等樹狀演算法能夠以 O(log n) 時間複雜性執行,以尋找特定元素。樹狀演算法也能透過保存各分支節點上的匯總值,計算出特定範圍中所有元素的匯總值,例如數量、最大值/最小值和平均值。使用這項技巧,就有可能以 O(log n) 的效能實作排名演算法。

Kaz 找到一個適用於 Datastore 的開放原始碼樹狀排名演算法實作方法,是由一位 Google 工程師編寫的 Google Code Jam 排名程式庫

這個 Python 程式庫顯示了兩種方法:

  • SetScore 可設定玩家的分數。
  • FindRank 可取得特定分數的排名。

隨著 SetScore 方法建立和更新玩家-分數組合,Code Jam 排名程式庫會也建立一個 N 元樹狀圖1。舉例來說,假設用一個三元樹狀圖來計算 0 至 80 分的玩家人數 (圖 5),則這個程式庫會將保存三個數字的根節點儲存為一個實體,每個數字分別對應至得分位於 0 至 26、27 至 53 和 54 至 80 這三個子範圍內的玩家人數。根節點擁有對應至各範圍的子節點,子節點中又保存了子範圍下層範圍裡的三個玩家人數值。這個階層總共需要用四個層級來儲存具有 81 個分數值的玩家人數。

圖 5:透過三元樹狀圖取得分數排名。

如要判斷獲得 30 分的玩家排名為何,這個程式庫只需讀取四個實體 (即圖表中用虛線圈出的部分),就能加總出分數高於 30 分的玩家人數;在這個例子中,由於有 22 位玩家在這四個實體的「右側」,所以查詢玩家排名第 23 位。

同樣地,對於 SetScore 的呼叫也只需更新四個實體。即使您有大量不同分數,Datastore 存取也只會按 O(log n) 增加,而不會受到玩家人數的影響。在實際操作中,Code Jam 排名程式庫將每個節點的值數預設為 100 而非 3,所以系統只需存取兩個實體;如果分數範圍超過 100,000,也只需存取三個實體。

Kaz 使用熱門的負載測試工具 Apache JMeter 對 Code Jam 排名程式庫進行測試,確認這個程式庫能夠快速回應。透過以 O(log n) 時間複雜性運作的 N 元樹狀演算法,SetScore 和 FindRank 都能夠在數百毫秒的時間內完成工作。

大量並行更新對擴充性造成限制

不過,在進行負載測試時,Kaz 發現 Code Jam 排名程式庫有一項重大限制:這個程式庫的更新總處理量擴充性相當低。當他將負載增加至每秒三項更新時,系統就開始傳回交易重試錯誤訊息;這個程式庫顯然無法滿足 Applibot 每秒 300 項更新的要求,大約只能應付目標總處理量的 1%。

為什麼會這樣呢?原因出在維護樹狀圖一致性的成本。在 Datastore 裡,更新交易中的多個實體時,必須使用實體群組來確保同步一致性。詳情請參閱「Google Cloud Datastore 同步一致性與最終一致性的平衡取捨」。Code Jam 排名程式庫是使用單一實體群組來保存整個樹狀圖,以確保樹狀圖元素數量的一致性。

然而在 Datastore 中,實體群組有效能限制;Datastore 對每個實體群組僅支援約每秒一筆交易。此外,如果在並行交易中修正同一個實體群組,就很可能會造成失敗,因而必須重試。Code Jam 排名程式庫具備同步一致性、具備交易性,速度也很快,但是卻無法支援大量並行更新。

Datastore 小組的解決方案:工作匯總

Kaz 想起 Datastore 小組中一位軟體工程師曾提及一項技巧,能夠在實體群組中取得比每秒一項更新高出許多的總處理量,做法是將一批更新匯總為一筆交易,而非將每項更新都當做獨立的單筆交易來執行。不過由於交易中包含大量更新,每筆交易所需的執行時間可能會較長,進而提高並行交易發生衝突的可能性。

應 Kaz 的要求,Datastore 小組開始討論這項問題,並建議使用與 Megastore 並用的一種設計模式,稱為「工作匯總」。

Megastore 是 Datastore 的基礎儲存層,負責管理實體群組的一致性及交易性;每秒一項更新的限制就是源於這個儲存層。由於 Megastore 廣泛應用於多項 Google 服務中,因此工程師一直都在公司內部收集和分享相關最佳做法及設計模式,以便使用這個 NoSQL 資料庫建置可擴充且一致的系統。

工作匯總的基本概念,是使用單一執行緒來處理一批更新。因為實體群組上只有一個執行緒且僅開啟一筆交易,所以不會因並行更新而導致交易失敗。VoltDbRedis 等其他儲存產品也應用了類似的概念。

不過,工作匯總有一個缺點:這個模式只使用一個執行緒來匯總所有更新,所以將更新傳送至 Datastore 的速度會受到限制。因此,接下來的重點就是要判定工作匯總是否能滿足 Applibot 每秒 300 項更新的總處理量要求。

使用提取佇列進行工作匯總

Kaz 按照 Datastore 小組的建議,將工作匯總模式和 Code Jam 排名程式庫相互結合,編寫出概念驗證 (PoC) 程式碼,其中含有下列元件:

  • 前端:接收來自使用者的 SetScore 要求,並將這些要求加入提取佇列,成為佇列中的工作。
  • 提取佇列:接收並保留來自前端的 SetScore 更新要求。
  • 後端:使用單一執行緒執行無限迴圈,以便從佇列中提取更新要求;接著,使用 Code Jam 排名程式庫執行這些要求。

PoC 會建立提取佇列,這是 App Engine 中的一種工作佇列,可讓開發人員實作一或多個工作站,以執行加入佇列中的工作。後端執行個體具有一個位於無限迴圈中的執行緒,用於持續從佇列中盡可能提取最多工作 (上限為 1,000 項)。這個執行緒會將所有更新要求傳送至 Code Jam 排名程式庫,程式庫則會在單一交易中批次執行要求。交易開啟的時間可能會持續一秒,甚至更長,但是因為只有一個執行緒在驅動程式庫和 Datastore,所以不會發生爭用情形和並行修改問題。

系統會將後端執行個體定義為模組,這項 App Engine 功能讓開發人員能夠定義具有多項特性的應用程式執行個體。在這個 PoC 中,後端執行個體的定義為手動調整資源調度的執行個體,系統在任何情況下都只會執行一個這類執行個體。

Kaz 使用 JMeter 對 PoC 進行了負載測試,確認 PoC 每秒能夠處理 200 個 SetScore 要求,每筆交易中的批次包含 500 至 600 項更新。工作匯總奏效了!

利用佇列資料分割獲得穩定效能

但是 Kaz 很快就發現另一個問題。他注意到持續執行測試幾分鐘後,提取佇列的總處理量會不時出現波動 (圖 6)。具體來說,他持續以每秒 200 項工作的量將要求加入佇列,幾分鐘後佇列就會突然停止將工作傳送至後端,且每項工作的延遲時間也會大幅拉長。

圖 6:提取佇列的效能波動。

Kaz 詢問工作佇列小組為什麼會發生這種情形,對方表示,目前依靠 BigTable 做為永久層的提取佇列實作方法已知會發生這種情況。當 BigTable 子表成長過大,就會拆分為多個子表;系統在拆分子表的期間無法傳送工作,所以佇列接收到大量工作時就會發生效能波動。工作佇列小組正在設法改進這些效能特性。

解決方案架構師 Michael Tang 建議使用「佇列資料分割」解決這個問題,也就是不要只使用一個佇列,改而將負載分散至多個佇列。只要將每個佇列分別儲存至不同的 BigTable 子表伺服器,就能夠降低拆分子表所帶來的影響,同時維持高工作處理速率。當一個佇列在處理拆分作業,另一個佇列可以繼續處理工作,而且由於資料分割作業已經降低了每個佇列上的負載,所以系統拆分子表的頻率也會降低。

這個經過改良的後端執行個體迴圈會執行下列演算法:

  1. 從 10 個佇列租用 SetScore 工作。
  2. 使用這些工作呼叫 SetScores 方法。
  3. 從佇列中刪除租用的工作。

在步驟 1 中,每個佇列最多提供 1,000 項工作,而每項工作都保存了一位玩家的名稱和分數。將所有玩家-分數組合匯總至字典後,步驟 2 會將更新批次傳送給 Code Jam 排名程式庫的 SetScores 方法,以便在 Datastore 開啟用於儲存這些更新的交易。如果執行方法時沒有發生錯誤,步驟 3 就會從佇列中刪除租用的工作。

如果發生錯誤或者迴圈/後端執行個體意外關閉,更新工作就會留在工作佇列中,於執行個體重新啟動後再行處理。在工作系統中,您可能有另一個用於監視的後端處於待命模式,可在第一個執行個體失敗時接手,繼續執行工作。

建議解決方案:可持續以每秒 300 項更新的效率執行2

圖 7 顯示使用佇列資料分割後最終 PoC 實作的負載測試結果。這個方法有效降低佇列的效能波動,而且可讓系統在數小時內皆維持每秒 300 項更新的處理效率。在一般負載的情況下,系統於收到要求後的幾秒內就能將更新套用至 Datastore。

圖 7:解決方案的效能圖表。

這個解決方案滿足了 Applibot 先前提出的每項要求:

  • 可適當擴充以處理數萬名玩家的要求。
  • 由於所有更新都是在 Datastore 交易中執行,所以可以確保持續性及一致性。
  • 速度夠快,足以每秒處理 300 項更新。

Kaz 將負載測試結果、PoC 程式碼和解決方案一併交給 Tomoaki 和其他 Applibot 工程師。Tomoaki 預計要將這項解決方案整合至他們的生產系統,希望能夠將更新排名資訊的延遲時間從一小時縮短為幾秒鐘,大幅改進使用者體驗。

使用工作匯總的排名樹狀演算法摘要

上述建議解決方案具備幾項優點和一項缺點:

優點:

  • 快速:FindRank 呼叫只需幾百毫秒,甚至更短。
  • 快速:SetScore 只負責分派工作;後端會在數秒內處理工作。
  • 在 Datastore 中具備高度一致性及持續性。
  • 排名結果準確。
  • 可根據任何玩家數量進行擴充。

缺點:

  • 總處理量有所限制,就目前的實作方法而言,約為 300 項更新/秒。

這項解決方案使用工作匯總模式,也就是依靠單一執行緒來匯總所有更新。如要以目前的 App Engine 執行個體 CPU 效能和 Datastore 效能達到高於每秒 300 項更新的總處理量,就必須要有額外的處理作業及複雜性。

更多使用資料分割樹狀演算法的可擴充解決方案

如果您需要更高的更新率,就必須對排名樹狀圖進行資料分割。請根據上述系統建立多項實作,也就是建立一組佇列,每個佇列都負責驅動一個後端模組,用於更新其排名樹狀圖。

一般來說,您不需要協調這些樹狀圖。在最簡單的案例中,系統會將每項 SetScore 更新隨機分派至佇列。只要建立三個這類樹狀圖 (需具備自己的 Datastore 實體群組和後端伺服器),更新總處理量預計就能夠變為三倍。不過相對來說,由於 FindRank 必須先查詢每個排名樹狀圖,取得特定分數的排名,然後再加總每個樹狀圖的排名以得出實際排名,所以花費的時間會較長。將實體保存在 Memcache 中可以大幅縮減 FindRank 的查詢時間。

這種做法類似於常見的資料分割計數器所使用的方法:每個計數器會各自進行累計,系統只會在用戶端有需求時才計算總和。

舉例來說,如果在使用三個樹狀圖的情況下,FindRank(865) 找到了 124、183 及 156 這三個數字 (分別代表各個樹狀圖中超過 865 分的得分數),那麼高於 865 分的總計得分數就是 124 + 183 + 156 = 463。

並非每種分散式演算法都適用這種方法,但是因為排名基本上屬於交換式計數問題,所以大多數排名問題應該都能使用這個方法解決。

更多採用推測約略值方法的可擴充解決方案

如果比起準確度,您的應用程式更需要具備擴充性,並且能夠容許一定程度的不精確或約略值,您可以選擇使用下列推測方法:

這些推測約略值的方法都是由同一個概念衍生出來的:如何透過降低一定程度的排名準確率來壓縮排名資訊的儲存空間?

值區與全域查詢是 Datastore 小組及 TAM Alex Amies 提出的替代解決方案。Alex 根據 Datastore 小組的構想實作 PoC,並執行了廣泛的效能分析;他證明「值區與全域查詢」不僅是可擴充的排名解決方案,排名準確率的降低程度也最少,適合總處理量需求比 Code Jam 排名程式庫更高的應用程式。詳細說明及測試結果請參閱附錄

失真計數方法節約式串流是所謂的線上演算法串流演算法,可讓您用極小的記憶體內儲存空間,從玩家-分數組合資料流中進行計算,推測估計出排名最高的玩家/項目是哪些。這些演算法適合需要極低延遲和極高頻寬 (例如每秒幾千項更新) 的應用程式,但準確率和排名結果的覆蓋範圍方面會有較多限制。舉例來說,如果您需要一個即時資訊主頁,其中顯示最常輸入社交網路訊息串的前 100 個關鍵字,這些演算法就能派上用場。

結論

在需要一致快速的可擴充演算法的前提下,排名是一項很難解決的常見問題。在這篇文章中,我們說明了 Google TAM 如何和客戶及 Google 工程小組密切合作以解決這個問題,並提供可將排名更新延遲從一小時縮減至數秒鐘的解決方案。在這個過程中發現的設計模式:工作匯總及佇列資料分割,也可以應用至其他需要每秒進行數百項更新並具備同步一致性的 Datastore 系統設計,以解決常見問題。

附註

  1. Code Jam 排名程式庫會使用「分支因子」參數指定每個實體所保存的分數數量;程式庫會將此參數預設為 100。在本範例中,0 至 9999 之間的分數會儲存於 100 個實體內,做為根節點的子節點。如果您需要處理更大範圍的分數,可以將分支因子變更為更高的值,以便最佳化實體存取的數量。
  2. 本篇文章提及的所有效能數據都是僅供參考的樣本值,我們不保證 App Engine、Datastore 或其他服務一定能達到這些效能標準。

附錄:值區與全球查詢解決方案

如同在如何計算排名一節中提及的,為每項排名要求查詢資料庫是成本高昂的做法。這項替代方法會定期取得所有分數的數量、計算指定分數的排名,並將這些資料點提供給系統,以計算特定玩家的排名。分數的總範圍會區分為多個「值區」,每個值區都擁有特定分數的子範圍和該範圍中具備分數的玩家人數,透過這些資料就能找到任何分數的排名約略值。這些值區類似於排名樹狀圖中的頂層節點,但是演算法不會向下尋找範圍更小的節點,而是改為在值區中進行內插。

使用者從前端擷取排名的作業會與後端在值區中進行的排名計算作業分離,以便縮短搜尋排名的時間。收到特定玩家排名的查詢要求時,系統會根據該玩家的分數找到適當的值區,值區中包含排名上限和該值區內的玩家人數。系統會於值區中使用線性內插法估計玩家在值區內的排名。我們進行測試時,都能在不到 400 毫秒的時間內完成完整的 HTTP 往返,取得玩家的排名。FindRank 方法的成本和母體內的玩家人數無關。

計算特定分數的排名

圖 8:值區中的分數分佈。

系統會記錄值區中的數量和最高排名,針對介於值區分數上限及下限之間的分數,則會使用線性內插法來估計排名。舉例來說,如果某位玩家的分數是 60,系統會找出 [50, 74] 值區,然後根據計數 (指該值區中的玩家/分數數量,在此範例中為 42) 和最高排名 (5),以下列公式計算該玩家的排名。

    rank = 5  + (74 - 60)*42/(74 - 50) =  30

計算各個值區的數量及範圍

系統會在背景使用 Cron 工作或工作佇列,藉由疊代所有值區的方式計算及儲存每個值區的數量。我們將這個方法稱為「全域查詢」,因為系統會透過檢查所有玩家的分數,計算估計排名所需的參數。以下 Python 程式碼範例示範如何根據每個值區中 [low_score, high_score] 範圍內的分數執行上述操作。

next_upper_rank = 1
for b in buckets:
  count = GetCountInRange(b.low_score, b.high_score)
  b.count = count
  b.upper_rank = next_upper_rank
  b.put()
  next_upper_rank += count

GetCountInRange() 方法會計算分數位於值區涵蓋範圍內的每位玩家。由於 Datastore 會維護玩家分數的分類索引,因此可以快速計算出此數量。

需要尋找特定玩家的排名時,可以使用下列程式碼。

b = GetBucketByScore(score)
rank = RankInBucket(b, score)
return rank + b.upper_rank - 1

GetBucketByScore(score) 方法會擷取包含指定分數的值區,RankInBucket() 方法則會估計值區內的排名。玩家的排名等於值區最高排名加上包含該玩家分數的特定值區中的排名。結果必須再減去 1,因為頂層值區的最高排名為 1,而特定值區中最高分玩家的排名也是 1。

這些值區會儲存在 Datastore 和 Memcache。需要計算排名時,系統會從 Memcache 讀取值區;如果 Memcache 中沒有該項資料,則會從 Datastore 讀取。我們自己實作這個演算法時,是以採用 Memcache 的 Python NDB 用戶端程式庫來快取儲存在 Datastore 的資料。

因為使用值區 (或其他方法) 會以壓縮資料方式表示資料,因此產生的排名並不精確,從值區中取得的排名是透過線性內插法得到的約略值。您可以使用其他更準確的內插方法 (例如迴歸公式) 在值區中獲得更精確的約略值。

成本

尋找排名和更新玩家分數的成本皆為 O(1);換句話說,成本與玩家人數無關。

全域查詢工作的成本為 O(玩家人數) * 快取更新的頻率。

在後端工作中計算值區資料的成本也和值區數量有關,因為系統會對每個值區執行計數查詢。為了使用僅限索引鍵查詢,「計數」查詢經過最佳化;儘管如此,還是必須擷取完整的索引鍵清單。

優點

使用這個方法可以十分快速地更新玩家的分數及尋找特定分數的排名。儘管系統是根據背景工作取得結果,但如果某玩家的分數發生變化,排名還是會立即顯示正確的變化趨勢,這是因為系統在值區中使用的是內插法。

由於值區的最高排名計算作業是在背景中透過排程工作執行,所以值區資料不必時時保持同步,也能更新玩家的分數,更新玩家分數的總處理量也不會因此而受到限制。

缺點

這種做法必須將計算所有玩家的分數、計算全域排名及更新值區所需的時間納入考量。我們針對有一千萬名玩家的母體進行測試後,發現 App Engine 測試系統需要花費 8 分鐘又 34 秒;雖然不像計算每位玩家的排名一樣需要花上數小時那麼久,但是只能取得每個值區中的分數約略值。相對來說,樹狀演算法每隔幾秒就會以遞增方式計算「值區範圍」(樹狀圖的頂端節點),但實作複雜性較高,總處理量也會受限。

在所有情況下,FindRank 所需的時間都取決於從 Memcache 快速擷取資料 (值區或樹狀圖節點) 的速度。一旦資料從 Memcache 遭到撤銷,系統就必須自 Datastore 重新擷取資料並重新快取,以供後續的 FindRank 要求使用。

準確率

影響值區方法準確率的因素包含值區數量、玩家排名,以及分數的分佈情況。我們針對不同值區數量的估計排名準確率進行了研究,圖 9 顯示的是研究結果。

圖 9:不同值區數量的準確率變化。

這項測試的母體包含 10,000 名玩家,其分數在 [0-9999] 的範圍內平均分佈。測試中只有 5 個值區,相對誤差皆為約 1%。

針對排名較高的玩家,準確率會下降,主要是因為僅尋找高分時,大數法則不適用。在多數情況下,我們建議使用較為精確的演算法來維護前一千或兩千名得分較高玩家的排名,這樣一來,因為要追蹤的玩家人數較少,更新的匯總率也相對較低,問題就能明顯改善。

上述測試使用平均分佈的隨機數字,累計分佈函式呈現線性,有助於在值區中使用線性內插法;不過值區內的內插法其實在任何分數的密集分佈中都適用。圖 10 顯示分數近似於常態分佈的估計排名和實際排名。

圖 10:常態分佈的估計排名

本實驗使用含 100 名玩家的母體進行小型資料集的準確率測試,從 0 至 100 之間隨機選出 4 個數字,取其平均而產生分數,結果分數近似於常態分佈。系統針對 10 個值區使用全域查詢和線性內插法計算出估計排名,最後發現即使是針對非常小型的資料集和非平均分佈,計算出的結果也十分理想。

本頁內容對您是否有任何幫助?請提供意見:

傳送您對下列選項的寶貴意見...

這個網頁
Cloud Datastore 說明文件