文件與硬盤 I/O

硬盤

• 機械硬盤

• 主要部分

• 磁盤

• 高速旋轉

• 磁頭

• 磁頭臂

• 帶動磁頭在磁盤上面移動

• 讀寫

• 指定 (盤面、磁道，扇區)

• 驅動器移動磁頭臂至相對應位置 (盤面、磁道)落下磁頭

• 等到需要的扇區轉至磁頭位置後，讀寫資料

• 耗時因素

• 移動磁頭臂

• 落下磁頭

• 轉動磁盤

• 不利於數據

• 離散儲存在不同區域

• 隨機讀寫

• 讀寫性能取決於數據是否連續的儲存在一起

固態硬盤

• 高速的硬盤

• 沒有機械結構、全部為電子操作

• 讀寫性能沒有內存快

• 分配資料到不同芯片

• 控制器的複雜度高

• 連續儲存還是比離散儲存性能高

文件管理方式

• 文件系統將硬盤空間以 "塊" 為單位進行劃分

• 透過文件控制塊 FCB (File Control Block) 記錄每個文件佔據的硬盤數據塊

• 文件系統定義每個數據塊大小 (如 4K)

• 每個文件均有一個 FCB

• FCB 記錄此文件所佔據的所有數據塊編號

• Example - Linux  inode FCB

• 記錄

• 文件權限

• 所有者

• 修改時間

• 文件大小

• 數據塊硬盤地址索引

• inode 是固定結構 (固定大小)

• 15 個索引

• 12 個直接索引

• 直接指向數據塊

• 1 個一級索引

• 經由一層索引表指向真正數據塊

• 1 個二級索引

• 經由兩層索引表指向真正數據塊

• 1 個三級索引

• 經由三層索引表指向真正數據塊

• 單個文件大小

• 不超過 70 G

• 數據塊大小 4K

• 數據塊數量

• 12 + 256 + 256^2 + 256^3

提升數據庫資料讀寫性能

利用硬盤特性

• 連續讀寫能力強

• 隨機讀寫能力差

B 樹

• 是一排序樹、索引樹

• 一個硬碟數據塊可以儲存多組數據

• 數據塊還是離散儲存，所以性能還是比較差

• B 樹特性

• 保持鍵值有序，以順序遍歷

• 使用層次化的索引來最小化磁碟讀取

• 使用不完全填充的塊來加速插入和刪除

• 通過優雅的遍歷算法來保持索引平衡

• 一個 m 階的 B 樹是一個有以下屬性的樹：

• 每一個節點最多有 m 個子節點

• 每一個非葉子節點（除根節點）最少有 ⌈m/2⌉ 個子節點

• 如果根節點不是葉子節點，那麼它至少有兩個子節點

• 非葉子節點若擁有 k 個鍵，則有 k + 1 個子節點

• 有 k + 1 個指針指向子節點

• 所有的葉子節點都在同一層

LSM 樹 (Log Strutured-Merge Tree)

• 避免離散數據的查找

• 盡量順序的去讀寫

• 日誌結構為一個連續的數據結構

• 先於內存內建立一樹

• 當數據大於某個範圍後，將樹合併至外部

• 日誌方式為連續讀寫

提高文件併發讀寫能力

RAID 獨立硬盤冗餘陣列 (Redundant Array of Independent Drivers)

• 多個硬盤同時進行讀寫

• 將硬盤組成一個陣列，共同對操作系統提供服務

RAID 0 (Striped)

• 磁碟陣列由兩臺以上的磁碟所組成

• 在存放資料時，分段後分散儲存在這些磁碟中

• 磁碟陣列效能與硬碟的數量成正比

• 不具容錯的功能

• 當磁碟陣列中的一臺硬碟故障時，整個磁碟陣列上的 資料便會損毀

RAID 1 (Mirrored)

• 磁碟陣列必須由兩臺以上的磁碟組成，而且硬碟的數量必須為雙數臺

• RAID 控制器會將硬碟分為兩組

• 將資料同時寫入第一組硬碟與第二組硬碟

• 兩組硬碟上的資料完全相同

• 其中一組硬碟的資料屬於備份用途

RAID 10

• 磁碟陣列必須由四臺以上的雙數硬碟構成

RAID 0 + 1

• 資料先鏡像再分割

• 同組硬碟間遵守 RAID 0 規範

• 不同組間遵守 RAID 1 規範

RAID 1 +

• 資料先分割在鏡像

• 同組硬碟間遵守 RAID 1 規範

• 不同組間遵守 RAID 0 規範

RAID 5 (Parity RAID)

• 磁碟陣列至少需要三顆硬碟

• 資料分段，並計算奇偶校驗資訊

• 奇偶校驗資訊和相對應的資料分別儲存於不同的磁碟上

• 奇偶校驗資訊不存於某一台固定的硬碟上，分散在各個硬碟上

• 如 Ap、Bp、Cp、Dp

• 當 RAID5 的一個磁碟資料發生損壞後，可以利用剩下的資料和相應的奇偶校驗資訊去恢復被損壞的資料

• 可以理解為是 RAID 0 和 RAID 1 的折衷方案

RAID 6

• 磁碟陣列必須具備四顆以上的磁碟

• 與 RAID 5 相比，RAID 6 增加第二個獨立的奇偶校驗資訊塊

• 兩個獨立的奇偶系統使用不同的演算法，資料的可靠性非常高

• 如 Ap、Aq

• 任意兩顆磁碟同時失效時不會影響資料完整性

比較

分布式文件系統 HDFS

• 提供大量的 I/O 吞吐能力

• 將文件分片，存儲在多個服務器上

• 以服務器為單位，記錄分片

• 多個服務器可以併發的進行讀寫動作

• 服務器越多，性能提升也越快

簡介

• NameNode

• 作用如 Linux inode FCB

• 真正數據存儲於 DataNode 內

• 寫入時，NameNode 分配空閒 DataNode

• IP、端口、塊編號

• 將其記錄於 NameNode 中，並傳至客戶端

• 由客戶端對服務器寫入

• 客戶端可以併發對多個 DataNode 提出寫的操作

• 一個在 DataNode 的數據塊大小為 64 MB

• HDFS 不適合小文件存儲

• 浪費大量空間

如何保證數據可靠性

• 寫入 DataNode 後，自動複製至其他服務器

• 複製後，其他服務器會再複製一份出去

• 共三份相同數據的 DataNode 在系統中

• 跨機架進行複製

• 當路由器當機時，文件仍然可以正常讀寫

• DataNode 當機處理

• DataNode 平時會與 NameNode 進行心跳檢測

• 回報狀態報告

• 當 NameNode 長時間沒收到某個 DataNode 的心跳檢測時

• 斷定 DataNode 當機

• 默認所有存於此 DataNode 的數據塊丟失

• 數據塊複製會少於三分

• NameNode 收集所有在當機 DataNode 上的數據塊編號

• 所有丟失的數據塊

• NameNode 檢查這些數據塊還有在那些 DataNode 上有備份

• NameNode 通知那些 DataNode 針對當機 DataNode 上的數據塊進行複製

• 完成後，所有數據塊還是保持三份備份

常見數據結構與 Hash 表原理分析

衡量算法及數據結構優劣

指標

• 時間複雜度

• 不是計算程序運行的時間

• 運行時間與編程語言、操作系統與硬件相關

• 無法客觀衡量演算法本身的優劣

• 是計算演算法執行語句的次數

• 如查詢、比較等關鍵的次數

• 以 Big O 來標記

• O(2^n) 表示對 n 個數據處理，需要進行 2^n 次計算

• 多項式複雜度

• 如 O(1)、O(long(n))、O(n^a)

• 非多項式複雜度

• 如 O(a^n)、O(n!)

• 很多時候在計算機中是無解的

• 無法用非多項式複雜度的演算法，對數據進行計算

• 空間複雜度

• 演算法在運行過程中，臨時占用存儲空間大小的量度

• 也以 Big O 來標示

• O(n) 表示需要臨時存儲 n 個數據

• 演算法需在時間及空間複雜度之間取得平衡

數據結構

數組 (Array)

• 存在於內存中一塊連續的空間

• 數組中必須存放相同的數據類型

• 存放的數據長度(大小)必須一樣

• 每一個數據有固定長度的空間，才能達到隨機快速讀寫

• 利用指標與下標即可計算

• 重要特性

• 隨機快速讀寫

• 以數組的下標訪問數據

• a[0]、a[1]....

• 時間複雜度為 O(1)

• 連續空間、數據長度一樣

• 增刪元素

• 增加需要另外找一塊連續空間

• 需要對數組所有元素進行移動

• 時間複雜度 O(n)

鏈表 (List)

• 使用零散的內存空間存儲數據

• 由頭指標指向鏈表第一個元素

• 鏈表每一個元素包含

• 存儲的數據

• 長度不要求一樣

• 指向下一個元素的內存地址指標

• 最後一個元素指向 一個空 (null)

• 查找一個數據，只能遍歷整個鏈表

• 時間複雜度 O(n)

• 刪除、增加元素時間比數組好

• 修改相關元素的指標即可

• 時間複雜度 O(1)

數組與鏈表結合

• 實現快速查找和快速增刪

• 快速查找 - 數組

• 存放分類查找的鏈表

• 快速增刪 - 鏈表

• 存放真正的數據

哈希表 (Hash Table)

• 實現快速訪問數據及快速增刪數據

• 使用數組-快速查找

• 利用 Key 計算出數組下標

• 計算 hash code

• hash code 以數組長度取模

• hash 衝突

• 兩數據 hash 取模後衝突 (下標相同)

• 利用鏈表存儲衝突的數據

• 訪問、增刪時間複雜度 O(1)

• hash 攻擊

• 知道 hash 表 長度

• 故意找大量相同 hash code 取模相同的數據

• 使存儲 hash 衝突的鏈表，變得很長

• 計算機資源被 hash 表內的鏈表搜尋耗光

堆棧 (Stack)

• 可用數組或鏈表實作

• 數組、鏈表稱為線性表

• 線性表每一個元素

• 只有一個前驅

• 只有一個後繼

• "棧" 就是在線性表上增加操作限制

• 後進先出

• 最後加入的數據，在刪除時必須先刪除

• 應用

• 線程調用棧

• 棧頂元素一定是當前執行函數的棧幀

• g 函數與 f 函數個別的 x 變量，存於不同的棧幀，故不會混淆

對列 (Queue)

• 對列也是操作受限的線性表

• 先進先出

• 應用

• 生產者、消費者

• 阻塞等待的線程被放入對列中

• 公平鎖

• 搜尋最短路徑

• 將起點入對列

• 每當元素出對列時，檢查是否為終點

• 若否，則將相連接的路徑加入對列中

• 反覆直到到達終點

樹

• 非線性表

• 節點

• 根節點

• 樹的根，沒有父節點

• 中間節點

• 彼此間有父、子節點關係

• 由父節點可以找到子節點，或相反

• 葉節點

• 沒有子節點

二叉排序樹

• 遞歸定義

• 左子樹上所有節點的值均小於它根節點的值

• 右子樹上所有節點的值均大於它跟節點的值

• 左、右兩樹也分別為二叉排序樹

• 查找、增刪時間複雜度 O(long(n))

• 二叉排序樹可能退化成鏈表

• 不平衡二叉排序樹

• 在數據不斷的增刪過程中，逐漸形成

• 查找時間複雜度退化成 O(n)

平衡二叉排序樹

• 從任何一個節點出發，左右子樹深度之差的絕對值不超過 1

• 深度 - 由根節點出發，一直到葉節點最長的路徑

• 左右子樹仍然為平衡二叉排序樹

• 增刪元素，可透過旋轉(左、右旋)二叉樹恢復平衡

• 插入元素，最多之需要兩次旋轉就會恢復平衡

• 刪除時，需要維護從被刪節點到根節點路徑上所有節點的平衡性

• 時間複雜度 O(long(n))

紅黑樹

• 定義

• 每個節點只有兩種顏色 - 紅色、黑色

• 根節點是黑色

• 每個葉節點 (null) 都是黑色的空節點

• 從根節點到葉節點，不會出現兩個連續的紅色節點

• 黑色節點則可以出現

• 從任何一個節點出發到葉節點，路徑上有相同數目的黑色節點

• 增刪時的旋轉

• 紅黑數通過染色和旋轉，保持紅黑樹滿足定義

• 與平衡二叉樹的比較

• 紅黑樹最多只需要 3 次旋轉，就會重新達成紅黑平衡

• 時間複雜度為 O(1)

• 大量增刪的情況下，紅黑樹效率更高

• 紅黑樹平衡性不如平衡二叉樹

• 查找效率會差一些

跳表

• 實現上比較簡單

• 實作

• 先有一個排序過的鏈表

• 每隔幾個元素用另一個類似樹的鏈表指向元素 (一級)

• 針對一級，每隔幾個元素用類素樹的鏈表指向 (二級)

• 可依需求反覆

• 查找

• 由最上級開始查找

• 若查找的元素介於最大級兩個元素間，則往下一級查找

• 反覆直到找到元素

• 增刪

• 查找到適當位置

• 進行鏈表增刪

• 更新跳表

• 增加或刪除每一級的元素

• 時間複雜度 O(long(n))

• 空間複雜度高

• 很多數據是冗餘的

經典算法

• 演算法趨勢

• 對資源越來越不重視 (內存很大，所以不重視)

• 對性能要求越來越高

• 對編程或程序維護的簡單性和複雜性要求越來越高

• 人的資源最寶貴

• 計算機資源次之

窮舉算法

• 將所有可能條件都列出來

• 在所有可能性中找最優的解

• 暴力、但在窮舉數目不多時很有效

遞歸算法

• 函式自己調用自己

• 如 Quick Sort

• 時間複雜度

• 隨機數組 - O( n * long(n))

• 已排序數組 - O(n^2)

• 包含

• 基線條件

• 遞歸退出條件

• 如果沒有，則會無窮遞歸下去，直到程序崩潰

• stack overflow : 堆棧溢出異常

• 遞歸條件

• 在此呼叫自己

貪心算法

說明

• 對問題求解時，總是做出當前看起來最好的選擇

• 不從整體最優上加以考慮

• 算法達到的是，某種意義上的局部最優解

• 由多個最優解，得到一個全局解

解背包問題

• 將那些商品放入 4 磅背包才能收益最大化

貪心算法

• 找到一個可以放進背包且收益最大者

• 音響

• 還可以再放?

• 不行，得解

• 非全局最優

• 全局最優: 筆記電腦 + 吉他

迪傑斯特拉算法 (最快路徑)

核心

• 找到起點到每個節點的最快路徑

演算法

• 找出 "最便宜" 的節點

• 可以最短時間內到達的節點

• 更新該節點鄰居的開銷

• 檢查是否有前往鄰居更短的路徑

• 如果有，更新其開銷

• 並更新該節點為到鄰居最短路徑的節節點

• 重複這個過程，直到所有節點都做過了

• 計算最終路徑

例子

• 第一步

• 計算由起點到各鄰居點 (A、B)的開銷

• 並記錄此開銷是由起點而來

• 第二步

• 計算由 B 點到各鄰居點(A、終點)的開銷

• 由 B 到 A 開銷為 5，比現存(6)小，故更新 A 的開銷

• 並記錄由 B 點而來

• 終點也記錄開銷，由 B 點而來

• 第三步

• 計算由 A 點到各鄰居點(僅有終點)的開銷

• 由目前的 A 到終點開銷為 6，比現存(7)小，故更新終點開銷

• 並記錄由 A 點來

• 最終

• 根據表格回推，最短路徑為

• 起點 -> B -> A -> 終點

• 其開銷為 6

動態規劃

• 找到合適的角度，將所求解的目標值在某個維度上展開

• 將一個大問題，拆解為若干小問題

• 從小問題的最優解，尋找大問題的最優解

• 可找全局最優，但不像窮舉法列出所有可能

動態規劃解背包問題

第一步

• 每個動態規劃都由一個表格開始

• 展開所有可能

第二步

• 放入吉他的狀況

• 吉他 1 磅故可以放入所有磅數的背包

第三步

• 放入音響的狀況

• 音響 4 磅，所以僅能放入 4 磅背包

• 收益(3000) 比吉他高，故選音響放入

• 其他磅數背包，目前最優也是吉他，故全部填入吉他

第四步

• 填入筆記電腦的狀況

• 筆記電腦 3 磅，故先放入 3 磅背包

• 收益(2000) 比吉他高，故選筆記電腦放入

• 1、2 磅背包也僅能放吉他

• 但 4 磅背包

• 可以選擇由行直接下來 - 3000

• 或由列選擇 3 + 1 搭配 - 3500

最終

• 由列選擇 3 + 1 搭配收益較高，所以為最後結果

注意

• 二維表格越往下，越是當前(行)最優解

• 根據歷史做出選擇

• 二維表格越往右，也是當前(列)最優解

• 根據歷史做出選擇

• 最終答案需考慮行的最優解與列的最優解

遺傳算法 (Genetic Algorithm，GA)

• 模擬進化論自然選擇和遺傳學機理的生物進化過程的計算模型

• 模擬自然進化過程，搜索最優解的方法

• 得出來的解並非最優解

說明

• 列出群體中所有個體

• 利用隨機化技術指導一個被編碼的參數空間進行高效搜索

• 遺傳操作

• 選擇

• 交叉

• 變異

• 核心內容

• 參數編碼

• 初始群體設定

• 適應度函數的設計

• 遺傳操作設計

• 控制參數設定

流程

遺傳算法解背包問題

• 80 公斤背包裝那些物品價值最大

編碼

• 基因組合: 染色體

初始化群體選擇

• 隨機產生

• 也可以人為或算法選擇

評估群體中，個體適應度

適應度函數 -> 商品總價值

• 算出初始群體各個總價值

控制參數 -> 總重量不得超過 80 公斤

• 算出初始群體各個總重量

• 染色體 101011 超出重量需淘汰

選擇

• 在剩下的染色體中選擇

• 選擇可以被遺傳下去的染色體

• 選擇繁殖次數

算法

• 輪盤賭選擇 (Roulette Wheel Selection)

• 回放式隨機採樣方法

• 每個染色體進入下一代的機率，等於適應度值與整體適應度值合的比例

• 隨機競爭選擇 (Stochastic Tournament)

• 每次按輪盤賭選擇一對個體

• 讓這兩個個體進行競爭

• 適應度高的被選中

• 反覆直到選滿為止

• 均勻排序

• 對群體中所有個體按適應度大小排序

• 基於排序，分配各個個體被選中的機率

選擇結果

• 101010 和 010101

• 各繁殖兩次

交叉遺傳

• 產生下一代 - 染色體交叉遺傳

• 交叉點 3

• 101010 -> 101，010

• 010101 -> 010 ，101

• 交叉點 4

• 101010 -> 1010，10

• 010101 -> 0101，01

變異

• 在遺傳過程中進行基因突變

• 選擇某幾個， 0 變 1 ，1 變 0

• 得到基因突變染色體

演化

• 循環迭代

• 如果連續幾代遺傳都沒有出現更強的染色體 (價值總和更大)，算法收斂

• 當前最大價值的染色體為最終解

網路通信基本原理與性能優化

Web 請求網路通信歷程

• 客戶端由域名 (domain name) 發起請求

• 域名非網路通信一部分

• 經由 DNS 服務器進行域名解析

• 解析出 IP address

• 不會每一次請求均要求域名解析

• 超過時效後，才會再一次請求解析

• 請求可能發給

• CDN

• 有緩存，直接返回

• 無緩存，經請求發至負載均衡服務器

• 數據中心的負載均衡服務器

• 動態內容直接送至負載均衡服務器

• 負載均衡服務器分發給多個反向代理服務器

• 有緩存，直接返回

• 前端緩存

• 靜態內容緩存

• 無緩存，繼續向下發送請求

• 反向代理服務器透過內部的負載均衡服務器，經請求發給網關服務器

• 網關服務器將請求發給某個微服務應用服務器

• 使用微服務的 RPC 通信

• 微服務應用服務器

• 調用

• 緩存服務器

• 數據庫服務器

• 底層資源服務

• 進行

• 數據組合

• 業務邏輯處理

• 完成請求後，反向返回至客戶端

網路通信模型

• 通信標準

• 不同設備間通信

• 保證數據傳輸正確性

• 遵循同樣的通信標準，保證數據通信協議的完成

• 多層模型達成通訊協議更好復用性

OSI 七層模型

物理層

• 處理不同傳輸介質的訊號、數據格式

• 光纖、無線、電纜、雙絞線

數據鏈路層

• 幀

• 將傳輸數據分包成一段段

• 以 "幀" 為單位發送、接受數據

• 進行高效傳輸

• 保證數據可靠和正確性

• 網卡的位址 (MAC address)

• 真正物理上存在的地址

網路層

• 數據由發送端至接收端需經多次轉換

• 保證轉換的正確性

• 選擇哪一些中間節點

傳輸層

• 連接兩端應用程序進程，進行通信

• 解決程序識別問題

• 處理服務器監聽的端口

會話層、表示層、應用層，均需應用程序自己處理

• 如 HTTP 協議便會處理這三層

通信協議

• 主機間通信，在不同層，使用不同的協議

• 傳送

• 上層調用下一層協議

• 下一層協議用自己的 packet header 封裝上層的資料

• 在由最下層(物理層 or 網路鏈路層)分包成數據幀包傳送出去

• 接收

• 接收端重組數據幀包後，往上層送

• 下層解析自己的 packet header 做相應處理後，將上一層資料往上一層送

• 網路數據包格式

TCP / IP 通信協議

物理層

• 負責數據在不同的通信線路上的物理傳輸

鏈路層

• 定義 "幀" 的大小

• 最大傳輸單位

• 將數據封裝成 "數據幀" 後交由物理層進行傳輸

• 以 "幀" 為單位進行通信

• 進行數據校驗

• 進行流量控制

• 將封裝好的 "幀" 添加一個 "幀頭"

• 發送者與接收者的 MAC 地址

• MAC 地址

• 網卡的設備標識符

• 是唯一的地址，網卡出廠時便設定

• 確保數據送達正確的目標機器

• 應用 - 鏈路層負載均衡

• 負載均衡服務器與應用服務器共享一個虛擬 IP 地址

• 當請求到達負載均衡服務器

• 改變目的 MAC 地址

• 在局網內的服務器辨識 MAC 地址

• 是服務器的 MAC - 接收處理後，網上一層送

• 不是服務器的 MAC - 直接丟棄

• 網路通信利用 IP 地址進行路由選擇

• 更改 MAC 不影響

• 在局網內的 IP (負載、服務集群) 都一樣

• 請求返回可以直接路由至用戶端，不必再經由負載均衡服務器

• IP 地址沒變更，所以可以經由原來的 TCP 連接的路由路徑返回請求

• 網路層的封包不變，僅變更鏈路層的目標 MAC 地址

• 響應返回直接送至用戶端，減少負載均衡服務器負擔

• 性能比網路層負載均衡好

網路層 (IP 協議)

• 根據 IP 地址訪問目標服務器

• 請求經營運服務商的交換機，交換機根據 IP 地址進行路由轉發

• 中間會經過很多轉發節點

• 網路層的 IP 數據包，必須小於最大傳輸單元

• 因為網路層數據需要交給鏈路層處理

• 鏈路層定義最大傳輸單元

• 數據包也有一個網路層的封包頭

• 主要記載發送者和接受者的 IP 地址

• IP 協議不是一個可靠的通信協議

• 不會建立穩定的通信鏈路

• 不會確保數據一定送達

• 應用 - 網路層負載均衡

• 負載均衡服務器透過修改 IP 地址進行請求轉發

• 修改

• 來源 IP: 用戶 IP -> 負載均衡服務器內部 IP

• 目的 IP: 負載均衡服務器外部 IP -> 應用服務器內部 IP

• 修改後重新發送請求

• 請求重新進行路由選擇

• 服務器處理請求後，響應返回需再經負載均衡服務器轉發

• 修改

• 來源 IP: 應用服務器內部 IP -> 負載均衡服務器外部 IP

• 目的 IP: 負載均衡服務器內部 IP -> 用戶 IP

• 復用用戶請求到負載均衡服務器的 IP 路徑

傳輸層 (TCP 協議)

• 一種面向連接的、可靠的、基於字節流的傳輸層協議

• 確保協議可靠性和強壯性的重要機制

• 使用序號

• 對收到的 TCP 報文進行排序與重複數據檢測

• 無錯傳輸

• 使用校驗和檢測報文段的錯誤

• 使用確認和計時器

• 檢測和糾正丟包或延時

• 流量控制

• 避免發送過快而使接收方來不及完全收下

• 壅塞控制

• 發送方根據網路承載情況控制分組發送量，以獲得高性能

• 同時避免壅塞崩潰，緩解網路堵塞的情況

• 丟失包重傳

• 三次握手建立連接

• 服務器監聽通信端口，等待其他程序來連結

• 先啟動等待通信的是服務器

• 發起通信的是客戶端

• 一次握手

• APP 請求建立連線

• APP 發送 SYN = 1，SEQ = X

• X 為隨機數

• 二次握手

• 服務器應答，同意建立連線

• 應答 SYN = 1, ACK = X + 1，SEQ = Y

• APP 收到後

• 檢查 ACK 為自己發送的 SEQ (X) + 1

• 三次握手

• 確認建立連接

• APP 發送 ACK = Y + 1，SEQ = Z

• 服務器收到後

• 檢查 ACK 為自己發送的 SEQ (Y)+ 1+ 1

• 至此，APP 和服務器建立 TCP 連接，可以進行數據傳輸

• 四次揮手關閉連接

• 保證穩定的鏈路關閉

• 可以由任何一方(服務器或客戶端)發起

• 一次揮手

• 主動方發送 FIN = 1，SEQ = M

• 主動方進入 FIN_WAIT_1 狀態

• 二次揮手

• 被動方收到後，回復 ACK = 1，SEQ = M + 1

• 被動方進入 CLOSE_WAIT 狀態

• 主動方收到 ACK，檢查無誤後，進入 FIN_WAIT_2 狀態

• 三次揮手

• 被動方發送 FIN = 1，SEQ = N

• 被動方進入 LAST_WAIT 狀態

• 主動發收到後，進入 TIME_WAIT 狀態

• 四次揮手

• 主動方發送 ACK = 1，SEQ = N + 1

• 主動方進入 CLOSE 狀態

• 被動方收到 ACK，檢查無誤後，也進入 CLOSE 狀態

• 完成鏈路關閉

應用層

• 兩應用程序可定義自己的應用層協議

• 但僅這兩程序認得

• 無法大量應用

HTTP 協議

• 互聯網應用需要在全球範圍內提供服務

• 將全球應用和全球用戶連繫在一起

• 需要一個統一的應用層協議，即 HTTP 協議

HTTP 請求

7 種方法

• GET

• 只讀請求

• 不應該產生副作用

• 不發生任何狀態改變

• HEAD

• 與 GET 同

• 但只返回響應頭

• POST

• 提交請求

• 真正是一個寫操作

• 資源新增

• PUT

• 上傳請求

• 更新(資源存在)或新增(資源不存在)

• DELETE

• 刪除 URL 標識的資源

• TRACE

• 回顯服務器收到的請求

• 用於測試或診斷

• OPTIONS

• 請求服務器返回支持的所有 HTTP 請求方法

• 測試服務器是否正常

HTTP 響應

5 種狀態

• 1XX 消息

• 請求已被服務器接收

• 繼續處理

• 2XX 成功

• 請求已成功被服務器接收、理解、並接受

• 3XX 重定向

• 需要後續操作才能完成這一個請求

• 4XX 請求錯誤

• 請求含有語法錯誤或無法被執行

• 5XX 服務器錯誤

• 服務器在處理某個正確請求時發生錯誤

HTTP 協議版本

• 版本的演進主要解決性能問題

HTTP/1.0

• 每一次請求 / 響應都會創建新的 TCP 連接

• 每一次 TCP 連接資源開銷大

• 經三次握手

• 請求 / 響應

• 經四次揮手

HTTP/1.1

• 目前用最多的版本

• 實現 TPC 連接復用

• 分攤初始連接成本

• 分攤多個請求緩慢啟動成本

• 但任意時點，每個連接只能執行一次請求 / 響應

• 所有請求需要串行(一個接一個)執行

• 問題

• 網站資源(CSS，JavaScript、圖像等)不斷增長

• 網頁呈現需要越來越多並發性

• 獲得並發性唯一方法 - 使用多個 TCP 連接

HTTP/2.0

• 引入 HTTP "流" 的概念

• 可以併發不童的 HTTP 請求到同一個 TCP 連接

• 可以通過同一個連接同時傳輸多個請求 / 響應

• 問題

• 通常請求很短，並發不會產生問題，但響應時的數據量大，會爭奪同一 TCP 連接

• TCP 不理解 HTTP 流

• 多個 HTTP 請求復用一個 TCP 連接

• 前面的請求 / 響應沒有處理完，後面的請求/響應也無法處理

• 出現隊頭堵塞現象

• 數據若丟包，在重傳完成前，後面的請求/響應會被堵塞

HTTP Over QUIC

• 使用 UDP 數據包

• 由 QUIC 傳輸層處理保證數據傳輸的可靠性

• 多個 QUIC 流共享一個 QUIC 連接

非阻塞網路 I/O

網路編程

• 不需要關心傳輸層及其以下的各層通信協議

• 由操作系統提供

• 利用操作系統提供的網路編程接口進行編程

• 封裝傳輸層即其下個層的通訊協議

BIO (Blocking I/O，阻塞式 I/O)

• 進行 I/O 操作時，用戶線程會一直阻塞，直到讀 / 寫操作完成

• 內核處理 socket 接收數據過程

• 網路數據到達網卡

• 網卡解析協議數據

• 網卡產生中斷

• CPU 執行中斷服務程序，將數據寫入接收緩衝區中

• 操作系統喚醒等待隊列的線程處理接收的數據

• 處理完若無後續數據，線程會再度進入等待隊列

• 線程大部分會在阻塞狀態，因為網路傳輸比較慢

• 編程

• 服務器 - 客戶端

• A - 客戶端

• B - 服務器

• 操作系統提供 Socket

• accept()

• 接受 A 連接

• socket.getInputStream()

• 取得 A 請求

• socket.getOutputStream()

• 返回響應

• 高並發處理

• 多線程服務器

• 每個客戶端由一個 socket 處理

• 每一個 socket 在一個線程執行

• socket 隨時可能會被阻塞

• 讀/寫都會堵塞

• 阻塞式編程方式

• 線程數有限，可處理的並發數也就有限

• 線程池服務器

• 利用線程池可以提高性能，但也有限

Non-Blocking I/O (非阻塞 I/O)

• I/O 操作立即返回，線程不會阻塞等待

• 非阻塞 read 操作

• socket 接收緩衝區有數據，讀取

• 不保證數據被完整讀取

• 可能需要多次讀取

• socket 接收緩衝區沒有數據

• 返回失敗

• 不會等待

• 非阻塞 write 操作

• socket 發送緩衝區滿

• 返回失敗

• 不會等待

• socket 發送緩衝區不滿，寫入

• 不保證一次性全部寫入

• 可能需要多次寫入

• 內核處理過程

• 有 select、poll、epoll 三種

• Select (poll) 管理下，Read 過程

• 當有 socket 事件發生時，通知 selector

• selector 不知道哪個 socket 發生事件

• 遍尋所有 socket 以找到發生事件的 socket

• epoll 管理下，Read 過程

• 需要操作系統本身支持

• 提供一個 eventpoll 列表

• 當 socket 有事件發生，會將事件發至 eventpoll 列表

• 事件也會標明 socket 作用

• 編程

• 每一個客戶端建立一個 Channel

• selector 選擇器

• 監聽所有 channel

• 服務器 channel

• 是否有新的連接

• 客戶端 channel

• Read/Write

• 在 Buffer 上讀寫數據

Java 實現

• Java IO

• block

• ServerSocket::accept()

• InputStream::read(...)

• OutputStream::write(...)

• 為每一個 socket，new 一個線程

• Java NIO

• block

• Selector::select()

• non-block

• ServerSocketChannel::accept()

• SocketChannel::read(...)

• SocketChannel::write(...)

• 主線程就可以處理所有的 socket