# 進階資料庫
期中考範圍
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)
- 圖形表示法
橢圓：物件（主詞或受詞）
長方形：屬性值
線：屬性 或 關聯
ps. ER圖 -> 集合間的關係，這個 -> 物件間的關係
- triple 表示法
用 (主詞, 屬性 or 關聯, 受詞) 來表示
- 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;
```
- 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個大檔案
* **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
### 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
**第一種schedule(T1完再換T2)**
**第二種schedule(T2完再換T1)**
**第三種schedule（穿插的）**
==只要維持一致性即可== 通常都是這種
**第四種schedule（錯誤的例子）**
一開始A+B = 1000+2000 = 3000
最後的A+B = 950+2100 = 3050
不符合一致性
### **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
* 範例2
`因為他不管怎麼轉都無法變成serial schedule`
所以這個schedule不是conflict serializable
### **Testing for Serializability** ==（可能會考）==
* **Precedence graph**
* **圓圈**
代表transactions
* **線（有向的）**
代表存在一組**conflict**的指令
若線是從T1 指到 T2
代表T1先執行，再執行T2
把你要測試的＆Serializability的都畫成圓圈＆線的形式
若兩個長得一樣就代表測試的可以換成Serial Schedule
若是conflict serializability，會形成迴圈
* **topological sorting**
若Precedence graph沒有迴圈
則可以透過 topological化成以下形式
`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：成功就成功，不能事後再反悔
```
若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
若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
上面是別人的
當別人在寫的時候，不論你提什麼要求都會被拒絕
若別人在讀的時候，你只能讀不能寫
若你request但現在沒辦法給你，你就只能等！！
**Schedule With Lock Grants**
`這個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. 不會有互等的狀況，一定是小孩等爸爸
---
### Deadlock handling
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
`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之前）
---
### Recovery and Atomicity
之前說transaction須遵守ACID
為了達到Atomicity(ACID的A)(要就全做 不然就不做)
因為不做的話需要Recovery
接下來要講為了Recovery的相關事項
* 較少使用的替代方案
* **shadow-copy**
當你要編輯時，先複製一份原本的（編輯複製的）
如果編輯成功，用編輯完成的（複製的那個）
如果編輯失敗，用原本的就行
* **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` ⚠️
* 紀錄的範例
`所有transaction都紀錄在log裡面`
**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演算法的完整敘述
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
補：
`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、資料，還要系統是好的）
`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 標準化
* 架構
* **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`
* scale up
問題變n倍複雜 看時間能不能變快
公式定義: `scaleup = 小系統小問題花的時間/大系統大問題花的時間`
最佳情況 `scaleup = 1`
又可以細分為兩類
* 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) ]==
* Gustafson’s law（scaledup的上限）
==1 / [ p + n(1-p) ]==
* 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
:::
* **網路架構**
* **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: 每個都連到很多個
* **資料庫架構**
`P`: 處理器
`M`: 記憶體
`圓柱`: 硬碟(disk)
* **shared memory**
**共享記憶體＆disk**
==！處理器之間的通訊非常快！==
（P1叫P2做事可以很快 因為都是到同一個地方做事）
* bus -> network
每個CPU有自己的記憶體 也可以拿到別人的記憶體
P1 拿 P3會比較慢（跟拿自己的比起來） 稱之為`NUMA`
補: `bus大約只能64~128個處理器(一個在跑 其他就不能跑)`
* 速度仍然不夠快 -> 加上==cache==
一個多核心的處理器
每個core都有自己的cache
L1最快但最小...以此類推
傳輸的單位: `cache line（大約是64 Bytes）`
* **shared disk**
**只共享disk**
`優點`: 若處理器壞掉 影響不會太大（因為資料在硬碟 可以換其他處理器做）
因此又稱之為 ==**fault-tolerance**==（容錯）的架構
`缺點`: 只要有共享就有bottle neck(卡在bus那)
所以用網路 讓他快一點
而且現在電腦不一定放在硬碟(大量的資料)旁邊 通常用網路(LAN)連接
* **shared nothing**
什麼都不共享
溝通比較慢 因為都要透過網路來溝通
`RDMA`: 拿自己的東西非常快(就在自家後院)
`non-local disk access`: 彼此間溝通就比較耗時
* **hierarchical**
混合的來做(可以自己設計)
top-level(shared nothing)下面接三個子系統(shared memory)
---
### Distributed Systems
再次說明
`平行`強調 很多人(process)一起分擔工作
`分散`強調 資料分散在很多地方
`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（雲端運算）
* 視需求提供
需求少 -> 少租一點電腦
需求多 -> 多租一點電腦
優點： 可在短時間內快速擴充 不用時再還回去
* 種類
* **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
* `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**（水平）
早期可能會以某個屬性的值來分
`沒講的話就是說這個`
* **Vertical partitioning**（垂直）
因為要合併 所以primary key(之類的)兩邊都要有
`r(A, B, C, D) -> r(A, B) & r(A, C, D)`
#### 水平分割法的種類
假設node = n
* **round-robin**
第i個tuple 會放在第i % n 個電腦（可以達到平均分配到n個裡）
資料庫查根據屬性查詢 常常需要全找
* **Hash partitioning**
把屬性的值丟到hash函數裡 hash的回傳值介於0~n-1之間
SQL where=某個值的話 就可以找很快
但也常常查某個範圍 範圍很大的話需要花很多時間
* **Range partitioning**
Vector = [V~0~, V~1~, …, V~n-2~]，切出n個範圍
-
* 針對簡單的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**（等寬）
* **Equi-depth**（等高）
每n次
ex.（1～4歲、4～10歲...）
* **Virtual node partitioning**
因為資料放進去之後 很難再移動，這樣做彈性大
`資料列-> 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都可以改變
⚠️ 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`
* 限制
* 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(發請求的＆資料在不同地方)`
step1. `transaction在某台電腦開始執行(會先丟給coordinator)`
step2. `coordinator把多個subtransaction丟到資料所在的電腦`
step3. `manager接收到subtransaction就執行（一樣會紀錄log）`
step4. `subtransaction執行結束 manger向coordinator回報`
step5. `coordinator根據大家的狀況決定commit還是abort`
`fail-stop`: 若有電腦壞掉 他就自己壞掉 不會出去干擾別人
`後面講的都是假設在這種情況下`
* commit protocols(希望維持不可分割性)
* **2PC**
* 正常流程
* 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
然後傳訊息給你 告訴你我做了什麼 要求你做對應的動作
-> **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: 最終一定會一致
Sign in with Wallet
Connect another wallet