1 背景介紹

1.1 數(shù)據(jù)產(chǎn)生的三個(gè)階段

• 運(yùn)營(yíng)式系統(tǒng)階段（被動(dòng)）
• 用戶原創(chuàng)內(nèi)容階段（主動(dòng)）
• 感知式系統(tǒng)階段（自動(dòng)）

1.2 數(shù)據(jù)種類定義

1.3 大數(shù)據(jù)的定義

大數(shù)據(jù)是指利用常用軟件工具捕獲、管理和處理數(shù)據(jù)所耗時(shí)間超過可容忍時(shí)間的數(shù)據(jù)集。

1.4 大數(shù)據(jù)的4V特性

• Volume 體積： Volume scale of data 數(shù)據(jù)的體積規(guī)模
• Variety 種類： Variety different forms of data 數(shù)據(jù)的多種不同形式
• Velocity 速度： Velocity analysis of streaming data 流數(shù)據(jù)的速度分析
• Veracity* 準(zhǔn)確性： Veracity uncertainty of data 數(shù)據(jù)的不準(zhǔn)確性

1.5 大數(shù)據(jù)特征

• Value 價(jià)值：價(jià)值密度低是大數(shù)據(jù)的一個(gè)典型特征。
• Variety 多樣性：能夠在不同的數(shù)據(jù)類型中進(jìn)行交叉分析是大數(shù)據(jù)的核心技術(shù)之一。
• Velocity 速度：<1s 秒級(jí)響應(yīng) 實(shí)時(shí)處理的要求是區(qū)別大數(shù)據(jù)應(yīng)用和傳統(tǒng)數(shù)據(jù)倉(cāng)庫(kù)技術(shù)、BI技術(shù)的關(guān)鍵差別之一。
• Volume 數(shù)據(jù)量：>1PB PB級(jí)數(shù)據(jù)

1.6 數(shù)據(jù)處理需求與傳統(tǒng)平臺(tái)硬件擴(kuò)展能力之間的差距不斷擴(kuò)大

1.7 大數(shù)據(jù)分析與傳統(tǒng)BI分析的區(qū)別

分析過程的區(qū)別

• 傳統(tǒng)BI分析：事務(wù) ---> 關(guān)系型數(shù)據(jù)庫(kù) ---批處理--> 數(shù)據(jù)倉(cāng)庫(kù) ---> 分析
• 大數(shù)據(jù)分析：非結(jié)構(gòu)化 ---流式--> 集群化數(shù)據(jù)庫(kù) <--- 組織分析

1.8 大數(shù)據(jù)應(yīng)用的類型

2 E-R模型

2.1 數(shù)據(jù)庫(kù)設(shè)計(jì)過程

需求分析 <==> 概念數(shù)據(jù)庫(kù)設(shè)計(jì) <==> 邏輯數(shù)據(jù)庫(kù)設(shè)計(jì) <==> 物理數(shù)據(jù)庫(kù)設(shè)計(jì)

2.2 E-R模型基本概念

• 實(shí)體（Entity）：客觀存在可以相互區(qū)分的事物（矩形）
• 屬性（Attribute）：實(shí)體具有的某一特性（橢圓）
• 域（Domain）：屬性的取值范圍，即值集
• 實(shí)體型（Entity Type）：實(shí)體名和其屬性名集共同構(gòu)成
• 實(shí)體集（Entity Set）：同型實(shí)體的集合
• 聯(lián)系（Relationship）：多個(gè)實(shí)體之間的相互關(guān)聯(lián)（菱形）
• 聯(lián)系集（Relationship Set）：同類聯(lián)系的集合
• 聯(lián)系的元或度（Degree）：參與聯(lián)系的實(shí)體集的個(gè)數(shù)
• 碼（Key）
  • 超碼：能唯一標(biāo)識(shí)實(shí)體的屬性或?qū)傩越M
  • 候選碼：其任意真子集都不能成為超碼的最小超碼
  • 主碼：從所有候選碼中選定的一個(gè)用來區(qū)別同一實(shí)體集中的不同實(shí)體的候選碼（下劃線）
• 參與（Participation）：實(shí)體集之間的關(guān)聯(lián)
  • 全部參與：實(shí)體集E中的每個(gè)實(shí)體都參與到聯(lián)系集R中的至少一個(gè)聯(lián)系，E全部參與R（雙線連接）
  • 部分參與：實(shí)體集E中只有部分實(shí)體參與到聯(lián)系集R的聯(lián)系中，E部分參與R
• 存在依賴（Existence Dependency）：實(shí)體x的存在依賴于實(shí)體y的存在，x存在依賴于y
  • x稱為支配實(shí)體，y稱為從屬實(shí)體
  • 存在依賴一定全部參與
  • 參照完整性：一個(gè)實(shí)體集的屬性是另一實(shí)體集的主碼屬性
• 角色（Role）：實(shí)體在聯(lián)系中的作用

2.3 屬性的類型

• 復(fù)合（Composite）屬性：可以劃分為更小的屬性的屬性，對(duì)應(yīng)簡(jiǎn)單屬性
• 多值屬性：有多于一個(gè)取值的屬性，對(duì)應(yīng)單值屬性（雙橢圓）
• 派生（Derived）屬性：可以從其他相關(guān)的屬性或?qū)嶓w派生出來的屬性值，對(duì)應(yīng)基屬性/存儲(chǔ)屬性（虛橢圓）

2.4 映射的基數(shù)（Mapping Cardinalities）

實(shí)體之間聯(lián)系的數(shù)量，即一個(gè)實(shí)體通過一個(gè)聯(lián)系集能與另一實(shí)體集相關(guān)聯(lián)的實(shí)體的數(shù)目。

• 一對(duì)一（1:1），一對(duì)多（1:m），多對(duì)多（m:n）
• 在E-R圖中用箭頭或線段表示（箭頭表示1，線段表示m）

2.5 鍵

• 實(shí)體主鍵在E-R圖中用下劃線表示
• 聯(lián)系集的鍵：在聯(lián)系集中可唯一確定一個(gè)聯(lián)系的屬性

參與聯(lián)系的實(shí)體集的主鍵的聯(lián)合包含聯(lián)系集的主鍵

2.6 弱實(shí)體集（Weak Entity Set）

如果一個(gè)實(shí)體集的所有屬性都不足以形成主碼的，則稱這樣的實(shí)體集為弱實(shí)體集。

2.6.1 分辨符（Discriminator）

弱實(shí)體集中用于區(qū)別依賴于某個(gè)特定強(qiáng)實(shí)體集的屬性集合，也稱作部分碼（Partial Key）

2.6.2 弱實(shí)體集的主碼

由該弱實(shí)體集所存在依賴的強(qiáng)實(shí)體集的主碼和該弱實(shí)體集的分辨符組成。

2.6.3 為什么使用弱實(shí)體集？

• 避免數(shù)據(jù)冗余、以及因此帶來的數(shù)據(jù)的不一致性
• 反映了一個(gè)實(shí)體對(duì)其他實(shí)體依賴的邏輯結(jié)構(gòu)
• 弱實(shí)體集可以隨它們的強(qiáng)實(shí)體集的刪除而自動(dòng)刪除
• 弱實(shí)體集可以物理地隨它們的強(qiáng)實(shí)體集存儲(chǔ)

2.6.4 弱實(shí)體集在E-R圖中的表示

• 弱實(shí)體集：雙邊框矩形
• 標(biāo)識(shí)性聯(lián)系：雙邊框菱形
• 聯(lián)系集雙線連接弱實(shí)體集（全部參與），箭頭指向強(qiáng)實(shí)體集（一對(duì)多聯(lián)系）
• 弱實(shí)體集的分辨符：下劃虛線

2.7 擴(kuò)展E-R特性

• 特殊化（Specialization）：根據(jù)實(shí)體集中子集的差異特性對(duì)實(shí)體集進(jìn)行分組（ISA倒三角）
• 一般化（概括）（Generalization）：根據(jù)實(shí)體集共有的性質(zhì)，合成一個(gè)較高層的實(shí)體集（逆特殊化）
• 屬性繼承（Attribute Inheritance）：高層實(shí)體集的屬性被低層實(shí)體集自動(dòng)繼承
  • 層次結(jié)構(gòu)（Hierarchy）：實(shí)體集作為低層實(shí)體只能參與到一個(gè)ISA聯(lián)系中
  • 格結(jié)構(gòu)（Lattice）：低層實(shí)體集可以參與到多個(gè)ISA聯(lián)系中
• 聚集（Aggregation）：實(shí)體集與聯(lián)系集之間的聯(lián)系，以及聯(lián)系集之間的聯(lián)系，解決E-R模型不能表達(dá)聯(lián)系間的聯(lián)系、或聯(lián)系集與實(shí)體集間的聯(lián)系的問題

2.8 設(shè)計(jì)E-R圖的過程

1. 確定實(shí)體類型
2. 確定聯(lián)系類型
3. 連接實(shí)體類型和聯(lián)系類型，組合E-R圖
4. 確定實(shí)體類型和聯(lián)系類型的屬性
5. 確定實(shí)體類型的碼

2.9 E-R模型向關(guān)系模式的轉(zhuǎn)換

• 實(shí)體 → 關(guān)系
• 屬性 → 關(guān)系的屬性
• 復(fù)合屬性 → 將每個(gè)組合屬性作為復(fù)合屬性所在實(shí)體的屬性
• 多值數(shù)型 → 新的關(guān)系 + 所在實(shí)體的碼
• 一對(duì)多聯(lián)系 → 將單方參與實(shí)體的碼作為多方參與實(shí)體的屬性
• 多對(duì)多聯(lián)系 → 將聯(lián)系定義為新的關(guān)系，屬性為參與雙方的碼
• 一對(duì)一聯(lián)系 → 若聯(lián)系一方全部參與，則將聯(lián)系另一方的碼作為全部參與一方的屬性
• 弱實(shí)體集 → 所對(duì)應(yīng)的關(guān)系的碼與弱實(shí)體集本身的分辨符加上所依賴的強(qiáng)實(shí)體集的碼
• 概括 → 高層實(shí)體集和低層實(shí)體集分別轉(zhuǎn)為表，低層實(shí)體集所對(duì)應(yīng)的關(guān)系包括高層實(shí)體集的碼
• 聚集 → 實(shí)體集A和B與他們的聯(lián)系集R被看成實(shí)體集C，C與另一實(shí)體集D構(gòu)成聯(lián)系S，則S所對(duì)應(yīng)的關(guān)系的碼由R和D的碼構(gòu)成

3 數(shù)據(jù)庫(kù)應(yīng)用設(shè)計(jì)和優(yōu)化基礎(chǔ)

3.1 優(yōu)化

• 不訪問不必要的數(shù)據(jù)
  • B*Tree/hash等索引方法 定位必要的數(shù)據(jù)
  • Column Store（列存儲(chǔ)？）/分表方式 分開存儲(chǔ)數(shù)據(jù)
• 合理利用硬件提高訪問效率
  • 緩存：消除對(duì)數(shù)據(jù)的重復(fù)訪問
  • 批處理：減少交互的次數(shù)（網(wǎng)絡(luò)、磁盤）
  • 新硬件：降低后端的延時(shí)，提高效率
• 提高系統(tǒng)吞吐量
  • 細(xì)化工作單元，減少串行操作
  • 優(yōu)化硬件配置，提高整體TCO和硬件利用率
  • 合理拆分（水平、垂直拆分），提高系統(tǒng)整體吞吐能力

3.2 響應(yīng)時(shí)間 vs 吞吐量

性能：衡量完成特定任務(wù)的速度或速率
響應(yīng)時(shí)間：衡量系統(tǒng)與用戶交互時(shí)多久能夠收到響應(yīng)
吞吐量：衡量系統(tǒng)在單位時(shí)間里可以完成的任務(wù)量
*響應(yīng)時(shí)間 = 服務(wù)時(shí)間 + 隊(duì)列時(shí)間
經(jīng)典響應(yīng)時(shí)間曲線：
Arrival Rate = 1.55 trx/s
Service Time = 2 ms/trx
Queue Time = 1ms/trx
Response Time = 3ms/trx

3.3 磁盤性能估計(jì)

3.3.1 訪問時(shí)間

• 從發(fā)出請(qǐng)求到數(shù)據(jù)開始傳輸之間的時(shí)間
• 尋道時(shí)間（Seek Time）
  • 磁盤臂定位時(shí)間，即磁盤臂移動(dòng)到正確的磁道所需的時(shí)間
  • 與移動(dòng)距離成正比，平均尋道時(shí)間是最壞時(shí)間的 1/3（4-10 ms）
• 旋轉(zhuǎn)等待時(shí)間（Rotational latency）
  • 尋道結(jié)束后，等待被存取的扇區(qū)出現(xiàn)在讀寫頭下面的時(shí)間
  • 平均旋轉(zhuǎn)等待時(shí)間是磁盤旋轉(zhuǎn)一周時(shí)間的 1/2（2-5 ms）

3.3.2 數(shù)據(jù)傳輸率

• 從磁盤獲得數(shù)據(jù)或向磁盤存儲(chǔ)數(shù)據(jù)的速率（4-8 MB/s）

3.3.3 平均故障時(shí)間

• 預(yù)期系統(tǒng)無故障連續(xù)運(yùn)行的時(shí)間
• （30,000-800,000 小時(shí)，即 3.4-91 年）

3.4 磁盤塊存取的優(yōu)化

• 在主存儲(chǔ)器中對(duì)塊進(jìn)行緩沖以減少塊的讀寫次數(shù)
• 按柱面組織數(shù)據(jù)
• 使用多個(gè)磁盤
• 磁盤鏡像
• 磁盤臂調(diào)度——電梯算法
• 利用非易失性RAM作為寫緩沖
• 預(yù)讀和雙緩沖
• 日志磁盤

3.5 I/O調(diào)度器（Scheduler）

• 目標(biāo)
  • 減少尋道時(shí)間，讓旋轉(zhuǎn)一周讀取更多扇區(qū)
• 任務(wù)
  • 1.管理塊設(shè)備請(qǐng)求隊(duì)列
  • 2.分配I/O資源給請(qǐng)求
• 做法
  • 合并 + 排序

3.5.1 合并

• 同一或多個(gè)相鄰扇區(qū)的請(qǐng)求 ---合并--> 一次I/O
• 一次I/O對(duì)應(yīng)一條尋址指令
• 減少系統(tǒng)開銷和尋址次數(shù)

3.5.2 排序

• I/O請(qǐng)求按照扇區(qū)增長(zhǎng)序列
• Sorted Queue

3.5.3 linus電梯

簡(jiǎn)單的合并+排序
避免請(qǐng)求饑餓

• 檢測(cè)到隊(duì)列中有長(zhǎng)時(shí)間沒有被處理的請(qǐng)求，就暫時(shí)中止插入

缺點(diǎn)

• I/O調(diào)度器并沒有直接處理饑餓請(qǐng)求，沒有解決實(shí)質(zhì)問題

3.5.4 ANTICIPATORY(AS)

• 2.6.18 之前默認(rèn)的I/O調(diào)度器
  • 基于預(yù)測(cè)算法
• 處理完一個(gè)請(qǐng)求，不直接處理下一個(gè)請(qǐng)求，而是針對(duì)上一個(gè)請(qǐng)求的進(jìn)程等待片刻，如果該進(jìn)程發(fā)出一個(gè)與當(dāng)前扇區(qū)相同或相鄰的請(qǐng)求，則優(yōu)先處理
• 默認(rèn)等待6ms
• 如果系統(tǒng)存在大量相鄰扇區(qū)的請(qǐng)求，性能會(huì)很好
  • 當(dāng)有一個(gè)I/O發(fā)生時(shí)，若又有進(jìn)程請(qǐng)求I/O操作，則將產(chǎn)生一個(gè)默認(rèn)的6毫秒猜測(cè)時(shí)間，對(duì)下一個(gè)進(jìn)程請(qǐng)求的I/O進(jìn)行猜測(cè)。
  • 這對(duì)于隨機(jī)讀寫會(huì)造成比較大的延時(shí)，對(duì)數(shù)據(jù)庫(kù)應(yīng)用也很糟糕，而對(duì)于Web Server等則會(huì)表現(xiàn)得不錯(cuò)。
  • 這個(gè)算法可以簡(jiǎn)單理解為是面向低速磁盤的，猜測(cè)時(shí)間實(shí)際上是為了減少磁頭移動(dòng)的時(shí)間。

3.5.5 CFQ(COMPLETELY FAIR QUEUING)

• 2.6.18 之后默認(rèn)的I/O調(diào)度器
  • 每一個(gè)提交I/O請(qǐng)求的進(jìn)程都有一個(gè)自己?jiǎn)为?dú)的Sorted Queue
• 在一個(gè)時(shí)間片中，CFQ調(diào)度器選擇一個(gè)進(jìn)程，處理其I/O隊(duì)列
• 不是簡(jiǎn)單的輪詢，基于紅黑樹選擇進(jìn)程（進(jìn)程優(yōu)先級(jí)）
• 特點(diǎn)是保證各個(gè)進(jìn)程的I/O請(qǐng)求能被均衡處理
• 也有類似AS的等待機(jī)制
• 適合多進(jìn)程同時(shí)發(fā)出多I/O請(qǐng)求的狀況，CFQ對(duì)每一個(gè)進(jìn)程維護(hù)一個(gè)I/O隊(duì)列，各個(gè)進(jìn)程發(fā)來的I/O請(qǐng)求會(huì)被CFQ以輪詢方式處理，也就是對(duì)每一個(gè)I/O請(qǐng)求都是公平的。這使得CFQ很適合隨機(jī)讀寫的應(yīng)用（eg: OLTP DB）

3.5.6 DEADLINE

• 帶超時(shí)的調(diào)度算法
  • 除了CFQ本身具有的IO隊(duì)列之外，DEADLINE額外分別為讀IO和寫IO提供了FIFO隊(duì)列。
  • 讀FIFO隊(duì)列的最大等待時(shí)間為500ms，寫FIFO隊(duì)列的最大等待時(shí)間為5s。
  • 優(yōu)先級(jí)：FIFO(Read) > FIFO(Write) > CFQ
• 3個(gè)I/O Queue
  • Read Queue(default timeout: 500ms) FIFO
  • Write Queue(default timeout: 5000ms) FIFO
  • Sorted Queue
• 缺點(diǎn)
  • 當(dāng)系統(tǒng)存在大量順序請(qǐng)求時(shí)，可能導(dǎo)致請(qǐng)求無法被很好地排序，引發(fā)頻繁尋道，比較適合隨機(jī)訪問多、時(shí)效性高的場(chǎng)景
• 特點(diǎn)
  • 權(quán)衡了全局吞吐量和系統(tǒng)延遲
  • 避免寫?zhàn)囸I，當(dāng)寫?zhàn)囸I次數(shù)達(dá)到writes_starved，寫請(qǐng)求會(huì)被立即處理

3.5.7 NOOP(NO OPERATION)

• 最簡(jiǎn)單的I/O調(diào)度策略，本質(zhì)上就是先來先到服務(wù)FIFO，意思就是哪個(gè)進(jìn)程先請(qǐng)求I/O系統(tǒng)就先為哪個(gè)服務(wù)
• 面向隨機(jī)訪問設(shè)備（例如SSD）
• 對(duì)于SSD
  • 選擇NOOP還是DEADLINE？
  • DEADLINE平衡讀寫比例

3.5.8 比較

對(duì)于數(shù)據(jù)庫(kù)應(yīng)用

• CFQ綜合表現(xiàn)最好
• AS表現(xiàn)最差
• DEADLINE在DSS環(huán)境表現(xiàn)比CFQ更好一點(diǎn)

3.6 數(shù)據(jù)訪問流程

結(jié)合流程圖理解

3.7 服務(wù)器體系結(jié)構(gòu)

商用服務(wù)器大體可以分為三類

• 對(duì)稱多處理器結(jié)構(gòu)（SMP: Symmetric Multi-Processor）
• 非一致存儲(chǔ)訪問結(jié)構(gòu)（NUMP: Non-Uniform Memory Access）
• 海量并行處理結(jié)構(gòu)（MPP: Massive Parallel Proccessing）

4 大型數(shù)據(jù)庫(kù)系統(tǒng)應(yīng)用設(shè)計(jì)方法

……