作者：京東零售 煉訓卿

一 資料庫發展史

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

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

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

二 資料庫名詞概念

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的負載和資源浪費減少；

適用場景

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

五 總結

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

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

標籤：其他

上一篇：MySQL 存盤程序&觸發器&事務

下一篇：返回列表