大家好,我是小林。
原來薪資開太高,也會讓人猶豫。最近知道國內(nèi)某新能源公司和跨境電商的公司校招月薪很多都開 30-35K,超過了一線BAT ,很多同學都覺得太高了,都不太敢接。給低了也不想接,給太高也不敢接,真有趣。
說到校招,很多公司秋招階段沒有招滿人,就會繼續(xù)進行補錄,面試官大部分都是從簡歷池撈人起來面試,補錄的時候被撈起來面試,很大概率是能撿漏 offer 的,我接觸到很多同學其實都是在 12 月份補錄的環(huán)節(jié)中,突然就上岸大廠了。
這次分享一位 12 月末被騰訊撈起來面試的 Java 后端同學,同學穩(wěn)打穩(wěn)扎經(jīng)歷了一二面,坐等三面,我把一二面比較通用問題做了下分類和解答。
除開實習和項目問題,考察的知識內(nèi)容主要是Java 集合+Java并發(fā)+JVM+MySQL+Redis+網(wǎng)絡(luò)+操作系統(tǒng)+數(shù)據(jù)結(jié)構(gòu)與算法這幾大塊,整體上就是后端開發(fā)+計算機基礎(chǔ)。
這幾大塊是后端開發(fā)面試中比較常見的類型的,所以同學們在準備面試或者學習的時候,需要重點學習這幾大塊的原理知識,以面試問題反推復(fù)習的方向,是最高效和快速的方式。
索引的作用是為了加快查詢效率,MySQL 默認存儲引擎 Innodb 的索引結(jié)構(gòu)是用了 B+樹,B+樹索引按照索引列的值進行排序,并將數(shù)據(jù)分層存儲在索引樹的節(jié)點中,這樣可以通過比較索引值,快速定位到符合條件的數(shù)據(jù)行。
B+樹
數(shù)據(jù)庫的索引和數(shù)據(jù)都是存儲在硬盤的,我們可以把讀取一個節(jié)點當作一次磁盤 I/O 操作。
B+Tree 存儲千萬級的數(shù)據(jù)只需要 3-4 層高度就可以滿足,這意味著從千萬級的表查詢目標數(shù)據(jù)最多需要 3-4 次磁盤 I/O,所以B+Tree 相比于 B 樹和二叉樹來說,最大的優(yōu)勢在于查詢效率很高,因為即使在數(shù)據(jù)量很大的情況,查詢一個數(shù)據(jù)的磁盤 I/O 依然維持在 3-4次。
1、B+Tree vs B Tree
B+Tree 只在葉子節(jié)點存儲數(shù)據(jù),而 B 樹 的非葉子節(jié)點也要存儲數(shù)據(jù),所以 B+Tree 的單個節(jié)點的數(shù)據(jù)量更小,在相同的磁盤 I/O 次數(shù)下,就能查詢更多的節(jié)點。
另外,B+Tree 葉子節(jié)點采用的是雙鏈表連接,適合 MySQL 中常見的基于范圍的順序查找,而 B 樹無法做到這一點。
2、B+Tree vs 二叉樹
對于有 N 個葉子節(jié)點的 B+Tree,其搜索復(fù)雜度為O(logdN),其中 d 表示節(jié)點允許的最大子節(jié)點個數(shù)為 d 個。
在實際的應(yīng)用當中, d 值是大于100的,這樣就保證了,即使數(shù)據(jù)達到千萬級別時,B+Tree 的高度依然維持在 3~4 層左右,也就是說一次數(shù)據(jù)查詢操作只需要做 3~4 次的磁盤 I/O 操作就能查詢到目標數(shù)據(jù)。
而二叉樹的每個父節(jié)點的兒子節(jié)點個數(shù)只能是 2 個,意味著其搜索復(fù)雜度為 O(logN),這已經(jīng)比 B+Tree 高出不少,因此二叉樹檢索到目標數(shù)據(jù)所經(jīng)歷的磁盤 I/O 次數(shù)要更多。
3、B+Tree vs Hash
Hash 在做等值查詢的時候效率賊快,搜索復(fù)雜度為 O(1)。
但是 Hash 表不適合做范圍查詢,它更適合做等值的查詢,這也是 B+Tree 索引要比 Hash 表索引有著更廣泛的適用場景的原因。
Redis 是一種基于內(nèi)存的數(shù)據(jù)庫,對數(shù)據(jù)的讀寫操作都是在內(nèi)存中完成,因此讀寫速度非常快,常用于緩存,消息隊列、分布式鎖等場景。
Redis用途
Redis 提供了多種數(shù)據(jù)類型來支持不同的業(yè)務(wù)場景,比如 String(字符串)、Hash(哈希)、 List (列表)、Set(集合)、Zset(有序集合)、Bitmaps(位圖)、HyperLogLog(基數(shù)統(tǒng)計)、GEO(地理信息)、Stream(流),并且對數(shù)據(jù)類型的操作都是原子性的,因為執(zhí)行命令由單線程負責的,不存在并發(fā)競爭的問題。
除此之外,Redis 還支持事務(wù) 、持久化、Lua 腳本、多種集群方案(主從復(fù)制模式、哨兵模式、切片機群模式)、發(fā)布/訂閱模式,內(nèi)存淘汰機制、過期刪除機制等等。
BitMap是用一個bit位來標記某個元素,如果該元素存在,則將對應(yīng)的比特位設(shè)置為1,否則設(shè)置為0。
BitMap
由于采用了Bit為單位來存儲數(shù)據(jù),因此在存儲空間方面,可以大大節(jié)省BitMap適用于對大量的離散元素進行快速判斷和計數(shù),例如IP地址統(tǒng)計、重復(fù)元素判斷等。
布隆過濾器是用于判斷一個元素是否屬于一個集合。布隆過濾器通過多個哈希函數(shù)和一個位數(shù)組來表示集合中的元素,將元素映射到位數(shù)組中的多個位上。當一個元素經(jīng)過多個哈希函數(shù)映射后,對應(yīng)的位都被置為1。
舉個例子,假設(shè)有一個位圖數(shù)組長度為 8,哈希函數(shù) 3 個的布隆過濾器。
布隆過濾器
布隆過濾器判斷一個元素是否存在時,只需要檢查對應(yīng)的位是否都為1:
查詢布隆過濾器說數(shù)據(jù)存在,并不一定證明數(shù)據(jù)庫中存在這個數(shù)據(jù),但是查詢到數(shù)據(jù)不存在,數(shù)據(jù)庫中一定就不存在這個數(shù)據(jù)。布隆過濾器適用于對大規(guī)模數(shù)據(jù)進行快速的去重或判重操作,例如網(wǎng)絡(luò)爬蟲的URL去重、緩存的緩存命中判斷等。
主要是從內(nèi)存占用、對范圍查找的支持、實現(xiàn)難易程度這三方面總結(jié)的原因:
在 JDK 1.7 版本之前, HashMap 數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表,HashMap通過哈希算法將元素的鍵(Key)映射到數(shù)組中的槽位(Bucket)。如果多個鍵映射到同一個槽位,它們會以鏈表的形式存儲在同一個槽位上,因為鏈表的查詢時間是O(n),所以沖突很嚴重,一個索引上的鏈表非常長,效率就很低了。
所以在 JDK 1.8版本的時候做了優(yōu)化,當一個鏈表的長度超過8的時候就轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu),不再使用鏈表存儲,而是使用紅黑樹,查找時使用紅黑樹,時間復(fù)雜度O(log n),可以提高查詢性能,但是在數(shù)量較少時,即數(shù)量小于6時,會將紅黑樹轉(zhuǎn)換回鏈表。
HashMap
不是的,會產(chǎn)生這些并發(fā)安全問題:
可以改用并發(fā)安全的 map 容器,比如ConcurrentHashMap 或者 hashtable,都是能保證線程安全的。
JDK 1.7 ConcurrentHashMap
在 JDK 1.7 中它使用的是數(shù)組加鏈表的形式實現(xiàn)的,而數(shù)組又分為:大數(shù)組 Segment 和小數(shù)組 HashEntry。Segment 是一種可重入鎖(ReentrantLock),在 ConcurrentHashMap 里扮演鎖的角色;HashEntry 則用于存儲鍵值對數(shù)據(jù)。一個 ConcurrentHashMap 里包含一個 Segment 數(shù)組,一個 Segment 里包含一個 HashEntry 數(shù)組,每個 HashEntry 是一個鏈表結(jié)構(gòu)的元素。
JDK 1.7 ConcurrentHashMap
分段鎖技術(shù)將數(shù)據(jù)分成一段一段的存儲,然后給每一段數(shù)據(jù)配一把鎖,當一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候,其他段的數(shù)據(jù)也能被其他線程訪問,能夠?qū)崿F(xiàn)真正的并發(fā)訪問。
在 JDK 1.7 中,ConcurrentHashMap 雖然是線程安全的,但因為它的底層實現(xiàn)是數(shù)組 + 鏈表的形式,所以在數(shù)據(jù)比較多的情況下訪問是很慢的,因為要遍歷整個鏈表,而 JDK 1.8 則使用了數(shù)組 + 鏈表/紅黑樹的方式優(yōu)化了 ConcurrentHashMap 的實現(xiàn),具體實現(xiàn)結(jié)構(gòu)如下:
JDK 1.8 ConcurrentHashMap
JDK 1.8 ConcurrentHashMap 主要通過 volatile + CAS 或者 synchronized 來實現(xiàn)的線程安全的。
添加元素時首先會判斷容器是否為空:
如果根據(jù)存儲的元素計算結(jié)果為空,則利用 CAS 設(shè)置該節(jié)點;
如果根據(jù)存儲的元素計算結(jié)果不為空,則使用 synchronized ,然后,遍歷桶中的數(shù)據(jù),并替換或新增節(jié)點到桶中,最后再判斷是否需要轉(zhuǎn)為紅黑樹,這樣就能保證并發(fā)訪問時的線程安全了。
如果把上面的執(zhí)行用一句話歸納的話,就相當于是ConcurrentHashMap通過對頭結(jié)點加鎖來保證線程安全的,鎖的粒度相比 Segment 來說更小了,發(fā)生沖突和加鎖的頻率降低了,并發(fā)操作的性能就提高了。而且 JDK 1.8 使用的是紅黑樹優(yōu)化了之前的固定鏈表,那么當數(shù)據(jù)量比較大的時候,查詢性能也得到了很大的提升,從之前的 O(n) 優(yōu)化到了 O(logn) 的時間復(fù)雜度。
JDK 1.7 ConcurrentHashMap中的分段鎖是用了 ReentrantLock,是一個可重入的鎖。
可重入鎖是指同一個線程在獲取了鎖之后,可以再次重復(fù)獲取該鎖而不會造成死鎖或其他問題。當一個線程持有鎖時,如果再次嘗試獲取該鎖,就會成功獲取而不會被阻塞。
ReentrantLock實現(xiàn)可重入鎖的機制是基于線程持有鎖的計數(shù)器。
這種計數(shù)器的設(shè)計使得同一個線程可以多次獲取同一個鎖,而不會造成死鎖或其他問題。每次獲取鎖時,計數(shù)器加1;每次釋放鎖時,計數(shù)器減1。只有當計數(shù)器減到0時,鎖才會完全釋放。
ReentrantLock通過這種計數(shù)器的方式,實現(xiàn)了可重入鎖的機制。它允許同一個線程多次獲取同一個鎖,并且能夠正確地處理鎖的獲取和釋放,避免了死鎖和其他并發(fā)問題。
圖片
JVM的內(nèi)存結(jié)構(gòu)主要分為以下幾個部分:
Java 堆還被分為年輕代、老年代兩個區(qū)域,年輕代還被進一步劃分為 Eden 區(qū)、From Survivor 0、To Survivor 1 區(qū)。
不同的區(qū)域存放不同生命周期的對象,這樣可以根據(jù)不同的區(qū)域使用不同的垃圾回收算法,更具有針對性。
jvm-memory
當有對象需要分配時,一個對象永遠優(yōu)先被分配在年輕代的 Eden 區(qū),等到 Eden 區(qū)域內(nèi)存不夠時,Java 虛擬機會啟動垃圾回收。此時 Eden 區(qū)中沒有被引用的對象的內(nèi)存就會被回收,而一些存活時間較長的對象則會進入到老年代。在 JVM 中有一個名為 -XX:MaxTenuringThreshold 的參數(shù)專門用來設(shè)置晉升到老年代所需要經(jīng)歷的 GC 次數(shù),即在年輕代的對象經(jīng)過了指定次數(shù)的 GC 后,將在下次 GC 時進入老年代。
之所以要在堆區(qū)進一步劃分,主要是為了提高垃圾回收的效率。虛擬機中的對象必然有存活時間長的對象,也有存活時間短的對象,這是一個普遍存在的正態(tài)分布規(guī)律。如果我們將其混在一起,那么因為存活時間短的對象有很多,那么勢必導(dǎo)致較為頻繁的垃圾回收。而垃圾回收時不得不對所有內(nèi)存都進行掃描,但其實有一部分對象,它們存活時間很長,對他們進行掃描完全是浪費時間
String 保存在字符串常量池中,不同于其他對象,它的值是不可變的,且可以被多個引用共享。
類從被加載到虛擬機內(nèi)存開始,到卸載出內(nèi)存為止,它的整個生命周期包括以下 7 個階段:
驗證、準備、解析 3 個階段統(tǒng)稱為連接。
Load Class
JVM 中類的裝載是由類加載器,也就是ClassLoader,和它的子類來實現(xiàn)的,Java 中的類加載器是一個重要的 Java 運行時系統(tǒng)組件,它負責在運行時查找和裝入類文件中的類。
由于 Java 的跨平臺性, 經(jīng)過編譯的 Java 源程序并不是一個可執(zhí)行程序, 而是一個或多個類文件。當 Java 程序需要使用某個類時,JVM 會確保這個類已經(jīng)被加載、連接( 驗證、 準備和解析)和初始化。
類的加載是指把類的.class 文件中的數(shù)據(jù)讀入到內(nèi)存中,通常是創(chuàng)建一個字節(jié)數(shù)組讀入.class 文件,然后產(chǎn)生與所加載類對應(yīng)的 Class 對象。加載完成后, Class 對象還不完整, 所以此時的類還不可用。當類被加載后就進入連接階段, 這一階段包括驗證、準備( 為靜態(tài)變量分配內(nèi)存并設(shè)置默認的初始值) 和解析( 將符號引用替換為直接引用) 三個步驟。
最后 JVM 對類進行初始化,包括:1)如果類存在直接的父類并且這個類還沒有被初始化,那么就先初始化父類;2)如果類中存在初始化語句, 就依次執(zhí)行這些初始化語句。
我們先來看看發(fā)送方的窗口,下圖就是發(fā)送方緩存的數(shù)據(jù),根據(jù)處理的情況分成四個部分,其中深藍色方框是發(fā)送窗口,紫色方框是可用窗口:
圖片
在下圖,當發(fā)送方把數(shù)據(jù)「全部」都一下發(fā)送出去后,可用窗口的大小就為 0 了,表明可用窗口耗盡,在沒收到 ACK 確認之前是無法繼續(xù)發(fā)送數(shù)據(jù)了。
可用窗口耗盡
在下圖,當收到之前發(fā)送的數(shù)據(jù) 32~36 字節(jié)的 ACK 確認應(yīng)答后,如果發(fā)送窗口的大小沒有變化,則滑動窗口往右邊移動 5 個字節(jié),因為有 5 個字節(jié)的數(shù)據(jù)被應(yīng)答確認,接下來 52~56 字節(jié)又變成了可用窗口,那么后續(xù)也就可以發(fā)送 52~56 這 5 個字節(jié)的數(shù)據(jù)了。
32 ~ 36 字節(jié)已確認
TCP 滑動窗口方案使用三個指針來跟蹤在四個傳輸類別中的每一個類別中的字節(jié)。其中兩個指針是絕對指針(指特定的序列號),一個是相對指針(需要做偏移)。
圖片
SND.WND、SND.UN、SND.NXT
那么可用窗口大小的計算就可以是:
可用窗口大小 = SND.WND -(SND.NXT - SND.UNA)
接下來我們看看接收方的窗口,接收窗口相對簡單一些,根據(jù)處理的情況劃分成三個部分:
接收窗口
其中三個接收部分,使用兩個指針進行劃分:
粘包的問題出現(xiàn)是因為不知道一個用戶消息的邊界在哪,如果知道了邊界在哪,接收方就可以通過邊界來劃分出有效的用戶消息。
一般有三種方式分包的方式:
這種是最簡單方法,即每個用戶消息都是固定長度的,比如規(guī)定一個消息的長度是 64 個字節(jié),當接收方接滿 64 個字節(jié),就認為這個內(nèi)容是一個完整且有效的消息。
但是這種方式靈活性不高,實際中很少用。
我們可以在兩個用戶消息之間插入一個特殊的字符串,這樣接收方在接收數(shù)據(jù)時,讀到了這個特殊字符,就把認為已經(jīng)讀完一個完整的消息。
HTTP 是一個非常好的例子。
圖片
HTTP 通過設(shè)置回車符、換行符作為 HTTP 報文協(xié)議的邊界。
有一點要注意,這個作為邊界點的特殊字符,如果剛好消息內(nèi)容里有這個特殊字符,我們要對這個字符轉(zhuǎn)義,避免被接收方當作消息的邊界點而解析到無效的數(shù)據(jù)。
我們可以自定義一個消息結(jié)構(gòu),由包頭和數(shù)據(jù)組成,其中包頭包是固定大小的,而且包頭里有一個字段來說明緊隨其后的數(shù)據(jù)有多大。
比如這個消息結(jié)構(gòu)體,首先 4 個字節(jié)大小的變量來表示數(shù)據(jù)長度,真正的數(shù)據(jù)則在后面。
struct { u_int32_t message_length; char message_data[]; } message;
當接收方接收到包頭的大小(比如 4 個字節(jié))后,就解析包頭的內(nèi)容,于是就可以知道數(shù)據(jù)的長度,然后接下來就繼續(xù)讀取數(shù)據(jù),直到讀滿數(shù)據(jù)的長度,就可以組裝成一個完整到用戶消息來處理了。
HTTP/2 相比 HTTP/1.1 性能上的改進:
HTTP/2 會壓縮頭(Header)如果你同時發(fā)出多個請求,他們的頭是一樣的或是相似的,那么,協(xié)議會幫你消除重復(fù)的部分。
這就是所謂的 HPACK 算法:在客戶端和服務(wù)器同時維護一張頭信息表,所有字段都會存入這個表,生成一個索引號,以后就不發(fā)送同樣字段了,只發(fā)送索引號,這樣就提高速度了。
HTTP/2 不再像 HTTP/1.1 里的純文本形式的報文,而是全面采用了二進制格式,頭信息和數(shù)據(jù)體都是二進制,并且統(tǒng)稱為幀(frame):頭信息幀(Headers Frame)和數(shù)據(jù)幀(Data Frame)。
HTTP/1 與 HTTP/2
這樣雖然對人不友好,但是對計算機非常友好,因為計算機只懂二進制,那么收到報文后,無需再將明文的報文轉(zhuǎn)成二進制,而是直接解析二進制報文,這增加了數(shù)據(jù)傳輸?shù)男省?span style="display:none">FJ128資訊網(wǎng)——每日最新資訊28at.com
我們都知道 HTTP/1.1 的實現(xiàn)是基于請求-響應(yīng)模型的。同一個連接中,HTTP 完成一個事務(wù)(請求與響應(yīng)),才能處理下一個事務(wù),也就是說在發(fā)出請求等待響應(yīng)的過程中,是沒辦法做其他事情的,如果響應(yīng)遲遲不來,那么后續(xù)的請求是無法發(fā)送的,也造成了隊頭阻塞的問題。
而 HTTP/2 就很牛逼了,引出了 Stream 概念,多個 Stream 復(fù)用在一條 TCP 連接。
圖片
從上圖可以看到,1 個 TCP 連接包含多個 Stream,Stream 里可以包含 1 個或多個 Message,Message 對應(yīng) HTTP/1 中的請求或響應(yīng),由 HTTP 頭部和包體構(gòu)成。Message 里包含一條或者多個 Frame,F(xiàn)rame 是 HTTP/2 最小單位,以二進制壓縮格式存放 HTTP/1 中的內(nèi)容(頭部和包體)。
針對不同的 HTTP 請求用獨一無二的 Stream ID 來區(qū)分,接收端可以通過 Stream ID 有序組裝成 HTTP 消息,不同 Stream 的幀是可以亂序發(fā)送的,因此可以并發(fā)不同的 Stream ,也就是 HTTP/2 可以并行交錯地發(fā)送請求和響應(yīng)。
比如下圖,服務(wù)端并行交錯地發(fā)送了兩個響應(yīng):Stream 1 和 Stream 3,這兩個 Stream 都是跑在一個 TCP 連接上,客戶端收到后,會根據(jù)相同的 Stream ID 有序組裝成 HTTP 消息。
圖片
HTTP/2 還在一定程度上改善了傳統(tǒng)的「請求 - 應(yīng)答」工作模式,服務(wù)端不再是被動地響應(yīng),可以主動向客戶端發(fā)送消息。
客戶端和服務(wù)器雙方都可以建立 Stream, Stream ID 也是有區(qū)別的,客戶端建立的 Stream 必須是奇數(shù)號,而服務(wù)器建立的 Stream 必須是偶數(shù)號。
比如下圖,Stream 1 是客戶端向服務(wù)端請求的資源,屬于客戶端建立的 Stream,所以該 Stream 的 ID 是奇數(shù)(數(shù)字 1);Stream 2 和 4 都是服務(wù)端主動向客戶端推送的資源,屬于服務(wù)端建立的 Stream,所以這兩個 Stream 的 ID 是偶數(shù)(數(shù)字 2 和 4)。
再比如,客戶端通過 HTTP/1.1 請求從服務(wù)器那獲取到了 HTML 文件,而 HTML 可能還需要依賴 CSS 來渲染頁面,這時客戶端還要再發(fā)起獲取 CSS 文件的請求,需要兩次消息往返,如下圖左邊部分:
如上圖右邊部分,在 HTTP/2 中,客戶端在訪問 HTML 時,服務(wù)器可以直接主動推送 CSS 文件,減少了消息傳遞的次數(shù)。
I/O 的多路復(fù)用,可以只在一個進程里處理多個文件的 I/O,Linux 下有三種提供 I/O 多路復(fù)用的 API,分別是:select、poll、epoll。
select 和 poll 并沒有本質(zhì)區(qū)別,它們內(nèi)部都是使用「線性結(jié)構(gòu)」來存儲進程關(guān)注的 Socket 集合。
在使用的時候,首先需要把關(guān)注的 Socket 集合通過 select/poll 系統(tǒng)調(diào)用從用戶態(tài)拷貝到內(nèi)核態(tài),然后由內(nèi)核檢測事件,當有網(wǎng)絡(luò)事件產(chǎn)生時,內(nèi)核需要遍歷進程關(guān)注 Socket 集合,找到對應(yīng)的 Socket,并設(shè)置其狀態(tài)為可讀/可寫,然后把整個 Socket 集合從內(nèi)核態(tài)拷貝到用戶態(tài),用戶態(tài)還要繼續(xù)遍歷整個 Socket 集合找到可讀/可寫的 Socket,然后對其處理。
很明顯發(fā)現(xiàn),select 和 poll 的缺陷在于,當客戶端越多,也就是 Socket 集合越大,Socket 集合的遍歷和拷貝會帶來很大的開銷,因此也很難應(yīng)對 C10K。
epoll 是解決 C10K 問題的利器,通過兩個方面解決了 select/poll 的問題。
本文鏈接:http://www.www897cc.com/showinfo-26-57939-0.html還得是騰訊,撈了我一把!
聲明:本網(wǎng)頁內(nèi)容旨在傳播知識,若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系,我們將在第一時間刪除處理。郵件:2376512515@qq.com
上一篇: 分享元服務(wù)「心情盲盒」開發(fā)經(jīng)歷
下一篇: Spring 七種事務(wù)傳播性介紹