背景:
每一條微博的轉發和評論背後都是一串串說不完的故事，但是今天主要講的是 計數服務，計數服務詳盡地記錄著每條微博 被評論的次數 和 被轉發的次數，當然也還有更多的喜怒哀樂都記錄於此。
數據量:
微博總數量: 千億級 而且每秒都在飛速增長中。每條微博都有一個64位的唯一id。
訪問量: 每秒百萬級 還在穩步增長中。 根據微博的id來訪問。
主要接口:
增加評論數 (默認為0)
增加轉發數 (默認為0)
獲取評論數
獲取轉發數
獲取評論數 + 獲取轉發數 (這個接口訪問量最大)
評論數和轉發數，你都可以認為是 32位的整形數值。不會是負數，默認是0。
要求:
由於用戶對於數字非常的敏感(想想你好不容易拉到一位粉絲，但是粉絲數沒漲的痛苦吧。)，所以我們要求數據非常準確，延遲極低(1s以內)，服務穩定性極高(千萬別因為某大媽掃個地撥了插座就把數字弄沒了...)
做為架構師，當然也需要全方位地考慮架構成本問題，然後去做各種的折衷。 這裡主要考慮的成本是: 機器成本，開發成本，維護成本。
有興趣的架構師和準架構師們可以一起思考，怎樣才能用最少的機器，最短時間內開發出最易維護的計數器系統。。。當然，得滿足我們數據量，性能和高可用的要求。
對這一塊非常的感興趣，而且有靠譜的想法和建議，煩請私信簡歷給 @cydu 或者 @微博平臺架構，我們這裡還有大量類似的問題期待著你來解決！ 當然，也可以直接評論一起討論。
PS: 後面我會給出我們的理解和解決的思路，期待大家一起來優化。
Update: 更新了數據持久化和一致性保證相關的內容，多謝 @lihan_harry @鄭環Zheng @51劉達 等同學的提醒。
Update2: 更新了 對於weibo_id key的優化，使用前綴壓縮，可以節省近一半的空間。 感謝 @吳廷彬 @drdrxp 的建議！
Update3: 更新了 對於value 使用二維數組，多列進行壓縮編碼的優化思路， 再次感謝 @吳廷彬 的建議，
Update4: 更新Redis方案下內存使用的估算, 感謝 @劉浩bupt 的提醒。
上週挖了一個坑
([微架構設計]微博計數器的設計(上) http://qing.weibo.com/1639780001/61bd0ea133002460.html ) ，
雖然挖這個坑的動機是很不純的(很明顯的招聘軟文, 非常欣慰的是確實收到了不少靠譜的簡歷, 希望簡歷來得更猛烈一些! ), 但是和大家討論的過程中，還是收穫很大的, 也認識了不少新朋友。
對於一個簡單的計數服務來說，確實非常的簡單，我們可以有很多的解決方案:
方案一: 直接上mysql
這個不用多說了吧，足夠的簡單暴力。 但是在產品發展的初期快速迭代的階段，他能夠解決很多的問題，也不失為一個不錯的解決方案。
數據量過大怎麼辦？
對於一億甚至幾億以下的數據規模來說，拆表能夠解決很多問題，對於微博計數器來說至少有兩種經典的拆法:
一. 按id取模，把數據拆分到N個表當中去。 這個方案的悲劇是: 擴展性不好，不好加表，數據一旦滿了，加起來很鬱悶。雖然可以預先多分一些表，但是對於weibo這種快速增長的業務來說，嚴重影響了業務的快速增長需求。
二. 按id的時間來分段拆表，滿了就建新表。 這個方案的悲劇是: 冷熱不均，最近的weibo肯定是被訪問最頻繁的，而老的庫又基本沒有訪問。 可以通過冷熱庫混合部署的方案來緩解，但是部署和維護的成本非常大。
數據量從億上升到千億後，這個問題的本質就發生了變化，維護上千張表，熱點還各不相同需要經常切換調整，這是一件非常悲劇的事情。。。
訪問量太大怎麼辦？
應對訪問量，也有很多的經典的方法:
一. 上Cache(Eg: Memcache), 訪問時先訪問Cache，不命中時再訪問mysql. 這樣做有兩個鬱悶點: 空數據也得Cache(有一半以上的微博是沒有轉發也沒有評論的，但是依然有大量的訪問會查詢他); Cache頻繁失效(由於計數更新非常快，所以經常需要失效Cache再重種，還會導致數據不一致);做為最基礎的服務，使用複雜，客戶端需要關注的東西更多
二. 更好的硬件解決。 上FusionIO + HandleSocket + 大內存 優化. 通過硬件的方式也能夠解決問題，但是這是最典型的Scale up的方案。雖然完全不用開發，但是硬件成本不低，且對於更復雜的需求，以及流量快速的增長，也很難應對。
優點:
一. 不用開發, 碼農們可以用寫代碼的時間出去泡泡妞。
二. 方案成熟, 數據複製，管理，修復方案都很成熟。
缺點:
一. 對大數據量和高併發訪問支持不好，非常的力不從心。
二. 維護成本和硬件成本都很高。
總的來說: Mysql分表 + Cache/硬件 加速的方案 對於數據規模和訪問量不是特別巨大的情況下，非常不錯的解決方案，但是量大了之後非常不合事宜.
既然 Mysql不行，那用NoSQL 呢？
方案二: Redis
做為一個簡單的內存數據結構來說，Redis提供非常簡單易用的訪問接口，而且有相當不錯的單機性能。 通過incr實現的 Counter Pattern，用來做計數器服務，更是簡單輕鬆。 通過上層的分表，增加slave等方式，堆一些機器，也能夠解決大數據量和高併發訪問的問題。
但是Redis是純內存的(vm機制不成熟而且即將被廢棄,我們線上肯定是不敢直接使用的！)，所以成本也不算低，我們簡單的來估算一下數據存儲量(下面都是按照Redis 2.4.16的實現，在64位系統，指針為8字節來估算的) :
假設 key 為8字節，value為 4字節，通過incr存儲的話:
一個 value 通過 createStringObjectFromLongLong 創建一個robj，由於value在LONG_MIN 和LONG_MAX 之間，所以可以將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.6TB來存儲，內存的有效利用率約為: 400GB/7600GB = 5.3%.
即使這樣，對於很多熱點的數據，只有一個副本，單機性能不夠，系統的穩定性也無法保證(單機Down掉咋辦？)， 還需要複製多份。 再算上為了避免內存碎片引入的jemalloc的內存開銷; 再算了dictExpand等需要的臨時內存空間; 再算上系統要用的內存開銷。。。那要的機器就更多了，保守估計需要300-400臺以上的機器。
總的來說: Redis做為優秀的內存數據結構，接口方便，使用簡單，對於小型數據量的中高訪問量的計數類服務來說，是一個很不錯的選擇，但是對於微博計數器這種極端的應用場景，成本還是無法接受！
還有一些同學提出了用 Cassandra，MongoDB 等其他NoSQL的方案，無論是從可維護性的角度，還是從機器利用率的角度，都很難以接受(有興趣的同學可以仔細分析一下)。
普通的NoSQL也不行，那怎麼辦？ 嘗試定製我們自己的Counter！
Update4:
//@劉浩bupt: @cydu 剛剛仔細閱讀了文中redis容量預估的部分，有兩點小瑕疵：1.對於value的存儲，文中估算了16個字節，其實這部分開銷是可以節省的。createStringObjectFromLongLong函數，對於小於REDIS_SHARED_INTEGERS的value值，不會額外分配空間。REDIS_SHARED_INTEGERS默認是10000，調大一些可以滿足大部分需求
//@劉浩bupt: @cydu 2.是可以評估下使用zipmap達到的內存利用率。redis不是隻有string->string的kv存儲，還是有一些可以挖掘的東西的。instagram在其工程博客中介紹過（http://t.cn/S7EUKe），改用zipmap後，其存儲1M的數據，內存佔用由70M優化到了16M。鑑於新浪微博大量的使用redis，定製redis實現服務也是個思路。
感謝 @劉浩bupt 同學幫我指出對於Redis容量預估的不準確，通過Redis自帶的 REDIS_SHARED_INTEGERS 機制確實可能大量節省value所佔的內存，但是由於這個方案需要依賴存儲shared_int的指針，不太好遷移到方案三裡面去。
Zipmap這個優化的思路是相當不錯的，對於通用的Redis的使用，我們會持續關注。
方案三: Counter
計數器是一個普通的基礎服務，但是因為數據量太大了，從而量變引發了質變。 所以我們做Counter時的一個思路就是: 犧牲部分的通用性，針對微博轉發和評論的大數據量和高併發訪問的特點來進行定點優化。
1. 大量微博(一半以上)是沒有轉發，或者沒有評論，甚至是沒有轉發也沒有評論。
針對這種情況的優化: 拋棄 存儲+Cache的思路, 因為這些為0的數據，也必須進到Cache中(無論是旁路還是穿透)，因為查詢量並不小，這對於我們Cache的利用率影響非常非常的大(有一半的數據是空的。) 而我們採用類似 存儲即Cache(存儲本身就在內存中) 時，這一類的數據是可以不存儲的，當查不到的時候，就返回0。
通過這種情況，1000億個數字，我們可以減少3/5，即最多隻需要存 400億個數字。這算是最經典的稀疏數組的優化存儲方式了。
2. 微博的評論數和轉發數 的關聯度非常的高。
他們都有相同的主Key, 有大量轉發的微博一般也有評論，有大量評論的一般轉發量也不小。 而且訪問量最大的Feed頁基本上取評論數的時候，也會取轉發數。。。
針對這種情況的優化: 我們將評論數和轉發數 可以考慮存儲在一起，這樣的話，可以節省大量key的存儲空間。 由 微博ID+評論數; 微博ID+轉發數 變為: 微博ID+評論數+轉發數的結構。
PS： 這個優化和上一個優化是有一些小衝突的，部分有轉發沒有評論的微博，需要多存一個0; 但是經過數據評估，我們發現這個優化還是相當必要的: a. key存儲的空間比評論數還要長，一個8字節，一個4字節; b. 對於應用層來說，批量請求可以減少一次訪問，能夠降請求的壓力，同時提升響應的時間;
(具體的數字不方便透露，但是這個結論大家可以隨機抽取一批公開的微博來驗證)
3. 數據結構的優化
通過方案二中Redis對內存使用的分析，我們發現是非常"奢侈"的, 大量的重複存儲著指針和預留的字段，而且造成大量的碎片內存的使用， 當然Redis主要是出於通用性的考慮。 針對這種情況:
@果爸果爸 同學設計了一個更輕量更簡單的數據結構，能更好的利用內存，核心思路:
a. 通過下面的item結構來存儲 轉發和評論數:
struct item{
int64_t weibo_id;
int repost_num;
int comment_num;
};
存儲數字，而不是字符串，沒有多餘的指針存儲， 這樣的話，兩個數字只佔 16個字節;
b. 程序啟動的時候，開闢一大片的內存 (table_size * sizeof(item)) 並清0他。
c. 插入時:
h1 = hash1(weibo_id);
h2 = hash2(weibo_id);
如果 h1%table_size 是空的，則把item存儲到這個位置上;
否則 s=1 並找 ( h1 + h2*s ) % table_size 的位置，如果還不空的話，s++繼續找空位。。。
d. 查詢時:
和插入的過程類似，找到一個數據後，比較weibo_id 和 item.weibo_id 是否一致，一致
則表示查到，否則查到空的則表示為值為0;
e. 刪除時:
查找到所在位置，設置特殊的標誌; 下次插入時，可以填充這個標誌位，以複用內存。。。
經過我們實測，當2億數據這種長度的數組中，容量不超過95%的時候，衝突率是可以接受的
(最悲劇的時候可能需要做幾百次的內存操作才能找到相應的空位, 性能上完全能夠接受; )
經過這個優化之後，我們的總數據量變成了:
400億 * 16B = 640GB; 基本是方案二的 十分之一還少！
4. 轉發和評論數 Value的優化
繼續觀察，我們發現大量的微博，雖然有轉發和評論，但是值一般都比較小，幾百或者幾千的，
超過幾萬的weibo很少(數據調研顯示在十萬分之一以下)。
所以我們把 item 升級為:
struct item{
int64_t weibo_id;
unsigned short repost_num;
unsigned short comment_num;
};
對於轉發數和評論數大於 65535 的weibo，我們在這裡記錄一個特殊的標誌位FFFF，然後去
另外的dict中去查找(那邊不做這個優化)。事實上，還可以把 unsigned short優化為 int:12 之類的極端情況，但是更復雜，且收益一般，所以我們還是選用unsigned short。
經過這個優化後，我們的總數據量變成了:
400億 * 12B = 480GB, 這個數據量已經差不多是單機能夠存儲的容量了。
每秒的查詢量由100W變成了50W, 更新量每秒只有數萬沒有變化，和查詢量比可以先忽略。
4.1 補充 Value的優化
@吳廷彬: 另外，64bit value可以用utf-8的類似思想再壓縮。最後因為cpu/mem不是瓶頸，可以將weibo_id和後面的value分開放在兩個數組裡面，對應的index一樣即可。然後會發現value數組裡面的64bit很多位全是0，或許可以考慮以K為單位的數據做簡單數據壓縮放入內存裡面，這個壓縮比應該是驚人的。
@吳廷彬: 回覆@cydu:value可以用二維數組怎麼樣。 如果1K為單位壓縮則每一行表示1K個數據。然後對數據進行壓縮寫入。 一般可能每行只用100個字節？
@cydu: 這樣確實可以，變長編碼會有意義，反正cpu應該不是瓶頸，有更新的時候整塊重新編碼，取也是全取出再解壓。還一個好處是我加列更方便了，現在我加列的代價其實是很高的。
最早的時候，我也想過用變長壓縮，但是思路一直侷限在一個value裡面做壓縮，由於只有兩列，我們又是用定長的存儲，一方面變長有開銷(標誌位標誌用了多少位來表示)，另一方面定長開給的32位省出來也沒有合適的用處(可以和key的優化結合起來，用更少的字段)。 @吳廷彬 一說二維數據，立馬變長壓縮的好處就顯現出來了。
我可以把key單獨存儲，把value，按 1024個value甚至更多個value 壓縮到一個mini block中存儲，在定長的情況下，這個mini block的size是 1024*32 = 4K. 但是事實上，這4K中包含了大量的 0, 我不用自己整複雜的變長編碼，直接拿這4K的數據做LZF壓縮，只存儲壓縮後的數據就行了, 取的時候先解壓縮。 具體的壓縮效率得看數據才能定，但是根據一般文本的壓縮到 50% 應該是非常輕鬆的，也就是說，至少可以節省 400億 * 2 = 80GB的內存。
這個方案最大的一個好處還不在於這80GB的內存的節省，而是：
1. 我前面優化提到的 大於 65535 的轉發和評論，我可以考慮簡單做了，反正變長嘛，不影響，整個方案是簡化了的。(當然需要具體的數據測試一下，驗證哪個更好)
2. [相當重要！！] 對於微博的計數，其實我們是有加列的需求的，比如其他的類似評論數的數字，我原來的方案中，加列的代價是相當高的，需要重開一個大數組，還要事先設好hint(對於新業務來說，hint值的不好選取，但是他對性能和內存的使用率影響又是致命的!)，而這個方案，無論你加多少列都其實沒啥關係，用內存的長度只和你真實的數據量相關！
經過這個優化後，我保守的估計，我們能夠在之前的基礎上，再節省 80GB的內存！
5. key的優化
@吳廷彬 很好的文章。weibo_id是8byte的，壓縮能夠壓到接近4byte.假如一堆數據是AB,AC,AD,AE,AF, XE,XY,XZ.把他在內存裡面A開頭放在一坨內存，X開頭放在另外一坨，裡面只用存B,C,D,E,F和Y,Z. 基本上能減少4個字節。能省掉40G*4=160G？
@drdrxp: 存儲分成2^24個區,weibo_id%(2^24)指到區的號上,記錄中再用40bit 存儲weibo_id/(2^24),記錄中另外12bit 存轉發,12bit存評論, 1條記錄總共8字節,480G可以優化到320G. 如果能實際考察下評論轉發數的分佈應該可以更加優化1些.
感謝 @吳廷彬 @drdrxp 提的這個建議，這一塊的優化空間確實非常的大。後面其實有提到，我們會根據時間段或者根據weibo id把大的table 劃分成多個小的table(主要是為了能夠序列化到磁盤騰空間給更熱的數據)。 所以在一個小table裡面的數據都是weibo_id比較接近的，Eg: 5612814510546515491， 5612814510546515987， 我們可以把這64位key中相同的高32位歸併起來。做為小table的屬性(prefix)，就不必每一條都存儲了。 8字節的key，至少能夠節省 4字節。
struct item{
int weibo_id_low;
unsigned short repost_num;
unsigned short comment_num;
};
經過這個優化後，我們的總數據量變成了:
400億 * 8B = 320GB， ^_^
也感謝 @drdrxp 的建議，之前也考慮過12bit來存評論數和轉發數，確實能夠優化不少，但是由於多出來的bit不知道幹嘛，就沒搞了，呵呵。你的建議和 @吳廷彬 提的建議都主要是在key上做文章，很贊！
6. 批量查詢
對於Feed頁來說，一次取到N條微博，然後查詢他的計數，這裡可以很好的批量化查詢來優化響應時間。
以一次批量訪問10個微博的計數來說，對於Counter碰到的壓力就是 5W requests/second， 100W keys/second;
對於全內存的簡單服務來說，單機已經基本能夠扛 5W+ 的請求了。
7. 冷熱數據
繼續看這400億個數字，我們發現，訪問熱點非常的集中，大量去年，甚至前年的weibo無人訪問。
本能的可能想到經典Cache的做法，熱的數據在內存，冷的數據放磁盤。 但是如果引入lru的話，意味
著我們的struct item得膨脹，會佔用更多內存。而且對於0數據也得Cache。。。
對於這種情況，我們設計了一個非常簡單的內存和磁盤淘汰策略，根據weiboid的區間（其實是時間）
來進行淘汰，按區間劃分，超過半年的dump到磁盤上去，半年內的繼續留存在內存，當少量用戶挖墳的時候
(訪問很老的微博並轉發/評論)，我們去查詢磁盤，並將查詢的結果放到 Cold Cache當中.
為了方便把舊的數據dump到磁盤，我們把那個大的table_size拆成多個小的table，每個table都是不同的
時間區間內的weibo計數，dump的時候，以小的table為單位。
為了提高磁盤的查詢效率，dump之前先排序，並在內存中建好索引，索引建在Block上，而非key上。
一個Block可以是4KB甚至更長，根據索引最多一次隨機IO把這個Block取出來，內存中再查詢完成;
經過這個優化，我們可以把將近200G的數據放到磁盤當中, 剩餘120GB的數據仍然留在內存當中。 而且即使隨著weibo數越來越多，我們也依然只要保存120GB的數據在內存中就行了，磁盤的數據量會增加，熱點的數據也會變化，但是總的熱點數據的量是變化很少的！
背景:
每一條微博的轉發和評論背後都是一串串說不完的故事，但是今天主要講的是 計數服務，計數服務詳盡地記錄著每條微博 被評論的次數 和 被轉發的次數，當然也還有更多的喜怒哀樂都記錄於此。
數據量:
微博總數量: 千億級 而且每秒都在飛速增長中。每條微博都有一個64位的唯一id。
訪問量: 每秒百萬級 還在穩步增長中。 根據微博的id來訪問。
主要接口:
增加評論數 (默認為0)
增加轉發數 (默認為0)
獲取評論數
獲取轉發數
獲取評論數 + 獲取轉發數 (這個接口訪問量最大)
評論數和轉發數，你都可以認為是 32位的整形數值。不會是負數，默認是0。
要求:
由於用戶對於數字非常的敏感(想想你好不容易拉到一位粉絲，但是粉絲數沒漲的痛苦吧。)，所以我們要求數據非常準確，延遲極低(1s以內)，服務穩定性極高(千萬別因為某大媽掃個地撥了插座就把數字弄沒了...)
做為架構師，當然也需要全方位地考慮架構成本問題，然後去做各種的折衷。 這裡主要考慮的成本是: 機器成本，開發成本，維護成本。
有興趣的架構師和準架構師們可以一起思考，怎樣才能用最少的機器，最短時間內開發出最易維護的計數器系統。。。當然，得滿足我們數據量，性能和高可用的要求。
對這一塊非常的感興趣，而且有靠譜的想法和建議，煩請私信簡歷給 @cydu 或者 @微博平臺架構，我們這裡還有大量類似的問題期待著你來解決！ 當然，也可以直接評論一起討論。
PS: 後面我會給出我們的理解和解決的思路，期待大家一起來優化。
Update: 更新了數據持久化和一致性保證相關的內容，多謝 @lihan_harry @鄭環Zheng @51劉達 等同學的提醒。
Update2: 更新了 對於weibo_id key的優化，使用前綴壓縮，可以節省近一半的空間。 感謝 @吳廷彬 @drdrxp 的建議！
Update3: 更新了 對於value 使用二維數組，多列進行壓縮編碼的優化思路， 再次感謝 @吳廷彬 的建議，
Update4: 更新Redis方案下內存使用的估算, 感謝 @劉浩bupt 的提醒。
上週挖了一個坑
([微架構設計]微博計數器的設計(上) http://qing.weibo.com/1639780001/61bd0ea133002460.html ) ，
雖然挖這個坑的動機是很不純的(很明顯的招聘軟文, 非常欣慰的是確實收到了不少靠譜的簡歷, 希望簡歷來得更猛烈一些! ), 但是和大家討論的過程中，還是收穫很大的, 也認識了不少新朋友。
對於一個簡單的計數服務來說，確實非常的簡單，我們可以有很多的解決方案:
方案一: 直接上mysql
這個不用多說了吧，足夠的簡單暴力。 但是在產品發展的初期快速迭代的階段，他能夠解決很多的問題，也不失為一個不錯的解決方案。
數據量過大怎麼辦？
對於一億甚至幾億以下的數據規模來說，拆表能夠解決很多問題，對於微博計數器來說至少有兩種經典的拆法:
一. 按id取模，把數據拆分到N個表當中去。 這個方案的悲劇是: 擴展性不好，不好加表，數據一旦滿了，加起來很鬱悶。雖然可以預先多分一些表，但是對於weibo這種快速增長的業務來說，嚴重影響了業務的快速增長需求。
二. 按id的時間來分段拆表，滿了就建新表。 這個方案的悲劇是: 冷熱不均，最近的weibo肯定是被訪問最頻繁的，而老的庫又基本沒有訪問。 可以通過冷熱庫混合部署的方案來緩解，但是部署和維護的成本非常大。
數據量從億上升到千億後，這個問題的本質就發生了變化，維護上千張表，熱點還各不相同需要經常切換調整，這是一件非常悲劇的事情。。。
訪問量太大怎麼辦？
應對訪問量，也有很多的經典的方法:
一. 上Cache(Eg: Memcache), 訪問時先訪問Cache，不命中時再訪問mysql. 這樣做有兩個鬱悶點: 空數據也得Cache(有一半以上的微博是沒有轉發也沒有評論的，但是依然有大量的訪問會查詢他); Cache頻繁失效(由於計數更新非常快，所以經常需要失效Cache再重種，還會導致數據不一致);做為最基礎的服務，使用複雜，客戶端需要關注的東西更多
二. 更好的硬件解決。 上FusionIO + HandleSocket + 大內存 優化. 通過硬件的方式也能夠解決問題，但是這是最典型的Scale up的方案。雖然完全不用開發，但是硬件成本不低，且對於更復雜的需求，以及流量快速的增長，也很難應對。
優點:
一. 不用開發, 碼農們可以用寫代碼的時間出去泡泡妞。
二. 方案成熟, 數據複製，管理，修復方案都很成熟。
缺點:
一. 對大數據量和高併發訪問支持不好，非常的力不從心。
二. 維護成本和硬件成本都很高。
總的來說: Mysql分表 + Cache/硬件 加速的方案 對於數據規模和訪問量不是特別巨大的情況下，非常不錯的解決方案，但是量大了之後非常不合事宜.
既然 Mysql不行，那用NoSQL 呢？
方案二: Redis
做為一個簡單的內存數據結構來說，Redis提供非常簡單易用的訪問接口，而且有相當不錯的單機性能。 通過incr實現的 Counter Pattern，用來做計數器服務，更是簡單輕鬆。 通過上層的分表，增加slave等方式，堆一些機器，也能夠解決大數據量和高併發訪問的問題。
但是Redis是純內存的(vm機制不成熟而且即將被廢棄,我們線上肯定是不敢直接使用的！)，所以成本也不算低，我們簡單的來估算一下數據存儲量(下面都是按照Redis 2.4.16的實現，在64位系統，指針為8字節來估算的) :
假設 key 為8字節，value為 4字節，通過incr存儲的話:
一個 value 通過 createStringObjectFromLongLong 創建一個robj，由於value在LONG_MIN 和LONG_MAX 之間，所以可以將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.6TB來存儲，內存的有效利用率約為: 400GB/7600GB = 5.3%.
即使這樣，對於很多熱點的數據，只有一個副本，單機性能不夠，系統的穩定性也無法保證(單機Down掉咋辦？)， 還需要複製多份。 再算上為了避免內存碎片引入的jemalloc的內存開銷; 再算了dictExpand等需要的臨時內存空間; 再算上系統要用的內存開銷。。。那要的機器就更多了，保守估計需要300-400臺以上的機器。
總的來說: Redis做為優秀的內存數據結構，接口方便，使用簡單，對於小型數據量的中高訪問量的計數類服務來說，是一個很不錯的選擇，但是對於微博計數器這種極端的應用場景，成本還是無法接受！
還有一些同學提出了用 Cassandra，MongoDB 等其他NoSQL的方案，無論是從可維護性的角度，還是從機器利用率的角度，都很難以接受(有興趣的同學可以仔細分析一下)。
普通的NoSQL也不行，那怎麼辦？ 嘗試定製我們自己的Counter！
Update4:
//@劉浩bupt: @cydu 剛剛仔細閱讀了文中redis容量預估的部分，有兩點小瑕疵：1.對於value的存儲，文中估算了16個字節，其實這部分開銷是可以節省的。createStringObjectFromLongLong函數，對於小於REDIS_SHARED_INTEGERS的value值，不會額外分配空間。REDIS_SHARED_INTEGERS默認是10000，調大一些可以滿足大部分需求
//@劉浩bupt: @cydu 2.是可以評估下使用zipmap達到的內存利用率。redis不是隻有string->string的kv存儲，還是有一些可以挖掘的東西的。instagram在其工程博客中介紹過（http://t.cn/S7EUKe），改用zipmap後，其存儲1M的數據，內存佔用由70M優化到了16M。鑑於新浪微博大量的使用redis，定製redis實現服務也是個思路。
感謝 @劉浩bupt 同學幫我指出對於Redis容量預估的不準確，通過Redis自帶的 REDIS_SHARED_INTEGERS 機制確實可能大量節省value所佔的內存，但是由於這個方案需要依賴存儲shared_int的指針，不太好遷移到方案三裡面去。
Zipmap這個優化的思路是相當不錯的，對於通用的Redis的使用，我們會持續關注。
方案三: Counter
計數器是一個普通的基礎服務，但是因為數據量太大了，從而量變引發了質變。 所以我們做Counter時的一個思路就是: 犧牲部分的通用性，針對微博轉發和評論的大數據量和高併發訪問的特點來進行定點優化。
1. 大量微博(一半以上)是沒有轉發，或者沒有評論，甚至是沒有轉發也沒有評論。
針對這種情況的優化: 拋棄 存儲+Cache的思路, 因為這些為0的數據，也必須進到Cache中(無論是旁路還是穿透)，因為查詢量並不小，這對於我們Cache的利用率影響非常非常的大(有一半的數據是空的。) 而我們採用類似 存儲即Cache(存儲本身就在內存中) 時，這一類的數據是可以不存儲的，當查不到的時候，就返回0。
通過這種情況，1000億個數字，我們可以減少3/5，即最多隻需要存 400億個數字。這算是最經典的稀疏數組的優化存儲方式了。
2. 微博的評論數和轉發數 的關聯度非常的高。
他們都有相同的主Key, 有大量轉發的微博一般也有評論，有大量評論的一般轉發量也不小。 而且訪問量最大的Feed頁基本上取評論數的時候，也會取轉發數。。。
針對這種情況的優化: 我們將評論數和轉發數 可以考慮存儲在一起，這樣的話，可以節省大量key的存儲空間。 由 微博ID+評論數; 微博ID+轉發數 變為: 微博ID+評論數+轉發數的結構。
PS： 這個優化和上一個優化是有一些小衝突的，部分有轉發沒有評論的微博，需要多存一個0; 但是經過數據評估，我們發現這個優化還是相當必要的: a. key存儲的空間比評論數還要長，一個8字節，一個4字節; b. 對於應用層來說，批量請求可以減少一次訪問，能夠降請求的壓力，同時提升響應的時間;
(具體的數字不方便透露，但是這個結論大家可以隨機抽取一批公開的微博來驗證)
3. 數據結構的優化
通過方案二中Redis對內存使用的分析，我們發現是非常"奢侈"的, 大量的重複存儲著指針和預留的字段，而且造成大量的碎片內存的使用， 當然Redis主要是出於通用性的考慮。 針對這種情況:
@果爸果爸 同學設計了一個更輕量更簡單的數據結構，能更好的利用內存，核心思路:
a. 通過下面的item結構來存儲 轉發和評論數:
struct item{
int64_t weibo_id;
int repost_num;
int comment_num;
};
存儲數字，而不是字符串，沒有多餘的指針存儲， 這樣的話，兩個數字只佔 16個字節;
b. 程序啟動的時候，開闢一大片的內存 (table_size * sizeof(item)) 並清0他。
c. 插入時:
h1 = hash1(weibo_id);
h2 = hash2(weibo_id);
如果 h1%table_size 是空的，則把item存儲到這個位置上;
否則 s=1 並找 ( h1 + h2*s ) % table_size 的位置，如果還不空的話，s++繼續找空位。。。
d. 查詢時:
和插入的過程類似，找到一個數據後，比較weibo_id 和 item.weibo_id 是否一致，一致
則表示查到，否則查到空的則表示為值為0;
e. 刪除時:
查找到所在位置，設置特殊的標誌; 下次插入時，可以填充這個標誌位，以複用內存。。。
經過我們實測，當2億數據這種長度的數組中，容量不超過95%的時候，衝突率是可以接受的
(最悲劇的時候可能需要做幾百次的內存操作才能找到相應的空位, 性能上完全能夠接受; )
經過這個優化之後，我們的總數據量變成了:
400億 * 16B = 640GB; 基本是方案二的 十分之一還少！
4. 轉發和評論數 Value的優化
繼續觀察，我們發現大量的微博，雖然有轉發和評論，但是值一般都比較小，幾百或者幾千的，
超過幾萬的weibo很少(數據調研顯示在十萬分之一以下)。
所以我們把 item 升級為:
struct item{
int64_t weibo_id;
unsigned short repost_num;
unsigned short comment_num;
};
對於轉發數和評論數大於 65535 的weibo，我們在這裡記錄一個特殊的標誌位FFFF，然後去
另外的dict中去查找(那邊不做這個優化)。事實上，還可以把 unsigned short優化為 int:12 之類的極端情況，但是更復雜，且收益一般，所以我們還是選用unsigned short。
經過這個優化後，我們的總數據量變成了:
400億 * 12B = 480GB, 這個數據量已經差不多是單機能夠存儲的容量了。
每秒的查詢量由100W變成了50W, 更新量每秒只有數萬沒有變化，和查詢量比可以先忽略。
4.1 補充 Value的優化
@吳廷彬: 另外，64bit value可以用utf-8的類似思想再壓縮。最後因為cpu/mem不是瓶頸，可以將weibo_id和後面的value分開放在兩個數組裡面，對應的index一樣即可。然後會發現value數組裡面的64bit很多位全是0，或許可以考慮以K為單位的數據做簡單數據壓縮放入內存裡面，這個壓縮比應該是驚人的。
@吳廷彬: 回覆@cydu:value可以用二維數組怎麼樣。 如果1K為單位壓縮則每一行表示1K個數據。然後對數據進行壓縮寫入。 一般可能每行只用100個字節？
@cydu: 這樣確實可以，變長編碼會有意義，反正cpu應該不是瓶頸，有更新的時候整塊重新編碼，取也是全取出再解壓。還一個好處是我加列更方便了，現在我加列的代價其實是很高的。
最早的時候，我也想過用變長壓縮，但是思路一直侷限在一個value裡面做壓縮，由於只有兩列，我們又是用定長的存儲，一方面變長有開銷(標誌位標誌用了多少位來表示)，另一方面定長開給的32位省出來也沒有合適的用處(可以和key的優化結合起來，用更少的字段)。 @吳廷彬 一說二維數據，立馬變長壓縮的好處就顯現出來了。
我可以把key單獨存儲，把value，按 1024個value甚至更多個value 壓縮到一個mini block中存儲，在定長的情況下，這個mini block的size是 1024*32 = 4K. 但是事實上，這4K中包含了大量的 0, 我不用自己整複雜的變長編碼，直接拿這4K的數據做LZF壓縮，只存儲壓縮後的數據就行了, 取的時候先解壓縮。 具體的壓縮效率得看數據才能定，但是根據一般文本的壓縮到 50% 應該是非常輕鬆的，也就是說，至少可以節省 400億 * 2 = 80GB的內存。
這個方案最大的一個好處還不在於這80GB的內存的節省，而是：
1. 我前面優化提到的 大於 65535 的轉發和評論，我可以考慮簡單做了，反正變長嘛，不影響，整個方案是簡化了的。(當然需要具體的數據測試一下，驗證哪個更好)
2. [相當重要！！] 對於微博的計數，其實我們是有加列的需求的，比如其他的類似評論數的數字，我原來的方案中，加列的代價是相當高的，需要重開一個大數組，還要事先設好hint(對於新業務來說，hint值的不好選取，但是他對性能和內存的使用率影響又是致命的!)，而這個方案，無論你加多少列都其實沒啥關係，用內存的長度只和你真實的數據量相關！
經過這個優化後，我保守的估計，我們能夠在之前的基礎上，再節省 80GB的內存！
5. key的優化
@吳廷彬 很好的文章。weibo_id是8byte的，壓縮能夠壓到接近4byte.假如一堆數據是AB,AC,AD,AE,AF, XE,XY,XZ.把他在內存裡面A開頭放在一坨內存，X開頭放在另外一坨，裡面只用存B,C,D,E,F和Y,Z. 基本上能減少4個字節。能省掉40G*4=160G？
@drdrxp: 存儲分成2^24個區,weibo_id%(2^24)指到區的號上,記錄中再用40bit 存儲weibo_id/(2^24),記錄中另外12bit 存轉發,12bit存評論, 1條記錄總共8字節,480G可以優化到320G. 如果能實際考察下評論轉發數的分佈應該可以更加優化1些.
感謝 @吳廷彬 @drdrxp 提的這個建議，這一塊的優化空間確實非常的大。後面其實有提到，我們會根據時間段或者根據weibo id把大的table 劃分成多個小的table(主要是為了能夠序列化到磁盤騰空間給更熱的數據)。 所以在一個小table裡面的數據都是weibo_id比較接近的，Eg: 5612814510546515491， 5612814510546515987， 我們可以把這64位key中相同的高32位歸併起來。做為小table的屬性(prefix)，就不必每一條都存儲了。 8字節的key，至少能夠節省 4字節。
struct item{
int weibo_id_low;
unsigned short repost_num;
unsigned short comment_num;
};
經過這個優化後，我們的總數據量變成了:
400億 * 8B = 320GB， ^_^
也感謝 @drdrxp 的建議，之前也考慮過12bit來存評論數和轉發數，確實能夠優化不少，但是由於多出來的bit不知道幹嘛，就沒搞了，呵呵。你的建議和 @吳廷彬 提的建議都主要是在key上做文章，很贊！
6. 批量查詢
對於Feed頁來說，一次取到N條微博，然後查詢他的計數，這裡可以很好的批量化查詢來優化響應時間。
以一次批量訪問10個微博的計數來說，對於Counter碰到的壓力就是 5W requests/second， 100W keys/second;
對於全內存的簡單服務來說，單機已經基本能夠扛 5W+ 的請求了。
7. 冷熱數據
繼續看這400億個數字，我們發現，訪問熱點非常的集中，大量去年，甚至前年的weibo無人訪問。
本能的可能想到經典Cache的做法，熱的數據在內存，冷的數據放磁盤。 但是如果引入lru的話，意味
著我們的struct item得膨脹，會佔用更多內存。而且對於0數據也得Cache。。。
對於這種情況，我們設計了一個非常簡單的內存和磁盤淘汰策略，根據weiboid的區間（其實是時間）
來進行淘汰，按區間劃分，超過半年的dump到磁盤上去，半年內的繼續留存在內存，當少量用戶挖墳的時候
(訪問很老的微博並轉發/評論)，我們去查詢磁盤，並將查詢的結果放到 Cold Cache當中.
為了方便把舊的數據dump到磁盤，我們把那個大的table_size拆成多個小的table，每個table都是不同的
時間區間內的weibo計數，dump的時候，以小的table為單位。
為了提高磁盤的查詢效率，dump之前先排序，並在內存中建好索引，索引建在Block上，而非key上。
一個Block可以是4KB甚至更長，根據索引最多一次隨機IO把這個Block取出來，內存中再查詢完成;
經過這個優化，我們可以把將近200G的數據放到磁盤當中, 剩餘120GB的數據仍然留在內存當中。 而且即使隨著weibo數越來越多，我們也依然只要保存120GB的數據在內存中就行了，磁盤的數據量會增加，熱點的數據也會變化，但是總的熱點數據的量是變化很少的！
8. 數據的持久化
對於Sorted 部分的數據，一旦刷到磁盤後，就只會讀，不會修改，除非在做和Cold Block做merge的時候，才會重寫 (目前這一塊merge的邏輯沒有實現，因為必要性不高)。
對於內存中的數據，我們會定期把 Block 完整的dump到 磁盤中，形成 unsorted block。 然後每一次內存操作都會有相應的Append log， 一旦機器故障了，可以從 磁盤上的Block上加載，再追加Append log中的操作日誌來恢復數據。
當然，從整個架構上，一旦Counter崩潰等嚴重錯誤，導致數據錯誤，我們還可以通過 具體數據的存儲服務上把數據重新計算出來，恢復到Counter當中。 當然這種計數的代價是非常高的，你想想姚晨那麼多粉絲，counter一遍很恐怖的， 我們也另外做了一些二級索引之類的簡單優化。
9. 一致性保證
@lihan_harry上邊文章提到計數對正確性要求高，由於計數不滿足冪等性。那麼這個問題是怎麼解決的
@cydu回覆 @lihan_harry ：是這樣的，前面有一個消息隊列，通過類似於transid的方案來做除重，避免多加和少加; 當然這裡主要是指用主從的結構，incr累加，即使是最終一致也不至於太離譜; 另外，我們還有做實際的存儲數據到Counter的定期數據校驗，以後面的數據存儲為準
@鄭環Zheng貌似還會有寫請求單點問題，老數據的刪除遞減走硬盤，多機房冗餘，機器假死宕機數據會不會丟失，刪微博的時候還要清空相關計算不呢
@cydu回覆 @鄭環Zheng ：是的，為了incr 的準確性，還是使用Master-Slave的結構，所以Master的單點問題依然存在，需要靠主從切換，以及事後的數據修復來提高數據的準確性。
10. 分佈式化
出於穩定性的數據冗餘的考慮，而且考慮到weibo現在數據增長的速度，在可預見的未來，數字會
變成1500億，2000億甚至更高。
我們在上層還是做了一些簡單的拆分的，按照weiboid取模，劃分到4套上(主要是考慮到後續數據的增長)，
每套Master存儲後面又掛2個Slave, 一方面是均攤讀的壓力，另一方面主要是容災(當主掛掉的時候，
還有副在，不影響讀，也能夠切換)
so, 我還是沒能單機扛住這1000億個數字，和每秒100W次的查詢。。。只好厚著臉皮問老大申請了十幾臺機器。
優點: 單機性能真的很好，內存利用率很高，對後續擴展的支持也相當不錯。
缺點: 我們碼農泡妞的時間少了，得抽空寫寫代碼。。。但是，如果不用寫碼的話，那碼農還能幹嘛呢？
總之: 對於這種極端的情況，所以我們採用了同樣極端的方式來優化，犧牲了部分的通用性。
方案四: Counter Service
方案三出來後, 微博計數的問題是解決了，但是我們還有用戶關注粉絲計數呢，好友計數，會員計數...
數字社會嘛，自然是很多數字，每一個數字背後都是一串串的故事。
背景:
每一條微博的轉發和評論背後都是一串串說不完的故事，但是今天主要講的是 計數服務，計數服務詳盡地記錄著每條微博 被評論的次數 和 被轉發的次數，當然也還有更多的喜怒哀樂都記錄於此。
數據量:
微博總數量: 千億級 而且每秒都在飛速增長中。每條微博都有一個64位的唯一id。
訪問量: 每秒百萬級 還在穩步增長中。 根據微博的id來訪問。
主要接口:
增加評論數 (默認為0)
增加轉發數 (默認為0)
獲取評論數
獲取轉發數
獲取評論數 + 獲取轉發數 (這個接口訪問量最大)
評論數和轉發數，你都可以認為是 32位的整形數值。不會是負數，默認是0。
要求:
由於用戶對於數字非常的敏感(想想你好不容易拉到一位粉絲，但是粉絲數沒漲的痛苦吧。)，所以我們要求數據非常準確，延遲極低(1s以內)，服務穩定性極高(千萬別因為某大媽掃個地撥了插座就把數字弄沒了...)
做為架構師，當然也需要全方位地考慮架構成本問題，然後去做各種的折衷。 這裡主要考慮的成本是: 機器成本，開發成本，維護成本。
有興趣的架構師和準架構師們可以一起思考，怎樣才能用最少的機器，最短時間內開發出最易維護的計數器系統。。。當然，得滿足我們數據量，性能和高可用的要求。
對這一塊非常的感興趣，而且有靠譜的想法和建議，煩請私信簡歷給 @cydu 或者 @微博平臺架構，我們這裡還有大量類似的問題期待著你來解決！ 當然，也可以直接評論一起討論。
PS: 後面我會給出我們的理解和解決的思路，期待大家一起來優化。
Update: 更新了數據持久化和一致性保證相關的內容，多謝 @lihan_harry @鄭環Zheng @51劉達 等同學的提醒。
Update2: 更新了 對於weibo_id key的優化，使用前綴壓縮，可以節省近一半的空間。 感謝 @吳廷彬 @drdrxp 的建議！
Update3: 更新了 對於value 使用二維數組，多列進行壓縮編碼的優化思路， 再次感謝 @吳廷彬 的建議，
Update4: 更新Redis方案下內存使用的估算, 感謝 @劉浩bupt 的提醒。
上週挖了一個坑
([微架構設計]微博計數器的設計(上) http://qing.weibo.com/1639780001/61bd0ea133002460.html ) ，
雖然挖這個坑的動機是很不純的(很明顯的招聘軟文, 非常欣慰的是確實收到了不少靠譜的簡歷, 希望簡歷來得更猛烈一些! ), 但是和大家討論的過程中，還是收穫很大的, 也認識了不少新朋友。
對於一個簡單的計數服務來說，確實非常的簡單，我們可以有很多的解決方案:
方案一: 直接上mysql
這個不用多說了吧，足夠的簡單暴力。 但是在產品發展的初期快速迭代的階段，他能夠解決很多的問題，也不失為一個不錯的解決方案。
數據量過大怎麼辦？
對於一億甚至幾億以下的數據規模來說，拆表能夠解決很多問題，對於微博計數器來說至少有兩種經典的拆法:
一. 按id取模，把數據拆分到N個表當中去。 這個方案的悲劇是: 擴展性不好，不好加表，數據一旦滿了，加起來很鬱悶。雖然可以預先多分一些表，但是對於weibo這種快速增長的業務來說，嚴重影響了業務的快速增長需求。
二. 按id的時間來分段拆表，滿了就建新表。 這個方案的悲劇是: 冷熱不均，最近的weibo肯定是被訪問最頻繁的，而老的庫又基本沒有訪問。 可以通過冷熱庫混合部署的方案來緩解，但是部署和維護的成本非常大。
數據量從億上升到千億後，這個問題的本質就發生了變化，維護上千張表，熱點還各不相同需要經常切換調整，這是一件非常悲劇的事情。。。
訪問量太大怎麼辦？
應對訪問量，也有很多的經典的方法:
一. 上Cache(Eg: Memcache), 訪問時先訪問Cache，不命中時再訪問mysql. 這樣做有兩個鬱悶點: 空數據也得Cache(有一半以上的微博是沒有轉發也沒有評論的，但是依然有大量的訪問會查詢他); Cache頻繁失效(由於計數更新非常快，所以經常需要失效Cache再重種，還會導致數據不一致);做為最基礎的服務，使用複雜，客戶端需要關注的東西更多
二. 更好的硬件解決。 上FusionIO + HandleSocket + 大內存 優化. 通過硬件的方式也能夠解決問題，但是這是最典型的Scale up的方案。雖然完全不用開發，但是硬件成本不低，且對於更復雜的需求，以及流量快速的增長，也很難應對。
優點:
一. 不用開發, 碼農們可以用寫代碼的時間出去泡泡妞。
二. 方案成熟, 數據複製，管理，修復方案都很成熟。
缺點:
一. 對大數據量和高併發訪問支持不好，非常的力不從心。
二. 維護成本和硬件成本都很高。
總的來說: Mysql分表 + Cache/硬件 加速的方案 對於數據規模和訪問量不是特別巨大的情況下，非常不錯的解決方案，但是量大了之後非常不合事宜.
既然 Mysql不行，那用NoSQL 呢？
方案二: Redis
做為一個簡單的內存數據結構來說，Redis提供非常簡單易用的訪問接口，而且有相當不錯的單機性能。 通過incr實現的 Counter Pattern，用來做計數器服務，更是簡單輕鬆。 通過上層的分表，增加slave等方式，堆一些機器，也能夠解決大數據量和高併發訪問的問題。
但是Redis是純內存的(vm機制不成熟而且即將被廢棄,我們線上肯定是不敢直接使用的！)，所以成本也不算低，我們簡單的來估算一下數據存儲量(下面都是按照Redis 2.4.16的實現，在64位系統，指針為8字節來估算的) :
假設 key 為8字節，value為 4字節，通過incr存儲的話:
一個 value 通過 createStringObjectFromLongLong 創建一個robj，由於value在LONG_MIN 和LONG_MAX 之間，所以可以將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.6TB來存儲，內存的有效利用率約為: 400GB/7600GB = 5.3%.
即使這樣，對於很多熱點的數據，只有一個副本，單機性能不夠，系統的穩定性也無法保證(單機Down掉咋辦？)， 還需要複製多份。 再算上為了避免內存碎片引入的jemalloc的內存開銷; 再算了dictExpand等需要的臨時內存空間; 再算上系統要用的內存開銷。。。那要的機器就更多了，保守估計需要300-400臺以上的機器。
總的來說: Redis做為優秀的內存數據結構，接口方便，使用簡單，對於小型數據量的中高訪問量的計數類服務來說，是一個很不錯的選擇，但是對於微博計數器這種極端的應用場景，成本還是無法接受！
還有一些同學提出了用 Cassandra，MongoDB 等其他NoSQL的方案，無論是從可維護性的角度，還是從機器利用率的角度，都很難以接受(有興趣的同學可以仔細分析一下)。
普通的NoSQL也不行，那怎麼辦？ 嘗試定製我們自己的Counter！
Update4:
//@劉浩bupt: @cydu 剛剛仔細閱讀了文中redis容量預估的部分，有兩點小瑕疵：1.對於value的存儲，文中估算了16個字節，其實這部分開銷是可以節省的。createStringObjectFromLongLong函數，對於小於REDIS_SHARED_INTEGERS的value值，不會額外分配空間。REDIS_SHARED_INTEGERS默認是10000，調大一些可以滿足大部分需求
//@劉浩bupt: @cydu 2.是可以評估下使用zipmap達到的內存利用率。redis不是隻有string->string的kv存儲，還是有一些可以挖掘的東西的。instagram在其工程博客中介紹過（http://t.cn/S7EUKe），改用zipmap後，其存儲1M的數據，內存佔用由70M優化到了16M。鑑於新浪微博大量的使用redis，定製redis實現服務也是個思路。
感謝 @劉浩bupt 同學幫我指出對於Redis容量預估的不準確，通過Redis自帶的 REDIS_SHARED_INTEGERS 機制確實可能大量節省value所佔的內存，但是由於這個方案需要依賴存儲shared_int的指針，不太好遷移到方案三裡面去。
Zipmap這個優化的思路是相當不錯的，對於通用的Redis的使用，我們會持續關注。
方案三: Counter
計數器是一個普通的基礎服務，但是因為數據量太大了，從而量變引發了質變。 所以我們做Counter時的一個思路就是: 犧牲部分的通用性，針對微博轉發和評論的大數據量和高併發訪問的特點來進行定點優化。
1. 大量微博(一半以上)是沒有轉發，或者沒有評論，甚至是沒有轉發也沒有評論。
針對這種情況的優化: 拋棄 存儲+Cache的思路, 因為這些為0的數據，也必須進到Cache中(無論是旁路還是穿透)，因為查詢量並不小，這對於我們Cache的利用率影響非常非常的大(有一半的數據是空的。) 而我們採用類似 存儲即Cache(存儲本身就在內存中) 時，這一類的數據是可以不存儲的，當查不到的時候，就返回0。
通過這種情況，1000億個數字，我們可以減少3/5，即最多隻需要存 400億個數字。這算是最經典的稀疏數組的優化存儲方式了。
2. 微博的評論數和轉發數 的關聯度非常的高。
他們都有相同的主Key, 有大量轉發的微博一般也有評論，有大量評論的一般轉發量也不小。 而且訪問量最大的Feed頁基本上取評論數的時候，也會取轉發數。。。
針對這種情況的優化: 我們將評論數和轉發數 可以考慮存儲在一起，這樣的話，可以節省大量key的存儲空間。 由 微博ID+評論數; 微博ID+轉發數 變為: 微博ID+評論數+轉發數的結構。
PS： 這個優化和上一個優化是有一些小衝突的，部分有轉發沒有評論的微博，需要多存一個0; 但是經過數據評估，我們發現這個優化還是相當必要的: a. key存儲的空間比評論數還要長，一個8字節，一個4字節; b. 對於應用層來說，批量請求可以減少一次訪問，能夠降請求的壓力，同時提升響應的時間;
(具體的數字不方便透露，但是這個結論大家可以隨機抽取一批公開的微博來驗證)
3. 數據結構的優化
通過方案二中Redis對內存使用的分析，我們發現是非常"奢侈"的, 大量的重複存儲著指針和預留的字段，而且造成大量的碎片內存的使用， 當然Redis主要是出於通用性的考慮。 針對這種情況:
@果爸果爸 同學設計了一個更輕量更簡單的數據結構，能更好的利用內存，核心思路:
a. 通過下面的item結構來存儲 轉發和評論數:
struct item{
int64_t weibo_id;
int repost_num;
int comment_num;
};
存儲數字，而不是字符串，沒有多餘的指針存儲， 這樣的話，兩個數字只佔 16個字節;
b. 程序啟動的時候，開闢一大片的內存 (table_size * sizeof(item)) 並清0他。
c. 插入時:
h1 = hash1(weibo_id);
h2 = hash2(weibo_id);
如果 h1%table_size 是空的，則把item存儲到這個位置上;
否則 s=1 並找 ( h1 + h2*s ) % table_size 的位置，如果還不空的話，s++繼續找空位。。。
d. 查詢時:
和插入的過程類似，找到一個數據後，比較weibo_id 和 item.weibo_id 是否一致，一致
則表示查到，否則查到空的則表示為值為0;
e. 刪除時:
查找到所在位置，設置特殊的標誌; 下次插入時，可以填充這個標誌位，以複用內存。。。
經過我們實測，當2億數據這種長度的數組中，容量不超過95%的時候，衝突率是可以接受的
(最悲劇的時候可能需要做幾百次的內存操作才能找到相應的空位, 性能上完全能夠接受; )
經過這個優化之後，我們的總數據量變成了:
400億 * 16B = 640GB; 基本是方案二的 十分之一還少！
4. 轉發和評論數 Value的優化
繼續觀察，我們發現大量的微博，雖然有轉發和評論，但是值一般都比較小，幾百或者幾千的，
超過幾萬的weibo很少(數據調研顯示在十萬分之一以下)。
所以我們把 item 升級為:
struct item{
int64_t weibo_id;
unsigned short repost_num;
unsigned short comment_num;
};
對於轉發數和評論數大於 65535 的weibo，我們在這裡記錄一個特殊的標誌位FFFF，然後去
另外的dict中去查找(那邊不做這個優化)。事實上，還可以把 unsigned short優化為 int:12 之類的極端情況，但是更復雜，且收益一般，所以我們還是選用unsigned short。
經過這個優化後，我們的總數據量變成了:
400億 * 12B = 480GB, 這個數據量已經差不多是單機能夠存儲的容量了。
每秒的查詢量由100W變成了50W, 更新量每秒只有數萬沒有變化，和查詢量比可以先忽略。
4.1 補充 Value的優化
@吳廷彬: 另外，64bit value可以用utf-8的類似思想再壓縮。最後因為cpu/mem不是瓶頸，可以將weibo_id和後面的value分開放在兩個數組裡面，對應的index一樣即可。然後會發現value數組裡面的64bit很多位全是0，或許可以考慮以K為單位的數據做簡單數據壓縮放入內存裡面，這個壓縮比應該是驚人的。
@吳廷彬: 回覆@cydu:value可以用二維數組怎麼樣。 如果1K為單位壓縮則每一行表示1K個數據。然後對數據進行壓縮寫入。 一般可能每行只用100個字節？
@cydu: 這樣確實可以，變長編碼會有意義，反正cpu應該不是瓶頸，有更新的時候整塊重新編碼，取也是全取出再解壓。還一個好處是我加列更方便了，現在我加列的代價其實是很高的。
最早的時候，我也想過用變長壓縮，但是思路一直侷限在一個value裡面做壓縮，由於只有兩列，我們又是用定長的存儲，一方面變長有開銷(標誌位標誌用了多少位來表示)，另一方面定長開給的32位省出來也沒有合適的用處(可以和key的優化結合起來，用更少的字段)。 @吳廷彬 一說二維數據，立馬變長壓縮的好處就顯現出來了。
我可以把key單獨存儲，把value，按 1024個value甚至更多個value 壓縮到一個mini block中存儲，在定長的情況下，這個mini block的size是 1024*32 = 4K. 但是事實上，這4K中包含了大量的 0, 我不用自己整複雜的變長編碼，直接拿這4K的數據做LZF壓縮，只存儲壓縮後的數據就行了, 取的時候先解壓縮。 具體的壓縮效率得看數據才能定，但是根據一般文本的壓縮到 50% 應該是非常輕鬆的，也就是說，至少可以節省 400億 * 2 = 80GB的內存。
這個方案最大的一個好處還不在於這80GB的內存的節省，而是：
1. 我前面優化提到的 大於 65535 的轉發和評論，我可以考慮簡單做了，反正變長嘛，不影響，整個方案是簡化了的。(當然需要具體的數據測試一下，驗證哪個更好)
2. [相當重要！！] 對於微博的計數，其實我們是有加列的需求的，比如其他的類似評論數的數字，我原來的方案中，加列的代價是相當高的，需要重開一個大數組，還要事先設好hint(對於新業務來說，hint值的不好選取，但是他對性能和內存的使用率影響又是致命的!)，而這個方案，無論你加多少列都其實沒啥關係，用內存的長度只和你真實的數據量相關！
經過這個優化後，我保守的估計，我們能夠在之前的基礎上，再節省 80GB的內存！
5. key的優化
@吳廷彬 很好的文章。weibo_id是8byte的，壓縮能夠壓到接近4byte.假如一堆數據是AB,AC,AD,AE,AF, XE,XY,XZ.把他在內存裡面A開頭放在一坨內存，X開頭放在另外一坨，裡面只用存B,C,D,E,F和Y,Z. 基本上能減少4個字節。能省掉40G*4=160G？
@drdrxp: 存儲分成2^24個區,weibo_id%(2^24)指到區的號上,記錄中再用40bit 存儲weibo_id/(2^24),記錄中另外12bit 存轉發,12bit存評論, 1條記錄總共8字節,480G可以優化到320G. 如果能實際考察下評論轉發數的分佈應該可以更加優化1些.
感謝 @吳廷彬 @drdrxp 提的這個建議，這一塊的優化空間確實非常的大。後面其實有提到，我們會根據時間段或者根據weibo id把大的table 劃分成多個小的table(主要是為了能夠序列化到磁盤騰空間給更熱的數據)。 所以在一個小table裡面的數據都是weibo_id比較接近的，Eg: 5612814510546515491， 5612814510546515987， 我們可以把這64位key中相同的高32位歸併起來。做為小table的屬性(prefix)，就不必每一條都存儲了。 8字節的key，至少能夠節省 4字節。
struct item{
int weibo_id_low;
unsigned short repost_num;
unsigned short comment_num;
};
經過這個優化後，我們的總數據量變成了:
400億 * 8B = 320GB， ^_^
也感謝 @drdrxp 的建議，之前也考慮過12bit來存評論數和轉發數，確實能夠優化不少，但是由於多出來的bit不知道幹嘛，就沒搞了，呵呵。你的建議和 @吳廷彬 提的建議都主要是在key上做文章，很贊！
6. 批量查詢
對於Feed頁來說，一次取到N條微博，然後查詢他的計數，這裡可以很好的批量化查詢來優化響應時間。
以一次批量訪問10個微博的計數來說，對於Counter碰到的壓力就是 5W requests/second， 100W keys/second;
對於全內存的簡單服務來說，單機已經基本能夠扛 5W+ 的請求了。
7. 冷熱數據
繼續看這400億個數字，我們發現，訪問熱點非常的集中，大量去年，甚至前年的weibo無人訪問。
本能的可能想到經典Cache的做法，熱的數據在內存，冷的數據放磁盤。 但是如果引入lru的話，意味
著我們的struct item得膨脹，會佔用更多內存。而且對於0數據也得Cache。。。
對於這種情況，我們設計了一個非常簡單的內存和磁盤淘汰策略，根據weiboid的區間（其實是時間）
來進行淘汰，按區間劃分，超過半年的dump到磁盤上去，半年內的繼續留存在內存，當少量用戶挖墳的時候
(訪問很老的微博並轉發/評論)，我們去查詢磁盤，並將查詢的結果放到 Cold Cache當中.
為了方便把舊的數據dump到磁盤，我們把那個大的table_size拆成多個小的table，每個table都是不同的
時間區間內的weibo計數，dump的時候，以小的table為單位。
為了提高磁盤的查詢效率，dump之前先排序，並在內存中建好索引，索引建在Block上，而非key上。
一個Block可以是4KB甚至更長，根據索引最多一次隨機IO把這個Block取出來，內存中再查詢完成;
經過這個優化，我們可以把將近200G的數據放到磁盤當中, 剩餘120GB的數據仍然留在內存當中。 而且即使隨著weibo數越來越多，我們也依然只要保存120GB的數據在內存中就行了，磁盤的數據量會增加，熱點的數據也會變化，但是總的熱點數據的量是變化很少的！
8. 數據的持久化
對於Sorted 部分的數據，一旦刷到磁盤後，就只會讀，不會修改，除非在做和Cold Block做merge的時候，才會重寫 (目前這一塊merge的邏輯沒有實現，因為必要性不高)。
對於內存中的數據，我們會定期把 Block 完整的dump到 磁盤中，形成 unsorted block。 然後每一次內存操作都會有相應的Append log， 一旦機器故障了，可以從 磁盤上的Block上加載，再追加Append log中的操作日誌來恢復數據。
當然，從整個架構上，一旦Counter崩潰等嚴重錯誤，導致數據錯誤，我們還可以通過 具體數據的存儲服務上把數據重新計算出來，恢復到Counter當中。 當然這種計數的代價是非常高的，你想想姚晨那麼多粉絲，counter一遍很恐怖的， 我們也另外做了一些二級索引之類的簡單優化。
9. 一致性保證
@lihan_harry上邊文章提到計數對正確性要求高，由於計數不滿足冪等性。那麼這個問題是怎麼解決的
@cydu回覆 @lihan_harry ：是這樣的，前面有一個消息隊列，通過類似於transid的方案來做除重，避免多加和少加; 當然這裡主要是指用主從的結構，incr累加，即使是最終一致也不至於太離譜; 另外，我們還有做實際的存儲數據到Counter的定期數據校驗，以後面的數據存儲為準
@鄭環Zheng貌似還會有寫請求單點問題，老數據的刪除遞減走硬盤，多機房冗餘，機器假死宕機數據會不會丟失，刪微博的時候還要清空相關計算不呢
@cydu回覆 @鄭環Zheng ：是的，為了incr 的準確性，還是使用Master-Slave的結構，所以Master的單點問題依然存在，需要靠主從切換，以及事後的數據修復來提高數據的準確性。
10. 分佈式化
出於穩定性的數據冗餘的考慮，而且考慮到weibo現在數據增長的速度，在可預見的未來，數字會
變成1500億，2000億甚至更高。
我們在上層還是做了一些簡單的拆分的，按照weiboid取模，劃分到4套上(主要是考慮到後續數據的增長)，
每套Master存儲後面又掛2個Slave, 一方面是均攤讀的壓力，另一方面主要是容災(當主掛掉的時候，
還有副在，不影響讀，也能夠切換)
so, 我還是沒能單機扛住這1000億個數字，和每秒100W次的查詢。。。只好厚著臉皮問老大申請了十幾臺機器。
優點: 單機性能真的很好，內存利用率很高，對後續擴展的支持也相當不錯。
缺點: 我們碼農泡妞的時間少了，得抽空寫寫代碼。。。但是，如果不用寫碼的話，那碼農還能幹嘛呢？
總之: 對於這種極端的情況，所以我們採用了同樣極端的方式來優化，犧牲了部分的通用性。
方案四: Counter Service
方案三出來後, 微博計數的問題是解決了，但是我們還有用戶關注粉絲計數呢，好友計數，會員計數...
數字社會嘛，自然是很多數字，每一個數字背後都是一串串的故事。
針對這種情況，我們在Counter的基礎上，再把這個模塊服務化，對外提供一整套的 Counter Service，
並支持動態的Schema修改(主要是增加)，這個服務的核心接口類似於下面這個樣子:
//增加計數, 計數的名字是: "weibo"
add counter weibo
// 向"weibo"這個計數器中增加一列，列名是 weibo_id, 最長為64位，一般也是64位，默認值為0, 而且這一列是key
add column weibo weibo_id hint=64 max=64 default=0 primarykey
// 向"weibo"這個計數器中增加一列，列名是 comment_num, 最長為32位，一般是16位，默認值為0
add column weibo comment_num hint=16 max=32 default=0 suffix=cntcm
// 向"weibo"這個計數器中增加一列，列名是 repost_num, 最長為32位，一般是16位，默認值為0
add column weibo repost_num hint=16 max=32 default=0 suffix=cntrn
// 向"weibo"這個計數器中增加一列，列名是 attitude_num, 最長為32位，一般是8位，默認值為0
add column weibo attitude_num hint=8 max=32 default=0 suffix=cntan
....
// 設置weibo計數中 weibo_id=1234 的相關計數，包括 comment_num, repost_num, attitude_num
set weibo 1234 111 222 333
// 獲取weibo計數中 weibo_id=1234 的相關計數，包括 comment_num, repost_num, attitude_num
get weibo 1234
// 獲取weibo計數中 weibo_id=1234 的相關 comment_num
get weibo 1234.cntcm
// 增加weibo計數中 weibo_id=1234 的相關 comment_num
incr weibo 1234.cntcm
....
當 add column的時候，我們會根據hint值再增加一個大的table (table_size * sizeof(hint)),
但是這裡不存儲key，只有value，用原來item那個大table的相同key。 對於超過部分依然是走
另外的存儲。
通過計數器服務化之後，最大的好處就是，後面我們再要加計數，有可能量沒有那麼大，可以很快的
創建出來。。。
缺點:
對於非數值類的key名，可能會退化到字符串的存儲，我們可以通過簡化的base64等機制來縮短空間;
對於頻繁修改老的數據，導致cold buffer膨脹的問題，可以通過定期的merge來緩解（類似於Leveldb的機制）;
方案五: 你的方案
對於工程類的問題，其實永遠不會有標準的答案，一千個架構師能給出一萬個設計方案來，而且沒有
一個是標準的答案，只有最適合你的那一個！ 這裡只簡單分享一下我的一個思考過程和不同階段最核心
關注的點，歡迎大家一起討論。
期待你的思路和方案！ 期待你們的簡歷， 請私信 @cydu 或者 @微博平臺架構。
當然，微博平臺除了計數器這一個典型的小Case外，還有更多更大的挑戰需要你的方案！