[[231802]]

最近，想必大家的朋友圈都被“王菊”占領了，打開朋友圈到處可以見到“pick王菊”、“陶淵明”、“菊外人”等字眼，可謂是火的一塌糊涂。

作為一個“菊外人”的我“跟風”的去了解了一下到底是怎么回事兒。原來是最近很火的一個選秀節目，大家都在呼吁給一個叫“王菊”的人投票。然后就有各種媒體發文分析“到底王菊是誰？”、“王菊為什么火了？”、“pick王菊給這個社會帶來了什么？”等等文章。

但是，作為一個程序員，我們看這個世界的角度永遠是那么的獨特：

我們是那個瀏覽網頁的時候經常會按ctrl + s的人。

我們是那個按下電梯的之后就會忍不住想電梯調度算法的人。

我們是那個每次支付寶付款的時候都會考慮二維碼的生成邏輯的人。

不管是作為“菊外人”還是“陶淵明”，對于這個“pick王菊”事件，我們的角度是：如何實現一個高并發的投票系統？

[[231803]]

我們需要一個怎樣的投票系統？筆者分別瀏覽了目前創造101的各個投票通道，基本的要求有以下幾個：

1、只有登錄用戶能投票 

2、每個用戶投票數有限 

3、不同用戶可投票數不同，如Vip會比普通用戶的票數多 

4、投票是限時的，只有在有效時段內才能投票

除了以上幾個功能性要求外，作為一個開發人員，還需要考慮以下幾個非功能性需求：

1、計數要準確 

2、可以處理高并發投票 

3、可以處理大量的投票數據 

4、要有很好的可用性 

5、要把每個人的投票記錄下來

登錄驗證

投票網站都是需要登錄驗證的，用戶想要進行投票，需要先登錄。目前很多大型網站的登錄都采用單點登錄（SSO，Single Sign On）技術，SSO是在多個應用系統中，用戶只需要登錄一次就可以訪問所有相互信任的應用系統。它是目前比較流行的企業業務整合的解決方案之一。

[[231804]]

實現SSO的技術主要有以下幾種：

(1）基于cookies實現。 最簡單的單點登錄實現方式，是使用cookie作為媒介，存放用戶憑證。但是存在幾個問題；1、cookies并不安全，2、cookies本身不跨域。3、瀏覽器對cookies個數和大小有限制。但是，如果想要解決的話，以上三個問題還是可以找到方案的。只不過會讓整個方案變得復雜而已。

(2)  Broker-based（基于經紀人），例如Kerberos等；這種技術的特點就是，有一個集中的認證和用戶帳號管理的服務器。經紀人給被用于進一步請求的電子的身份存取。中央數據庫的使用減少了管理的代價，并為認證提供一個公共和獨立的"第三方"。例如Kerberos,Sesame,IBM KryptoKnight（憑證庫思想)等。Kerberos是由麻省理工大學發明的安全認證服務，當前版本V5，已經被UNIX和Windows作為默認的安全認證服務集成進操作系統。

(3)  Agent-based（基于代理人）在這種解決方案中，有一個自動地為不同的應用程序認證用戶身份的代理程序。這個代理程序需要設計有不同的功能。比如，它可以使用口令表或加密密鑰來自動地將認證的負擔從用戶移開。代理人被放在服務器上面，在服務器的認證系統和客戶端認證方法之間充當一個"翻譯"。例如SSH等。

(4)  Token-based，例如SecurID,WebID，現在被廣泛使用的口令認證，比如FTP,郵件服務器的登錄認證，這是一種簡單易用的方式，實現一個口令在多種應用當中使用。

(5)  基于安全斷言標記語言（SAML）實現，SAML(Security Assertion Markup Language，安全斷言標記語言）的出現大大簡化了SSO，并被OASIS批準為SSO的執行標準。開源組織OpenSAML 實現了 SAML 規范。可參考http://www.opensaml.org。

目前，很多大型網站都采用一個開源的SSO解決方案——CAS，CAS由耶魯大學開發的單點登錄系統（SSO,single sign-on），應用廣泛，具有獨立于平臺的，易于理解，支持代理功能。

權限控制

在投票網站驗證完用戶的登錄信息之后，緊接著會判斷用戶的權限，然后根據不同的權限來給用戶分配不同的可投票次數。

關于權限的設計，一直是很多網站都要關心的問題。幾乎所有的網站都會有一定的權限要求。

目前，關于權限設計大部分均采用RBAC理論（Role-Based Access Control），即基于角色的權限訪問控制。

RBAC認為權限授權實際上是Who、What、How的問題。在RBAC模型中，Who、What、How構成了訪問權限三元組,也就是“Who對What進行How的操作”。

一個簡單的權限系統應該包含以下幾個基本元素：

用戶、角色、權限、資源、操作。

【用戶】可以屬于多個【角色】。【角色】可以認為是【權限】的合集。【權限】描述的是對【資源】的可【操作】能力。

比如在“pick王菊”這件事上，雖然大家都是“陶淵明”（王菊的粉絲自稱陶淵明，因為陶淵明愛菊花），但是有些用戶的角色是VIP用戶，有些用戶的角色是普通用戶。VIP角色的用戶在投票權限上就比普通用戶更高。

限時開啟

幾乎所有的投票活動都是有一個起止時間的，只有在有效時間段內用戶才可以參與投票。也就是說，當活動未開始的時候，用戶來到投票頁面，投票按鈕應該是置灰無法點擊的，有些網站還會給出倒計時的提示。

[[231805]]

這其中就涉及到很多問題了。如何在時間到達時將按鈕點亮呢？用戶通過非法手段在有效時間外點擊按鈕如何處理？到時間后按鈕又如何置灰？

一般情況下，用戶訪問的投票頁面被設計為靜態頁面，被緩存在 CDN 與反向代理服務器中，甚至在用戶的瀏覽器上。所以在投票活動未開始時，用戶的刷新頁面請求是不會到達應用服務器。同樣，在后端的投票接口中，在接受到用戶的投票請求時，也要做時間有效性的校驗。

我們在秒殺商品的靜態頁面中加入一個 JavaScript 文件引用，它包含投票是否已開始的標志。秒殺開始時，系統會生成一個新的 JavaScript 文件，它會被瀏覽器加載（刷新頁面或定時腳本），這樣就能點亮頁面中的購買按鈕。這個 JavaScript 文件使用隨機版本號，確保它不被瀏覽器、CDN 和反向代理服務器緩存。

同理，到達活動截止時間的按鈕置灰也通過js引用的方式可以解決。

準確計數

對于一個投票系統來說，最重要的就是計數了。要保證在高并發的情況下用戶的投票既不能多也不能少這是一個很大的挑戰。

在“pick王菊”的投票中，計數場景有多處需要。比如對于王菊的票數需要準確的記錄下來。還有，會員的已投票次數也要準確的記錄下來。這里我們就拿被投票者的票數來舉例。

[[231806]]

 

基于MySql計數

我們能想到的最簡單的方法就是在MySql數據庫表中創建一條記錄，記錄當前被投票者的票數即可。如：

CREATE TABLE IF NOT EXISTS `table_user_polls`( 
   `id` INT UNSIGNED AUTO_INCREMENT, 
   `user_id` bigint NOT NULL, 
   `polls` bigint NOT NULL 
   PRIMARY KEY ( `runoob_id` ) 
ENGINE=InnoDB DEFAULT CHARSET=utf8; 

當然，這只是一張記錄總票數的表。當有用戶投票的時候，我們通過修改表中的polls的值來進行：

update table_user_polls set polls = polls +1 where user_id = "1000"; 

當采用以上的update語句時，基本可以滿足簡單的票數的遞增。但是，一旦有高并發場景的話，就無法滿足了。因為多人同時執行這個語句的時候，就會有的人的更新結果丟失。

這時候，就需要引入鎖機制來處理。比如我們增加樂觀鎖，改進后的update語句如下：

update table_user_polls set polls = polls +1 where user_id = "1000" and polls = 1000000; 

在更新table_user_polls表的polls字段的時候，我們先把表中當前的polls值取出，然后作為樂觀鎖來控制更新，如果發生并發，只會有一個請求可以更新成功。其他請求就會更新失敗。

但是，緊接著又有兩個問題來了。

數據量太大 ?

如果數據量太大怎么辦？比如這場“全民Pick王菊”的行動，參與的用戶可能有很多很多，而我們要對每個用戶的投票數據都持久化下來。這就涉及到一旦數據量過大，就會導致數據庫的讀寫性能急劇下降。

傳統的做法是進行分庫分表，把投票表按照一定的維度進行拆分。比如這種投票的場景，我們可以按照投票的用戶的userId拆分，對userId取模，根據結果存儲到不同的表中。如把所有投票數據拆分到8個庫128張表中，路由規則就是userId%128。

其實，這種單純的分庫分表還有一個另外的問題，雖然投票場景中可能涉及不到。1、熱點數據問題。如多個熱點用戶的數據都分到了同一個庫甚至同一張表中，就會又給數據庫帶來巨大壓力。2、數據的二次分表問題。一旦分表數量不夠了，就要再次分表。比如把128張表擴展到256張表，這就麻煩了，需要對原來的1287張表中的數據重新進行拆分，數據遷移到新的256張表中。

訪問量太大 ?

通過分庫分表之后，我們暫時解決了數據量大的問題，那么如果遇到訪問量大的問題怎么辦。無論是我們的應用、服務器還是數據庫等，能承受的QPS(TPS)都是有限的。如果峰值的qps超過了限制，就有可能導致整個系統癱瘓。

那么如何提高一個服務或者接口的QPS呢，其實一個最簡單的方法就是降低響應時間（RT）。當然RT和QPS的關系還會受最佳線程數等影響，但是降低RT也是一個比較有效的辦法。如果一個請求，在執行過程中，什么都不需要需要等待，每個操作都可以快速執行（如單純的在內存中取數、計算等），那么RT就會低很多。

在程序中，導致請求阻塞的愿意可能有很多，數據庫操作可能是其中比較重要的一部分。雖然我們通過分庫的方式增加了數據庫的連接數，但是直接操作數據庫還是有很大的性能損耗的。

這時候，就要考慮在持久化存儲前面增加緩存了。在訪問數據庫之前先訪問緩存，如果緩存中沒有的話再訪問數據庫。這樣可以減少請求的響應時間，從而提高QPS，進而承載更大的訪問量。

這樣做有很大的好處，但是也不是完美的方案。比如這種投票系統，計數更新是非常頻繁的，所以要經常失效緩存在重新緩存，緩存和數據庫之間的數據一致性問題就體現出來了。

以上，是通過MySql來進行計數的方案，總結一下：

優點：便于理解、學習成本低、開發成本也低。 缺點：對大數據量和高并發量支持不友好。

基于Redis計數

Redis 是目前 NoSQL 領域的當紅炸子雞，它象一把瑞士軍刀，小巧、鋒利、實用，特別適合解決一些使用傳統關系數據庫難以解決的問題。

如果我們使用Redis來實現計數器的話，就相對來說簡單一些了。因為Redid提供了一個INCR命令，其使用方法如下：

redis> SET wangju_polls 20 
OK 
 
redis> INCR wangju_polls 
(integer) 21 
 
redis> GET wangju_polls    
"21" 

INCR key語法，可以將 key 中儲存的數字值增一。如果 key 不存在，那么 key 的值會先被初始化為 0 ，然后再執行 INCR 操作。最重要的是INCR是一個原子性的自增操作。非常適合用來實現計數器。

引入了Redis之后，遇到高并發和大數據量的問題解決起來就簡單了——堆機器。

當然，這個方案雖然在很大程度上解決了大數據量和高并發的問題。但是，如果真的是業務量特別巨大，總不能無限制的增加通過增加機器來解決問題吧，機器就是成本啊。

關于這種問題，微博就遇到了，因為微博的點贊功能和我們的投票功能其實是類似的。明星的一條微博的點贊數可能有幾十萬，甚至百萬以上。有人（微博計數器的設計）算過一筆帳：

假設 key 為8字節，value為 4字節，通過incr存儲的話:

一個 value 通過 createStringObjectFromLongLong 創建一個robj，由于value在LONGMIN 和LONGMAX 之間，所以可以將value用 ptr指針來存儲，需要占用 sizeof(robj) = 16 字節;

一個key(即微博id) 最長64位數字(Eg: 5612814510546515491)，但通過 sdsdup 以字符串的形式存儲，至少需要 8(struct sdshdr)+19+1 = 28字節;

為了存到Redis 的dict里面，需要一個dictEntry對象，繼續 3*8 = 24字節;

放到db->dict->ht[0]->table中存儲dictEntry的指針，再要 8個字節; 存儲一個64位key，32位value的計數，Redis也至少需要耗費: 16 + 28 + 24 + 8 = 76 字節。

1000億個key全內存的話，就至少需要 100G * 76 = 7.6TB 的內存了(折算76G內存機器也需要100臺！)。

我們的有效數據其實是1000億個32位 = 400GB，但是卻需要了7.6T來存儲，內存的有效利用率約為：400GB/7600GB = 5.3%

總的來說，Redis做為優秀的內存數據結構，接口方便，使用簡單，對于小型數據量的中高訪問量的計數類服務來說，是一個很不錯的選擇，但是對于微博計數器這種極端的應用場景，成本還是無法接受！

所以，微博的點贊功能，其實是在Redis的基礎上進行了二次開發。如在數據機構優化、轉發和評論數 Value的優化、key的優化、數據的持久化、一致性保證等方面做了很多事情。這里不詳細介紹了，感興趣的同學可以參考微博計數器的設計

其他

避免刷票

在創造101的投票規則中，明確規定了：請公平參與點贊，如采用違法或違反賽事規則的點贊行為，將會被收回相關點贊數并追究責任。

那么，如果我們是這個投票系統的開發，如何有效的避免刷票行為呢？

[[231808]]

首先，我們要通過設計一個很好的計數器，能夠有效的避免高并發請求帶來的計數錯誤。因為投票時可能有很多人使用腳本等構造多條請求，試圖來突破限制來多投票。

其次，還可以通過一些其他限制手段來防止惡意刷票，如限制同一IP的投票次數、限制同一帳號的投票頻率等。

避免數據溢出

據說，在前段時間的MSI比賽前期，MSI的助威活動中，人氣選手uzi的票數達到了網站開發人員設置的int的最大值。

以上只是個傳說，我并沒有去辯證他的真偽，但是這至少給我們一個提醒，在設計投票系統的時候，要充分的考慮到粉絲們的熱情和實力！

持久化數據的備份

無論最終選用那種方式進行計數，數據的持久化問題都至關重要，一定要做好數據存儲的容災工作。避免由于系統問題導致數據丟失。

【本文是51CTO專欄作者Hollis的原創文章，作者微信公眾號Hollis(ID：hollischuang)】

戳這里，看該作者更多好文