---
# System prepended metadata

title: 進階資料庫

---

# 進階資料庫

期中考範圍
ch10 17 18 hw1
可以帶一張A4正反都可以抄

protocol一定會考
重點在10(跟作業有關的一定會出)&18(所有的protocol都很重要)
17的transaction很重要
手冊＆作業1有關的會考

---

## ch8 Complex Data Types
### Semi-Structured Data（半結構化資料）

傳統的關聯式資料庫
- 有固定的 attribute（結構化）
- 裡面的值是 atomic data types（不可分割，裡面不能有集合）
    e.g. 看電影、聽音樂，這就是集合，因為有兩個興趣

半結構
- schema 可以經常變動
- 可以存集合的資料

--
#### Semi-Structured Data 的特性
- **Flexible schema**
    - **Wide column**
        每個資料可以有不同的 attribute，隨時增減
    - **Sparse column**
        每個資料可以有很多 attribute，但是是要固定的
        一開始就把所有可能的 attr 列好
- **Multivalued data type**
    - **Sets, multisets**
        e.g. {'basketball', 'La Liga', 'cooking', 'anime', 'jazz'}
    - **Key-value map**
        e.g. {(brand, Apple), (ID, MacBook Air), (size, 13), (color, silver)}
- Arryas
    原本是 (時間, 資料)，但時間是連續的所以省略時間的部分
    [5, 8, 9, 11] instead of {(1,5), (2, 8), (3, 9), (4, 11)}
- Multi-valued attribute types
    允許 non 第一正規化
- Array database
    支援一些對陣列的特別處理
    e.g. compressed storage

--
### Nested&Hierarchical Data Types
其實巢狀跟階層的概念是一樣的
把巢狀畫成 tree，就變成階層了
- **JSON**
    ```json
    {
        "ID": "22222",
        "name": {
            "firstname": "Albert", //name.firstname
            "lastname": "Einstein"
        },
        "deptname": "Physics",
        "children": [
            {"firstname": "Hans", "lastname": "Einstein" },
            {"firstname": "Eduard", "lastname": "Einstein" }
        ]
    } 
    ```
    JSON 壓縮之後稱為 BSON(Binary Json)
- **XML**
    ```xml
    <purchase_order>
        <identifier> P-101 </identifier> # /purchase_order/identifier
        <purchaser>
            <name> Cray Z. Coyote </name>
            <address> Route 66, Mesa Flats, Arizona 86047, USA </address>
        </purchaser>
        <supplier>
            <name> Acme Supplies </name>
            <address> 1 Broadway, New York, NY, USA </address>
        </supplier>
        <itemlist>
            <item>
                <identifier> RS1 </identifier>      
                <description> Atom powered rocket sled </description>
                <quantity> 2 </quantity>
                <price> 199.95 </price>        
            </item>
            <item>...</item>
        </itemlist>
        <total cost> 429.85 </total cost>            
    </purchase_order>
    ```
- **RDF(Resource Description Formnat)**
    AI的知識表達，就是一堆triple
    e.g.  (Washington-DC, population, 6,200,000)
    
    - 圖形表示法
        ![](https://i.imgur.com/8ooQnfI.png)
        橢圓：物件（主詞或受詞）
        長方形：屬性值
        線：屬性 或 關聯
        ps. ER圖 -> 集合間的關係，這個 -> 物件間的關係
        
    - triple 表示法
        用 (主詞, 屬性 or 關聯, 受詞) 來表示
        ![](https://i.imgur.com/8mfEiiB.png)

        - Querying RDF: **SPARQL** ==（期中會考一題！我猜是看圖）==
            ``` 
            ?cid title "Intro. to Computer Science"
            //?cid: 代表想知道的東西，也就是 CS-101
            
            ==?cid== title "Intro. to Computer Science"
            ?sid sec_course ==?cid==
            //?cid就是 CS-101，?sid就是sec1
            
            select ?name where {
                ?cid title "Intro. to Computer Science" .                     ?sid sec_course ?cid .
                ?id takes ?sid .
                ?id name ?name .
            }
            //?name 是Zhang
            
            ```
### Object Orientation
1. Object-relational data 提供更多的型態以表達物件的概念
2. 程式語言＆資料庫的型態、語法很可能不對應

-> 以前想要建立 OO 的 資料庫

- Object-Relational Database System
    - user-defined types ==（感覺是重點）==
        ```
        create type Person(
            ID varchar(20) primary key,
            name varchar(20),
            address varchar(20))  ref from(ID);  /* More on this later */
            create table people of Person; // people 這個資料表 裡面的資料都是 Person 這個型態
        ```
        比較不一樣的是 ==of Person== !!!
        她的概念就是用 Person 這個 type 來對應物件
        用 ref 來區別物件，可以用某個屬性去判斷(像是 primary key)，也可以讓系統自己產生
        
    - table types
        ```
        create type interest as table (
            topic varchar(20),
            degree_of_interest int);
            
        create table users (
            ID varchar(20),
            name varchar(20),
            interests interest); 
        ```
        有點巢狀的感覺
        
    - Reference Types
        ```
        create type Person(
            ID varchar(20) primary key,
            name varchar(20),
            address varchar(20))
            ref from(ID); 
            /* PS: reference 也可以是系統自動 生 產*/
            
            create table people of Person; 
            
            create type Department (
                dept_name varchar(20),
                head ref(Person) scope people); // 存著 Person 型態的 ref，範圍則是 people 這個表格
                
            create table departments of Department
            insert into departments values ('CS', '12345’)
        ```
        
        查詢範例
        ```
        select head->name, head->address
        from departments; 
        ```
        ![](https://i.imgur.com/bgKy58s.png)
        
    - Object-Relational Mapping
        程式語言對應資料庫的型態

### Textual Data（文字資料，沒有結構）
沒辦法下什麼查詢 -> 關鍵字查詢

[TF-IDF 概念（之前有筆記了）](https://www.notion.so/TF-IDF-ae3438571b9b4b518f85285b96f6f2e4)

[Precision, Recall（請去補筆記）](https://www.notion.so/Evaluation-f269fbd9cf1d4d74a16127c2b4abf907)

### Spatial Data

---
## ch10 Big Data

### 前言
* **Big Data的特性**
    * **Volume（大量）**
        資料儲存的量大
    * **Velocity（速度快）**
        新增資料的速度
    * **Variety（多類別）**
        資料類型廣泛，不像RDB(relational database)有固定的attribute
        
    以上是3V
    
    * Veracity（正確性）
        資料是否正確
    * Value（價值）
        資料多，但哪些才是有價值的
        
    以上是5V
        
* **關於Big Data**
    * Transcation processing systems
        * 有些應用程式會達到量大速度不變 而犧牲ACID（ch17會講）
    * Query processing systems
        * 資料量大速度也不會變慢
        * 需支援non-relation的資料


### Big Data的儲存方式（Big Data Storage Systems）

儲存Big Data的方法有四種
（老師說：第四個看看就好，是最早的）

* **Distributed File Systems（分散式的檔案系統）**
    把資料放在很多機器上
    一個node = 一個電腦
    E.g. 10K nodes, 100 million files, 10PB(1024TB)
    
    用的是便宜的電腦，但是怕電腦當機資料就不見了
    所以資料會重複儲存，要能夠偵測是否有資料掰了
    
    * **GFS(Google File Systems)**
    
    * **HDFS(Hadoop File Systems)**
        檔案會被切成很多block
        每個block的大小約為64MB
        block也會複製到不同的DataNodes
        
        * **`NameNode`**
            集中管理資料的地方
            所有的request(新增)都需經過NameNode
            紀錄的資料包含：
            * **metadata**(描述資料的資料)
            * **filename - Block IDs**
                檔案名稱與對應的block ids
                也就是檔案放在哪個block id
            * **Block IDs - DataNodes**
                block ids與對應的DataNodes
                （也包含複製品，因為單點脆弱，資料需複製多份）
        * **`BackupNode`**
            就是NameNode的複製品
        * **`Client`**
            直接透過DataNodes得到真正的記憶體位置＆能夠直接存取資料
        * **`DataNodes`**
            會紀錄block ids與對應的記憶體位置
            * 讀DataNode的資料
                HDFS server 會回傳block id
            * 寫DataNode的資料
                HDFS server 會創建新的block
                並且分配至多台電腦上（單點脆弱）
    
    **範例：**
    Client：（跟NameNode）我要讀xxx(file name)
    NameNode：他在ooo(block ID)
    Client：（跟NameNode）我要xxx的DataNodes
    NameNode：他在zzz(DataNodes)
    Client:（跟DataNode zzz）我要讀ooo
    DataNode：回傳真正的記憶體位置
    //使用者不需要知道，直接去問
    
    
    資料有兩種
    檔案很小但很多個
    檔案很大但很少個
    此方法可接受約million個大檔案
    
    
    ![](https://i.imgur.com/VoiASeW.png)
    
* **Sharding（碎片式的檔案系統）**
    
    把資料切開來放在很多資料庫
    
    但是該怎麼切？
    shard keys：
        key value的範圍在1~10000的放在DB1
        key value的範圍在100001~20000的放在DB2
    //application自己要知道(自己紀錄)，要自己去找
    
    - **優點**：
        * 量很大都不會慢，到billion也沒問題
    - **缺點**：
        * Not transparent（不透明）
            application需要知道底層怎麼存資料
            （必須自己處理查詢路由、跨多個數據庫的查詢）
        * load balancing不容易做（資料量>儲存量）
            當DB1的資料要放到DB2
            application去DB1找時 就會找不到
            整個程式就要重寫
        * DB越多 失敗機率越高
            同時application需要備份DB
    
* **Key Value Storage Systems**

    也會切資料，切成非常大量的小資料(KB~MB)
    查詢是由==系統==來找到正確的機器（Sharding是要自己找）
    也有備份，修改時兩邊都要改到(consistent一致性)
    
    每筆資料都包含一個key跟一個value
    儲存的形式包含
    * uninterpreted bytes
        value是二進位
    * wide-table（寬表格）
        value裡面可以包含很多屬性（彈性的RDB）
        //attribute不需定義死
        //filtering：可以根據wide-table裡的attribute來查詢
    * json
        就是json, ex. mongo DB
    
        ``` json
        {
        "ID": "22222",
        "name": 
            {
            "firstname: "Albert",
             "lastname: "Einstein"
            },
        "deptname": "Physics",
        "children":
            [
                { "firstname": "Hans", "lastname": "Einstein" },
                { "firstname": "Eduard", "lastname": "Einstein" }
            ]
        }
        ```
    put(key, val) 放新的進去
    get(key) 拿
    delete(key) 刪
    execute(key, operation, parameters)
    
    功能簡單化，讓資料量大的時候速度也不會太慢
    
* **parallel and distributed Database**
    用於多台機器，但規模較小，約10~100台
    一樣有備份但通常出問題是關掉重開


    CAP = Consistency + Availability + network Partitions
    CAP定理：若network Partitions存在，則不保證Consistency&Availability
    
    * **Consistency（一致性）**
        每個複製品都應該要有相同的值
    * **Availability（可用性）**
        即使部分機器發生故障 系統仍可運作
        （一個資料壞掉，還有他的複製品）
    * **network Partitions**
        網路可以分成兩個or多個部分
        彼此間不可互相通訊

## ch17

### Transaction Concept

transaction就是一串動作

* 轉帳的範例
    * 用sql表示
        ``` sql 
        /* account有這三個東西 */
        account (account_number, branch_name, balance)

        update account
        set balance = balance-50
        where account_number = 'A';

        update account
        set balance = balance+50
        where account_number = 'B';
        ```
    * 用非sql表示
        `接下來不會看到sql 因為太冗長`
        
        ```
        read(A)
        //把資料(data item A)的值 塞進某個變數(A)
        //data item ＆ 變數 都稱之為A
        
        A := A-50
        write(A)
        //跟read相反

        read(B)
        B := B+50
        write(B)
        ```

* 兩個主要的問題
    * 各種故障（ex. 硬體or系統）
    * 多個transaction同時執行該怎麼排？

### **ACID（由下面四個組合）**
* **==A==tomicity requirement**（不可分割）
    要就全做，不然就不要做
    不能只做一部份
* **==C==onsistency requirement**（一致性）
    轉帳前後，兩帳戶的總和不變
    轉帳前是正確，轉帳玩也是正確
    但==過程不正確是被允許的==（A拿出50塊，但還沒轉到B）
* **==I==solation requirement**（分離性）
    大家一起跑 但彼此互不影響 也就是
    即使「大家一起跑」結果也要跟「一個接著一個跑」一樣
    
    很多人一起跑，==看到的都要是正確的==
    我做到一半的東西，別人是看不見的
    ```
    1. T1 read(A)
    2. T1 A := A-50
    3. write(A)
    4. T2 read(A), read(B), print(A+B)
    ```
    
    Ti, Tj代表兩個transaction
    一定要一個跑完再跑另一個
    
* **==D==urability requirement**（持久性）
    一旦被通知完成，就要一直持續下去
    ex. 今天說轉帳成功，明天又說誒！其實沒成功啦
    
### Transaction State
* **Active**
    就是正在跑
* **Partially committed**
    執行完最後一個statement 但是資料還沒存到資料庫
* **Committed**
    IO沒問題 所有東西都進了資料庫 成功！
* **Failed**
    沒有辦法再繼續執行，失敗～～
    因為不可分割性，所以要roll back回到開始之前的狀態
* **Aborted**
    失敗的結束，滾回去之後會標註你是aborted的狀態（曾經失敗過）
    aborted後有兩個選擇
    * 重新執行這個transaction
    * 殺死這個transaction


![](https://i.imgur.com/Adxrgiw.png)

### Concurrent Executions（同時執行）

* 優點
    增加CPU、硬碟的處理效率（ex. 一個在用CPU 另一個就去讀寫）
    平均等待時間變短

* **Concurrency control schemes**（策略、機制）
    希望能夠控制所有在一起跑的人
    避免他們破壞資料庫的一致性
    需要維護ACID的Isolation requirement
    
ps. 接下來介紹的都與councurrent executions有關

### **Schedules**（排程）

會看process的內部，因為transaction會動到資料庫

定義：所有transaction的順序
每個transaction都有自己原本的順序（需要保留，原本先的還是先）
但這裡說的是所有的transaction

執行完要嘛是commit 要嘛是abort

**範例：**
T1：A轉50給B
T2：A轉自己的10%給B

![](https://i.imgur.com/YgHO36w.png)

**第一種schedule(T1完再換T2)**
![](https://i.imgur.com/W6FAAVE.png)

**第二種schedule(T2完再換T1)**
![](https://i.imgur.com/rWYf3P9.png)

**第三種schedule（穿插的）**
==只要維持一致性即可== 通常都是這種
![](https://i.imgur.com/vQBaHjW.png)

**第四種schedule（錯誤的例子）**
一開始A+B = 1000+2000 = 3000
最後的A+B = 950+2100 = 3050
不符合一致性
![](https://i.imgur.com/wg8H1P8.png)


### **Serializability**（可序列化）
    
* 定義
    由多個transaction組合而成的schedule
    跟多個transaction分別執行(一個接著一個)
    若結果一樣代表這個schedule是可序列化的

* **Conflict serializability**
    忽略細部的計算，只留下讀＆寫

    `一個transaction裡的指令不會互相衝突`
    `只有不同transaction間的指令才會衝突`

    當Ii, Ij都讀到同一個data item 且 互相影響才會衝突
    分為以下四種狀況
    * Ii = read(Q), Ij = read(Q)   不衝突（因為只是讀，沒差）
    * Ii = read(Q), Ij = write(Q)  衝突
    * Ii = write(Q), Ij = read(Q)  衝突
    * Ii = write(Q). Ij = write(Q) 衝突

    若兩個指令會衝突，就不能亂調整他們的順序

* 名詞解釋
    * **conflict equivalent**
        若通過不衝突的指令交換
        能夠將一個schedule S可以轉乘另一個schedule S'
        則我們說這兩個schedule是conflict equivalent

    * **conflict serializable**
        若某個schedule 跟 serial schedule 是conflict equivalent
        則我們說某個schedule是conflict serializable

* 範例
    * 範例1
        `左邊的（schedule3）`
        `中間的（schedule1）`
        `右邊的（serial schedule）`

        `schedule 3 可以交換 T2的write(A) & T1的read(B) 變成schedule 1`
        `而且兩個指令是不衝突的`

        `再繼續轉換的話就可以變成serial schedule`

        因此schedule3是conflict serializable
        ![](https://i.imgur.com/ZZy5mWE.png)

    * 範例2
        `因為他不管怎麼轉都無法變成serial schedule`

        所以這個schedule不是conflict serializable

        ![](https://i.imgur.com/UydT3oj.png)



### **Testing for Serializability** ==（可能會考）==
    
* **Precedence graph**
    ![](https://i.imgur.com/4Cqwct6.png)

    * **圓圈**
        代表transactions
    * **線（有向的）**
        代表存在一組**conflict**的指令
        若線是從T1 指到 T2
        代表T1先執行，再執行T2

    把你要測試的＆Serializability的都畫成圓圈＆線的形式
    若兩個長得一樣就代表測試的可以換成Serial Schedule

    若是conflict serializability，會形成迴圈

* **topological sorting**
    若Precedence graph沒有迴圈
    則可以透過 topological化成以下形式
        
    ![](https://i.imgur.com/GYOB3an.png)

    `j, k不能決定誰先誰後`
    `但利用topological把他排呈現性關係`
    `i, j, m 仍然是i, j, m`
    `i, k, m 仍然是i, k, m`

    圖a 可以轉換成「圖b」 也可以轉換成「圖c」

### **Recoverable Schedules**

* 定義
    若schedule發生問題必須可以rollback
    `(rollback的話 不能影響到其他transaction)`

    commit：成功就成功，不能事後再反悔

    ![](https://i.imgur.com/4tBKNTg.png)

    ```
    若T8在最後read(B)時停電了
    T8 read(A) //1000
    T8 write(A) //2000
    T9 read(A) //2000
    T9 commit
    T8 想要abort但T9已經commit了
    這時就會發生錯誤
    所以這個schedule「不是」recoverable
    ```

    因為Ti(T9)讀的是Tj(T8)寫的
    所以在Ti(T9) ==commit== 之前要確定Tj(T8)已經commit

### Cascadeless Schedules

* 定義
    cascading rollbacks永遠不會發生
    你的commit要在我讀之前

* **Cascading Rollbacks**

    先做的若要rollback
    後面跟著做的也要rollback

    ![](https://i.imgur.com/OOg9Ofa.png)

    若T10滾(rollback)，T11、T12都要跟著滾(rollback)

    一個人個失敗，導致所有人都要滾
    容易造成系統負擔

期待能做到Cascadeless Schedules(也會是recoverable)
就是能少一點Cascading Rollbacks

**Recoverable vs cascadeless**
1. 你的commit要在我的commit之前(Recoverable)
2. 你的commit要在我讀之前(Cascadeless)


### **Concurrency Control**

DB會提供一個機制以確保schedule是conflict serializable
並且一定要recoverable（最好是cascadeless）

希望有一個機制能讓schedule
一開始就產生對的
而不是產生完再慢慢調（這樣太浪費時間了）

---
## ch18

### Lock-Based Protocols
以lock為基礎的協定

要使用的時候需要跟系統要「lock」(lock request)
至於要不要給你，由concurrency-control manager決定
給你之後 transaction才能繼續動作

**lock的類型**
* **exclusive(X)**
    **X-lock**：這個lock的名字
    ==**lock-X**==：一個指令，代表準備要**寫入**
* **shared(S)**
    **S-lock**：這個lock的名字
    ==**lock-S**==：一個指令，代表準備要**讀取**
    因為大家一起讀沒差有點共享的概念，所以叫shared

**Lock-compatibility matrix**
左邊是request
上面是別人的
![](https://i.imgur.com/BVDYowl.png)

當別人在寫的時候，不論你提什麼要求都會被拒絕
若別人在讀的時候，你只能讀不能寫
若你request但現在沒辦法給你，你就只能等！！

**Schedule With Lock Grants**
![](https://i.imgur.com/qtvBhcy.png)


`這個schedule不是serializable`
一開始 A = 100, B = 200
T2 的 display(A+B)會是錯的 //250


光lock本身無法確定serializable
解決辦法👇🏻
**Two-Phase Locking Protocol**（兩階段的）
==對於單個transaction（只看自己）==
只要遵守規則，出來一定是conflict serializable schedules
* step1. **Growing Phase**
    在此階段只能要lock
    不能release lock
    
* step2. **Shrinking Phase**
    在此階段只能release lock
    不能要lock

* **lock point**
    最後一個要lock的時間點
    利用lock point決定誰先誰後(Testing Seriable的那個)

一開始就要要好所有的lock
unlock之後不能再要lock
==但沒有說unlock一定要在最後面==

* **Strict two-phase locking**
    若transaction裡有X-lock
    要等到commit完才會unlock
    
* **Rigorous two-phase locking**
    只要transaction裡有lock（X-lock & S-lock）
    就要等到commit完才會unlock
    通常都是用這個 但簡稱為two-phase locking


two-phase locking一定會seriziable
但seriziable的不一定全是two-phase locking

你如果沒有任何資訊 就要用two-phase locking
T1, T2只要有人不遵守two-phase locking，就會出錯！

---
#### Lock Conversions

一開始是S，等真正要給的時候再用X

Growing Phease
* acquire lock-S
* acquire lock-X
* convert lock-S to lock-X

Shrinking Phase
* release lock-S
* release lock-X
* convert lock-X to lock-S

---

### Tree Protocol

1. 全部都是exclusive的lock
2. 第一個可以是圖上的任何一個
    如果要取得J，一定要取得J的爸爸H
    即使不需要H，還是要拿H
3. 不會有互等的狀況，一定是小孩等爸爸
    
![](https://i.imgur.com/Ma7oKGU.png)

---
### Deadlock handling

![](https://i.imgur.com/oLKufyg.png)

T3： 老的
T4： 年輕的

wait-die: 
年輕的不等，發現沒資源時，年輕的「自己」rollback
（還沒到deadlock）

wound-wait: 
年輕的拿走的話，老的把資源搶走（年輕的等），老的叫年輕的rollback
（到真正互等時，年輕的才rollback）

其實都是把資源給老的
差別只在是主動 還是 被動 rollback

-
total rollback:全部滾回去
partial rollback:只滾一半


---
### Multiple Granularity

巢狀： File不會同時在兩個父節點下

Fine 小 ex. lock在record上
Coarse 大 ex. lock在file上


-

IS：沒人用我，我下面被讀
IX：沒人用我，我下面被寫
S：我被讀
SIX：我正在被讀，我下面被寫
X：我被寫

-

若爸爸有正確的lock，小孩才能繼續取得lock
lock從爸爸開始
unlock從小孩開始

--

## ch19

### Failure Classification（錯誤的類別）
* **Transaction failure**
    * Logical errors
        因為transaction的內部（邏輯）錯誤，transaction被迫停止
    * System errors
        因為deadlock之類的系統錯誤，DB被迫停止
        
* **System crash**
    因為電源被關掉、硬體、軟體毀壞導致系統故障
    * Fail-stop assumption
        假設non-volatile storage的內容不會因為system crash而損壞
        （DB有大量的完整性檢查，可以確保發生system crash時
        讓系統即時停止，防止non-volatile storage損壞）
        
* **Disk failure**
    磁頭故障等的disk failure破壞disk的內容
    （假設此種狀況可以利用checksum被偵測）

### Storage Structure（資料的儲存型態）
* **Volatile storage**（不穩定的）
    會跟著system crash一起損壞
    ex. main memory, cache memory
* **Nonvolatile storage**（穩定的）
    不會跟著system crash一起損壞
    但仍有機會損失資料
    ex. disk, tape, flash memory, non-volatile RAM
* **Stable storage**
    不管怎樣，資料都可以保存下來
    
### Data Acess（資料的存取）
* **Physical blocks**
    在disk裡面的block
* **Buffer blocks**
    暫時留在main memory的block
* **Block movements**
    * input(A)
        將A這個block的資從disk料移到main memory
    * output(B)
        將B這個block的資料從main memory移到disk
    ![](https://i.imgur.com/NXrs5hK.png)
   
`transaction就是一段程式碼`
`每個transaction的data item都會在transaction自己的work-area有一個副本`
* **buffer block <-> work-area**
    * read(x)
        將buffer block裡的x 複製到區域變數x~i~
    * write(x)
        將區域變數x~i~ 寫到buffer block裡
    
    **⚠️ 注意**
    1. 若x所在的block還不在buffer block裡
        則須先input(x)，才能read, write
    2. output(x)不用緊跟在write(x)後面
        系統可以在他認為合適的時候output
    3. 在使用x之前 必須要先read(x)
    4. write(x)可以在任意時候執行（但要在transaction commit之前）

    ![](https://i.imgur.com/EV92jNQ.png)
    
---

### Recovery and Atomicity
之前說transaction須遵守ACID
為了達到Atomicity(ACID的A)(要就全做 不然就不做)

因為不做的話需要Recovery
接下來要講為了Recovery的相關事項

* 較少使用的替代方案
    * **shadow-copy**
        ![](https://i.imgur.com/LSoGBLt.png)
        當你要編輯時，先複製一份原本的（編輯複製的）
        如果編輯成功，用編輯完成的（複製的那個）
        如果編輯失敗，用原本的就行

    * **shadow-paging**
        跟shadow-copy很像
        但資料庫那麼大 不可能全部複製
        所以只複製局部

### Log-Based Recovery
基於log的recovery
因為log是放在stable storage 所以很安全
log是一塊地方 記錄所有的transaction

紀錄transaction的update
只要記update 不用記read之類的
因為就算transaction失敗 read只是讀 不會影響資料庫

* 紀錄的內容
    1. **<T~i~ start>**
        `當transaction開始` log record紀錄<T~i~ start>
        代表現在是哪個transaction在跑

    2. **<T~i~, X, V~1~, V~2~>**
        `在transaction write之前` log record紀錄<T~i~, X, V~1~, V~2~>
        代表`write(X)`，X這個data item的值從V~1~變成V~2~

        * T~i~ 👉 transaction
        * X 👉 data item
        * V~1~ 👉 舊的值
        * V~2~ 👉 新的值

    3. **<T~i~ commit>**
       `當transaction結束` log record紀錄<T~i~ commit>
        
* 紀錄的方法
    * **Deferred database modification**（延遲）
        等transaction自己全部跑完再輸出到buffer或disk
        
        **優點**：不用還原，因為要等到commit以後才輸出
        **缺點**：在跑的過程要記錄改了哪些，要存local copy
        
        因為對local處理增加麻煩
        所以其實不太用
        大多用Immediate Database Modification
        
    * **Immediate database modification**（立即）
        transaction在commit之前 部分資料就先出去(到buffer、disk)
        由disk自己去看 如果這個block被改很多 就先輸出資料
        會先跑log再真正執行transaction
        
        **優點**：因沒有時間限制 彈性大、`output順序`可與`write順序`不同
        **缺點**：local負擔小
        
⚠️ `當<Ti commit>在stable storage被看到`
`才是真正的commit` ⚠️

* 紀錄的範例
    ![](https://i.imgur.com/oIiS0pQ.png)
    `所有transaction都紀錄在log裡面`
    
    ![](https://i.imgur.com/pSrxLMp.png)
    **write**: 從 `work area` 到 `buffer`
    **output**: 從 `buffer` 到 `disk`
    **B~c~**：代表C這個data item所在的block
    
    因為是Immediate 所以write都在commit之前
    但output到disk 是你無法決定的
    `像是A雖然很早就被送到buffer`
    `但卻是最後一個送到disk的`
    
    只要看到commit 我們都要重做一次
    因為無法確定到底output到disk了沒

---

### Concurrency Control and Recovery
concurrency 都是共用buffer、log
⚠️ `已經commit的資料 才能被別人讀取 才不會有無法recovery的狀況` ⚠️

* 針對log record
    * undo **<T~i~, X, V~1~, V~2~>**
        把X的值設成V~1~
    * redo **<T~i~, X, V~1~, V~2~>**
        把X的值設成V~2~
        
* 針對transaction
    因為同一個transaction對同一個data item可能做很多次
    所以 順序很重要！
    
    * **undo(T~i~)**
        ==從下到上(backword)==
        把所有處理過的data item
        都設成舊的
        
        因為有可能recovery到一半又當機
        所以undo的過程也需要紀錄
        不一樣的是只要紀錄data item`(X)`要更改成什麼值`(V)`
        ==<T~i~, X, V>==
        
        而完成所有的undo之後 還需要紀錄 ==<T~i~ abort>==
        
    * **redo(T~i~)**
        ==從上到下(forward)==
        把所有處理過的data item
        都設成新的
        
        雖然有可能recovery到一半又當機
        但==redo不需要紀錄==
        反正就再做一次就好
---

### Recovering from Failure
當斷電完 又有電之後 我們要recovery
要根據log做出對應的事情

* 復原的情況
    * 情況1
        若在log裡面看到 **<T~i~ start> && (<T~i~ commit> || <T~i~ abort>)**
        則需要 ==redo==

        `補充`
        `因為commit、abort都是一種合理的結束狀態`
        `commit 5行正確執行完`
        `abort 做了5行 再退回去5行`
        `雖然abort看起來很像多此一舉 但對於演算法來說會比較簡單`

    * 情況2
        若在log裡面只看到 **<T~i~ start>**
        則需要 ==undo==

* 復原的範例
:::info
(a)

**題目：**
<T~0~ start>
<T~0~, A, 1000, 950>
<T~0~, B, 2000, 2050>

**解答：**
因為沒有看到commit或abort 所以T~0~是undo（從下到上）
B <- 2000
log records <T~0~, B, 2000>
A <- 1000
log records <T~0~, A, 1000>
log records <T~0~, abort>

---

(b)

**題目：**
<T~0~ start>
<T~0~, A, 1000, 950>
<T~0~, B, 2000, 2050>
<T~0~ commit>
<T~1~ start>
<T~1~, C, 700, 600>

**解答：**
T~0~是redo（從上到下），T~1~是undo（從下到上）
A <- 950
B <- 2050
C <- 700
log records <T~1~, C, 700>
log records <T~1~, abort>

---

(c)

**題目：**
<T~0~ start>
<T~0~, A, 1000, 950>
<T~0~, B, 2000, 2050>
<T~0~ commit>
<T~1~ start>
<T~1~, C, 700, 600>
<T~1~ commit>

**解答：**
T~0~是redo（從上到下），T~1~是redo（從上到下）
A <- 950
B <- 2050
C <- 600

---

(d)
這個是(a)包含revoery的log

**題目：**
<T~0~ start>
<T~0~, A, 1000, 950>
<T~0~, B, 2000, 2050>
<T~0~, B, 2000>
<T~0~, A, 1000>
<T~0~ abort>

**解答：**
T~0~是redo（從上到下）
A <- 950
B <- 2050
B <- 2000
A <- 1000

---

(e)
這個是(b)包含revoery的log

**題目：**
<T~0~ start>
<T~0~, A, 1000, 950>
<T~0~, B, 2000, 2050>
<T~0~ commit>
<T~1~ start>
<T~1~, C, 700, 600>
<T~1~, C, 700>
<T~1~ abort>

**解答：**
T~0~、T~1~都是redo（從上到下）
A <- 950
B <- 2050
C <- 600
C <- 700
:::

---

### Checkpoints
* 產生checkpoints(n.)的原因
    1. 因為不常recovery，所以當你要recovery時
        log可能非常長（3個月之類的）
    2. 要全部redo，但其實很多東西都已經送到disk了
        會重複redo -> 沒必要

* checkpointing(v.)時所做的事
    1. **確定log record是放在安全的地方**
        以前都只是假設他是安全的(stable storage)
        但實際上不可能
    2. **把buffer的東西 都output到disk**
        以前都說沒有時間限制 由disk自己控制
        現在提前到checkpoint的時候做
    3. **log records <checkpoint L>**
        L: `在checkpointing的當下 正在跑的transaction`
    4. **在checkpointing時 所有的transaction都要暫停**
        不然太混亂了！！
    
    
* recovery演算法的完整敘述
    ![](https://i.imgur.com/5bbBp6x.png)
    T~c~: checkpoint發生的時間
    T~f~: 系統當機的時間
    此時checkpoint L所紀錄的為T~2~
    
    * 概念
        
        嚴格說起來總共會跑三趟`（但課本把找checkpoint合併在redo裡）`
        * 第一趟 ==**找checkpoint**==
            從後往前 找第一個遇到的checkpoint
        * 第二趟 ==**redo並記錄undo-list**==（後面會細說）
            從checkpoint開始（包含執行到一半的transaction 這裡是T~2~）
            從前往後 做redo
        * 第三趟 ==**undo**==
            從後往前 做undo
    
    * 完整的演算法
        * **redo階段**
            step1. 找到最新的checkpoint ==**並將L放入undo-list**==
            step2. 從舊的往新的看
                    只要看到<T~i~ start> ==**就將T~i~加入undo-list**==
                    只要看到<T~i~, X~j~,  V~1~,  V~2~> 或 <T~i~, X~j~, V~2~> ==**就將X~j~的值改成V~2~(新的)**==
                    只要看到<T~i~ commit> 或 <T~i~ abort> ==**就將T~i~移出undo-list**==
        
        * **undo階段**
            `只要undo undo-list裡面的transaction`
            step1. 只要遇到<T~i~, X~j~,  V~1~,  V~2~> ==**就將X~j~設成V~1~ 同時紀錄<T~i~ , X~j~,  V~1~>**==
            step2. 只要遇到<T~i~ start> ==**log紀錄<T~i~ abort> 同時將T~i~移出undo-list**==
            step3. 做到undo-list為空時 停止
    
    以上面的圖來說
    T~1~: 不用理他
    T~2~、T~3~: 做redo
    T~4~: undo
    
* recovery的範例
:::info
**Beginning of log**
<T~0~ start>
<T~0~, B, 2000, 2050>
<T~1~ start>
<checkpoint {T~0~, T~1~}>
<T~0~, C, 700, 600>
<T~1~ commit>
<T~2~ start>
<T~2~, A, 500, 400>
<T~0~, B, 2000>
<T~0~ abort>
**此時斷電(failure)**

---

**redo階段**(從舊往新):
找到最新的checkpoint，此時undo-list = [T~0~, T~1~]
C <- 600
將T~1~移出udo-list，此時undo-list = [T~0~]
將T~2~加入udo-list，此時undo-list = [T~0~, T~2~]
A <- 400
B <- 2000
將T~0~移出udo-list，此時undo-list = [T~2~]

**undo階段**(從新往舊):
只需要看undo-list裡面的，也就是T~2~
A <- 500，並紀錄<T~2~, A, 500>
紀錄<T~2~ abort> 並將T~2~移出udo-list，此時undo-list = []
因為undo-list為空，結束

---
**總結**:
* 值:
    A = 500
    B = 2000
    C = 600
    
* log:
    <T~2~, A, 500>
    <T~2~ abort>

:::

---

### Log Record Buffering

* **commit**
    再次修改commit的意思
    要等到log record輸出到stable storage，才是真正的commit
* **log force**
    一筆log record很小，不可能每紀錄一筆就輸出
    通常會等到1024Bytes(之類的)時，再一起輸出到stable storage
    這樣的話可以減少IO的負擔
    
    而log force是可以「強制」log輸出到stable storage
    
    除此之外因為log的順序非常重要！！（會影響到data item被修改的順序）
    ⚠️ `所以buffer在記憶體中的順序也很重要，log會須根據此順序輸出` ⚠️
    
* **WAL/write-ahead logging rule**（在寫之前的log）
    這個規則是在說
    log要先紀錄，才能更動data item的值
    不然改了但log沒紀錄，此時斷電，recovery時會復原不到


### Database Buffering
不可能每次讀資料都去disk讀
所以會在記憶體有buffer
若要讀的data item在buffer 就去buffer讀
若不再且buffer滿了 就要挑一個block swap-out出去
換一個新的進來（從disk）

* recovery algorithm 支持以下兩個policy
    * **no-force policy**
        force policy指的是，commit時，也確定所有
        data item更新完畢
        no-force則相反
        
        這也是為什麼需要redo，因為不確定到底輸出成功沒
    * **steal policy**
        在commit之前，有可能已經將data item輸出到disk
    
* 把一個block輸出到disk

    若此block尚未commit，須先在log紀錄undo
    step1. 先拿到exclusive-lock（更新時block不能動）
            因為時間很短，稱此lock為latches
    step2. 紀錄log
    step3. 將block送到disk
    step4. 歸還latches

### Buffer Management

* Database Buffer可以用兩種方法實作
    * **main-memory**
        缺點是資料大時不夠用、資料少時又太多（彈性小）
        所以 通常用virtual memory
        
    * **virtual memory**
        在disk裡挖一塊空間出來
        雖然還是有缺點，稱之為**dual paging**（雙重分頁）
        意思是當virtual memory裡的block要輸出到disk
        須先swap-out回主記憶體，再輸出到disk
        
        聰明的方法是直接從virtual memory送過去disk裡的資料庫部分
        但這需要資料庫＆作業系統密切合作
        但大部分系統不支援此想法（沒有那麼聰明）

### Fuzzy Checkpoints
為了改善原本的checkpoint
原本在checkpointing時 所有的transaction都要暫停

step1. 暫時停止所有的transaction
step2. log records <checkpoint L>
step3. 用list M來紀錄有需要修改(輸出)的buffer blocks
step4. 可以開始動了
step5. 輸出在list M裡的所有block(block在輸出時，其他不能動 要遵守WAL)
step6. 用一個指標記住最新的checkpoint
![](https://i.imgur.com/IfokMVz.png)

補：
`block輸出的當下不能動`

`block1在輸出的時候 block2可以動`
`block2輸出時 需要把之前的log都做一遍`

### Failure with Loss of Nonvolatile Storage
我們目前講的都是當機（硬碟不會壞）
但如果硬碟(Nonvolatile Storage的一種)壞掉怎麼辦？

* 事前作業
    定期的將資料庫內容送到stable storage（跟checkpoint做的事情很像）
    step1. 先把目前的所有log record送到stable storage
    stpe2. 把所有buffer都送到disk
    step3. 把資料庫的內容複製到stable storage
    step4. 在stable storage的log 紀錄 <dump>
    雖然這裡說stable storage，但其實就是另一塊硬碟or磁碟
    
    dump跟checkpoint一樣 會有比較彈性的作法
    稱之為fuzzy dump 或 online dump

* 復原
    復原的時候 因為會有時間差（12.dump 18.硬碟損毀）
    所以要先根據log 把該做的再做一次

### Remote Backup Systems
因為單點脆弱 所以需要遠端備份（才不會發生火災 就一起燒掉）
就算是從dump回來還是要時間還原
但希望整個系統可以馬上運作（不僅僅是資料）
所以需要有另外一個機器是好的（不只是log、資料，還要系統是好的）

![](https://i.imgur.com/m6XTa9U.png)
`primary`: 主要執行的機器
`backup`: 備用的機器
`network`: 兩台機器之前的溝通

* **Detection of failure**（偵測故障）
    為了知道primary什麼時候壞掉
    兩台機器之間會有多條溝通管道
    
    因為如果只有一條 會不知道是network壞掉 還是primary壞掉
    如果有多條第一條沒收到 就看第二條
    如果全部都沒收到就很可能是primary壞掉
    backup變成新的primary

* **Transfer of control**（轉移控制權）
    做的事很像recovery
    根據log record做事(redo、undo)
    
    但通常備援的配備都不會有primary好
    等primary恢復 再把東西弄回去

* **Time to recover**
    一樣有週期性的處理log record
    不然等到出事再處理 會等太久

* **Hot-Spare**
    checpoint是一段時間一段時間的做
    hot-spare是平常就一直redo primary的log record
    如此一來當primary壞掉 只要把沒有正常結束的transaction undo就行

* **commit**
    因為有primary、backup 所以commit又有新的定義
    * **one-safe**
        log record到primary

    * **two-very-safe**
        log record 在primary、backup都有
        因為兩邊都寫 所以時間長
        如果transaction已經跑完 但有一邊機器當機
        trnasaction永遠commit不了

    * **two-safe**
        平常兩邊都要有
        但如果只偵測的到一台
        primary的有的話 就可以commit
        這是一種折衷的方法




---

## ch20 Database System Architectures（資料庫系統架構）

### Centralized Database Systems（集中式系統）
    
只有一台電腦

* **Single-user system**
    只讓一個使用者用 是很小型的軟體
    ex. 嵌入式系統、冷氣（只需要少少的資料）
    
    `通常會提供API來存取資料 但不支持SQL`

* **Multi-user systems**（又稱為server systems）
    client(我們)端向server(資料庫)端要資料
    是coarse-grained parallelism的多核心系統
    
    補充
    `coarse-gramined parallelism`: 最多10核心（大略的切）
    `fine-grained`: 百~千核心（切的很細）
    
---
    
### Server System Architectures
大致可以分為兩大類
1. **transaction servers**
    用於RDB（Relational DataBase）
    所有資料庫效率、正確性都在server裡面處理
    
2. **data servers**
    資料提供者(只管資料 不管運算)
    因為client的運算能力很強
    所以把資料丟給clinet做 做完再把資料送回server
    
    `ps. 後來被RDB打敗，大數據出現後，又復出`
    
#### transaction servers

* 流程
    step1. client向server送請求
    （基本上就是SQL的請求 所以trnasaction servers又稱為SQL servers）
    step2. transaction在server上執行
    step3. 執行完把結果傳回client
    
    通常client、server是不同台電腦
    他們透過RPC(remote procedure call `從遠端丟程式 到server執行`)來溝通
    多次透過RPC(想成一行程式)傳送 會形成一個transaction(多行程式)

    應用程式也會透過ODBC、JDBC API來跟transaction server溝通
    微軟出來主導把clinet、server溝通的API 標準化

* 架構
    ![](https://i.imgur.com/HzJ2eoe.png)
    
    * **shared memory**
        共享記憶體
        * **buffer pool**
            放硬碟＆transaction的資料
            transaction要資料會先來這裡找
        * **log buffer**
            放log record
        * **lock table**
            就是linked-list的那個
        * **query plan cache**
            放最快的的執行策略
            其實RDB花很多時間在提升效率
            也要花時間找出最快的策略
            像我們在登教學務 做的事情都差不多(選課之類的) 
            只有學號不一樣 所以query的策略是一樣的
            找出策略以後 先暫存起來 下次如果是一樣的 就不用再找
    * **user process**
        就是使用者(client端)
        會透過ODBC、JDBC丟query或transaction
    * **server process**
        負責接收使用者丟過來的東西
        交給資料庫執行 執行完再傳回去給使用者
        通常都是用多個多線程(multithreaded)
    
    * **database writer process**
        負責寫data item，適時的把block輸出到disk
    * **log writer process**
        負責寫log（由server process寫 因為他負責接收使用者的請求）
        ps. 要趕快把log放到安全的地方(stable storage)
    * **checkpoint process**
        負責把那段時間的log寫出
    * **process monitor process**
        負責監督所有的process
        若監測到fail 要負責做recovery的相關措施
        （abort掉 之後重新執行）
        
    * **lock manager process**
        負責管理lock
        server process會跟lock manager要lock
        lock manager根據lock-table回應
        若有大量的transaction 會造成系統負擔
        有時候就乾脆不問lock manager 直接來查lock-table
        
        但因為deadlock不是單一transaction可以看到的
        所以deadlock detection 還是要由lock manager來負責
        但純粹要lock可以丟給server process

#### data servers

* 流程
    又稱為data storage system
    step1. client要data
    step2. sever送data給client
    step3. 在client運算完 再送回server
    step4. server收到並儲存
    
* 傳遞方法
    * 早期(OODB)
        系統裡面存的是物件 以送物件為主
        會給每個物件一個編號 編號對應到儲存的記憶體位置
        所以也會把記憶體位置送出去
        
    * 現在(就是一般的儲存資料)
        常用的像是JSON 一串二進位碼(影片)
        補: 一次傳64MB
        
* 策略
    因為是大數據 一次就會傳很多

    * **Prefetching**
        預測接下來需要什麼 先拿起來

    * **Data caching**
        拿完之後 不要那麼快丟掉
        若第二次要用的話
        在trnasaction跟server要lock時
        順便檢查這份資料是不是最新的

    * **Lock caching**
        不只是資料 lock也可以留下來
        T~A~ shared-lock(做完但留著lock)
        T~B~ shared-lock
        若此時T~B~要改
        server先檢查是否衝突
        如果衝突且T~A~已做完 則server 要回(calls back) lock

    * **Adaptive lock granularity**
        * **Lock granularity escalation**
            小的lock
        * **Lock granularity de-escalation**
            大的lock
        
        若讀的資料少 -> 小的lock
        若讀的資料多 -> 大的lock
        lock也可以在中途升級、降級
        若一開始給大的lock 但發現很多transaction都要讀裡面的東西
        就會換成很多小的lock 這樣大家都可以用了

---

### Parallel Systems

平行系統由多個process＆多個disk＆高速網路所組成

平行vs分散
`平行`強調 很多人(process)一起分擔工作
`分散`強調 資料分散在很多地方

* 動機
    為了處理超過單台電腦所能法負荷的工作量
    
* 特性
    * 高效能的transaction processing（能處理網路級別的user request）
    * 支持大數據

* 種類
    * **coarse-grain parallel**
        數量少但功能強的process
    * **fine grain parallel**
        數量多但功能弱的process
        ex. data center
        
* 性能指標
    * **throughput**
        一段時間內完成的工作量
    * **response time**
        完成一個任務所花的時間

* 計算方式
    假設系統變成n倍大(強)
    * speed up
        針對一個固定的問題 看時間能不能變快
        公式定義: `speedup = 小系統花的時間/大系統花的時間`
        最佳情況 `speedup = n`
        ![](https://i.imgur.com/iMRUwL8.png)
        
        
    * scale up
        問題變n倍複雜 看時間能不能變快
        公式定義: `scaleup = 小系統小問題花的時間/大系統大問題花的時間`
        最佳情況 `scaleup = 1`
        ![](https://i.imgur.com/1AeWqNk.png)
        
        又可以細分為兩類
        * Batch scaleup
            問題變複雜 但仍然是一個問題
            ex. 從1+2+...+100 變成 1+2+...+1000
            這種比較難做 因為要分割工作 最後再加總
            
        * Transaction scaleup
            問題一樣 但是數量變多
            ex. 從10個query 變成 100個query
            資料庫容易處理 因為彼此不相關 好分割工作
            
* 通常是sublinear的原因
    * startup/sequential costs
        startup: `在跑之前（暖身）的花費`
        sequential: `不能完全平行`
        * Amdahl’s law（speedup的上限）
            ==1 / [ (p/n) + (1-p) ]==
            ![](https://i.imgur.com/yVI4pEC.png)

        * Gustafson’s law（scaledup的上限）
            ==1 / [ p + n(1-p) ]==
            ![](https://i.imgur.com/C2vYLyk.png)

    * interference
        共用資源
        ex. 大家都用要用data item X
        A在用的時候 B就不能用
    * skew(偏移)
        每個人的困難度不見得一樣
        若要等最慢的執行完 其他人才能做事
        最慢的那個人就會拖累大家
        
:::info
題目:
假設p=0.9 n=10
根據上面的兩個公式
speedup為何?
scaleup為何?

---

答:
speedup = 1 / [ (p/n) + (1-p) ]
= 1 / (0.09 + 0.1)
= 5.26

scaleup = 1 / [ p + n(1-p) ]
= 1 / (0.9 + 1)
= 0.526
:::

* **網路架構**

    ![](https://i.imgur.com/JdLdQIB.png)
    ![](https://i.imgur.com/Fuw3oxI.png)

    * **bus**
        當有人在用的時候 大家都要停下來
    * **ring**
        比bus好一點 因為第一個連到最後一個
    * **mesh**
        中間的雖然連到4個 但周圍的連得少
        worst case: 走到對角線，需要走 `2√n` 次
    * **hypercube**
        需要 log~2~n 個bits去表示每個節點
        差一個bit 代表相鄰
        worst case: 走到對角線，需要走 log~2~n 次

    * **tree-like topology**
        常用於data center 又稱為**data center fabric**
        目標就是創造出很多條路
        最下面的: process或電腦（真正在跑的）
        top-of-rack switches: 很快 因為是連自己的process、電腦
        aggregation switches: 每個都連到很多個

*  **資料庫架構**

    ![](https://i.imgur.com/dXtRSA0.png)
    
    `P`: 處理器
    `M`: 記憶體
    `圓柱`: 硬碟(disk)

    * **shared memory**
        **共享記憶體＆disk**
        ==！處理器之間的通訊非常快！==
        （P1叫P2做事可以很快 因為都是到同一個地方做事）
        
        * bus -> network
        
            ![](https://i.imgur.com/pH40xVS.png)
            每個CPU有自己的記憶體 也可以拿到別人的記憶體
            P1 拿 P3會比較慢（跟拿自己的比起來） 稱之為`NUMA`
            補: `bus大約只能64~128個處理器(一個在跑 其他就不能跑)`
        
        * 速度仍然不夠快 -> 加上==cache==
        
            ![](https://i.imgur.com/3058IUp.png)

            一個多核心的處理器
            每個core都有自己的cache

            L1最快但最小...以此類推
            傳輸的單位: `cache line（大約是64 Bytes）`
    
    * **shared disk**
        **只共享disk**
        `優點`: 若處理器壞掉 影響不會太大（因為資料在硬碟 可以換其他處理器做）
        因此又稱之為 ==**fault-tolerance**==（容錯）的架構
        
        `缺點`: 只要有共享就有bottle neck(卡在bus那)
        所以用網路 讓他快一點
        而且現在電腦不一定放在硬碟(大量的資料)旁邊 通常用網路(LAN)連接
        ![](https://i.imgur.com/ba2ez9e.jpg)
        
    * **shared nothing**
        什麼都不共享
        溝通比較慢 因為都要透過網路來溝通
        `RDMA`: 拿自己的東西非常快(就在自家後院)
        `non-local disk access`: 彼此間溝通就比較耗時
    
    * **hierarchical**
        混合的來做(可以自己設計)
        top-level(shared nothing)下面接三個子系統(shared memory)

---

### Distributed Systems

再次說明
`平行`強調 很多人(process)一起分擔工作
`分散`強調 資料分散在很多地方

![](https://i.imgur.com/7zGTFsD.png)
`site`: 放資料的機器（地方）

* 網路類型
    * **Local-area networks** (LANs)
        site彼此很近 通常是因為資料量太大放不下 
        
    * **Wide-area networks** (WANs)
        site彼此很遠 通常是因為地理因素
        會有更高的延遲
        
* 架構類型
    * **Homogeneousdistributed databases**（同質性）
        通常使用的軟體、schema相同 只是資料太多所以要分散
            
    * **Heterogeneous distributed databases**（異質性）
        通常使用的軟體、schema不同(各自用各自的)
        整合資訊比較麻煩
        `補: 美國國防部最早提出這個問題`
        
    分散的資料是架構需要辨別trnasaction是local/global
    * **local transaction**
        在A提出要求 資料也在A
    * **global transaction**
        在A提出要求 但資料在B 或
        資料來自各地(C、D、E...)
        
* 整合分散式數據的優點
    * **Sharing data**
        可以達到資料分享
    * **Autonomy**(自治)
        彈性大 能夠讓分公司有自己的控制權
        
* Availability
    假設需要全部資料 系統才能活著
    只要一個site壞掉 系統也就壞了
    為了避免這種情況 -> 資料就要多存幾份（備份）

* 分散式架構的問題
    transaction是否仍能達到ACID?（這裡只講不可分割性）
    * 不可分割(ch24會細講)
        **two-phase-commit rpotocol(2PC)**
        一個transaction裡 分成兩階段
        第一階段 跑完各自的site
        第二階段 協調者根據每個人是否跑完決定此transaction是否成功

### Cloud-based Services（雲端運算）
* 視需求提供
    需求少 -> 少租一點電腦
    需求多 -> 多租一點電腦
    優點： 可在短時間內快速擴充 不用時再還回去

* 種類
    ![](https://i.imgur.com/WJu9CBi.png)

    * **Infrastructure as a service**(IaaS)
        可以生`機器`供你使用
        虛擬機器 ex. Amazon
    * **Platform as a service**(PaaS)
        有`平台、開發環境`可以供你使用
        ex. 資料庫(mySQL、PHP)、雲端硬碟
    * **Software as a servic**(SaaS)
        提供`軟體`（像是幫你分析東西之類的）
        ex. email、google document
* 缺點
    * 安全性
    * 網路頻寬(因為雲端都是靠網路)
    
* Application Deployment Alternatives
    ![](https://i.imgur.com/DuDpwCA.png)
    * `Individual Machines`: 一台電腦一個作業系統
    * `Virtual Machines`: 一台電腦兩個作業系統（可能有VM之類的）
    * `Containers`: 一台電腦一個作業系統(因為作業系統很耗記憶體) 但有多個(不同版本之類的)library、自己的IP
        又稱之為 微服務（可以根據需求新增或刪除）
        
    `補: 早期就是儀台機器一個服務(規定輸出入、讓別人來用你)`
    
---

## ch21 Parallel and Distributed Storage

### 背景
因為有需求 且當時硬體開始普及＆價格下降
平行、分散式系統開始出現

* 需求
    1. **儲存大量資料**
        因為web開始興起＆使用者很多＆影音
        資料量以PB(10^15^)來計算

    2. **決策支援（提供訊息供上位者判斷）太耗時**
        像是資料分析探勘(data-mining)
        挖掘trnasaction data(賣出物品)的association rule(關聯性)
        ex. 啤酒、尿布常常被一起購買
        `因為太花時間 所以需要平行處理`

    3. **需要high throughput的transaction**
        雖然每個query都很小 但是很多很多query加起來就很大
        以資料庫的角度來看 新增、刪除、修改等需要快速

    4. **對scalability＆availability的高要求**
        後面詳細說

* 歷史提出的方法
    * 1980/1990s(RDB)
        * distributed database systems(with tens of nodes)
            少、貴的電腦

    * 2000(web出來不久)(Big Data)
        * Distributed file systems(with 1000s of nodes)
            很多的大物件 ex. web log、影音檔案等
            只考慮新增資料（通常不太會修改）
        
        * Distributed data storage(with 1000s of nodes)
            更多的小物件 ex. 貼文、email、文書資料等
            考慮新增修改刪除
            
    * 2010(想成RDB)
        * distributed database systems(with 1000s of nodes)
        
---
### IO Parallelism

為了加快IO的速度
把relation切割放在多個硬碟上

#### 分割法
* **Horizontal partitioning**（水平）
    ![](https://i.imgur.com/PsYflYC.png)
    早期可能會以某個屬性的值來分
    `沒講的話就是說這個`
* **Vertical partitioning**（垂直）
    ![](https://i.imgur.com/0wIgNfy.png)
    因為要合併 所以primary key(之類的)兩邊都要有
    `r(A, B, C, D) -> r(A, B) & r(A, C, D)`

#### 水平分割法的種類
假設node = n
* **round-robin**
    第i個tuple 會放在第i % n 個電腦（可以達到平均分配到n個裡）
    資料庫查根據屬性查詢 常常需要全找
    ![](https://i.imgur.com/VeftSjp.png)

* **Hash partitioning**
    把屬性的值丟到hash函數裡 hash的回傳值介於0~n-1之間
    SQL where=某個值的話 就可以找很快
    但也常常查某個範圍 範圍很大的話需要花很多時間
* **Range partitioning**
    Vector = [V~0~, V~1~, …, V~n-2~]，切出n個範圍
    ![](https://i.imgur.com/u4DtvEN.png)

-

* 針對簡單的query來比較
    * **要讀到整個relation**
        * Round-robin（平均分散）
        * Hash partition（若hash平均分散的話）
        * Range partitioning（若vector設計的夠好）
    * **Point queries**(ex. r.A = 25)
        * Hash partitioning
        * Range partitioning（也算快）
    * **Range queries** (ex. 10 <= r.A <25)
        * Hash partitioning（若範圍小，且知道範圍內的每個值）
        * Range partitioning（但有可能有execution skew，超多資量集中在少數的node，會塞車）


* 資料大小
    * 小資料
        若沒什麼人要讀，就給一個node就好
        若很多人要讀，每個disk上都複製一份
    * 中資料
        假設有m個blocks, n個disks，用min(m, n)個disk
        `Ex. m=100, n=5 -> 平均分在5個disks`
        `Ex. m = 10, n=20 -> 10個disk（一個disk放一個block）`
    * 大資料
        就是上面那些分割法

#### skew
* 種類
    * **Data-distribution skew**（資料偏斜）
        某幾個node的資料特別多
        原因
        * **attribute-value skew**
            某個值特別多
        * **partition skew**
            vector的值沒有取好
    * **Execution skew**
        資料雖然分的平均 但query只找最近幾天的

* 如何避免skew
    * **balanced partitioning vector**
        * 依attr的值來排序`（V[0] = 第(data數/n)*1+1個, V[1] = 第(data數/n)*2+1個, ...）`
            若某個值重複太多 這個方法就沒什麼用了
            `（V[0], V[1], V[2]都是同一個值）`

            資料太多 排序太花時間 
            `可能就隨機挑幾個來排序就好`
        * 長條圖(依對應的值做分割)
            * **equi-width**（等寬）
                ![](https://i.imgur.com/FvwaRCp.png)

            * **Equi-depth**（等高）
                每n次
                ex.（1～4歲、4～10歲...）
    * **Virtual node partitioning**
        ![](https://i.imgur.com/zLhHpAE.png)

        因為資料放進去之後 很難再移動，這樣做彈性大
        `資料列-> virtual node`
        `virtual node->真正的node`

        Virtual node怎麼對到真正的node?
            1. **Round-robin**
            2. **Mapping table**
            `可能用hash、或自己指定`
            `用table把對應關係記起來`

        elasticity of storage大
        `增加、減少真正的node 只需要處理對應關係`
    * **Dynamic Repartitioning**
        `因virtual node能做到的還是有限`
        這個連virtual node都可以改變
        ![](https://i.imgur.com/rOCXrWY.png)

        ⚠️ Virtual 有太多值了 -> tablet split ⚠️
        ⚠️ 發現Node1太累 -> tablet move ⚠️
        `Ps. 一個tablet大約100~200MB`

---

### Replication（備份）
優點: availability
缺點: 要考慮一致性

* 一個tablet 對到多個node
    * ex. Tablet0 -> node0, node1
* 放置地點
    * **Replication within a data center**（同一個機器放兩個）
    * **Replication across data centers**（兩個放在不同地方）
* 一致性（細節在ch23講）
    * 每個備份都有一個master 更新都送到master 再由master送出去
    * 壞掉過後 希望拿到最新的 可以讀master就好
* Transaction（細節在ch23講）
    * Two-phase commit
        * 大家回報給組長 由組長做最後決定
    * Persistent messaging（又稱eventual consistency最終會一樣）
        * update以訊息傳過去（非同步）
        * ex. 5. Commit, R1 6.收到 R2 10.收到
        * 用於網路 資料晚一點收到沒關係(ex. ig的貼文)
    * Consensus protocols
        * 大家投票決定




---
### Distributed File Systems
* **HDFS**（先去看ch10）
    * 基本介紹
        * master(NameNode)
            就像metadata
        * chunk servers
            負責讀寫大量資料
        * chunks replicated
            資料會備份到3台機器上 由master來管理
        * replication
            備份放在同一個data center

        `一個block大約64MB 預設是3個DataNodes`
        ![](https://i.imgur.com/VoiASeW.png)

    * 限制
        * bottle neck
            因為都要去NameNode問
            所以metadata都放在記憶體來避免IO
            `記憶體的大小會影響藏放檔案的數量`
        * 不適合存超大量的資料
        * 對一致性沒有很嚴謹
            一開始認為不太會改檔案
            有人會把當作儲存資料的地方
    
* **sharding**（先去看ch10）
    routing、備份由應用程式做
* **key value**（先去看ch10）
    routing、備份自己做
    是半結構（結構複雜、查詢就只能簡單）
      

|  | 分散式的資料儲存 | RDB |
| -------- | -------- | -------- |
|relational model|有彈性|固定|
|參照完整性|不支援|支援|
|query|簡單|複雜|

#### 底層的儲存
* RDB（以row為主的儲存 用一個一個的tuple）
* noSQL(以cloumn為主的儲存 用record_id＆attr的值)
    直接用範例說明
    URL前面相同的會放在一起
    
---

## ch23 Parallel and Distributed Transaction Processing

### Distributed Transactions

#### 分散式系統可能失敗的原因
* 某一台電腦壞掉
* 無法傳送訊息（網路壞掉之類的）
* network partition(只要網路壞掉 兩邊就會無法溝通)

#### transaction的處理

`複習:`
`local transaction(發請求的＆資料在同個地方)` //因為只有一個資料庫
`global transaction(發請求的＆資料在不同地方)`

![](https://i.imgur.com/38WHoRR.png)

step1. `transaction在某台電腦開始執行(會先丟給coordinator)`
step2. `coordinator把多個subtransaction丟到資料所在的電腦`
step3. `manager接收到subtransaction就執行（一樣會紀錄log）`
step4. `subtransaction執行結束 manger向coordinator回報`
step5. `coordinator根據大家的狀況決定commit還是abort`

`fail-stop`: 若有電腦壞掉 他就自己壞掉 不會出去干擾別人
`後面講的都是假設在這種情況下`

* commit protocols(希望維持不可分割性) 
    * **2PC**
        * 正常流程
            ![](https://i.imgur.com/0V9Vvp5.png)
            * step1. 問大家
                C~i~ 紀錄 ==**<prepare T>**== 且送至stable storage
                送**prepare T**這個訊息給每個執行的電腦

                如果失敗 log records ==**<no T>**== 送**abort T**給C~i~
                如果成功 log records ==**<ready T>**== 送**ready T**給C~i~
                且需送至stable storage

            * step2. 做決定
                如果全部都ready -> C~i~紀錄 ==**<commit T>**==
                只要有人abort -> C~i~紀錄 ==**<abort T>**==
                紀錄完存到stable storage
                通知大家
                大家紀錄 ==**<commit T>**== 或 ==**<abort T>**==
                做該做的事(redo、undo)
                
        * site壞掉(非coordinator)
            S~k~斷電 恢復供電後
            先去看`log record`
            1. 看到 **<commit T>** -> **redo(T)**
            2. 看到 **<abort T>** -> **undo(T)**
            3. 看到 **<ready T>** -> 去問C~i~決定是啥 -> 做對應的事情
            4. 什麼都沒看到 -> **undo(T)**
            
        * coordinator壞掉
            1. 若其中一台收到commit -> 大家都commit
            2. 若其中一台收到abort -> 大家都abort
            3. 沒有人收到commit或abort＆有人沒收到ready T -> 大家abort
            4. 沒有人收到commit或abort＆所有人都有收到ready T -> 等C~i~恢復 等他送訊息
                
            ==**blocking problem**==（2PC最大的問題）
            情況4的話
            site手上的data item(因為有lock)其他人就不能用
            若C~i~又要很久才能恢復
            這會是一個大問題

    * **consensus protocols**（為了解決blocking problem）
        由一些電腦來決定最後是commit還是abort
        
        所有人要回應C~i~自己是commit還是abort
        所以如果最終要commit 要有夠多的人commit?
        
        1. C~i~在還沒告訴所有人之前就壞掉
            副班長先去檢查
            如果C~i~已經做決定 -> 發送訊息給大家
            如果C~i~還沒做決定 -> 副班長自己去調查、自己決定
        2. 如果C~i~恢復後 發現他跟副班長的決定不一致 -> 重新consensus
            
        問題1: 如果是共識決 為什麼還有coordinator
    
    * **Persistent Messaging**（有時需要人為處理）
        因為2PC太嚴格 要等到大家都成功才commit
        這個的話 可以自己先commit
        然後傳訊息給你 告訴你我做了什麼 要求你做對應的動作

        ![](https://i.imgur.com/fRd0JzU.png)


        -> **atomicity issue**
        只要S commit R也要commit
        只要R abort S也要abort
        * 正常情況
            `如果R活著`
            S已經commit 就要確保訊息有送給R（正好一次）
            而且R「一定也要commit」

            `如果R壞掉`
            S已經commit 那麼S就要undo ==都已經commit是要怎麼undo==

        * 例外處理
            雖然B活著 但是B abort
            這時候A也必須要 abort
            但如果A沒辦法abort
            就需要人類介入處理
    
---

### Replication（備份）

`Robustness: 即使有一些節點失敗 系統仍然可以執行`

* 一致性
    只要確保每次用都是最新的即可
    **linearizability**:
    每個data item的operation都可以畫成一個時間軸
    每次的operation 都要使用上一個結束的operation的值
    
* protocol
    原本策略 -> 
    要幹嘛都要拿到所有的lock
    ex. 要更新就大家一起更新 但這樣不好（可能有人會壞掉）
    1. **Primary copy**
        選一個當主要的(primary node)
        每次更新都先更新primary node
        其他的之後再慢慢更新
        
        優點: low overhead（只需要先拿一個lock）`可以把overhead想成是成本`
        缺點: primary壞掉 就要馬上去找另一個當作primary
        
    2. **Majority protocol**
        只要大部分可以更新 就更新
        
        優點: 有彈性 可接受某些電腦壞掉
        缺點: overhead（要拿多個lock、dealock等）
        像是就算只是read也要取得很多lock
        
        **處理Failure**
        給每個data item一個version number
        讀 -> 要lock的時候順便要version number 用version number最大的
        寫 -> 寫的時候 順便把version number + 1
        也可以順便更新其他電腦的data item
        
    3. **Biased protocol**
        把shared＆exclusive分開
        * shared lock -> 只要取得一個lock就好
        * exclusive lock -> 要取得目前活著的所有lock
        
        **處理Failure**
        問題 當壞掉的電腦復活後
        裡面的值都是舊的
        `老師沒講怎麼解決 他說用majority做一個精神（？）是指每個都這樣嗎？`
        
    4. **Quorum(法定人數) consensus**
        給每台電腦權重(weight) 也要分成讀＆寫
        `W`: 每台電腦的權重
        `S`: 所有權中的和
        Q~w~: write quorum（會給你式子算 ex. 2*Q~w~ > S）
        Q~r~: read quorum（會給你式子算 ex. Q~r~+Q~w~ > S）
        ps. 式子都是自己決定的 可以調整
        
        如果lock成功 total+=weight
        如果total>Q~r~ -> 可以讀
        如果total>Q~w~ -> 可以寫
        
**BASE**(Basically Available, Soft state, Eventual consistency)
有些no SQL的比起傳統的ACID 他們支援的是BASE
Basically Available: 基本上 資料都可以取得
Soft state: 資料在某些時間可能不一致
Eventual consistency: 最終一定會一致