1. 一般什麼產品或者系統或網站會使用K/V資料庫型資料庫呢
KV型存儲系統是最常用的NoSQL存儲系統之一。Memcached和Redis是其最具代表的兩個產品。本文將詳細介紹Memcached和Redis的常用場景及如何構建一個高可用和自動彈性伸縮的KV存儲系統。
Cache加DB是最常見的存儲層架構。時間局部性原理指出正在被訪問的數據很可能會在近期再次被訪問。根據這一原理應用程序將最近訪問過的數據保存在Cache中，每次讀取請求首先訪問Cache，若Cache中保存有該數據則直接獲取數據返回給前端。若Cache中該數據不存在則從DB獲取數據並將該數據保存到Cache；若數據被更新或刪除則將Cache中對應數據置為失效。使用Cache能夠很好地緩解DB的讀請求壓力。KV存儲系統既可以應用在Cache層也可以應用在DB層。
Memcached使用內存作為存儲介質，因為內存數據的易失性Memcached主要應用在Cache層。Memcached常見的應用場景是存儲一些讀取頻繁但更新較少的數據，如靜態網頁、系統配置及規則數據、活躍用戶的基本數據和個性化定製數據、准實時統計信息等。並不是所有場景都適合Memcached加DB的架構，在某些場景下這一架構存在一些局限。例如這一架構不能提升寫的性能，寫數據時還是數據直接存儲到DB，同時需要將Cache中數據置為失效，所以對以寫請求為主的應用使用Cache提升性能的效果並不是很明顯。如果應用的熱點數據或者活躍用戶分布較為分散也會降低Cache的命中率。如果遇到機器宕機，內存數據會丟失，那麼機器重啟後需要一段時間重新建立熱點數據，建立熱點數據的過程中會對DB會造成較大的壓力，嚴重時會導致系統雪崩。
相比Memcached，Redis做了一些優化。首先，Redis對數據做了持久化，支持AOF和RDB兩種持久化方式，機器重啟後能通過持久化數據自動重建內存。其次，Redis支持主從復制，主機會自動將數據同步到從機，可以進行讀寫分離，主機負責寫操作，從機負責讀操作。那樣既增加了系統的讀寫性能又提升了數據的可靠性。再次，Redis除了支持string類型的value外還支持string、hash、set、sorted set、list等類型的數據結構。因此，Redis既可以應用在Cache層，也可以替換或者部分替換DB存儲持久化數據。使用Redis作為Cache時機器宕機後熱點數據不會丟失，無須像Memcached一樣重建熱點數據。相比Cache加DB的架構方式，使用Redis存儲持久化數據不僅能夠提升讀性能，還能提升寫性能，而且不存在熱點數據分布是否集中而影響命中率的問題。Redis豐富的數據結構也使其擁有更加豐富的應用場景。Redis的命令都是原子性的，可以簡單地利用INCR和DECR實現計數功能。使用list可以實現獲取最近N個數的操作。sort set支持對數據排序，可以應用在排行榜中。set集合可以應用到數據排重。Redis還支持過期時間設置，可以應用到需要設定精確過期時間的應用。只要可以使用Redis支持的數據結構表示的場景，就可以使用Redis進行存儲。但Redis不是萬能的，它不支持關系型資料庫復雜的SQL操作。某些場景下，可結合Redis和關系型DB，將簡單查詢相關的數據保存在Redis中，復雜SQL操作由關系型DB完成。
雖然Redis集很多優點於一身，但在實際運營中也存在一些問題。首先，Redis不具備自動容錯和恢復功能，主機從機的宕機都會導致前端部分讀寫請求失敗，需要等待機器重啟或者手動切換前端的IP才能恢復。如果主機宕機，宕機前有部分數據未能及時同步到從機，切換IP後還會引入數據不一致的問題，降低了系統的可用性。其次，Redis的主從復制採用全量復制，復制過程中主機會fork出一個子進程對內存做一份快照，並將子進程的內存快照保持為文件發送給從機，這一過程需要確保主機有足夠多的空餘內存。若快照文件較大，對集群的服務能力會產生較大的影響，而且復制過程是在從機新加入集群或者從機和主機網路斷開重連時都會進行，也就是網路波動都會造成主機和從機間的一次全量的數據復制，這對實際的系統運營造成了不小的麻煩。最後，Redis較難支持在線擴容，在集群容量達到上限時在線擴容會變得很復雜。為避免這一問題，運維人員在系統上線時必須確保有足夠的空間，這對資源造成了很大的浪費。
2. 資料庫有哪些
資料庫有：
1、MySQL
MySQL是一個關系型資料庫管理系統，由瑞典MySQL AB公司開發，屬於Oracle旗下產品。MySQL是最流行的關系型資料庫管理系統之一，在WEB應用方面，MySQL是最好的RDBMS(Relational Database Management System，關系資料庫管理系統）應用軟體之一。
2、Oracle
Oracle開發的關系資料庫產品因性能卓越而聞名，Oracle資料庫產品為財富排行榜上的前1000家公司所採用，許多大型網站也選用了Oracle系統，是世界最好的資料庫產品。
3、SqlServer
SQL Server是由Microsoft開發和推廣的關系資料庫管理系統（DBMS），它最初是由Microsoft、Sybase和Ashton-Tate三家公司共同開發的，並於1988年推出了第一個OS/2版本。
4、SQLite
SQLite，是一款輕型的資料庫，是遵守ACID的關系型資料庫管理系統，它包含在一個相對小的C庫中。它是D.RichardHipp建立的公有領域項目。
5、INFORMIX
Informix是IBM公司出品的關系資料庫管理系統（RDBMS）家族。作為一個集成解決方案，它被定位為作為IBM在線事務處理（OLTP）旗艦級數據服務系統。
6、Redis
Redis（Remote Dictionary Server )，即遠程字典服務，是一個開源的使用ANSIC語言編寫、支持網路、可基於內存亦可持久化的日誌型、Key-Value資料庫，並提供多種語言的API。
7、MongoDB
MongoDB是一個基於分布式文件存儲的資料庫。由C++語言編寫。旨在為WEB應用提供可擴展的高性能數據存儲解決方案。是非關系資料庫當中功能最豐富，最像關系資料庫的。
8、HBase
HBase是一個分布式的、面向列的開源資料庫，該技術來源於Fay Chang所撰寫的Google論文「Bigtable：一個結構化數據的分布式存儲系統」。就像Bigtable利用了Google文件系統（File System）所提供的分布式數據存儲一樣，HBase在Hadoop之上提供了類似於Bigtable的能力。
9、Neo4J
Neo4j是一個高性能的，NOSQL圖形資料庫，它將結構化數據存儲在網路上而不是表中。它是一個嵌入式的、基於磁碟的、具備完全的事務特性的Java持久化引擎，但是它將結構化數據存儲在網路（從數學角度叫做圖）上而不是表中。10、CouchDB
10、CouchDB
CouchDB是一個開源的面向文檔的資料庫管理系統，可以通過 RESTful JavaScript Object Notation (JSON) API 訪問。它反映了 CouchDB 的目標具有高度可伸縮性，提供了高可用性和高可靠性，即使運行在容易出現故障的硬體上也是如此。
3. redis是什麼資料庫
redis是一個key-value存儲系統。和Memcached類似，它支持存儲的value類型相對更多，包括string(字元串)、list(鏈表)、set(集合)、zset(sorted set --有序集合)和hash（哈希類型）。這些數據類型都支持push/pop、add/remove及取交集並集和差集及更豐富的操作，而且這些操作都是原子性的。在此基礎上，redis支持各種不同方式的排序。與memcached一樣，為了保證效率，數據都是緩存在內存中。區別的是redis會周期性的把更新的數據寫入磁碟或者把修改操作寫入追加的記錄文件，並且在此基礎上實現了master-slave(主從)同步。
Redis 是一個高性能的key-value資料庫。 redis的出現，很大程度補償了memcached這類key/value存儲的不足，在部 分場合可以對關系資料庫起到很好的補充作用。它提供了Java，C/C++，C#，PHP，JavaScript，Perl，Object-C，Python，Ruby，Erlang等客戶端，使用很方便。[1]
Redis支持主從同步。數據可以從主伺服器向任意數量的從伺服器上同步，從伺服器可以是關聯其他從伺服器的主伺服器。這使得Redis可執行單層樹復制。存檔可以有意無意的對數據進行寫操作。由於完全實現了發布/訂閱機制，使得從資料庫在任何地方同步樹時，可訂閱一個頻道並接收主伺服器完整的消息發布記錄。同步對讀取操作的可擴展性和數據冗餘很有幫助。
redis的官網地址，非常好記，是redis.io。（域名後綴io屬於國家域名，是british Indian Ocean territory，即英屬印度洋領地），Vmware在資助著redis項目的開發和維護。
4. Redis百億級Key存儲設計方案
該應用場景為DMP緩存存儲需求，DMP需要管理非常多的第三方id數據，其中包括各媒體cookie與自身cookie（以下統稱supperid）的mapping關系，還包括了supperid的人口標簽、移動端id（主要是idfa和imei）的人口標簽，以及一些黑名單id、ip等數據。
在hdfs的幫助下離線存儲千億記錄並不困難，然而DMP還需要提供毫秒級的實時查詢。由於cookie這種id本身具有不穩定性，所以很多的真實用戶的瀏覽行為會導致大量的新cookie生成，只有及時同步mapping的數據才能命中DMP的人口標簽，無法通過預熱來獲取較高的命中，這就跟緩存存儲帶來了極大的挑戰。
經過實際測試，對於上述數據，常規存儲超過五十億的kv記錄就需要1T多的內存，如果需要做高可用多副本那帶來的消耗是巨大的，另外kv的長短不齊也會帶來很多內存碎片，這就需要超大規模的存儲方案來解決上述問題。
人⼝標簽主要是cookie、imei、idfa以及其對應的gender（性別）、age（年齡段）、geo（地域）等；mapping關系主要是媒體cookie對supperid的映射。以下是數據存儲⽰示例：
媒體編號-媒體cookie=>supperid
supperid => { age=>年齡段編碼，gender=>性別編碼，geo=>地理位置編碼 }
imei or idfa => { age=>年齡段編碼，gender=>性別編碼，geo=>地理位置編碼 }
顯然PC數據需要存儲兩種key=>value還有key=>hashmap，⽽而Device數據需要存儲⼀一種
key=>hashmap即可。
存儲吃緊的一個重要原因在於每天會有很多新數據入庫，所以及時清理數據尤為重要。主要方法就是發現和保留熱數據淘汰冷數據。
網民的量級遠遠達不到幾十億的規模，id有一定的生命周期，會不斷的變化。所以很大程度上我們存儲的id實際上是無效的。而查詢其實前端的邏輯就是廣告曝光，跟人的行為有關，所以一個id在某個時間窗口的（可能是一個campaign，半個月、幾個月）訪問行為上會有一定的重復性。
數據初始化之前，我們先利用hbase將日誌的id聚合去重，劃定TTL的范圍，一般是35天，這樣可以砍掉近35天未出現的id。另外在Redis中設置過期時間是35天，當有訪問並命中時，對key進行續命，延長過期時間，未在35天出現的自然淘汰。這樣可以針對穩定cookie或id有效，實際證明，續命的方法對idfa和imei比較實用，長期積累可達到非常理想的命中。
Hash表空間大小和Key的個數決定了沖突率（或者用負載因子衡量），再合理的范圍內，key越多自然hash表空間越大，消耗的內存自然也會很大。再加上大量指針本身是長整型，所以內存存儲的膨脹十分可觀。先來談談如何把key的個數減少。
大家先來了解一種存儲結構。我們期望將key1=>value1存儲在redis中，那麼可以按照如下過程去存儲。先用固定長度的隨機散列md5(key)值作為redis的key，我們稱之為BucketId，而將key1=>value1存儲在hashmap結構中，這樣在查詢的時候就可以讓client按照上面的過程計算出散列，從而查詢到value1。
過程變化簡單描述為：get(key1) -> hget(md5(key1), key1) 從而得到value1。
如果我們通過預先計算，讓很多key可以在BucketId空間里碰撞，那麼可以認為一個BucketId下面掛了多個key。比如平均每個BucketId下面掛10個key，那麼理論上我們將會減少超過90%的redis key的個數。
具體實現起來有一些麻煩，而且用這個方法之前你要想好容量規模。我們通常使用的md5是32位的hexString（16進制字元），它的空間是128bit，這個量級太大了，我們需要存儲的是百億級，大約是33bit，所以我們需要有一種機制計算出合適位數的散列，而且為了節約內存，我們需要利用全部字元類型（ASCII碼在0~127之間）來填充，而不用HexString，這樣Key的長度可以縮短到一半。
下面是具體的實現方式
參數bit決定了最終BucketId空間的大小，空間大小集合是2的整數冪次的離散值。這里解釋一下為何一個位元組中只有7位可用，是因為redis存儲key時需要是ASCII（0~127），而不是byte array。如果規劃百億級存儲，計劃每個桶分擔10個kv，那麼我們只需2^30=1073741824的桶個數即可，也就是最終key的個數。
碎片主要原因在於內存無法對齊、過期刪除後，內存無法重新分配。通過上文描述的方式，我們可以將人口標簽和mapping數據按照上面的方式去存儲，這樣的好處就是redis key是等長的。另外對於hashmap中的key我們也做了相關優化，截取cookie或者deviceid的後六位作為key，這樣也可以保證內存對齊，理論上會有沖突的可能性，但在同一個桶內後綴相同的概率極低(試想id幾乎是隨機的字元串，隨意10個由較長字元組成的id後綴相同的概率*桶樣本數=發生沖突的期望值<<0.05,也就是說出現一個沖突樣本則是極小概率事件，而且這個概率可以通過調整後綴保留長度控制期望值)。而value只存儲age、gender、geo的編碼，用三個位元組去存儲。
另外提一下，減少碎片還有個很low但是有效的方法，將slave重啟，然後強制的failover切換主從，這樣相當於給master整理的內存的碎片。
推薦Google-tcmalloc， facebook-jemalloc內存分配，可以在value不大時減少內存碎片和內存消耗。有人測過大value情況下反而libc更節約。
1）kv存儲的量級必須事先規劃好，浮動的范圍大概在桶個數的十到十五倍，比如我就想存儲百億左右的kv，那麼最好選擇30bit 31bit作為桶的個數。也就是說業務增長在一個合理的范圍（10 15倍的增長）是沒問題的，如果業務太多倍數的增長，會導致hashset增長過快導致查詢時間增加，甚至觸發zip-list閾值，導致內存急劇上升。
2）適合短小value，如果value太大或欄位太多並不適合，因為這種方式必須要求把value一次性取出，比如人口標簽是非常小的編碼，甚至只需要3、4個bit（位）就能裝下。
3）典型的時間換空間的做法，由於我們的業務場景並不是要求在極高的qps之下，一般每天億到十億級別的量，所以合理利用CPU租值，也是十分經濟的。
4）由於使用了信息摘要降低了key的大小以及約定長度，所以無法從redis裡面random出key。如果需要導出，必須在冷數據中導出。
5）expire需要自己實現，目前的演算法很簡單，由於只有在寫操作時才會增加消耗，所以在寫操作時按照一定的比例抽樣，用HLEN命中判斷是否超過15個entry，超過才將過期的key刪除，TTL的時間戳存儲在value的前32bit中。
6）桶的消耗統計是需要做的。需要定期清理過期的key，保證redis的查詢不會變慢。
人口標簽和mapping的數據100億條記錄。
優化前用2.3T，碎片率在2左右；優化後500g，而單個桶的平均消耗在4左右。碎片率在1.02左右。查詢時這對於cpu的耗損微乎其微。
另外需要提一下的是，每個桶的消耗實際上並不是均勻的，而是符合多項式分布的。
上面的公式可以計算桶消耗的概率分布。公式是唬人用的，只是為了提醒大家不要想當然的認為桶消耗是完全均勻的，有可能有的桶會有上百個key。但事實並不沒有那麼誇張。試想一下投硬幣，結果只有兩種正反面。相當於只有兩個桶，如果你投上無限多次，每一次相當於一次伯努利實驗，那麼兩個桶必然會十分的均勻。概率分布就像上帝施的魔咒一樣，當你面對大量的桶進行很多的廣義的伯努利實驗。桶的消耗分布就會趨於一種穩定的值。接下來我們就了解一下桶消耗分布具體什麼情況：
通過采樣統計
31bit（20多億）的桶，平均4.18消耗
100億節約了1.8T內存。相當於節約了原先的78%內存，而且桶消耗指標遠沒有達到預計的底線值15。
對於未出現的桶也是存在一定量的，如果過多會導致規劃不準確，其實數量是符合二項分布的，對於2 30桶存儲2 32kv，不存在的桶大概有（百萬級別，影響不大）：
Math.pow((1 - 1.0 / Math.pow(2, 30)), Math.pow(2, 32)) * Math.pow(2, 30);
對於桶消耗不均衡的問題不必太擔心，隨著時間的推移，寫入時會對HLEN超過15的桶進行削減，根據多項式分布的原理，當實驗次數多到一定程度時，桶的分布就會趨於均勻（硬幣投擲無數次，那麼正反面出現次數應該是一致的），只不過我們通過expire策略削減了桶消耗，實際上對於每個桶已經經歷了很多的實驗發生。
總結：信息摘要在這種場景下不僅能節約key存儲，對齊了內存，還能讓Key按照多項式分布均勻的散列在更少量的key下面從而減少膨脹，另外無需在給key設置expire，也很大程度上節約了空間。
這也印證了時間換空間的基本理論，合理利用CPU租值也是需要考慮的。
關注分布式存儲技術以及分布式計算方法