目錄
A: Algorithm，每周至少做一道 Leetcode
R: Review，閱讀并點(diǎn)評(píng)至少一篇英文文章
T: Tips，學(xué)習(xí)至少一個(gè)技術(shù)技巧
S: Share，分享一篇有觀點(diǎn)和思考的技術(shù)文章
? 堅(jiān)持一個(gè)月吃頓火鍋兒！?
第二周（11-30 至 12-06）
A:
題目：多數(shù)元素
很容易想到的是排序取中位數(shù)，這個(gè)是 O(nlog(n)) 的，更好的解決辦法是摩爾投票法，即對(duì)拼消耗，O(n) 時(shí)間復(fù)雜度。
class Solution {
public int majorityElement(int[] nums) {
int result = nums[0];
int mod = 1;
for (int i = 1; i < nums.length; i++) {
if (result == nums[i]) {
mod++;
} else if (--mod == 0) {
result = nums[i];
mod = 1;
}
}
return result;
}
}
題目：搜索二維矩陣 ||
同簡(jiǎn)單，從二維矩陣的右上角開始找，比目標(biāo)值大就往左查詢，小就往下。
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int i = 0, j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
int num = matrix[i][j];
if (num < target) {
i++;
} else if (num > target) {
j--;
} else {
return true;
}
}
return false;
}
}
R:
How to display your Android project dependency graph in your README file
這篇文章講的是可以在你的 Github README 文件里面展示 Android 項(xiàng)目的依賴關(guān)系圖。其實(shí)核心就是寫了一個(gè) Gradle Task，生成了一個(gè) .dot 文件，dot 即圖片描述語(yǔ)言，腳本中還涉及把 .dot 文件轉(zhuǎn)化成 png 的操作，用到的是 Graphviz，在安裝完這個(gè)軟件之后，還需要你的 AS 里面安裝一個(gè) State Art 插件，然后就可以直接運(yùn)行該 Task 了。
T:
如何提升 TCP 三次握手的性能？
TCP 是一個(gè)可以雙向傳輸?shù)娜p工協(xié)議，所以需要經(jīng)過三次握手才能建立連接。三次握手在一個(gè) HTTP 請(qǐng)求中的平均時(shí)間占比在 10% 以上，在網(wǎng)絡(luò)狀況不佳、高并發(fā)或者遭遇 SYN 泛洪攻擊等場(chǎng)景中，如果不能正確的調(diào)整三次握手中的參數(shù)，就會(huì)對(duì)性能有很大的影響。
首先看客戶端的優(yōu)化，客戶端在發(fā)出 SYN 報(bào)文后但沒有收到對(duì)端 ACK 時(shí)，客戶端會(huì)重發(fā) SYN，重試的次數(shù)由 tcp_syn_retries 參數(shù)控制，默認(rèn)是 6 次：
net.ipv4.tcp_syn_retries = 6
第 1 次重試發(fā)生在 1 秒鐘后，接著會(huì)以翻倍的方式在第 2、4、8、16、32 秒共做 6 次重試，最后一次重試會(huì)等待 64 秒，如果仍然沒有返回 ACK，才會(huì)終止三次握手。所以說(shuō)總耗時(shí)是 127 秒，超過 2 分鐘。
如果這是一臺(tái)有明確任務(wù)的服務(wù)器，就可以根據(jù)網(wǎng)絡(luò)的穩(wěn)定性和目標(biāo)服務(wù)器的繁忙程度修改重試次數(shù)，調(diào)整客戶端的三次握手時(shí)間上限。比如內(nèi)網(wǎng)中通訊時(shí)，就可以適當(dāng)調(diào)低重試次數(shù)，盡快的把錯(cuò)誤暴露給應(yīng)用程序。
再看服務(wù)端的優(yōu)化，服務(wù)端在收到 SYN 報(bào)文并回復(fù) SYN+ACK 時(shí)，此時(shí)服務(wù)端會(huì)把該連接信息放入一個(gè) SYN 版連接隊(duì)列里面，當(dāng)這個(gè)隊(duì)列溢出時(shí)，服務(wù)端將無(wú)法在建立新的連接。所以此時(shí)可以修改 SYN 半連接隊(duì)列的大小的，即：
net.ipv4.tcp_max_syn_backlog = 1024
如果 SYN 半連接隊(duì)列已滿，只能丟棄連接嗎？并不是這樣，開啟 syncookies 功能就可以在不使用 SYN 隊(duì)列的情況下成功建立連接。syncoookie 是這么做的：服務(wù)端根據(jù)當(dāng)前狀態(tài)計(jì)算出一個(gè)值，放在已方發(fā)出的 SYN+ACK 報(bào)文中發(fā)出，當(dāng)客戶端返回 ACK 報(bào)文時(shí)，取出該值驗(yàn)證，如果合法，就認(rèn)為連接建立成功。
Linux 下怎樣開啟 syncookies 功能呢？修改 top_syncookies 參數(shù)即可，其中值為 0 時(shí)表示關(guān)閉該功能，2 表示無(wú)條件開啟功能，而 1 則表示僅當(dāng) SYN 半連接隊(duì)列放不下時(shí)再啟用它。由于 syncookie 僅用于應(yīng)對(duì) SYN 泛洪攻擊，這種方式建立的連接，許多 TCP 特性都無(wú)法使用，所以，應(yīng)當(dāng)把 tcp_syncookies 設(shè)置為 1，僅在隊(duì)列滿時(shí)再啟用：
net.ipv4.tcp_syncookies = 1
當(dāng)服務(wù)端發(fā)送完 SYN+ACK 報(bào)文后，但是卻為收到對(duì)端 ACK，這時(shí)候服務(wù)端就會(huì)重發(fā) SYN+ACK。當(dāng)網(wǎng)絡(luò)繁忙、不穩(wěn)定時(shí)，報(bào)文丟失就會(huì)變嚴(yán)重，此時(shí)應(yīng)該調(diào)大重發(fā)次數(shù)，反之則可以調(diào)小重發(fā)次數(shù)。對(duì)應(yīng)的參數(shù)如下：
net.ipv4.tcp_synack_retries = 5
當(dāng)服務(wù)端收到 ACK 后，內(nèi)核就會(huì)把連接從 SYN 半連接隊(duì)列中移除，再移入 accept 隊(duì)列，等待進(jìn)程調(diào)用 accept 函數(shù)時(shí)再把連接取出來(lái)。如果進(jìn)程不能及時(shí)的調(diào)用 accept 函數(shù)，就會(huì)造成 accept 隊(duì)列溢出，最終導(dǎo)致建立好的 TCP 連接被丟棄。
實(shí)際上，丟棄連接只是 Linux 的默認(rèn)行為，我們還可以選擇向客戶端發(fā)送 RST 復(fù)位報(bào)文，告訴客戶端連接已經(jīng)建立失敗。打開這一功能需要將 tcp_abort_on_overflow 參數(shù)設(shè)置為 1。
不過通常情況下，應(yīng)該把該參數(shù)設(shè)置為 0，因?yàn)檫@樣更有利于應(yīng)對(duì)突發(fā)流量。
net.ipv4.tcp_abort_on_overflow = 0
舉個(gè)例子，當(dāng) accept 隊(duì)列滿導(dǎo)致服務(wù)端丟掉了 ACK，與此同時(shí)，客戶端的連接狀態(tài)卻是 ESTABLISHED，進(jìn)程就會(huì)在建立好的連接上發(fā)送請(qǐng)求。只要服務(wù)端沒有為請(qǐng)求回復(fù) ACK，請(qǐng)求就會(huì)被多次重發(fā)。如果服務(wù)端上的進(jìn)程只有短暫的繁忙導(dǎo)致 accept 隊(duì)列滿，那么當(dāng) accept 隊(duì)列有空位時(shí)，再次接收到的請(qǐng)求由于含有 ACK，仍然會(huì)觸發(fā)服務(wù)端成功建立連接。所以 tcp_abort_on_overflow 設(shè)為 0 可以提高連接建立的成功率，只有你非?？隙?accept 隊(duì)列會(huì)長(zhǎng)期溢出，才能設(shè)置為 1 以盡快通知客戶端。
TFO 技術(shù)如何繞過三次握手？
TFO 即 TCP Fast Open，客戶端可以在首個(gè) SYN 報(bào)文中就攜帶請(qǐng)求，這節(jié)省了 1 個(gè) RTT 的時(shí)間。TFO 具體是如何實(shí)現(xiàn)的呢？
為了讓客戶端在 SYN 報(bào)文中攜帶請(qǐng)求數(shù)據(jù)，必須解決服務(wù)端的信任問題。因?yàn)榇藭r(shí)服務(wù)端的 SYN 報(bào)文還沒有發(fā)給客戶端，客戶端是能夠正常建立連接還未可知，但此時(shí)服務(wù)端需要假定連接已經(jīng)建立成功，并把請(qǐng)求交付給進(jìn)程去處理，所以服務(wù)端必須能夠信任這個(gè)客戶端。
TFO 到底怎樣達(dá)成這一目的呢？它把通訊分為兩個(gè)階段，第一階段為首次建立連接，這時(shí)走正常的三次握手，但在客戶端的 SYN 報(bào)文會(huì)明確的告訴服務(wù)端它想使用 TFO 功能，這樣服務(wù)端會(huì)把客戶端 IP 地址用只有自己知道的密鑰加密（比如 AES），作為 Cookie 攜帶在返回的 SYN+ACK 報(bào)文中，客戶端收到后會(huì)將 Cookie 換存在本地。
之后，如果客戶端再次向服務(wù)端建立連接，就可以在第一個(gè) SYN 報(bào)文中攜帶請(qǐng)求數(shù)據(jù)，同時(shí)還要附帶緩存的 Cookie。服務(wù)端收到后，會(huì)用自己的密鑰驗(yàn)證返回 SYN+ACK。雖然客戶端收到后還會(huì)返回 ACK，但服務(wù)器不等收到 ACK 就可以發(fā)送 HTTP 相應(yīng)了，這就減少了握手帶來(lái)的 1 個(gè) RTT 的時(shí)間消耗。
小結(jié)一下，如何優(yōu)化 TCP 的三次握手？我們可以從控制重發(fā)次數(shù)、調(diào)整連接隊(duì)列的大小、開啟 TFO 等思路去著手優(yōu)化。
S:
How to display your Android project dependency graph in your README file
