目錄
A: Algorithm猾封，每周至少做一道 Leetcode
R: Review他嫡，閱讀并點評至少一篇英文文章
T: Tips昔逗，學(xué)習(xí)至少一個技術(shù)技巧
S: Share，分享一篇有觀點和思考的技術(shù)文章
? 堅持一個月吃頓火鍋兒绸硕！?
第二周（11-30 至 12-06）
A:
題目：多數(shù)元素
很容易想到的是排序取中位數(shù)，這個是 O(nlog(n)) 的魂毁，更好的解決辦法是摩爾投票法玻佩，即對拼消耗，O(n) 時間復(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;
}
}
題目：搜索二維矩陣 ||
同簡單夺蛇，從二維矩陣的右上角開始找，比目標(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 項目的依賴關(guān)系圖。其實核心就是寫了一個 Gradle Task闻镶，生成了一個 .dot 文件甚脉，dot 即圖片描述語言，腳本中還涉及把 .dot 文件轉(zhuǎn)化成 png 的操作铆农，用到的是 Graphviz牺氨，在安裝完這個軟件之后狡耻，還需要你的 AS 里面安裝一個 State Art 插件，然后就可以直接運行該 Task 了猴凹。
T:
如何提升 TCP 三次握手的性能夷狰？
TCP 是一個可以雙向傳輸?shù)娜p工協(xié)議，所以需要經(jīng)過三次握手才能建立連接郊霎。三次握手在一個 HTTP 請求中的平均時間占比在 10% 以上沼头，在網(wǎng)絡(luò)狀況不佳、高并發(fā)或者遭遇 SYN 泛洪攻擊等場景中书劝，如果不能正確的調(diào)整三次握手中的參數(shù)进倍，就會對性能有很大的影響。
首先看客戶端的優(yōu)化购对，客戶端在發(fā)出 SYN 報文后但沒有收到對端 ACK 時猾昆，客戶端會重發(fā) SYN，重試的次數(shù)由 tcp_syn_retries 參數(shù)控制骡苞，默認(rèn)是 6 次：
net.ipv4.tcp_syn_retries = 6
第 1 次重試發(fā)生在 1 秒鐘后垂蜗，接著會以翻倍的方式在第 2、4烙如、8么抗、16、32 秒共做 6 次重試亚铁，最后一次重試會等待 64 秒，如果仍然沒有返回 ACK螟加，才會終止三次握手徘溢。所以說總耗時是 127 秒，超過 2 分鐘捆探。
如果這是一臺有明確任務(wù)的服務(wù)器然爆，就可以根據(jù)網(wǎng)絡(luò)的穩(wěn)定性和目標(biāo)服務(wù)器的繁忙程度修改重試次數(shù)，調(diào)整客戶端的三次握手時間上限黍图。比如內(nèi)網(wǎng)中通訊時曾雕，就可以適當(dāng)調(diào)低重試次數(shù)，盡快的把錯誤暴露給應(yīng)用程序助被。
再看服務(wù)端的優(yōu)化剖张，服務(wù)端在收到 SYN 報文并回復(fù) SYN+ACK 時，此時服務(wù)端會把該連接信息放入一個 SYN 版連接隊列里面揩环，當(dāng)這個隊列溢出時搔弄，服務(wù)端將無法在建立新的連接。所以此時可以修改 SYN 半連接隊列的大小的丰滑，即：
net.ipv4.tcp_max_syn_backlog = 1024
如果 SYN 半連接隊列已滿顾犹，只能丟棄連接嗎？并不是這樣，開啟 syncookies 功能就可以在不使用 SYN 隊列的情況下成功建立連接炫刷。syncoookie 是這么做的：服務(wù)端根據(jù)當(dāng)前狀態(tài)計算出一個值擎宝，放在已方發(fā)出的 SYN+ACK 報文中發(fā)出，當(dāng)客戶端返回 ACK 報文時浑玛，取出該值驗證认臊，如果合法，就認(rèn)為連接建立成功锄奢。
Linux 下怎樣開啟 syncookies 功能呢失晴？修改 top_syncookies 參數(shù)即可，其中值為 0 時表示關(guān)閉該功能拘央，2 表示無條件開啟功能涂屁，而 1 則表示僅當(dāng) SYN 半連接隊列放不下時再啟用它。由于 syncookie 僅用于應(yīng)對 SYN 泛洪攻擊灰伟，這種方式建立的連接拆又，許多 TCP 特性都無法使用，所以栏账，應(yīng)當(dāng)把 tcp_syncookies 設(shè)置為 1帖族，僅在隊列滿時再啟用：
net.ipv4.tcp_syncookies = 1
當(dāng)服務(wù)端發(fā)送完 SYN+ACK 報文后，但是卻為收到對端 ACK挡爵，這時候服務(wù)端就會重發(fā) SYN+ACK竖般。當(dāng)網(wǎng)絡(luò)繁忙、不穩(wěn)定時茶鹃，報文丟失就會變嚴(yán)重涣雕，此時應(yīng)該調(diào)大重發(fā)次數(shù)，反之則可以調(diào)小重發(fā)次數(shù)闭翩。對應(yīng)的參數(shù)如下：
net.ipv4.tcp_synack_retries = 5
當(dāng)服務(wù)端收到 ACK 后挣郭，內(nèi)核就會把連接從 SYN 半連接隊列中移除，再移入 accept 隊列疗韵，等待進(jìn)程調(diào)用 accept 函數(shù)時再把連接取出來兑障。如果進(jìn)程不能及時的調(diào)用 accept 函數(shù)，就會造成 accept 隊列溢出蕉汪，最終導(dǎo)致建立好的 TCP 連接被丟棄流译。
實際上，丟棄連接只是 Linux 的默認(rèn)行為肤无，我們還可以選擇向客戶端發(fā)送 RST 復(fù)位報文先蒋，告訴客戶端連接已經(jīng)建立失敗。打開這一功能需要將 tcp_abort_on_overflow 參數(shù)設(shè)置為 1宛渐。
不過通常情況下竞漾，應(yīng)該把該參數(shù)設(shè)置為 0眯搭，因為這樣更有利于應(yīng)對突發(fā)流量。
net.ipv4.tcp_abort_on_overflow = 0
舉個例子业岁，當(dāng) accept 隊列滿導(dǎo)致服務(wù)端丟掉了 ACK鳞仙，與此同時，客戶端的連接狀態(tài)卻是 ESTABLISHED笔时，進(jìn)程就會在建立好的連接上發(fā)送請求棍好。只要服務(wù)端沒有為請求回復(fù) ACK，請求就會被多次重發(fā)允耿。如果服務(wù)端上的進(jìn)程只有短暫的繁忙導(dǎo)致 accept 隊列滿借笙，那么當(dāng) accept 隊列有空位時，再次接收到的請求由于含有 ACK较锡，仍然會觸發(fā)服務(wù)端成功建立連接业稼。所以 tcp_abort_on_overflow 設(shè)為 0 可以提高連接建立的成功率，只有你非陈煸蹋肯定 accept 隊列會長期溢出低散，才能設(shè)置為 1 以盡快通知客戶端。
TFO 技術(shù)如何繞過三次握手骡楼？
TFO 即 TCP Fast Open熔号，客戶端可以在首個 SYN 報文中就攜帶請求，這節(jié)省了 1 個 RTT 的時間鸟整。TFO 具體是如何實現(xiàn)的呢引镊？
為了讓客戶端在 SYN 報文中攜帶請求數(shù)據(jù)，必須解決服務(wù)端的信任問題吃嘿。因為此時服務(wù)端的 SYN 報文還沒有發(fā)給客戶端祠乃，客戶端是能夠正常建立連接還未可知，但此時服務(wù)端需要假定連接已經(jīng)建立成功兑燥，并把請求交付給進(jìn)程去處理，所以服務(wù)端必須能夠信任這個客戶端琴拧。
TFO 到底怎樣達(dá)成這一目的呢降瞳？它把通訊分為兩個階段，第一階段為首次建立連接蚓胸，這時走正常的三次握手挣饥，但在客戶端的 SYN 報文會明確的告訴服務(wù)端它想使用 TFO 功能，這樣服務(wù)端會把客戶端 IP 地址用只有自己知道的密鑰加密（比如 AES）沛膳，作為 Cookie 攜帶在返回的 SYN+ACK 報文中扔枫，客戶端收到后會將 Cookie 換存在本地。
之后锹安，如果客戶端再次向服務(wù)端建立連接短荐，就可以在第一個 SYN 報文中攜帶請求數(shù)據(jù)倚舀，同時還要附帶緩存的 Cookie。服務(wù)端收到后忍宋，會用自己的密鑰驗證返回 SYN+ACK痕貌。雖然客戶端收到后還會返回 ACK，但服務(wù)器不等收到 ACK 就可以發(fā)送 HTTP 相應(yīng)了糠排，這就減少了握手帶來的 1 個 RTT 的時間消耗舵稠。
小結(jié)一下，如何優(yōu)化 TCP 的三次握手入宦？我們可以從控制重發(fā)次數(shù)哺徊、調(diào)整連接隊列的大小、開啟 TFO 等思路去著手優(yōu)化乾闰。
S:
How to display your Android project dependency graph in your README file
