算法：

1.提取二進(jìn)制位最右邊的

r = i & (~i + 1)

2.樹上兩個節(jié)點(diǎn)最遠(yuǎn)距離，先考慮頭結(jié)點(diǎn)參與不參與。

3.暴力遞歸改dp。

1.確定暴力遞歸方式。

2.改記憶化搜索

3.嚴(yán)格表方式：

分析可變參數(shù)變化范圍，參數(shù)數(shù)量決定表維度、

標(biāo)出計算的終止位置、

標(biāo)出不用計算直接出答案的位置，根據(jù)暴力遞歸中的basecase、

推出普遍位置如何依賴其他位置、

確定依次計算的順序，跟遞歸順序一致。

4.得到精致版dp，如斜率優(yōu)化。

4.動態(tài)規(guī)劃嘗試模型

從左往右，范圍嘗試

5.嘗試的好壞：

1.單參的維度（如int類型和數(shù)組）。決定參數(shù)范圍

2.參數(shù)的個數(shù)

5.有序表包括：

1.紅黑樹、2.avl樹，3.sb樹，4.跳表

6.繩子問題用滑動窗口

7.打表法。

循環(huán)參數(shù)，暴力打印結(jié)果，根據(jù)結(jié)果找到規(guī)律。憋出表達(dá)式。

8.預(yù)處理

9.二維表問題關(guān)注宏觀設(shè)計，不要關(guān)心局部實(shí)現(xiàn)。

10.兩個隊列可以實(shí)現(xiàn)棧，兩個?？梢詫?shí)現(xiàn)隊列。

11.動態(tài)規(guī)劃dp表空間壓縮技巧。

12.菲波拉契數(shù)列復(fù)雜度從n優(yōu)化到logn。

相同類型問題通用。

幾階問題會生成幾階的行列式。

計算某數(shù)的次方。降為logn。

13.注意數(shù)字越界

math.MaxInt

14.假設(shè)答案法。

假設(shè)答案，用盡量簡單的流程找到答案。

15.壓縮數(shù)組

看到子矩陣，先想子數(shù)組。

16.優(yōu)化動態(tài)規(guī)劃

從數(shù)據(jù)狀況入手，從問題本身入手。

17.遞歸死循環(huán)，要根據(jù)實(shí)際增加平凡邊界。

18.看到子串和子數(shù)組問題，就想以每個字符結(jié)尾會怎樣。

19.舍棄可能性

20.dp斜率優(yōu)化，當(dāng)有枚舉行為時，使用臨近格子的值代替枚舉行為。（湊面值問題）

21.尋找等長有序的兩個數(shù)組上中位數(shù)。

22.約瑟夫環(huán)問題,可推理數(shù)學(xué)公式：老的編號=（新的編號 + m -1）% i + 1

m：數(shù)到哪個編號淘汰

i：本輪一共多少人

23.有序表增刪改查都是O(logn)

24.有單調(diào)性用滑動窗口。無單調(diào)性用 前綴和 map

25.動態(tài)規(guī)劃壓縮技巧，從dp表壓縮到數(shù)組，從數(shù)組壓縮到變量。

26.嘗試模型

從左往右、范圍上嘗試、兩個字符串對應(yīng)

范圍嘗試模型，重點(diǎn)討論開頭和結(jié)尾

范圍嘗試模型指在這樣的可能性分類下，能不能把整個域上的問題解決。

從i開始到j(luò)結(jié)尾的可能性討論下，能不能解決該問題。

一般來說子序列問題。

27.bfprt算法

28.如果沒有枚舉行為，停留在記憶化搜索就行，如果有，則改為dp表，嘗試進(jìn)行斜率優(yōu)化。

29.二叉樹的遞歸套路，父節(jié)點(diǎn)找左右子樹要信息，往上傳遞。

30.完美洗牌問題

abcde123字符串，原地變?yōu)?23 abcde：

abcde逆序，變?yōu)閑dcba；123逆序變?yōu)?21；整體逆序，變?yōu)?23abcde.

31.遞歸大問題調(diào)小問題，一定要保證，大問題所做決策的所有影響都已經(jīng)體現(xiàn)在小問題的參數(shù)上了。讓小問題再決策時有信息可用。（無后效性遞歸）

32.arr[start] 到 arr[i]的異或和 = arr[0] 到 arr[i] 的異或和 異或 arr[0] 到 arr[start] 的異或和。

33.前綴樹

34.不會碰到的遞歸狀態(tài)，dp填表的時候別填。

觀察好，哪些位置不需要填。

初始位置根據(jù)basecase填好，終止位置是哪個。

普遍位置怎么依賴，規(guī)定好填寫順序。

35.滑動窗口+負(fù)債表

36.二維圖形問題，轉(zhuǎn)為一維線段問題求解。

golang：

map：

1.k是可比較類型，切片，func和map是不可比較的。struct中至少有一個字段是可比較的。

2.寫數(shù)據(jù)時如果map沒有初始化，將會panic，刪除時如果沒有初始化，不會報錯。

3.map中有2的整數(shù)次冪的桶數(shù)組。桶中固定裝8個kv，超過放在溢出桶。

4.解決哈希沖突時兼顧了拉鏈法和開放地址法。

5.擴(kuò)容分為增量擴(kuò)容和等量擴(kuò)容。

增量擴(kuò)容閾值：kv數(shù)量/桶數(shù)量 > 6.5時。

等量擴(kuò)容：溢出桶數(shù)量 > 2^B ，B為桶數(shù)組長度的指數(shù)，2^B即桶的個數(shù)。

6.擴(kuò)容時kv的遷移位置是固定的，要么在原位置，要么在原位置+原來桶長度的位置。

7.bucket中不僅存儲kv，還存儲了hash值的高8位。

8.初始化map時，會根據(jù)數(shù)組長度預(yù)先創(chuàng)建溢出桶。

9.如果正在擴(kuò)容狀態(tài)，先判斷舊桶中的標(biāo)識，是否遷移完。如果遷移完，去新桶中查詢。

10.tophash有特殊標(biāo)識，標(biāo)識以后的位置都是空。

11.寫或刪除數(shù)據(jù)時如果正在擴(kuò)容，進(jìn)行輔助擴(kuò)容。

12.寫數(shù)據(jù)時判斷是否需要進(jìn)行增量或等量擴(kuò)容。

13.桶中每個槽位都有tophash，emptyone（當(dāng)前位置被刪除）和emptyrest（之后的位置都為空）。這兩個值都是刪除的時候設(shè)置的。

14.如果正在遷移，先遍歷新桶。

15.遍歷時如果桶正在遷移，按照已經(jīng)遷移完的順序遍歷。

16.根據(jù)oldbucket是否為空判斷是否處于擴(kuò)容階段。

17.如果處于擴(kuò)容階段，每次寫操作會幫助map進(jìn)行擴(kuò)容，1.幫助自己要寫入或刪除的桶，2.幫助索引最小的桶。

18.map不支持并發(fā)操作的主要原因是因?yàn)椴捎玫臐u進(jìn)式擴(kuò)容機(jī)制。

sync.map:

空間換時間

1.sync.map結(jié)構(gòu)包括四個字段，鎖，只讀value，讀寫map，和miss次數(shù)。

2.entry的狀態(tài)有3種，1：正常，2：軟刪除，3：硬刪除。

軟刪除的作用是，如果剛刪的數(shù)據(jù)要重新插入，不需要重新加鎖，只需要對entry的指針進(jìn)行原子操作即可。

3.miss次數(shù)>=寫map的kv數(shù)，把寫map覆蓋讀map。同時把讀map中的amemded flag置為false。寫map置為空。

4.因?yàn)樽x寫map的value存儲的都是指針，所以插入數(shù)據(jù)時，如果kv還存在是軟刪除狀態(tài)，直接使用cas更新，不需要加鎖。

5.插入完數(shù)據(jù)后，如果amended flag是true，就要將寫map拷貝到讀map。

6.插入數(shù)據(jù)時，如果寫map是空，需要從讀map拷貝一份到寫map。

7.寫map拷貝到讀map時是直接全量覆蓋，讀map拷貝到寫map時，需要過濾軟硬刪除的數(shù)據(jù)，量比較重。

8.寫多讀少時性能較低，寫指的是插入，如果是更新性能還好。

9.刪除如果讀map中有，就置為軟刪除態(tài)。如果讀map中沒有且amended flag是true，就在寫map中物理刪除。也會觸發(fā)misscount的增加。

10.執(zhí)行遍歷時，會判斷讀map的數(shù)據(jù)是不是完整的，如果不是，進(jìn)行寫map的覆蓋。

11.軟刪除態(tài)和硬刪除態(tài)：

軟刪除態(tài)是指讀map和寫map都有這個kv，只是v的指針指向軟刪除常量。

硬刪除態(tài)是指讀map中有這個kv，但是寫map沒有。

硬刪除態(tài)只發(fā)生在寫數(shù)據(jù)時，讀map向?qū)憁ap拷貝數(shù)據(jù)，寫map會過濾掉軟硬刪除態(tài)的數(shù)據(jù)，讀map同時要把軟刪除態(tài)變?yōu)橛矂h除態(tài)。

12.通過讀寫map的相互復(fù)制，實(shí)現(xiàn)內(nèi)存回收，避免內(nèi)存泄露。

鎖：

1.鎖沖突解決方式：

阻塞/喚醒屬于悲觀鎖。

自旋+CAS屬于樂觀鎖。

2.golang是兩種結(jié)合。

四次自旋未果之后，陷入阻塞。

或者cpu是單核的，直接進(jìn)行阻塞/喚醒。

當(dāng)前p后面還有待執(zhí)行的g。

3.饑餓模式：

有g(shù)長時間得不到鎖，將搶鎖的流程從非公平模式轉(zhuǎn)到公平模式。

進(jìn)入條件：存在協(xié)程1ms沒有獲取到鎖。

退出條件：沒有阻塞隊列，或者隊列中沒有等待時間超過1ms的協(xié)程。

4.正常模式：阻塞隊列頭部協(xié)程被喚醒，和剛到達(dá)的協(xié)程競爭鎖。如果失敗，重新回到隊列頭部。

5.饑餓模式：新進(jìn)入的協(xié)程不能競爭鎖，只從阻塞隊列遵循先進(jìn)先出。

6.饑餓模式會帶來性能損耗。

7.先嘗試使用cas加鎖。bit整體是0，才會加鎖成功。

8.當(dāng)有等待協(xié)程被喚醒時，判斷是否需要退出饑餓狀態(tài)。

讀寫鎖：

9.添加讀鎖是使用cas方法對readercount+1，如果加完是負(fù)值說明添加失敗，說明有寫鎖。因?yàn)樵谔砑訉戞i時readercount字段會直接減最大值。

10.解鎖時對readercount字段-1，如果減完是負(fù)值，說明有寫鎖在等待，嘗試喚醒。

11.釋放寫鎖之后，喚醒所有讀等待的協(xié)程。

12.如果有寫鎖阻塞，讀鎖也不可獲取。

13.添加寫鎖會把當(dāng)前讀鎖的數(shù)量放到readerwait中，此時readercount也被更新為負(fù)值，之后就不會有讀鎖進(jìn)來。

切片：

1.在作為參數(shù)傳遞時，是進(jìn)行的值拷貝，但是結(jié)構(gòu)體內(nèi)部存儲的是指向數(shù)組的指針。

map也會如此：

?2.切片的結(jié)構(gòu)：

len：邏輯意義上切片中實(shí)際存放了多少個元素。

cap：物理意義上的容量。

3.沒有初始化的切片也可以進(jìn)行append。

4.截取切片為左閉右開。截取完之后的新切片，還是指向同一底層數(shù)組。

5.append操作在容量不足時才會擴(kuò)容。

6.擴(kuò)容時，需要的容量大于老容量的2倍，直接取新容量。

如果容量小于256，翻倍擴(kuò)容。否則每次擴(kuò)容1/4并累加上192，直到大于等于預(yù)期容量。

最后根據(jù)元素類型結(jié)合go的內(nèi)存分配機(jī)制，向上取整，找到合適的容量。

將原數(shù)組拷貝到新數(shù)組，切換指針，完成拷貝。

7.切片的刪除操作只能使用截取拼接實(shí)現(xiàn)。

8.使用系統(tǒng)方法copy可以實(shí)現(xiàn)切片的深拷貝。

?

context：

1.生命周期的終止事件傳遞的單調(diào)性。由上往下傳遞。

2.context.Backgroud()和context.todo()返回的都是空context。

3.cancelContext的核心為開啟一個守護(hù)協(xié)程，在父終止時，終止子。

4.timerContext繼承cancelContext。

5.valueContext只能存儲一個key-value，獲取時如果當(dāng)前Context不存在會一直向父節(jié)點(diǎn)查找。

6.valueContext的讀取代價很高，而且相同的key不會覆蓋，在不同位置會取到不同的value。

gmp：

1.goroutine的?？蓜討B(tài)擴(kuò)縮容。

2.g有自己的運(yùn)行棧，狀態(tài)及任務(wù)函數(shù)。

3.g需要綁定p才能執(zhí)行，在g的視角，p就是他的cpu。

4.goroutine相對協(xié)程最大的優(yōu)化在于，goroutine將協(xié)程和線程的強(qiáng)綁定關(guān)系給釋放了。

5.因?yàn)閜的本地隊列有可能被竊取，所以也會有并發(fā)訪問，不能完全做到無鎖。

6.g結(jié)構(gòu)中存有m的指針，但不是強(qiáng)綁定關(guān)系，受p的調(diào)度。

7.g有自己的生命周期。

8.m中存儲特殊goroutine g0，屬于頂級goroutine。

9.p結(jié)構(gòu)中主要是環(huán)形隊列，和指向首尾的指針，以及下一個可執(zhí)行的g。

10.g0負(fù)責(zé)調(diào)度，執(zhí)行一直在g0到g的切換。

11.調(diào)度類型：

主動調(diào)度：用戶主動調(diào)用runtime.Gosched

被動調(diào)度：如互斥鎖，channel等，后續(xù)需要被喚醒。

正常調(diào)度:

搶占調(diào)度：將由全局監(jiān)控goroutine monitor完成。因?yàn)榇藭r已經(jīng)進(jìn)入內(nèi)核態(tài)，綁定的m也失去控制。

12.schedule負(fù)責(zé)找到下一個要被執(zhí)行的goroutine。

13.先從本地隊列取，取不到從全局隊列取，再嘗試獲取io就緒態(tài)的goroutine，最后從其他隊列竊取一半的goroutine，放到本地隊列。

每第61次，會直接從全局隊列取，避免goroutine饑餓。

14.竊取會嘗試4次，隨機(jī)選擇其他隊列。

15.竊取是撥動對方隊列的頭指針實(shí)現(xiàn)的。

16.用戶主動讓出執(zhí)行權(quán)，會將執(zhí)行權(quán)轉(zhuǎn)移給g0，g0將該goroutine加入全局隊列。

17.全局監(jiān)控goroutine是main方法啟動的，會定時檢查p的狀態(tài)。滿足條件就會進(jìn)行搶占。抽離當(dāng)前的p，為他分配新的m。

channel：

1.讀已關(guān)閉且緩沖區(qū)為空的channel，bool返回false。

2.讀已關(guān)閉channel不會陷入阻塞。

3.向已關(guān)閉channel寫入數(shù)據(jù)會panic。

4.channel的緩沖區(qū)是一個喚醒數(shù)組。

5.空status類型長度為0.

6.往沒有初始化的channel中寫數(shù)據(jù)，goroutine會陷入異常阻塞。

7.channel寫入時，如果有阻塞讀goroutine。會通過memmove element直接把數(shù)據(jù)拷貝給阻塞等待的goroutine。然后喚醒讀取的goroutine。

8.對于用select的情況，在讀寫該陷入goroutine阻塞的情況，轉(zhuǎn)而進(jìn)入自旋。

9.當(dāng)channel被關(guān)閉時，所有阻塞的讀或?qū)慻oroutine都會被喚醒。寫goroutine會panic。

10.避免重復(fù)關(guān)閉channel，可以用sync包的once方法。

11.for range 循環(huán)遍歷channel，只要channel沒關(guān)閉，就會一直讀取。

sync.WaitGroup:

等待聚合模式。

1.本質(zhì)上是并發(fā)計數(shù)器。

2.可以被多個goroutine監(jiān)聽。即wait方法可以被多個goroutine調(diào)用。

3.盡量先調(diào)用add再調(diào)用wait。

4.waitGroup是防拷貝的。指在不同的方法內(nèi)也應(yīng)該傳遞指針，不應(yīng)該傳遞值。

5.done方法本身也是調(diào)用的add，傳-1.

6.如果done之后數(shù)量為0，則喚醒所有wait goroutine。

7.核心還是利用atomic包進(jìn)行計數(shù)。

8.在執(zhí)行過wait之后，add的操作不應(yīng)該并發(fā)執(zhí)行，注意waitgroup的輪次性。

內(nèi)存管理&垃圾回收

1.虛擬內(nèi)存最小單位為頁，物理內(nèi)存最小單位為幀。

2.單位太小會影響效率，太大會造成內(nèi)存碎片。Linux為4kb。

3.golang內(nèi)存分配核心：以空間換時間，一次申請多次復(fù)用。利用多級緩存，實(shí)現(xiàn)無鎖||細(xì)鎖化。

4.golang頁的大小為8kb。

5.mspan為最小的管理單元，大小為8kb的整數(shù)倍。從8到80被劃分成67個類型。

6.mspan會減少外部內(nèi)存碎片，且細(xì)化鎖的粒度。

7.mspan分配的內(nèi)存頁都是連續(xù)的。

8.同等級的mspan屬于同一個mcentral，會被前后指針組織成雙向鏈表。

9.mspan內(nèi)部會使用bitmap輔助尋找空閑的內(nèi)存頁。

10.mspan有隱藏等級0，上不封頂?shù)娜萘俊?/h6>

11.spanClass有8個比特位，高7位對應(yīng)等級，最低位表示nocan。nocan與垃圾回收有關(guān)。

12.每個p對應(yīng)的mcache

13.每個中心緩存mcentral都對應(yīng)一類spanClass。

14.全局堆緩存mheap，負(fù)責(zé)將連續(xù)頁組裝成span。通過heapArena記錄頁和span的映射關(guān)系。

15.通過空閑頁基數(shù)樹輔助快速尋找空閑頁。

16.內(nèi)存不夠時，向操作系統(tǒng)申請，單位是heapArena，即64M。

17.每個基數(shù)樹可以管理16G空間內(nèi)存的占用情況，用于幫助mheap快速找到連續(xù)的未使用的內(nèi)存空間。mheap一共持有2^14個基數(shù)樹。

?分別標(biāo)識，從起點(diǎn)開始最大連續(xù)空閑頁、最大連續(xù)空閑頁、尾端最大連續(xù)空閑頁。

?尋找時相鄰的pallocSum可以拼接。如尾部有3個空閑連續(xù)頁可以和下一個頭部的空閑頁相加。

18.對象類型：

微對象tiny 0-16kb，小對象small 16-32kb，大對象>32kb。

19.內(nèi)存分配函數(shù)也是一個觸發(fā)垃圾回收的入口。

20.gc由守護(hù)goroutine來執(zhí)行。

21.經(jīng)典垃圾回收算法有：標(biāo)記-清楚、標(biāo)記-壓縮、半空間復(fù)制、引用計數(shù)等。

22.golang從1.8之后的垃圾回收算法為：并發(fā)三色標(biāo)記法+混合寫屏障機(jī)制。

黑色：自身可達(dá)且指向?qū)ο髽?biāo)記完成。

灰色：自身可達(dá)但指向?qū)ο笪礃?biāo)記完成。

白色：尚未被標(biāo)記，可能是垃圾。

23.使用廣度優(yōu)先遍歷。

24.分級別的內(nèi)存管理機(jī)制會將垃圾回收產(chǎn)生的碎片控制在內(nèi)部。

25.golang的內(nèi)存逃逸機(jī)制，判斷對象的生命周期如果更長，就會轉(zhuǎn)移到堆上。生命周期短的會被分配到棧上，隨方法結(jié)束被回收。

26.強(qiáng)弱三色不變式。

27.插入寫屏障保證強(qiáng)三色不變式。

28.刪除寫屏障實(shí)現(xiàn)若三色不變式。

29.因?yàn)槠琳嫌行阅軗p耗，所以無法用于棧對象，因棧是輕量級，且變化比較頻繁。

30.混合寫屏障。

31.跨棧的對象會進(jìn)入堆中。

32.gc觸發(fā)分為三類，1是定時觸發(fā)，兩分鐘一次，2是對象分配時達(dá)到堆內(nèi)存閾值，3是手動調(diào)用。

33.標(biāo)記準(zhǔn)備工作

34.開啟的標(biāo)記goroutine數(shù)量占p資源的25%，開啟的標(biāo)記goroutine會放到池子中。

如果p能被4整出，則按p的數(shù)量進(jìn)行計算，否則按執(zhí)行時間計算。

35.stop the world 將所有的p設(shè)置為stop狀態(tài)。

36.開啟寫屏障后，對象會被放入緩沖隊列中，在標(biāo)記完成前取出置灰。

37.p在獲取可執(zhí)行g(shù)oroutine時，會判斷是否在gc階段，保證p只會獲得一次gc goroutine。

38.每種顏色的對象都在一個隊列里。

39.每次彈出一個灰色對象，把他指向的對象變成灰色，把自己變成黑色。

40.標(biāo)記模式：

41.對象是否在使用的標(biāo)識利用mspan的bitmap。

42.標(biāo)記的本質(zhì)是修改mspan中bitmap的標(biāo)記位。

43.掃描根對象是掃描每個goroutine對應(yīng)的方法棧，會根據(jù)函數(shù)的入?yún)⑦M(jìn)行掃描，如果是引用類型，才需要去判斷其指向的對象。非指針類型利用函數(shù)銷毀即可完成回收，指針類型才有可能引用堆上的對象。

44.每個函數(shù)棧都有一個bitmap，來標(biāo)識參數(shù)。

45.通過heapArena可以實(shí)現(xiàn)從頁到mspan的映射。

46.輔助標(biāo)記，當(dāng)goroutine有負(fù)債的時候，會先嘗試從全局資產(chǎn)中竊取，如果竊取不到，就要進(jìn)行輔助標(biāo)記進(jìn)行償還。

47.標(biāo)記終止。

48.清掃goroutine會在main方法中初始化，陷入阻塞，被終止標(biāo)記喚醒，清掃完一個goroutine后就會讓出p，直到所有g(shù)oroutine清掃完成后重新陷入阻塞。

49.重新設(shè)置下次觸發(fā)gc的閾值，閾值可通過用戶設(shè)置，默認(rèn)為100%。

50.將內(nèi)存還給操作系統(tǒng)：runtime會啟動一個回收協(xié)程，以1%cpu的利用率運(yùn)行，持續(xù)回收內(nèi)存。

利用基數(shù)樹輔助查詢。

string：

1.string會被分配到只讀內(nèi)存段，不可被修改，即使切換到unsafe類型。修改會重新分配內(nèi)存。

2.stringstruct包含兩個字段，str和len，str是內(nèi)存的起始位置，len表示長度為多少字節(jié)。

mysql：

1.page頁大小為4kb。mysql一次取16kb。

2.mysiam引擎葉子節(jié)點(diǎn)存儲指針，類似于非聚簇索引，好處在于不會頻繁導(dǎo)致頁分裂，從而降低增刪數(shù)據(jù)成本。

高性能MYSQL(學(xué)習(xí)筆記）—索引篇3_劇組索引-CSDN博客

3.mysql數(shù)據(jù)量到達(dá)兩千萬或三千萬后性能會急劇下降，因?yàn)闃涞纳疃茸兩?#xff0c;io次數(shù)增加。

4.innodb三大特性：1.自適應(yīng)哈希、2.buffer poll、雙寫緩沖區(qū)。

5.自適應(yīng)哈希：1.不需要手動添加，2.底層是散列表，3.只使用等值查詢。

6.buffer pool即緩沖池，由緩存數(shù)據(jù)頁和數(shù)據(jù)塊組成。默認(rèn)大小128m。

7.page頁大小為16kb，數(shù)據(jù)塊為數(shù)據(jù)頁的5%，大概800字節(jié)。

8.mysql通過哈希表判斷數(shù)據(jù)頁是否在緩沖池中。

9.配置頁會根據(jù)狀態(tài)分為三種，通過三個鏈表進(jìn)行管理。

freelist表示空閑緩沖區(qū)，管理freepage，只保存對應(yīng)的控制塊。

flushlist表示需要刷新到磁盤的緩沖區(qū)。管理dirty page。指被修改過的page頁。

lrulist表示正在使用的緩沖區(qū)，用來管理沒有被修改的數(shù)據(jù)頁cleanpage和dirtypage。

10.寫緩沖區(qū)change buff是針對二級索引頁的更新優(yōu)化。占用的buffer pool的空間。

如果要更新的頁沒有在緩存中，就會先把更新操作緩存起來。查詢時如果更新操作在緩存中，就更新到頁離。

11.寫緩沖區(qū)只適用于非唯一索引，因?yàn)槲ㄒ凰饕枰鑫ㄒ恍孕ｒ?yàn)，需要io頁。

12.傳統(tǒng)lru算法存在的問題是，當(dāng)進(jìn)行大范圍數(shù)據(jù)查詢時，會將真正的熱數(shù)據(jù)替換掉。mysql的預(yù)讀也會影響真正的熱數(shù)據(jù)。

13.優(yōu)化過的lru分為熱數(shù)據(jù)和冷數(shù)據(jù)區(qū)，數(shù)據(jù)新進(jìn)來的時候插入到冷數(shù)據(jù)的頭部。

如果存在時間超過1秒鐘，就會將它移動到熱數(shù)據(jù)的頭部。

14.索引最好不要超過五個字段。

15.創(chuàng)建索引的原則。

16.page頁分為幾種：數(shù)據(jù)頁，undo頁，系統(tǒng)頁，事務(wù)數(shù)據(jù)頁等。

fileheader：文件頭，描述頁信息。

pageheader：記錄頁的狀態(tài)。

infimun和supermum records用來記錄比行記錄主鍵都小的值和比行記錄主鍵都大的值。

user records：記錄的是實(shí)際行的記錄。

free space：記錄空閑空間。

page directory：查找page頁記錄的信息。

file trailer：檢測數(shù)據(jù)完整性。

17.頁整體分為三個部分，通用部分（文件頭和文件尾）、存儲記錄空間、索引部分。

通用部分有指向上一頁和下一頁的指針。

18.數(shù)據(jù)頁中的行記錄由記錄頭使用單向鏈表串聯(lián)起來，page directory實(shí)現(xiàn)了目錄功能，可以使用二分查找。

19.mysiam的索引都是指向數(shù)據(jù)存儲的地址的，因此也不存在回表。

20.聚簇索引和非局促索引的區(qū)別。

21.全文索引

22.聯(lián)合索引創(chuàng)建時，mysql會根據(jù)最左邊的字段進(jìn)行排序，所以要查詢時要遵循最左原則。

23.索引下推：在遍歷的過程中進(jìn)行判斷，減少回表次數(shù)。

24.想解決%在左邊的模糊查詢索引失效問題，使用覆蓋索引。會從全文掃描變成全索引掃描。

25.自增id的缺點(diǎn)：高并發(fā)情況下競爭自增鎖。

26.頁插入大小到15/16時就會插入下一個頁，留下的空間為以后更新用。

27.b樹主要用于文件系統(tǒng)及部分?jǐn)?shù)據(jù)庫索引，如mogodb。

28.根節(jié)點(diǎn)保存在內(nèi)存中，其余節(jié)點(diǎn)保存在磁盤。

29.一個b+樹能存儲的最大數(shù)據(jù)量。

30.explain用于模擬sql的執(zhí)行過程。

31.分頁查詢在偏移量固定時，隨返回條數(shù)性能下降，同理，在條數(shù)固定時，隨偏移量增加性能也下降。因?yàn)榉猪摬樵兠看味际菑牡谝粭l開始掃描。

32.優(yōu)化方案：1.利用滾動翻頁。2.利用子查詢，實(shí)際上與1一致。

33.排序有全字段排序和rowid排序兩種。

redis：

sds：

1.redis中的string為sds類型，即動態(tài)字符串。

2.redis不使用c中的字符串是因?yàn)?#xff1a;1.獲取長度困難，2.非二進(jìn)制安全，3.不可修改。

3.sds可以進(jìn)行擴(kuò)容。

intset：

4.intset是set集合的一種實(shí)現(xiàn)方式，基于整數(shù)數(shù)組實(shí)現(xiàn)，具備長度可變和有序性。

5.contents存儲的是指針，真正的數(shù)字大小由encoding決定。

6.存儲的元素所占字節(jié)一樣，是為了方便尋址。

7.超過預(yù)定大小會進(jìn)行類型升級，整個數(shù)組都要統(tǒng)一類型，倒序重新放置。

8.插入時使用的是二分查找，找到要插入的位置，后面的元素后移。

dict：

9.dict由3部分組成：1.哈希表，2.哈希節(jié)點(diǎn)，3.字典。

求一個數(shù)的余數(shù)，相當(dāng)于&該數(shù)-1。sizemask的用處。

10.如果有hash沖突，新來的元素會占據(jù)頭位置。

11.dict在每次新增時會檢查是否需要擴(kuò)容，根據(jù)元素個數(shù)/數(shù)組長度來計算出負(fù)載因子。

12.如果是新建的hash表，初始大小為4.

13.擴(kuò)容會在原基礎(chǔ)上+1，尋找到大于該數(shù)的2的n次方的數(shù)。

14.在刪除元素的時候會檢查用不用收縮，負(fù)載因子小于0.1進(jìn)行收縮。

15.收縮最小不能小于初始化長度4.

16.dict中有兩個hash表，擴(kuò)容時會創(chuàng)建新的放到ht[1]，等遷移完成后，重新放到ht[0]。

17.擴(kuò)容時漸進(jìn)式進(jìn)行的，每次增刪改查時，遷移一個位置。

ziplist：

18.ziplist是壓縮列表，使用連續(xù)的內(nèi)存模仿雙端鏈表，可以省去指針占用的內(nèi)存。

19.entry的長度是不固定的，以此來達(dá)到節(jié)省空間的目的。

20.查詢數(shù)據(jù)必須遍歷，會有性能的損耗。所以ziplist長度不宜過長。

21.連鎖更新也會造成性能損耗。

quicklist：

22.結(jié)構(gòu)為雙端列表，用于解決ziplist的長度限制問題，每個節(jié)點(diǎn)都是一個ziplist。

skiplist：

23.最多允許32級指針。

redisObject：

24.redis中任意的鍵值都會被封裝成redisObject。

25.每個對象頭都有固定的空間占用，存儲多個string占用的空間比用list要大。

string：

26.string有三種編碼方式，如果存儲的是數(shù)字，則不需要sds對象。如果是字符串，有raw和embstr兩種編碼方式，raw編碼時對象頭和sds的內(nèi)存是不連續(xù)的，通過指針指向。embstr編碼時，內(nèi)存是連續(xù)的。

27.選擇44字節(jié)進(jìn)行判斷是為了方便內(nèi)存分配，object信息+存儲的信息=64，正好是內(nèi)存的一個分片，可以避免內(nèi)存碎片。

28.使用object encoding命令可以查看key的編碼方式。

list：

29.list類型可以從首尾操作元素，使用quicklist實(shí)現(xiàn)。

30.默認(rèn)ziplist為8kb，壓縮等級為1，首尾各有一個節(jié)點(diǎn)不壓縮。

set：

31.單列集合，元素唯一，不保證順序，可以求交并集。

32.set需要經(jīng)常判斷元素存不存在，所以鏈表結(jié)構(gòu)不適合查詢。

33.使用哈希表，即dict。value統(tǒng)一放null。

34.如果存入的都是整數(shù)，且元素數(shù)量不超過閾值，使用intset。

35.intset編碼后續(xù)有可能轉(zhuǎn)為dict。

zset：

36.zset同時使用dict和skiplist。

37.當(dāng)數(shù)據(jù)量過小時，會使用ziplist作為底層結(jié)構(gòu)。

hash：

38.hash和zset一樣，在數(shù)據(jù)量小的時候用ziplist，數(shù)據(jù)量超過閾值，使用dict。

內(nèi)核態(tài)和用戶態(tài)：

39.提高io效率核心要解決的問題是等待時間和拷貝時間。

io模型：

40.五種io模型

阻塞io：在數(shù)據(jù)沒有到達(dá)時會陷入阻塞。

非阻塞io：循環(huán)調(diào)用數(shù)據(jù)有沒有到達(dá)，到達(dá)后拷貝數(shù)據(jù)也會陷入阻塞。

io多路復(fù)用：利用單線程同時監(jiān)聽多個fd，即文件描述符。

select、poll在有數(shù)據(jù)到達(dá)時不知道具體的fd是哪個，epoll是直接知道的。

41.select有數(shù)量限制，poll沒有數(shù)量限制。

42.select底層使用的bitmip上線1024，poll底層使用的鏈表，雖然無上限，但是過長會影響性能。epoll底層使用紅黑樹。

43.異步io也是比較好的方式，只是用戶代碼實(shí)現(xiàn)需要考慮并發(fā)問題。

44.redis多路復(fù)用會監(jiān)聽3個時間，客戶端連接，客戶端可讀，客戶端可寫。

45.單線程模型的瓶頸主要在讀數(shù)據(jù)。引入多線程進(jìn)行讀寫客戶端請求和解析命令。

過期策略：

46.每個redis的db都是一個redisDb對象，里面包含多個dict字典。

47.redis過期使用惰性刪除。訪問key的時候如果過期則刪除。

48.周期刪除：定時抽樣部分過期數(shù)據(jù)進(jìn)行刪除。

49.周期刪除有兩種模式。

淘汰策略：

50.redis是在每次處理命令之前，檢查內(nèi)存。

51.每個redisObject對象中都會記錄key的訪問時間或訪問次數(shù)，根據(jù)根據(jù)配置不同，記錄信息不同。

52.redis使用的不是嚴(yán)格的lru和lfu，每次是挑選樣本進(jìn)入淘汰池，從淘汰池中淘汰。因?yàn)槌刈訒M，所以最后會趨近lru和lfu。

哨兵模式：

53.redis快的原因，純內(nèi)存操作、單線程無上下文切換、漸進(jìn)式rehash、緩存時間戳、多路復(fù)用。

擴(kuò)容也是兩倍擴(kuò)容，利用空間換時間，有兩個數(shù)組，交換使用。

獲取時間戳是系統(tǒng)調(diào)用，所以redis有定時任務(wù)來緩存時間戳。

54.redis為什么不用多線程：1.redis的性能瓶頸不在cpu，在內(nèi)存和網(wǎng)絡(luò)。使用redispipeline可達(dá)到每秒鐘百萬請求。

55.redis高級功能：1.慢查詢，2.pipeline，3.watch，4.lua腳本

56.redis的事務(wù)是弱事務(wù)，不支持回滾操作，只能做語法判斷。

57.看門狗問題。

58.redis和memcache。redis是支持集群的。memcached是預(yù)申請內(nèi)存。

59.過期key有可能造成主從不同步。

60.hyperloglog的每個輸入都會進(jìn)行hash轉(zhuǎn)換成二進(jìn)制串。

每一個二進(jìn)制串，我們都可以看作是一個伯努利過程。

每個二進(jìn)制位可以當(dāng)做硬幣的正反面，通過出現(xiàn)1的次數(shù)，估算進(jìn)行了多少次投幣。

【Redis筆記】一起了解 Redis 中的 HyperLogLog 算法？-CSDN博客

61.rdb為快照，不適合實(shí)時持久化，有數(shù)據(jù)丟失問題。

aof的效率沒有rdb高。

生產(chǎn)可以使用混合模式。

62.mysql和redis數(shù)據(jù)一致性的保證，容易出現(xiàn)的問題。

63.redis集群功能的限制。

64.集群不可用情況。

65.redis分槽使用的是一致性哈希的改進(jìn)，虛擬一致性哈希。

66.redis槽一共16384個，不設(shè)計更多的槽是因?yàn)樵?000個節(jié)點(diǎn)的情況下，16384個槽就夠用了，如果節(jié)點(diǎn)過多，節(jié)點(diǎn)間通信會占用大量的網(wǎng)絡(luò)帶寬。

67.redis的哈希槽使用bitmap進(jìn)行存儲。

68.redis集群寫入數(shù)據(jù)有可能丟失，redis不提供數(shù)據(jù)一致性保證。

69.提升redis性能。

主節(jié)點(diǎn)不開啟持久化，從節(jié)點(diǎn)進(jìn)行持久化。數(shù)據(jù)比較重要，主節(jié)點(diǎn)就使用aof。

主從復(fù)制速度的保證，盡量在同一內(nèi)網(wǎng)。

70.數(shù)據(jù)更新之前被度去過兩次，可以成為熱數(shù)據(jù)。

71.redis阻塞的情況：1.來自客戶端的命令執(zhí)行耗時，如keys*，hgetall等。2.大key的獲取和刪除。3.清空庫，4.aof同步寫。

etcd：

raft協(xié)議：

1.etcd是一個鍵值對存儲組件，可以實(shí)現(xiàn)配置共享和服務(wù)發(fā)現(xiàn)。

2.etcd滿足cap理論的c和p指標(biāo)。

3.etcd內(nèi)部通信使用grpc。

4.使用mvcc將數(shù)據(jù)記錄在boltDB中。

5.etcd中的數(shù)據(jù)提交前都會先記錄到日志中。

6.利用日志和快照機(jī)制實(shí)現(xiàn)故障恢復(fù)。

7.raft算法需要超過半數(shù)節(jié)點(diǎn)同意，不包括半數(shù)。

8.預(yù)寫日志保證了操作順序，保證最終一致性的核心。

9.數(shù)據(jù)足夠新的follower才能競選leader。

10.leader在發(fā)送預(yù)寫日志時，會帶上上一個預(yù)寫日志索引。

11.索引包含任期和索引。

12.如果缺少索引，會向主節(jié)點(diǎn)請求。

13.如果日志索引超前，從節(jié)點(diǎn)就會刪除超前日志，以主節(jié)點(diǎn)為準(zhǔn)。

14.索引有兩個，一個是apliedindex，一個是commitindex。

15.解決讀不一致性的方案，1：都從leader節(jié)點(diǎn)讀，2：寫入時主節(jié)點(diǎn)返回最新的index，讀的時候帶上。

16.寫記錄現(xiàn)在leader執(zhí)行，然后通知follower，得到響應(yīng)后提交。

17.如果有兩個leader，在收到消息后，會判斷任期，如果自己更靠前，則拒絕，讓另一個leader退位。

18.follower中會有定時器，一段時間沒有收到leader的心跳，就會發(fā)起選舉。

19.發(fā)起選舉時，如果任期相同，會判斷索引大小，索引大于等于自己，就會同意，否則拒絕。

20.如果拉票超時，就會增加任期值，從新發(fā)起。

21.配置變更和增加節(jié)點(diǎn)都需要leader節(jié)點(diǎn)同步。

22.節(jié)點(diǎn)變更期間的選舉，只有老節(jié)點(diǎn)可以參與投票，處理請求也是如此。

23.為了解決瓜分選票造成的無限循環(huán)問題，在心跳超時和選舉超時時間上會加上擾動值。

24.每個leader上任后，必須提交一筆自己任期內(nèi)的寫數(shù)據(jù)操作。

25.leader向follower同步數(shù)據(jù)，超時會進(jìn)行重發(fā)。

26.通過冪等處理leader成功提交，但未完成響應(yīng)客戶端的情況。

27.為了規(guī)避無意義競選，follower在發(fā)起競選前，會提前試探，有多數(shù)派回復(fù)，確認(rèn)自己網(wǎng)絡(luò)沒有問題，才會競選。

28.ack重試機(jī)制保證客戶端數(shù)據(jù)不丟失，冪等序列號，保證請求的唯一性。

etcd實(shí)現(xiàn)：

29.etct結(jié)構(gòu)分為應(yīng)用層和算法層。

30.應(yīng)用層和算法層都使用for+select監(jiān)聽對方的消息。

31.算法層本質(zhì)上是一個節(jié)點(diǎn)狀態(tài)機(jī)。

32.兩次提交指的是預(yù)寫日志提交和真實(shí)提交。

33.預(yù)寫日志有兩種類型，一種是配置變更如節(jié)點(diǎn)增加或減少，另一種是正常寫請求。

34.預(yù)寫日志會被封裝到message中。message有多種類型。

35.算法層只能對持久化日志進(jìn)行查詢，真正的持久化是在應(yīng)用層做的。

36.算法層會將預(yù)寫日志先緩存在內(nèi)存中，收到應(yīng)用層可提交的消息后，通知應(yīng)用層持久化。

37.node是應(yīng)用層和算法層通信的入口。

38.強(qiáng)制讀主的方式需要leader去自證自己是主節(jié)點(diǎn)，沒有出現(xiàn)分裂。

39.raft是算法層的核心類。

40.應(yīng)用層是提供服務(wù)的入口。

41.etcd默認(rèn)是線性讀。

?42.數(shù)據(jù)持久在boltDB中。

43.mvcc是一種樂觀鎖。不能解決更新丟失問題。

44.讀請求會請求leader拿到最新的index，然后判斷自己的節(jié)點(diǎn)是否和最新的一致。

45.在 etcd v3 中引入 treeIndex 模塊正是為了解決這個問題，支持保存 key 的歷史版本，提供穩(wěn)定的 Watch 機(jī)制和事務(wù)隔離等能力。
46.etcd 在每次修改 key 時會生成一個全局遞增的版本號(revision)。

然后通過數(shù)據(jù)結(jié)構(gòu) B-tree 保存用戶 key 與版本號之間的關(guān)系;

再以版本號作為 boltdb key，以用戶的 key-value 等信息作為 boltdb value，保存到 boltdb。

47.當(dāng)etcd服務(wù)器重啟后，內(nèi)存中的treeIndex數(shù)據(jù)確實(shí)會丟失，因?yàn)閠reeIndex是內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，用于快速索引和查找鍵值對。但是，etcd具有持久化存儲機(jī)制，它將數(shù)據(jù)寫入磁盤以在重啟后恢復(fù)數(shù)據(jù)。

具體來說，etcd使用一種稱為WAL（Write-Ahead Log）的機(jī)制來持久化數(shù)據(jù)。每當(dāng)在etcd中進(jìn)行更改（比如添加、更新或刪除鍵值對）時，這些更改會被追加到WAL日志中。WAL日志是一個順序?qū)懭氲娜罩疚募?#xff0c;它確保了數(shù)據(jù)的持久性和一致性。

在etcd啟動時，它會讀取WAL日志文件并重新構(gòu)建內(nèi)存中的樹狀結(jié)構(gòu)。

48.在treelndex中，每個節(jié)點(diǎn)的 key是一個keyIndex結(jié)構(gòu)，etcd就是通過它保存了用戶的key 與版本號的映射關(guān)系。

49.那么 key 打上刪除標(biāo)記后有哪些用途呢?什么時候會真正刪除它呢?

• 一方面刪除 key 時會生成 events，Watch 模塊根據(jù) key 的刪除標(biāo)識，會生成 對應(yīng)的 Delete 事件。

• 另一方面，當(dāng)你重啟 etcd，遍歷 boltdb 中的 key 構(gòu)建 treeIndex 內(nèi)存樹時， 你需要知道哪些 key 是已經(jīng)被刪除的，并為對應(yīng)的 key 索引生成 tombstone 標(biāo) 識。

而真正刪除 treeIndex 中的索引對象、boltdb 中的 key 是通過壓縮 (compactor) 組件異步完成。

正因?yàn)?etcd 的刪除 key 操作是基于以上延期刪除原理實(shí)現(xiàn)的，因此只要壓縮組件未回收歷 史版本，我們就能從 etcd 中找回誤刪的數(shù)據(jù)。

50.在 etcd v3 中，為了解決 etcd v2 的以上缺陷，使用的是基于 HTTP/2 的 gRPC 協(xié)議，雙向流的 Watch API 設(shè)計，實(shí)現(xiàn)了連接多路復(fù)用。

在 HTTP/2 協(xié)議中，HTTP 消息被分解獨(dú)立的幀（Frame），交錯發(fā)送，幀是最小的數(shù)據(jù)單位。每個幀會標(biāo)識屬于哪個流（Stream），流由多個數(shù)據(jù)幀組成，每個流擁有一個唯一的 ID，一個數(shù)據(jù)流對應(yīng)一個請求或響應(yīng)包。

50.etcd 的確使用 map 記錄了監(jiān)聽單個 key 的 watcher，但是你要注意的是 Watch 特性不僅僅可以監(jiān)聽單 key，它還可以指定監(jiān)聽 key 范圍、key 前綴，因此 etcd 還使用了如下的區(qū)間樹。

當(dāng)收到創(chuàng)建 watcher 請求的時候，它會把 watcher 監(jiān)聽的 key 范圍插入到上面的區(qū)間樹中，區(qū)間的值保存了監(jiān)聽同樣 key 范圍的 watcher 集合 /watcherSet。

51.定時自動淘汰（leader做的）

??? leader 在 etcd server 啟動時會啟動一個 goroutine RevokeExpiredLease() ， 每 500ms 檢查一次。
??? 使用 最小堆 管理 lease，按到期時間升序排序，每次檢查時從堆頂取出元素，檢查lease過期時間

52.Checkpoint 檢查點(diǎn)機(jī)制（leader做的）

??? leader 在 etcd server 啟動時會啟動一個 goroutine CheckpointScheduledLeases()，每 500ms 將 lease 的 ttl 通過 raft 同步給 follower

RabbitMQ：

1.4種交換機(jī)類型。

2.消息可靠性保證。

3.生產(chǎn)者確認(rèn)有兩種方式，同步和異步。

4.如果沒有開啟消息持久化，當(dāng)內(nèi)存滿了，mq要將一部分?jǐn)?shù)據(jù)遷移到磁盤，會造成阻塞。

5.數(shù)據(jù)可靠性保證有兩種方式1：數(shù)據(jù)持久化，2：lazyqueue。

5.消費(fèi)者確認(rèn)機(jī)制。

6.消息失敗可以先在本地重試，不要直接重新投遞給mq。

7.利用死信交換機(jī)實(shí)現(xiàn)延遲隊列。

8.底層使用最小堆實(shí)現(xiàn)。

9.RabbitMQ 的元數(shù)據(jù)都是存在于 Erlang 自帶的分布式數(shù)據(jù)庫 Mnesia 中的。

10.在實(shí)現(xiàn)上，每臺 Broker 節(jié)點(diǎn)都會保存集群所有的元數(shù)據(jù)信息。當(dāng) Broker 收到請求后，根據(jù)本地緩存的元數(shù)據(jù)信息判斷 Queue 是否在本機(jī)上，如果不在本機(jī)，就會將請求轉(zhuǎn)發(fā)到 Queue 所在的目標(biāo)節(jié)點(diǎn)。

11.Mnesia 本身是一個分布式的數(shù)據(jù)庫，自帶了多節(jié)點(diǎn)的 Mnesia 數(shù)據(jù)庫之間的同步機(jī)制。

12.如果消費(fèi)者（處理消息的程序）連接到節(jié)點(diǎn) B 來讀取隊列的消息，節(jié)點(diǎn) B 會自動把這個請求轉(zhuǎn)發(fā)到節(jié)點(diǎn) A，因?yàn)殛犃写嬖谟?A。

13.集群模式可以為節(jié)點(diǎn)添加鏡像隊列節(jié)點(diǎn)，同步節(jié)點(diǎn)的數(shù)據(jù)。

鏡像隊列可以讓隊列的數(shù)據(jù)在多個節(jié)點(diǎn)之間復(fù)制。例如，你可以讓隊列的副本同時存在于節(jié)點(diǎn) A 和 B 上。這樣，即使節(jié)點(diǎn) A 掛了，節(jié)點(diǎn) B 依然有該隊列的完整副本，可以繼續(xù)處理消息。

14.不支持有且僅有一次的保證。

15.RabbitMQ 從隊列中取出待處理的消息，并將其分發(fā)給消費(fèi)者 A。

消息的狀態(tài)在分發(fā)后會被標(biāo)記為“正在處理中”，即消息進(jìn)入了一個凍結(jié)狀態(tài)。

16.RabbitMQ 使用文件來存儲持久化消息。這些文件通常位于 RabbitMQ 的數(shù)據(jù)目錄（如 /var/lib/rabbitmq/mnesia/）中，文件格式通常是二進(jìn)制格式，專門設(shè)計用于高效存取和存儲消息。

17.隊列元數(shù)據(jù)：隊列的元數(shù)據(jù)也會被持久化到磁盤中，包括隊列的定義、綁定信息等。這些數(shù)據(jù)存儲在 Mnesia 數(shù)據(jù)庫中，這是 RabbitMQ 用來管理內(nèi)部狀態(tài)的數(shù)據(jù)庫。

es：

1.非關(guān)系型文檔數(shù)據(jù)庫。

2.pb級數(shù)據(jù)秒級查詢。

3.穩(wěn)當(dāng)是json格式。

4.mapping中的類型，數(shù)字類型，keyword：精確查找不進(jìn)行分詞，text：文本類型會被分詞，時間類型，alias：別名。另外還有結(jié)構(gòu)類型，如坐標(biāo)類型。

5.可以不定義結(jié)構(gòu)直接寫入數(shù)據(jù)，會動態(tài)判斷自動創(chuàng)建。

6.映射方式分為自動和手動兩種。

7.全文檢索就是會被分詞的檢索。

8.檢索和搜索的區(qū)別，檢索是指相關(guān)度。

9.全文索引步驟：切詞、規(guī)范化、去重、字典序。

10.將用戶輸入進(jìn)行分詞，每個詞進(jìn)行查詢，命中次數(shù)最多的id，相關(guān)度就高。

11.should在和must或者filter同時出現(xiàn)時，should會失效。

12.filter是不計算相關(guān)度的，效率相對高一些。

13.嵌套查詢：object、nested、join。

14.按查詢準(zhǔn)確度可以分為：1.全文檢索match、2.精確查找term、模糊匹配：suggester、通配符正則等。搜索提示是基于suggester實(shí)現(xiàn)的。

15.match會進(jìn)行分詞搜索，term不會。

16.如果使用.keyword，查詢的就是不分詞的。

17.match和term是針對輸入詞的，keyword是針對源數(shù)據(jù)的。

18.評分算法：BM25和tf-idf。

19.倒排索引的存儲結(jié)構(gòu)為fst。

20.倒排表使用壓縮算法：稠密數(shù)組for，稀疏數(shù)組roaring bitmaps。

21.通用最小化算法。

22.fst 和 trie字典樹又稱前綴樹。

23.數(shù)據(jù)模型。

• 倒排索引：用于存儲詞項(xiàng)到文檔 ID 的映射，優(yōu)化了全文搜索。采用壓縮的索引結(jié)構(gòu)，如跳躍表、B+ 樹或哈希表。
• 文檔 ID 到文檔的映射：存儲字段以列式存儲方式存儲，確?？焖偬崛∷枳侄?。
• DocValues：為排序和聚合操作設(shè)計的列式存儲結(jié)構(gòu)，提供高效的數(shù)據(jù)訪問。
• 段：包含上述所有結(jié)構(gòu)的基本單元，每個段都是獨(dú)立的索引，段合并優(yōu)化了存儲和查詢效率。

24.段和文檔的關(guān)系，段是不可修改的。

段存儲的是文檔數(shù)據(jù)，因此它們之間的關(guān)系可以這樣概括：

• 文檔被寫入 Elasticsearch 時，Lucene 會將其組織到段中。段中包含多個文檔，這些文檔會按照倒排索引的方式被存儲，便于高效檢索。
• 每個段包含文檔的多個部分，包括：
  1. 倒排索引（Inverted Index）：文檔中的詞項(xiàng)（Token）到文檔 ID 的映射，用于支持全文搜索。
  2. 存儲字段（Stored Fields）：文檔的實(shí)際內(nèi)容（如 JSON 格式的數(shù)據(jù)），以便在搜索時返回文檔的原始數(shù)據(jù)。
  3. DocValues：用于排序和聚合的字段值。
  4. 刪除標(biāo)記（Delete Markers）：如果文檔被刪除，則該文檔不會立即被物理刪除，而是在段中添加刪除標(biāo)記，直到段合并時才真正刪除這些標(biāo)記的文檔。

25.FST 的作用是：

• 通過快速查找定位詞項(xiàng)在倒排索引中的位置；
• 一旦定位到詞項(xiàng)，倒排索引會提供對應(yīng)的文檔 ID 列表，這個列表可以包含與該詞項(xiàng)相關(guān)的所有文檔。

26.每個文檔存儲在某個 段（Segment） 中，每個段會存儲文檔的元數(shù)據(jù)以及文檔的實(shí)際內(nèi)容。Elasticsearch 會根據(jù)文檔 ID 查找到具體的段文件，然后在段文件中讀取該文檔的內(nèi)容。

27.每個文檔都有一個全局的文檔 ID（用戶提供的 ID），而 Lucene 內(nèi)部為每個段中的文檔分配一個局部的 DocID，這個 DocID 僅在段內(nèi)部有效。

28.查詢示例。

• 段掃描順序：通常是從舊到新，或者從小到大，但實(shí)際操作中可能會并行掃描多個段。
• 并行掃描：多個線程可以并行掃描不同的段，以提高查詢效率。
• FST 和倒排索引：在每個段中，首先使用 FST 查找關(guān)鍵詞，然后使用倒排索引獲取匹配的文檔 ID。
• 結(jié)果合并：最終結(jié)果會在所有段的匹配結(jié)果中合并、去重和排序后返回給用戶。

29.數(shù)據(jù)先寫入內(nèi)存buffer中，當(dāng)?shù)竭_(dá)時間閾值或空間閾值時，會寫入到索引段文件中，段文件將數(shù)據(jù)放入到OS Cache中。

30.當(dāng)數(shù)據(jù)放入到OS Cache中后，索引段文件將處于open狀態(tài)，此時數(shù)據(jù)就可被查到了。

31.當(dāng)OS Cache數(shù)據(jù)達(dá)到閾值，會fsync到磁盤中。

32.讀寫分離的意義在于減小磁盤的讀寫壓力。

33.commit point會將段文件進(jìn)行合并。

34.數(shù)據(jù)寫入內(nèi)存buffer中時，會同步寫入到tranlog中，以保證數(shù)據(jù)的完整性。

35.es多節(jié)點(diǎn)寫入流程。請求的節(jié)點(diǎn)會找到寫入數(shù)據(jù)對應(yīng)的主節(jié)點(diǎn)，寫入主節(jié)點(diǎn)之后，主節(jié)點(diǎn)同步副節(jié)點(diǎn)，副節(jié)點(diǎn)完成寫入后，通知主節(jié)點(diǎn)，主節(jié)點(diǎn)將結(jié)果通知請求節(jié)點(diǎn)，請求節(jié)點(diǎn)響應(yīng)客戶端。

36.拼寫糾錯和模糊查詢利用fuzzy實(shí)現(xiàn)。fuzziness步長最大為2。不指定的話為auto，會根據(jù)字符總長度來給定。

37.距離算法為damerau-萊文斯坦距離。

38.多個分片組成一個index，每個分片都是一個單獨(dú)的lucene實(shí)例。

39.主分片可讀可寫，副本分片是只讀的。

40.分片創(chuàng)建策略：分片在創(chuàng)建之前要指定分片的數(shù)量和大小。

分片的分配策略：要盡可能均勻的分配到不同的節(jié)點(diǎn)上。

再分配策略：當(dāng)有節(jié)點(diǎn)加入或離開時，會重新分配。

延遲分配策略：再分配會延遲一分鐘執(zhí)行。

分片的數(shù)量策略：不宜太多或太少。

分片的大小策略：10-50g

41.1gb堆內(nèi)存能管理的分片在20左右。

42.兩個節(jié)點(diǎn)不具備選舉能力，穩(wěn)定的集群至少需要三個節(jié)點(diǎn)。

43.索引的組成部分。

44.索引的分片的數(shù)量和副本的數(shù)量是在settings中設(shè)置的。

45.索引有三種含義:1.es的index，2.索引文件，3.動詞寫入數(shù)據(jù)。

46.es會有兩個進(jìn)程定時檢查主節(jié)點(diǎn)和副節(jié)點(diǎn)的存活狀態(tài)。masterFD和nodesFD。通過其他節(jié)點(diǎn)給master節(jié)點(diǎn)發(fā)送請求。

47.當(dāng)副節(jié)點(diǎn)發(fā)現(xiàn)master節(jié)點(diǎn)失聯(lián)，或者主節(jié)點(diǎn)能聯(lián)系到的副節(jié)點(diǎn)小于n/2+1會發(fā)起選舉。

48.從配置了master角色的節(jié)點(diǎn)中選舉。

49.fd發(fā)起請求，找到響應(yīng)請求的所有節(jié)點(diǎn)，不包括發(fā)起的節(jié)點(diǎn)。經(jīng)過過濾找到符合選舉的節(jié)點(diǎn)。

如果已經(jīng)存在活躍master，而且不是自己，則停止。

判斷候選節(jié)點(diǎn)是否滿足指定票數(shù)。

50.選舉完成后要將節(jié)點(diǎn)信息分發(fā)到每個節(jié)點(diǎn)。

51.集群節(jié)點(diǎn)數(shù)量為偶數(shù)時，es會使一個節(jié)點(diǎn)失去選舉權(quán)，避免腦裂。

grpc：

1.四種模式：單一模式，客戶端流，服務(wù)端流，雙向流。

2.基于http2實(shí)現(xiàn)。http支持流和幀的多路復(fù)用。

分布式：

1.補(bǔ)償性事務(wù)：

TCC的核心思想是：針對每一個操作都需要注冊一個和其相對應(yīng)的確認(rèn)和補(bǔ)償?shù)牟僮?#xff0c;他分為三個階段Try、Confirm和Cancel

2.分布式事務(wù)使用base理論，實(shí)現(xiàn)最終一致性。

3.分布式唯一id：

uuid、數(shù)據(jù)庫子增、批量生成id、redis生成id、雪花算法snowflflake。

4.負(fù)載均衡算法：

輪詢、加權(quán)輪詢、隨機(jī)輪詢、最少鏈接（適用redis實(shí)現(xiàn)）、源地址散列（適用session和長鏈接）

5.計數(shù)器，即固定窗口算法。

適用redis的incrby和過期時間實(shí)現(xiàn)。

風(fēng)險在于無法應(yīng)對突增。如服務(wù)器限流60，在00:50有50個請求，在01:00有50個請求。

6.滑動時間窗口

將窗口分為小粒度的幾個固定時間窗口，進(jìn)行計算。

7.漏桶算法

8.令牌桶算法

9.數(shù)據(jù)庫處理大數(shù)據(jù)

分區(qū)、分庫、分表、讀寫分離。

10.服務(wù)熔斷，服務(wù)熔斷為了解決服務(wù)雪崩，如a->b->c->d，如果d有問題卡住，調(diào)用鏈路都會卡住。

觸發(fā)熔斷之后需要添加標(biāo)記，后續(xù)走降級策略。

11.降級和熔斷

熔斷會觸發(fā)降級，但降級還有多種情況。

12.提升系統(tǒng)并發(fā)能力

分流：負(fù)載均衡、消息隊列、數(shù)據(jù)庫拆分

導(dǎo)流：緩存、cdn

13.微服務(wù)劃分：準(zhǔn)確識別系統(tǒng)隔離點(diǎn)也就是系統(tǒng)邊界。

14.最大努力消息通知

消息重復(fù)通知、消息可查詢校對。

內(nèi)部系統(tǒng)可使用消息隊列，外部系統(tǒng)暴露接口。

15.解決緩存不一致問題（cache-asid），使用read/write through，即寫入數(shù)據(jù)時直接寫入到緩存中，再由緩存同步數(shù)據(jù)庫。

項(xiàng)目啟動時先從數(shù)據(jù)庫讀取到緩存中。

gin：

1.基于http/net包實(shí)現(xiàn)。

2.gin的特點(diǎn)。支持中間件headlerschain，方便的使用gin.context 并發(fā)安全的，路有數(shù)radix tree。

3.gin和http包的關(guān)系。

藍(lán)色代表gin的功能，紅色代表gin的結(jié)構(gòu)，黃色代表http包。

4.gin.engine結(jié)構(gòu)。

5.gin.engine是實(shí)現(xiàn)了http接口的實(shí)例。

6.sync.pool中包含Context，用來復(fù)用。每個請求都會分配一個Context。

7.如果池子里有Context，將會把數(shù)據(jù)清空，用來復(fù)用。

8.自動清理的能力，當(dāng)兩輪gc之后，還未被用到的Context就會被清除。

9.routergroup中所有的配置會被這個組中所有的成員共同使用。會在自己路徑之前拼接上routergroup的路徑。

10.routergroup中的中間件也會被成員共同使用。

11.engine中會有九棵壓縮樹，對應(yīng)http的九種請求，節(jié)點(diǎn)會根據(jù)路徑掛載在樹上，當(dāng)請求到達(dá)時，再通過樹去查找對應(yīng)的headers。

12.所有實(shí)現(xiàn)了http包handler方法的結(jié)構(gòu)體，都可以被注入到net的框架中。

13.routergroup中表示是否是根節(jié)點(diǎn)。默認(rèn)分配為是。

14.在engine被創(chuàng)建出來時，會初始化Context池。

15.使用中間件會將中間件添加到group所對應(yīng)的handler的切片中。

16.注冊handler流程。

17.核心就是把自己當(dāng)做http的實(shí)現(xiàn)類。

18.http啟動之后會循環(huán)監(jiān)聽對應(yīng)的端口，每次調(diào)用端口端口監(jiān)聽器的accept方法。使用epoll技術(shù)。

19.針對到達(dá)的請求會分配goroutine去服務(wù)，找到啟動時注入的handler，也就是gin的實(shí)現(xiàn)。

20.gin框架處理流程。

21.Context用完之后沒有進(jìn)行清理，獲取時才執(zhí)行清理。

22.根據(jù)請求的方法找到對應(yīng)的請求壓縮前綴樹，從前壓縮前綴樹中找到對應(yīng)的處理鏈條。

23.獲取到鏈路后會掛載到對應(yīng)的Context上。承載請求參數(shù)和處理鏈條。

24.gin為什么使用壓縮前綴樹，map適合單點(diǎn)操作，無法應(yīng)付模糊。

25.補(bǔ)償機(jī)制：每次都是從節(jié)點(diǎn)的左邊開始遍歷子樹。

26.Context結(jié)構(gòu)。

27.gin使用sync.pool實(shí)現(xiàn)Context復(fù)用。

28.sync.pool是物理意義上的緩存，但內(nèi)存回收不穩(wěn)定，需要兩輪gc。

29.Context中index字段表示遍歷到了哪個handlers。

30.最多只能注冊62個handler。

31.用戶可以在某個handler中調(diào)用Context.about。該方法會將index值設(shè)置為63。

redigo：

1.連接池使用雙端鏈表存儲。

2.獲取時從頭部獲取。

3.close方法是將鏈接放回鏈接池，并不是關(guān)閉。

gorm：

1.內(nèi)部使用很多反射，性能較低。編譯階段不容易發(fā)現(xiàn)問題。

2.builder設(shè)計模式，分為存儲數(shù)據(jù)+處理數(shù)據(jù)兩步。

3.高頻重復(fù)拼接sql。

docker：

k8s：

1.kube-proxy ipvs和iptables的異同。

都是通過netfilter內(nèi)核進(jìn)行轉(zhuǎn)發(fā)的。

iptables是為防火墻設(shè)計的，ipvs是專門用于高性能負(fù)載均衡。使用更高效的hash表結(jié)構(gòu)。

ipvs有更好的性能和擴(kuò)展性，支持更復(fù)雜的負(fù)載均衡算法，支持服務(wù)健康檢測和連接重試的功能。

支持動態(tài)修改ipset設(shè)置。

網(wǎng)絡(luò)：

1.tcp/ip網(wǎng)絡(luò)分層架構(gòu)。

2.tcp四次揮手。

如果減少為3次，服務(wù)端將客戶端fin的響應(yīng)和自己fin的響應(yīng)合二為一，中間可能會有延遲，因?yàn)閔ttp是可靠傳輸，客戶端會不停地發(fā)起fin請求，造成資源浪費(fèi)。

3.凡是對端的確認(rèn)，無論客戶端確認(rèn)服務(wù)端，或者服務(wù)端確認(rèn)客戶端，都要消耗tcp報文的序列號。因?yàn)橛兄卦嚨男袨椤?/p>

4.半連接隊列和syn flood洪泛攻擊，

5.tcp fast open利用cookie減少一次請求的往返。

6.tcp報文中時間戳的作用。計算往返時間和解決序列號重用問題。

7.重試時間如何計算，

平滑往返時間。根據(jù)上次的重傳時間進(jìn)行計算。適用于波動比較小的時候。

8.tcp流量控制。對于接收方和發(fā)送發(fā)，都需要把數(shù)據(jù)放在自己的緩沖區(qū)。交互時會將自己的緩沖區(qū)大小告訴對方。

緩沖區(qū)使用滑動窗口進(jìn)行。

9.keep alive會定時檢查鏈接存活狀態(tài)，但是需要7200s，一般不用。

10.端口在傳輸層的頭里面。一個是源端口，一個是目標(biāo)端口。

臨時端口是從48152-65535的。

11.tcp的確認(rèn)號計算。

12.對應(yīng)的協(xié)議。

13.消息邊界

14.netstat用于顯示網(wǎng)絡(luò)連接信息。

15.命令行抓包工具tcpdump。

16.len長度為0的數(shù)據(jù)是握手和揮手?jǐn)?shù)據(jù)。

17.windows抓包工具winreshark。

18.tcp和udp的區(qū)別。

19.http是無連接的，指的是交互完成后鏈接就斷開了。

20.http是無狀態(tài)的。

21.https是http+ssl/tls。

22.ssl+tls處于tcp/ip協(xié)議和應(yīng)用層協(xié)議中間的位置。也可以說屬于應(yīng)用層。

23.服務(wù)端證書相當(dāng)于公鑰。

24.http1.0只能保持短暫鏈接，發(fā)送大文件需要多次握手。需要提供規(guī)范，connection，最常見的為keep-alive。只有g(shù)et和post兩種請求方式。

http 1.1是使用最廣泛的協(xié)議，支持保持鏈接，默認(rèn)包含keep-alive。不需要等待服務(wù)端返回就可以發(fā)送下一次請求。支持緩存的控制。

25.http2.0 支持多路復(fù)用，二進(jìn)制分幀。

使用二進(jìn)制傳輸。

首部壓縮。第一次發(fā)送頭部，后面發(fā)送頭部的差異就行。

允許服務(wù)端推送。

26.cdn內(nèi)容分發(fā)網(wǎng)絡(luò)，中心平臺服務(wù)器進(jìn)行分發(fā)，分配到離你最近的邊緣節(jié)點(diǎn)服務(wù)器。

27.在解析域名時，指向的是cname，即cdn的節(jié)點(diǎn)，而不是源服務(wù)器。

28.cdn全局負(fù)載均衡，會根據(jù)用戶ip找到用戶的真實(shí)地址，根據(jù)用戶的真實(shí)地址，運(yùn)營商和節(jié)點(diǎn)的壓力，為用戶分配合適的節(jié)點(diǎn)。

29.cdn緩存，如果發(fā)現(xiàn)用戶請求的資源在緩存中有，會直接返回。命中率在90以上。

30.域名。

面試題：

1.mysql同一個事務(wù)里語句不同表的執(zhí)行順序會影響效率嗎。

據(jù)說有鎖釋放時機(jī)的問題。

2.mysql索引失效。

要盡量滿足全值匹配

要滿足最佳左前綴法則

主鍵插入順序盡量自增

計算、函數(shù)導(dǎo)致索引失效

類型轉(zhuǎn)換導(dǎo)致索引失效

范圍條件右邊的列索引失效

沒覆蓋索引時，“不等于”導(dǎo)致索引失效

沒覆蓋索引時，is not null、not like導(dǎo)致索引失效

沒覆蓋索引時，左模糊查詢導(dǎo)致索引失效

“OR”前后存在非索引列，導(dǎo)致索引失效

不同字符集導(dǎo)致索引失敗，建議utf8mb4

3.redis刪除大key，hash類型。不知道有哪些成員。

使用hash的迭代器，一點(diǎn)一點(diǎn)的刪除成員。

4.查詢字符串類型的字段where條件不加單引號，和查詢int類型，where條件加單引號。

前者會失效，后者不會。

5.有序數(shù)組的歸并。

func mergeSortedSlice2(l, r []int) []int {lOldLen := len(l)l = append(l, make([]int, len(r))...)i := lOldLen - 1j := len(r) - 1index := len(l) - 1for {if i > -1 && j > -1 {if l[i] > r[j] {l[index] = l[i]i--} else {l[index] = r[j]j--}index--continue}break}if i == -1 {for i := j; i >= 0; i-- {l[i] = r[i]}}return l
}

. - 力扣（LeetCode）