###### tags: `code`
# 品優科技筆試(網路)
Brian Cho卓宥辰

## 請簡述 TCP 建立到關閉的過程，並簡單舉例。
建立連線：三次握手
斷開連線：四次揮手
由於 TCP 連線是全雙工的，因此每個方向都必須單獨進行關閉。
這個原則是當一方完成它的資料傳送任務後就能傳送一個 FIN 來終止這個方向的連線。

## 請簡述MySQL中myisam與innodb的區別，至少5點。

### myisam
myisam不支持事務，但是每次查詢都是原子的；
myisam支持表級鎖，即每次操作是對整個表加鎖；

#### 存儲表的總行數；
一個 MYISAM 表有三個文件：索引文件、表結構文件、數據文件；
採用菲聚集索引，索引文件的數據域存儲指向數據文件的指針。輔索引與主索引
基本一致，但是輔索引不用保證唯一性。

### InnoDb：
支持 ACID 的事務，支持事務的四種隔離級別；
支持行級鎖及外鍵約束：因此可以支持寫並發；

#### 不存儲總行數：
一個 InnoDb 引擎存儲在一個文件空間（共享表空間，表大小不受操作系統控制，
一個表可能分佈在多個文件裡），也有可能為多個（設置為獨立表空，表大小受
操作系統文件大小限制，一般為 2G），受操作系統文件大小的限制；
主鍵索引採用聚集索引（索引的數據域存儲數據文件本身），輔索引的數據域存
儲主鍵的值；因此從輔索引查找數據，需要先通過輔索引找到主鍵值，再訪問輔
索引；最好使用自增主鍵，防止插入數據時，為維持 B+樹結構，文件的大調整。

## 請描述如何使用 Redis 來做分佈鎖，會用到什麼 api?

1. 加鎖動作
2. 守護線程,鎖自動續期
3. 解鎖動作

## 請列出使用過的 RDBMS 與 NoSQL，並描述兩者差異。

### 使用過
PostgreSQL ,ArandoDB

### 關聯式資料庫(RDBMS)
RDBMS (Relational Database Management System) 又為關聯式資料庫管理系統，意即資料庫是由多個資料表(Table)所組成，並且可以將資料表關聯起來，去連結多個資料表之間的關係。諸如 MySQL, PostgreSQL, MS SQL, … 都是關聯式資料庫。以下列出幾個關聯式資料庫的特點：
由資料表(Table)組成，其中 row 代表一筆資料，column 代表資料欄位名稱
Schema 必須先定義好，並且只接受同樣格式資料的插入與修改。往後如果要修改 schema，必須對於已存在的資料做相對應的處理較為麻煩
可以使用 JOIN 來連結多個資料表，做較複雜的查詢
具備 ACID 特性
使用 SQL(Structured Querying Language) 來管理及查詢資料

### 非關聯式資料庫(NOSQL)
NOSQL(Non-SQL，又為 Not only SQL) 稱為非關聯式資料庫，跟關聯式資料庫不一樣，不需要定義 schema、沒有關聯的關係。諸如 MongoDB, Redis, … 都是非關聯式資料庫的一種。以下為非關聯式資料庫的幾個特點：
資料庫由 collection 組成
collection 中每筆資料為一份 document，document 的資料格式不需一致
以 CAP theorem 為概念設計
常用於分散式雲端系統

## 請說明 Message Queue 的用途，並列出具有其功能的工具。
訊息佇列（Message Queue，簡稱MQ），從字面意思上看，本質是個佇列，FIFO先入先出，只不過佇列中存放的內容是message。
其主要用途：
不同程序 Process 之間
不同執行緒 Thread 之間
不同服務之間 (Microservice)

RabbitMQ , moonmq

## 請描述一個分散式架構系統，並畫出其架構圖。
玩家登入與遊玩服務做分散設計

graph LR
GS[GameService]
GS2[GameService2]
GM[Login]
C[Client]

C-->GM
GM-->GS
GM-->GS2
GM-->DB
GS-->DB
GS2-->DB

### 承6，請描述在架構中如何設計跨服務的 GUID

GUID的總數也足夠大，達到了2128（3.4×1038）個，所以隨機生成兩個相同GUID的可能性是非常小的

### 承6，請描述在該架構中，如何處理資料落地時的一致性問題 (e.g. Cache 與 Database)
Consistency (一致性)
站在 client 的角度來觀察系統的行為和特徵

從 client 的讀寫角度來描述資料一致性

在事務執行過程中，系統其實處於一個不一致的狀態，不同的節點的資料並不完全一致，但 client 讀操作能夠獲取最新的寫結果就沒有問題

Availability (可用性)
只有非故障節點才能滿足可用性要求，如果節點本身就故障了，發給節點的請求不一定能得到一個響應

不能超時、不能出錯，結果是合理的(但結果有可能因為資料尚未同步完整，導致資料是不正確的)

Partition Tolerance (分區容忍性)
只有返回 reasonable response 才是 function(可用功能)，而 function 強調”發揮作用” & “履行職責”

即發生了分區現象，不管是什麼原因，可能是網路封包遺失，也可能是連接中斷，還可能是擁塞，只要導致了網路分區，就通通算在裡面

### 承6，請描述在該架構中，所出現的併發情境及可能產生的問題，提出對應的解決方案
高併發登入時,會壅塞登入系統,可以做附載平衡系統處理

### 承6，請以架構中的任一 Service 為例，如何實現 Graceful shutdown 與災難恢復
1. 單一Service,藉由context來Graceful shutdown相關線程
2. 定期或即時快取系統快照至redis或其他外部儲存設備
3. 如果需要災難恢復,則根據快照恢復系統

## 排序過的 N 個正整數中，如何使用二元搜尋法找到其中的一個數？

e.g. [3, 5, 6, 7, 8, 10]，找到 5。

func Search(n int, f func(int) bool) int {
	// Define f(-1) == false and f(n) == true.
	// Invariant: f(i-1) == false, f(j) == true.
	i, j := 0, n
	for i < j {
		h := int(uint(i+j) >> 1) // avoid overflow when computing h
		// i ≤ h < j
		if !f(h) {
			i = h + 1 // preserves f(i-1) == false
		} else {
			j = h // preserves f(j) == true
		}
	}
	// i == j, f(i-1) == false, and f(j) (= f(i)) == true  =>  answer is i.
	return i
}

## 在一個產生隨機 1 或 0 陣列中，如何簡化隨機的次數？

e.g. [30%, 70%] 產生兩個數，
第一個數有 30% 機率為 0，70 % 為 1
第二個數有 70% 機率為 1，30% 為 0
如何只用一次亂數就產生出需要的陣列

$rng \in [0,2^{32}-1]$
rng1 = rng&0x0000FFFF
rng2 = (rng&0xFFFF0000)>>16
$rng1,rng2 \in [0,2^{16}-1]$
根據rng1,rng2在2^16的占比即可決定隨機數列