作者：京東零售 劉慧卿

一 資料庫發展史

起初，數據的管理方式是文件系統，數據存儲在文件中，數據管理和維護都由程式員完成。後來發展出樹形結構和網狀結構的資料庫，但都存在著難以擴展和維護的問題。直到七十年代，關係資料庫理論的提出，以表格形式組織數據，數據之間存在關聯關係，具有了良好的結構化和規範化特性，成為主流資料庫類型。

先來看一張資料庫發展史圖鑒：

隨之高併發大數據時代的來臨，資料庫按照各種應用場景進行了更細粒度的拆分和演進，資料庫細分領域的典型代表：

二 資料庫名詞概念

RDBS

1970年的6月，IBM 公司的研究員埃德加·考特 （Edgar Frank Codd） 發表了那篇著名的《大型共用資料庫數據的關係模型》（A Relational Model of Data for Large Shared Data Banks）的論文，拉開了關係型資料庫（Relational DataBase Server）軟體革命的序幕（之前是層次模型和網狀模型資料庫為主）。直到現在，關係型資料庫在基礎軟體應用領域仍是最主要的數據存儲方式之一。

關係型資料庫建立在關係型數據模型的基礎上，是藉助於集合代數等數學概念和方法來處理數據的資料庫。在關係型資料庫中，實體以及實體間的聯繫均由單一的結構類型來表示，這種邏輯結構是一張二維表。關係型資料庫以行和列的形式存儲數據，這一系列的行和列被稱為表，一組表組成了資料庫。

NoSQL

NoSQL（Not Only SQL） 資料庫也即非關係型資料庫，它是在大數據的時代背景下產生的，它可以處理分散式、規模龐大、類型不確定、完整性沒有保證的“雜亂”數據，這是傳統的關係型資料庫遠遠不能勝任的。NoSQL資料庫並沒有一個統一的模型，是以犧牲事務機制和強一致性機制，來獲取更好的分散式部署和橫向擴展能力，使其在不同的應用場景下，對特定業務數據具有更強的處理性能。常用數據模型示例如下：

NewSQL

NewSQL 是一類新的關係型資料庫， 是各種新的可擴展和高性能的資料庫的簡稱。它不僅具有 NoSQL 資料庫對海量數據的存儲管理能力，同時還保留了傳統資料庫支持的 ACID 和 SQL 特性，典型代表有TiDB和OceanBase。

OLTP

聯機事務處理過程(On-Line Transaction Processing)：也稱為面向交易的處理過程，其基本特征是前臺接收的用戶數據可以立即傳送到計算中心進行處理，併在很短的時間內給出處理結果，是對用戶操作快速響應的方式之一。

OLAP

聯機分析處理（On-Line Analytical Processing）是一種面向數據分析的處理過程，它使分析人員能夠迅速、一致、交互地從各個方面觀察信息，以達到深入理解數據的目的。它具有FASMI(Fast Analysis of Shared Multidimensional Information)，即共用多維信息的快速分析的特征。

關於OLTP和OLAP的區別，借用一張表格對比如下：

HTAP

HTAP (Hybrid Transactional/Analytical Processing) 混合型資料庫基於新的計算存儲框架，能夠同時支撐OLTP和OLAP場景，避免傳統架構中大量數據交互造成的資源浪費和衝突。

三 領域資料庫

列式資料庫

傳統的以行形式保存的數據主要滿足OLTP應用，列形式保存的數據主要滿足以查詢為主的OLAP應用。在列式資料庫中，數據按列存儲，而每個列中的數據類型相同。這種存儲方式使列式資料庫能夠更高效地處理大量的數據，特別是需要進行大規模的數據分析和處理時（如金融、醫療、電信、能源、物流等行業）。

兩種存儲結構的區別如下圖：

列式資料庫的主要優點：

•更高的壓縮比率：由於每個列中的數據類型相同，列式資料庫可以使用更高效的壓縮演算法來壓縮數據（壓縮比可達到5～20倍），從而減少存儲空間的使用。

•更快的查詢速度：列式資料庫可以只讀取需要的列，而不需要讀取整行數據，從而加快查詢速度。

•更好的擴展性：列式資料庫可以更容易地進行水平擴展，即增加更多的節點和伺服器來處理更大規模的數據。

•更好的數據分析支持：由於列式資料庫可以處理大規模的數據，它可以支持更複雜的數據分析和處理操作，例如數據挖掘、機器學習等。

列式資料庫的主要缺點：

•更慢的寫入速度：由於數據是按列存儲，每次寫入都需要寫入整個列，而不是單個行，因此寫入速度可能較慢。

•更複雜的數據模型：由於數據是按列存儲，數據模型可能比行式資料庫更複雜，需要更多的設計和開發工作。

列式資料庫的應用場景：

•金融：金融行業的交易數據和市場數據，例如股票價格、外匯匯率、利率等。列式資料庫可以更快速地處理這些數據，並且支持更複雜的數據分析和處理操作，例如風險管理、投資分析等。

•醫療：醫療行業的病曆數據、醫療圖像和實驗數據等。列式資料庫可以更高效地存儲和處理這些數據，並且支持更複雜的醫學研究和分析操作。

•電信：電信行業的用戶數據和通信數據，例如電話記錄、簡訊記錄、網路流量等。列式資料庫可以更快速地處理這些數據，並且支持更複雜的用戶行為分析和網路優化操作。

•能源：能源行業的感測器數據、監測數據和生產數據等。列式資料庫可以更高效地存儲和處理這些數據，並且支持更複雜的能源管理和控制操作。

•物流：物流行業的運輸數據、庫存數據和訂單數據等。列式資料庫可以更快速地處理這些數據，並且支持更複雜的物流管理和優化操作。

總之，列式資料庫是一種高效處理大規模數據的資料庫管理系統，但需要權衡寫入速度、數據模型複雜度和成本等因素。 隨著傳統關係型資料庫與新興的分散式資料庫不斷的發展，列式存儲與行式存儲會不斷融合，資料庫系統呈現雙模式數據存放方式。

時序資料庫

時序資料庫全稱為時間序列資料庫 ( Time Series Database)，用於存儲和管理時間序列數據的專業化資料庫，是優化用於攝取、處理和存儲時間戳數據的資料庫。其跟常規的關係資料庫SQL相比，最大的區別在於：時序資料庫是以時間為索引的規律性時間間隔記錄的資料庫。

時序資料庫在物聯網和互聯網應用程式監控（APM）等場景應用比較多，以監控數據採集來舉例，如果數據監控數據採集時間間隔是1s，那一個監控項每天會產生86400個數據點，若有10000個監控項，則一天就會產生864000000個數據點。在物聯網場景下，這個數字會更大，整個數據的規模，是TB甚至是PB級的。

時序資料庫發展史：

當下最常見的Kubernetes容器管理系統中，通常會搭配普羅米修斯（Prometheus）進行監控，Prometheus就是一套開源的監控&報警&時間序列資料庫的組合。

圖資料庫

圖資料庫（Graph Database）是基於圖論實現的一種新型NoSQL資料庫。它的數據存儲結構和數據的查詢方式都是以圖論為基礎的。圖論中圖的基本元素為節點和邊，在圖資料庫中對應的就是節點和關係。

圖資料庫在反欺詐多維關聯分析場景，社交網路圖譜，企業關係圖譜等場景中可以做一些非常複雜的關係查詢。這是由於圖數據結構表現的是實體聯繫本身，它表現了現實世界中事物聯繫的本質，它的聯繫在節點創建時就已經建立，所以在查詢中能以快捷的路徑返回關聯數據，從而表現出非常高效的查詢性能。

目前市面上較為流行的圖資料庫產品有以下幾種：

與傳統的關係資料庫相比，圖資料庫具有以下優點：

1.更快的查詢速度：圖資料庫可以快速遍歷圖數據，找到節點之間的關聯和路徑，因此查詢速度更快。

2.更好的擴展性：圖資料庫可以輕鬆地擴展到大規模的數據集，因為它們可以分散式存儲和處理數據。

3.更好的數據可視化：圖資料庫可以將數據可視化為圖形，使用戶更容易理解和分析數據。

4.更好的數據一致性：圖資料庫可以確保數據的一致性，因為它們可以在節點和邊之間建立強制性的關係。

四 數據結構設計

前面簡單介紹了資料庫相關的基礎知識，下麵再介紹幾種我們常見的數據結構設計相關的應用實踐：拉鏈表，位運算和環形隊列。

4.1 拉鏈表

拉鏈表是一種數據倉庫中常用的數據模型，用於記錄維度數據的變化歷史。我們以一個人員變動的場景舉例，假設有一個員工信息表，其中包含了員工的姓名、工號、職位、部門、入職時間等信息。如果需要記錄員工的變動情況，就可以使用拉鏈表來實現。

首先，在員工信息表的基礎上新增兩個欄位：生效時間和失效時間。當員工信息發生變動時，不再新增一條記錄，而是修改原有記錄的失效時間，同時新增一條新的記錄。如下表所示：

這裡的生效時間指的是該記錄生效的時間，失效時間指的是該記錄失效的時間。例如，張三最初是技術部經理，生效時間為入職時間，失效時間為2012年底，之後晉升為技術部總監，生效時間為2013年初，失效時間為2015年底，最後又晉升為技術部總經理，生效時間為2016年初，失效時間為9999年底。

通過這種方式，可以記錄員工變動的歷史信息，並能夠方便地查詢某個時間點的員工信息。例如，如果需要查詢張三在2014年的職位和部門信息，只需查詢生效時間小於2014年且失效時間大於2014年的記錄即可。

拉鏈表通常包括以下幾個欄位：

1.主鍵：唯一標識每個記錄的欄位，通常是一個或多個列的組合。
2.生效時間：記錄的生效時間，即該記錄開始生效的時間。
3.失效時間：記錄的失效時間，即該記錄失效的時間。
4.版本號：記錄的版本號，用於標識該記錄的版本。
5.其他維度屬性：記錄的其他維度屬性，如客戶名、產品名、員工名等。

當一個記錄的維度屬性發生變化時，不再新增一條記錄，而是修改原有記錄的失效時間，同時新增一條新的記錄。新記錄的生效時間為變化的時間，失效時間為9999年底。這樣就能夠記錄每個維度屬性的歷史變化信息，同時保證查詢時能夠正確獲取某個時間點的維度屬性信息。

拉鏈表與傳統的流水錶相比，它們的主要區別在於：

1.數據結構不同：流水錶是一張只有新增和更新操作的表，每次更新都會新增一條記錄，記錄中包含了所有的歷史信息。而拉鏈表則是一張有新增、更新和刪除操作的表，每個記錄都有一個生效時間段和失效時間段，記錄的歷史信息通過時間段的變化來體現。

2.查詢方式不同：流水錶的查詢方式是基於時間點的查詢，即查詢某個時間點的記錄信息。而拉鏈表的查詢方式是基於時間段的查詢，即查詢某個時間段內的記錄信息。

3.存儲空間不同：由於流水錶需要記錄所有歷史信息，所以存儲空間相對較大。而拉鏈表只記錄生效時間段和失效時間段，所以存儲空間相對較小。

4.數據更新方式不同：流水錶只有新增和更新操作，每次更新都會新增一條記錄，不會對原有記錄進行修改。而拉鏈表有新增、更新和刪除操作，每次更新會修改原有記錄的失效時間，同時新增一條新的記錄。

4.2 巧用位運算

藉助於電腦位運算的特性，可以巧妙的解決某些特定問題，使實現更加優雅，節省存儲空間的同時，也可以提高運行效率，典型應用場景：壓縮存儲、點陣圖索引、數據加密、圖形處理和狀態判斷等，下麵介紹幾個典型案例。

4.2.1 位運算

•使用位運算實現開關和多選項疊加（資源許可權）等應用場景。一個int類型有32個位，理論上可以表示32個開關狀態或業務選項；以用戶每個月的簽到場景舉例：用一個int欄位來表示用戶一個月的簽到情況，0表示未簽到，1表示簽到。想知道某一天是否簽到，則只需要判斷對應的比特位上是否為1。計算一個月累計簽到了多少次，只需要統計有多少個比特位為1就可以了。這種設計巧妙的數據存儲結構在後面的點陣圖（BitMap）中，還會進行更為詳細的介紹。

•使用位運算實現業務優先順序計算：

public abstract class PriorityManager {
    // 定義業務優先順序常量
    public static final int PRIORITY_LOW = 1;     // 二進位：001
    public static final int PRIORITY_NORMAL = 2;  // 二進位：010
    public static final int PRIORITY_HIGH = 4;    // 二進位：100
    
    // 定義用戶許可權常量
    public static final int PERMISSION_READ = 1;  // 二進位：001
    public static final int PERMISSION_WRITE = 2; // 二進位：010
    public static final int PERMISSION_DELETE = 4;// 二進位：100
    
    // 定義用戶許可權和業務優先順序的組合值
    public static final int PERMISSION_LOW_PRIORITY = PRIORITY_LOW | PERMISSION_READ;     // 二進位：001 | 001 = 001
    public static final int PERMISSION_NORMAL_PRIORITY = PRIORITY_NORMAL | PERMISSION_READ | PERMISSION_WRITE;  // 二進位：010 | 001 | 010 = 011
    public static final int PERMISSION_HIGH_PRIORITY = PRIORITY_HIGH | PERMISSION_READ | PERMISSION_WRITE | PERMISSION_DELETE;  // 二進位：100 | 001 | 010 | 100 = 111
    
    // 判斷用戶許可權是否滿足業務優先順序要求
    public static boolean checkPermission(int permission, int priority) {
        return (permission & priority) == priority;
    }
}

•其它使用位運算的典型場景：HashMap中的隊列長度的設計和線程池ThreadPoolExcutor中使用AtomicInteger欄位ctl，存儲當前線程池狀態和線程數量（高3位表示當前線程的狀態，低29位表示線程的數量）。

4.2.2 BitMap

點陣圖（BitMap）是一種常用的數據結構，在索引，數據壓縮等方面有廣泛應用。基本思想就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由於採用了Bit為單位來存儲數據，因此可以大大節省存儲空間，是少有的既能保證存儲空間又能保證查找速度的數據結構（而不必空間換時間）。

舉個例子，假設有這樣一個需求：在20億個隨機整數中找出某個數m是否存在其中，並假設32位操作系統，4G記憶體，在Java中，int占4位元組，1位元組=8位（1 byte = 8 bit）。

•如果每個數字用int存儲，那就是20億個int，因而占用的空間約為 (2000000000*4/1024/1024/1024)≈7.45G

•如果按位存儲就不一樣了，20億個數就是20億位，占用空間約為 (2000000000/8/1024/1024/1024)≈0.233G

存儲空間可以壓縮節省31倍！那麼它是如何通過二進位位實現數字標記的呢？ 其原理是用每個二進位位（下標）表示一個真實數字，0表示不存在，1表示存在，這樣我們可以很容易表示{1,2,4,6}這幾個數：

電腦記憶體分配的最小單位是位元組，也就是8位，那如果要表示{12,13,15}怎麼辦呢？可以另申請一個位元組b[1]：

通過一個二維數組來實現位數疊加，1個int占32位，那麼我們只需要申請一個int數組長度為 int index[1+N/32] 即可存儲，其中N表示要存儲的這些數中的最大值：

index[0]：可以表示0~31

index[1]：可以表示32~63

index[2]：可以表示64~95

以此類推...如此一來，給定任意整數M，那麼M/32就得到下標，M%32就知道它在此下標的哪個位置。

BitMap數據結構通常用於以下場景：

1.壓縮存儲大量布爾值：BitMap可以有效地壓縮大量的布爾值，從而減少記憶體的使用；

2.快速判斷一個元素是否存在：BitMap可以快速地判斷一個元素是否存在，只需要查找對應的位即可；

3.去重：BitMap可以用於去重操作，將元素作為索引，將對應的位設置為1，重覆元素只會對應同一個位，從而實現去重；

4.排序：BitMap可以用於排序，將元素作為索引，將對應的位設置為1，然後按照索引順序遍歷位數組，即可得到有序的元素序列；

5.ElasticSearch和Solr等搜索引擎中，在設計搜索剪枝時，需要保存已經搜索過的歷史信息，可以使用點陣圖減小歷史信息數據所占空間；

4.2.3 布隆過濾器

點陣圖（Bitmap）這種數據存儲結構，如果數據量大到一定程度，比如64bit類型的數據，簡單算一下存儲空間就知道，海量硬體資源要求，已經不太現實了：

所以另一個著名的工業實現——布隆過濾器（Bloom Filter） 出現了。如果說BitMap對於每一個可能的整型值，通過直接定址的方式進行映射，相當於使用了一個哈希函數，那布隆過濾器就是引入了k ( k > 1 )個相互獨立的哈希函數，保證在給定的空間和誤判率情況下，完成元素判重的過程。下圖中是k = 3 時的布隆過濾器：

布隆過濾器的內部依賴於哈希演算法，當檢測某一條數據是否見過時，有一定概率出現假陽性（False Positive），但一定不會出現假陰性（False Negative）。也就是說，當 布隆過濾器認為一條數據出現過，那麼該條數據很可能出現過；但如果布隆過濾器認為一條數據沒出現過，那麼該條數據一定沒出現過。布隆過濾器通過引入一定錯誤率，使得海量數據判重在可以接受的記憶體代價中得以實現。

上圖中，x,y,z經由哈希函數映射將各自在Bitmap中的3個位置置為1，當w出現時，僅當3個標誌位都為1時，才表示w在集合中。圖中所示的情況，布隆過濾器將判定w不在集合中。

常見實現

•Java中Guava工具包中實現；

•Redis 4.0開始以插件形式提供布隆過濾器功能；

適用場景

•網頁爬蟲對URL的去重，避免爬去相同的URL地址，比如Chrome瀏覽器就是使用了一個布隆過濾器識別惡意鏈接；

•垃圾郵件過濾，從數十億個垃圾郵件列表中判斷某郵箱是否是殺垃圾郵箱；

•解決資料庫緩存擊穿，黑客攻擊伺服器時，會構建大量不存在於緩存中的key向伺服器發起請求，在數據量足夠大的時候，頻繁的資料庫查詢會導致掛機；

•谷歌Bigtable、Apache HBase、Apache Cassandra和PostgreSQL使用布隆過濾器來減少對不存在的行或列的磁碟查找；

•秒殺系統，查看用戶是否重覆購買；

4.3 環形隊列

環形隊列是一種用於表示一個固定尺寸、頭尾相連的數據結構，很適合緩存數據流。在通信開發（Socket，TCP/IP，RPC開發），在內核的進程間通信（IPC），視頻音頻播放等各種場景中，都有其身影。日常開發過程中使用的Dubbo、Netty、Akka、Quartz、ZooKeeper 、Kafka等各種中間件，也都有環形隊列的思想。下麵介紹兩種常用的環形數據結構：Hash環和時間輪。

4.3.1 一致性Hash環

先來看一下，典型Hash演算法結構如下：

以上圖Hash策略為例，當節點數N發生變化的時候 之前所有的 hash映射幾乎全部失效，如果集群是無狀態的服務，倒是沒什麼事情，但是如果是分散式緩存這種場景，就會導致比較嚴重的問題。比如 Key1原本是路由到Node1上，命中緩存的Value1數據。但是當N節點變化後，Key1可能就路由到了Node2節點，這就產生了緩存數據無法命中的問題。而無論是機器故障還是緩存擴容，都會導致節點數的變化。

如何解決上面場景的問題呢？就是接下來介紹的一致性Hash演算法。

一致性哈希將整個哈希值空間組織成一個虛擬的圓環，假設某哈希函數H的值空間為0-2^32-1（即哈希值是一個32位無符號整型），所有的輸入值都被映射到 0-2^32-1 之間，組成一個圓環。整個哈希空間環如下：

路由數據的過程如下：將數據key使用相同的函數Hash計算出哈希值，並確定此數據在環上的位置，從此位置沿環順時針“行走”，遇到的第一個節點就是其應該定位到的伺服器。如果某個節點的伺服器故障，其影響範圍也不再是所有集群，而是限定在故障節點與其上游節點的部分區域。

當某個節點宕機後，原本屬於它的請求都會被重新hash映射到下游節點，會突然造成下游節點壓力過大有可能也會造成下游節點宕機，從而容易形成雪崩，為此引入了虛擬節點來解決這個問題。

根據Node節點生成很多的虛擬節點分佈在圓環上，，一個真實節點映射對應多個虛擬節點。這樣當某個節點掛了後原本屬於它的請求，會被均衡的分佈到其他節點上降低了產生雪崩的情況，也解決了物理節點數少，導致請求分佈不均的問題。

帶有虛擬節點的Hash環：

一致性Hash演算法由於均衡性，持久性的映射特點被廣泛應用於負載均衡領域，比如nginx、dubbo等內部都有一致性hash的實現。

4.3.2 時間輪分片

時間輪（TimeWheel）是一種實現延遲功能（定時器）的精妙的演算法，可以實現高效的延時隊列。以Kafka中的時間輪實現方案為例，它是一個存儲定時任務的環形隊列，底層採用數組實現，數組中的每個元素可以存放一個定時任務列表（TimerTaskList）。TimerTaskList是一個環形的雙向鏈表，鏈表中的每一項表示的都是定時任務項（TimerTaskEntry），其中封裝了真正的定時任務TimerTask。

通過上圖可以發現，時間輪演算法不再任務隊列作為數據結構，輪詢線程不再負責遍歷所有任務，而是僅僅遍歷時間刻度。時間輪演算法好比指針不斷在時鐘上旋轉、遍歷，如果一個發現某一時刻上有任務（任務隊列），那麼就會將任務隊列上的所有任務都執行一遍。

假設相鄰bucket到期時間的間隔為bucket=1s，從0s開始計時，1s後到期的定時任務掛在bucket=1下，2s後到期的定時任務掛在bucket=2下，當檢查到時間過去了1s時，bucket=1下所有節點執行超時動作，當時間到了2s時，bucket=2下所有節點執行超時動作。時間輪使用一個表盤指針（pointer），用來表示時間輪當前指針跳動的次數，可以用tickDuration * (pointer + 1)來表示下一次到期的任務，需要處理此bucket所對應的 TimeWheel中的所有任務。

時間輪的優點

1.任務的添加與移除，都是O(1)級的複雜度；

2.只需要有一個線程去推進時間輪，不會占用大量的資源；

3.與其他任務調度模式相比，CPU的負載和資源浪費減少；

適用場景

時間輪是為解決高效調度任務而產生的調度模型。在周期性定時任務，延時任務，通知任務等場景都可以發揮效用。

五 總結

本文針對數據存儲相關名詞概念進行瞭解釋，重點介紹了資料庫技術的發展史。為了豐富文章的可讀性以及實用性，又從數據結構設計層面進行了部分技術實戰能力的外延擴展，闡述了拉鏈表，位運算，環形隊列等相關數據結構在軟體開發領域的應用，希望本文給你帶來收穫。

註：本文個別圖片來自互聯網