騰訊的校招面試也沒那么難嘛!
今天分享的是騰訊校招Golang后端面經(jīng),這位同學一面之后信心滿滿的來找我說:“騰訊的校招面試也沒那么難嘛,也可能只是一面,后面才會放大招?!?/p>
TA復盤的關鍵面試題如下:
圖片
我給大家整理一下考察的知識:
- Go基礎:數(shù)組和切片,結構體,逃逸分析,GC
- 數(shù)據(jù)結構:B+樹和B樹
- 緩存:持久化策略,緩存穿透
- 計網(wǎng):TCP/UDP
- 算法:最長回文串
面試題詳解
slice和數(shù)組的區(qū)別
這是一個經(jīng)常問到的面試題。
slice 的底層數(shù)據(jù)是數(shù)組,它描述一個數(shù)組的片段。兩者都可以通過下標來訪問單個元素。
數(shù)組是定長的,長度定義好之后,不能再更改。在 Go 中,數(shù)組是不常見的,因為其長度是類型的一部分,限制了它的表達能力,比如 [3]int 和 [4]int 就是不同的類型。
而切片則非常靈活,它可以動態(tài)地擴容。切片的類型和長度無關。
數(shù)組就是一片連續(xù)的內(nèi)存, slice 實際上是一個結構體,包含三個字段:長度、容量、底層數(shù)組。
type slice struct {
array unsafe.Pointer // 元素指針
len int // 長度
cap int // 容量
}
slice的數(shù)據(jù)結構如下:
圖片
(注意: 底層數(shù)組是可以被多個 slice 同時指向的,因此對一個 slice 的元素進行操作是有可能影響到其他 slice 的。)
還有一個很重要的區(qū)別就是slice作為函數(shù)參數(shù)傳遞時為按引用傳遞的,函數(shù)內(nèi)對其元素的修改將導致函數(shù)外的值也發(fā)生改變,不過需要注意的是傳入的是一個指針的副本,如果對該指針進行修改,不會導致原本的指針發(fā)生變化。而數(shù)組是值傳遞,函數(shù)內(nèi)對數(shù)組的值的改變不影響初始數(shù)組。
兩個結構體可以進行等值比較嗎?
可以試一下運行下列代碼:
package main
import "fmt"
func main() {
sn1 := struct {
age int
name string
}{age: 11, name: "qq"}
sn2 := struct {
age int
name string
}{age: 11, name: "qq"}
if sn1 == sn2 {
fmt.Println("sn1 == sn2")
}
sm1 := struct {
age int
m map[string]string
}{age: 11, m: map[string]string{"a": "1"}}
sm2 := struct {
age int
m map[string]string
}{age: 11, m: map[string]string{"a": "1"}}
if sm1 == sm2 {
fmt.Println("sm1 == sm2")
}
}
參考答案:編譯不通過 invalid operation: sm1 == sm2
解析:
- 結構體能比較是否相等,不能比較大小。
- 相同類型的結構體才能夠進行比較,結構體是否相同不但與屬性類型有關,還與屬性順序相關,下面的sn3 與上面的 sn1 就是不同的結構體
sn3:= struct {
name string
age int
}{age:11,name:"qq"}
- 如果 struct 的所有成員都可以?較,則該 struct 就可以通過 == 或 != 進??較是否相等,?較時逐個項進??較,如果每?項都相等,則兩個結構體才相等,否則不相等;
那什么是可?較的呢,常?的有 bool、數(shù)值型、string、指針、數(shù)組等,像切?、map、函數(shù)等是不能 ?較的。
說說逃逸分析
要搞清楚GO的逃逸分析一定要先搞清楚內(nèi)存分配和堆棧:
內(nèi)存既可以分配到堆中,也可以分配到棧中。
GO語言是如何進行內(nèi)存分配的呢?其設計初衷和實現(xiàn)原理是什么呢?
要搞清楚上面的問題,我們先來聊一下內(nèi)存管理和堆、棧的知識點:
內(nèi)存管理
內(nèi)存管理主要包括兩個動作:分配與釋放。逃逸分析就是服務于內(nèi)存分配的,而內(nèi)存的釋放由GC負責。
棧
在Go語言中,棧的內(nèi)存是由編譯器自動進行分配和釋放的,棧區(qū)往往存儲著函數(shù)參數(shù)、局部變量和調(diào)用函數(shù)幀,它們隨著函數(shù)的創(chuàng)建而分配,隨著函數(shù)的退出而銷毀。
Go應用程序運行時,每個 goroutine 都維護著一個自己的棧區(qū),這個棧區(qū)只能自己使用不能被其他 goroutine 使用。棧是調(diào)用棧(call stack)的簡稱。一個棧通常又包含了許多棧幀(stack frame),它描述的是函數(shù)之間的調(diào)用關系
堆
與棧不同的是,堆區(qū)的內(nèi)存一般由編譯器和工程師自己共同進行管理分配,交給 Runtime GC 來釋放。在堆上分配時,必須找到一塊足夠大的內(nèi)存來存放新的變量數(shù)據(jù)。后續(xù)釋放時,垃圾回收器掃描堆空間尋找不再被使用的對象。
我們可以簡單理解為:我們用GO語言開發(fā)過程中,要考慮的內(nèi)存管理只是針對堆內(nèi)存而言的。
程序在運行期間可以主動從堆上申請內(nèi)存,這些內(nèi)存通過Go的內(nèi)存分配器分配,并由垃圾收集器回收。
為了方便大家理解,我們再從以下角度對比一下堆棧:
堆和棧的對比
加鎖
- 棧不需要加鎖:每個goroutine都獨享自己的??臻g,這就意味著棧上的內(nèi)存操作是不需要加鎖的。
- 堆有時需要加鎖:堆上的內(nèi)存,有時需要加鎖防止多線程沖突
延伸知識點:為什么堆上的內(nèi)存有時需要加鎖?而不是一直需要加鎖呢?
因為Go的內(nèi)存分配策略學習了TCMalloc的線程緩存思想,他為每個處理器分配了一個mcache,注意:從mcache分配內(nèi)存也是無鎖的。
性能
- 棧內(nèi)存管理 性能好:棧上的內(nèi)存,它的分配與釋放非常高效的。簡單地說,它只需要兩個CPU指令:一個是分配入棧,另外一個是棧內(nèi)釋放。只需要借助于棧相關寄存器即可完成。
- 堆內(nèi)存管理 性能差:對于程序堆上的內(nèi)存回收,還需要有標記清除階段,例如Go采用的三色標記法。
緩存策略
- 棧緩存性能更好
- 堆緩存性能較差原因是:棧內(nèi)存能更好地利用CPU的緩存策略,因為??臻g相較于堆來說是更連續(xù)的。
逃逸分析
上面說了這么多堆和棧的知識點,目的是為了讓大家更好的理解逃逸分析。
正如上面講的,相比于把內(nèi)存分配到堆中,分配到棧中優(yōu)勢更明顯。
Go語言也是這么做的:Go編譯器會盡可能將變量分配到到棧上。
但是,在函數(shù)返回后無法證明變量未被引用,則該變量將被分配到堆上,該變量不隨函數(shù)棧的回收而回收。以此避免懸掛指針(dangling pointer)的問題。
另外,如果局部變量占用內(nèi)存非常大,也會將其分配在堆上。
Go是如何確定內(nèi)存是分配到棧上還是堆上的呢?
答案就是:逃逸分析。
編譯器通過逃逸分析技術去選擇堆或者棧,逃逸分析的基本思想如下:檢查變量的生命周期是否是完全可知的,如果通過檢查,則在棧上分配。否則,就是所謂的逃逸,必須在堆上進行分配。
逃逸分析原則
Go語言雖然沒有明確說明逃逸分析原則,但是有以下幾點準則,是可以參考的。
- 不同于JAVA JVM的運行時逃逸分析,Go的逃逸分析是在編譯期完成的:編譯期無法確定的參數(shù)類型必定放到堆中;
- 如果變量在函數(shù)外部存在引用,則必定放在堆中;
- 如果變量占用內(nèi)存較大時,則優(yōu)先放到堆中;
- 如果變量在函數(shù)外部沒有引用,則優(yōu)先放到棧中;
GC中的根節(jié)點是什么?
Go 基礎知識中 GC 肯定是比較重要的部分,然而平時我們在看八股文的時候總會對文中所提到的“根節(jié)點”產(chǎn)生疑惑,那么到底什么是根節(jié)點呢?
在垃圾回收的上下文中,“根節(jié)點”是指程序中被直接或間接引用的對象集合。
針對 Go 語言,垃圾回收器會從程序的“根節(jié)點”開始遍歷,找出所有可以被訪問到的對象,并標記它們?yōu)榭蛇_對象。根據(jù)上述“根節(jié)點”定義,Go 程序的根節(jié)點通常包括以下幾類對象:
- 程序的全局變量和靜態(tài)變量:這些變量在整個程序執(zhí)行過程中都可以被訪問到,因此垃圾回收器會將它們作為根節(jié)點。
- 程序的調(diào)用棧中的變量:這些變量在函數(shù)調(diào)用過程中被創(chuàng)建,并在函數(shù)返回時被銷毀。因此,在函數(shù)調(diào)用期間,它們被認為是根節(jié)點。
- 當前執(zhí)行的Goroutine:在 Go 語言中,Goroutine 是輕量級的線程,它們可以獨立地運行,因此當前執(zhí)行的Goroutine也被認為是根節(jié)點。
垃圾回收器從這些根節(jié)點開始遍歷,查找所有可以被訪問到的對象,并標記它們?yōu)榭蛇_對象。而沒有被標記為可達對象的對象就是垃圾對象,可以被回收。這個過程被稱為可達性分析。
既然 GC 不在棧上起作用,那為什么根節(jié)點還包括程序的調(diào)用棧中的變量呢?
根節(jié)點是指程序中被直接或間接引用的對象集合,它們是垃圾回收器掃描堆中對象時的起點。程序的調(diào)用棧中的變量也可以被認為是根節(jié)點之一,因為它們可以被其他對象引用。
調(diào)用棧是用于存儲函數(shù)調(diào)用信息的一種數(shù)據(jù)結構,它由多個幀組成,每個幀對應一個函數(shù)調(diào)用。每當一個函數(shù)被調(diào)用時,就會在調(diào)用棧中創(chuàng)建一個新的幀,并將該函數(shù)的參數(shù)、局部變量和返回地址等信息保存到幀中。當函數(shù)返回時,對應的幀就會被銷毀,該函數(shù)的所有局部變量也隨之被釋放。雖然調(diào)用棧中的變量存儲在棧上,但它們也可以被其他對象引用,例如一個函數(shù)返回一個指向調(diào)用棧中局部變量的指針。因此,當垃圾回收器掃描堆中對象時,它也需要考慮調(diào)用棧中的變量是否被其他對象引用,以便正確地標記和回收不再使用的對象。
綜上所述,調(diào)用棧中的變量雖然存儲在棧上,但它們也可以被認為是根節(jié)點之一,因為它們可以被其他對象引用。因此,在Go語言中,垃圾回收器需要掃描調(diào)用棧中的變量,以確保不會回收被其他對象引用的變量。
b樹和b+樹的區(qū)別,為什么索引使用b+樹結構?
- B樹的每個節(jié)點都存儲了key和data,而B+樹的data存儲在葉子節(jié)點上。
B+樹非葉子節(jié)點僅存儲key不存儲data,這樣一個節(jié)點就可以存儲更多的key。可以使得B+樹相對B樹來說更矮(IO次數(shù)就是樹的高度),所以與磁盤交換的IO操作次數(shù)更少。
- B+樹所有葉子節(jié)點構成一個有序鏈表,按主鍵排序來遍歷全部記錄,能更好支持范圍查找。
由于數(shù)據(jù)順序排列并且相連,所以便于區(qū)間查找和搜索。而B樹則需要進行每一層的遞歸遍歷,相鄰的元素可能在內(nèi)存中不相鄰,所以緩存命中性沒有B+樹好。
- B+樹所有的查詢都要從根節(jié)點查找到葉子節(jié)點,查詢性能更穩(wěn)定;而B樹,每個節(jié)點都可能查找到數(shù)據(jù),需要在葉子節(jié)點和內(nèi)部節(jié)點不停的往返移動,所以不穩(wěn)定。
redis持久化策略?
RDB持久化(全量備份)
RDB持久化是指在指定時間間隔內(nèi)將內(nèi)存中的數(shù)據(jù)集快照寫入磁盤。實際上fork子線程,先將數(shù)據(jù)集寫入臨時文件,寫入成功后,在替換之前的文件,用二進制壓縮文件,RDB是Redis默認的持久化方式,會在對應目錄下生產(chǎn)一個dump.rdb文件,重啟會通過加載dump.rdb文件恢復數(shù)據(jù)
RDB優(yōu)點:
- 方便持久化:只有一個dump.rdb文件;
- 容災性好:一個文件可以保存到安全的磁盤;
- 性能好:fork子線程來完成寫操作,主線程繼續(xù)處理命令;
- 效率高:如何數(shù)據(jù)集偏大,RDB啟動效率比AOF高
RDB缺點:
- 數(shù)據(jù)安全性低:因為RDB是每隔一段時間進行持久化,可能會造成數(shù)據(jù)丟失。
- 由于RDB是通過fork子線程協(xié)助完成數(shù)據(jù)持久化工作的,因此如果數(shù)據(jù)集較大時,可能會導致整個服務停止服務幾百毫秒,甚至一分鐘。
AOF持久化(增量備份)
AOF持久化是以日志的形式記錄記錄每一個增刪操作然后追加到文件中。AOF的出現(xiàn)是為了彌補RDB備份的不足(數(shù)據(jù)不一致性)。
與RDB持久化相比,AOF的持久化實時性更好。
AOF的備份策略:Redis的配置文件中存在三種不同的AOF持久化方式:
- appendfsync always:每次有數(shù)據(jù)修改發(fā)生時都會同步。
- appendfsync everysec:每秒同步一次
- appendsync no:讓操作系統(tǒng)決定何時進行同步。
AOF優(yōu)點:
- AOF實時性哈好,數(shù)據(jù)安全性更高;
- AOF通過append模式寫文件,即使中途服務器宕機,也可以通過redis-check-aof工具解決數(shù)據(jù)一致性問題。
- AOF機制的rewrite模式(文件過大會對命令進行合并重寫),可以刪除其中某些命令(比如誤操作的命令)
AOF缺點:
- AOF文件比RDB文件大,且恢復慢;
- 根據(jù)同步策略的不同,AOF在運行效率上往往會慢于RDB。
兩者結合
將 RDB 和 AOF 合體使用,這個方法是在 Redis 4.0 提出的,該方法叫混合使用 AOF 日志和內(nèi)存快照,也叫混合持久化。
混合持久化工作在 AOF 日志重寫過程。
當開啟了混合持久化時,在 AOF 重寫日志時,fork 出來的重寫子進程會先將與主線程共享的內(nèi)存數(shù)據(jù)以 RDB 方式寫入到 AOF 文件,然后主線程處理的操作命令會被記錄在重寫緩沖區(qū)里,重寫緩沖區(qū)里的增量命令會以 AOF 方式寫入到 AOF 文件,寫入完成后通知主進程將新的含有 RDB 格式和 AOF 格式的 AOF 文件替換舊的的 AOF 文件。
也就是說,使用了混合持久化,AOF 文件的前半部分是 RDB 格式的全量數(shù)據(jù),后半部分是 AOF 格式的增量數(shù)據(jù)。
這樣的好處在于,重啟 Redis 加載數(shù)據(jù)的時候,由于前半部分是 RDB 內(nèi)容,這樣加載的時候速度會很快。
加載完 RDB 的內(nèi)容后,才會加載后半部分的 AOF 內(nèi)容,這里的內(nèi)容是 Redis 后臺子進程重寫 AOF 期間,主線程處理的操作命令,可以使得數(shù)據(jù)更少的丟失。
緩存穿透,怎么解決?
當用戶訪問的數(shù)據(jù),既不在緩存中,也不在數(shù)據(jù)庫中,導致請求在訪問緩存時,發(fā)現(xiàn)緩存缺失,再去訪問數(shù)據(jù)庫時,發(fā)現(xiàn)數(shù)據(jù)庫中也沒有要訪問的數(shù)據(jù),沒辦法構建緩存數(shù)據(jù),來服務后續(xù)的請求。那么當有大量這樣的請求到來時,數(shù)據(jù)庫的壓力驟增,這就是緩存穿透的問題。
緩存穿透的發(fā)生一般有這兩種情況:
- 業(yè)務誤操作,緩存中的數(shù)據(jù)和數(shù)據(jù)庫中的數(shù)據(jù)都被誤刪除了,所以導致緩存和數(shù)據(jù)庫中都沒有數(shù)據(jù);
- 黑客惡意攻擊,故意大量訪問某些讀取不存在數(shù)據(jù)的業(yè)務;
應對緩存穿透的方案,常見的方案有三種。
- 第一種方案,非法請求的限制;
- 第二種方案,緩存空值或者默認值;
- 第三種方案,使用布隆過濾器快速判斷數(shù)據(jù)是否存在,避免通過查詢數(shù)據(jù)庫來判斷數(shù)據(jù)是否存在;
第一種方案,非法請求的限制
當有大量惡意請求訪問不存在的數(shù)據(jù)的時候,也會發(fā)生緩存穿透,因此在 API 入口處我們要判斷求請求參數(shù)是否合理,請求參數(shù)是否含有非法值、請求字段是否存在,如果判斷出是惡意請求就直接返回錯誤,避免進一步訪問緩存和數(shù)據(jù)庫。
第二種方案,緩存空值或者默認值
當我們線上業(yè)務發(fā)現(xiàn)緩存穿透的現(xiàn)象時,可以針對查詢的數(shù)據(jù),在緩存中設置一個空值或者默認值,這樣后續(xù)請求就可以從緩存中讀取到空值或者默認值,返回給應用,而不會繼續(xù)查詢數(shù)據(jù)庫。
第三種方案,使用布隆過濾器快速判斷數(shù)據(jù)是否存在,避免通過查詢數(shù)據(jù)庫來判斷數(shù)據(jù)是否存在。
我們可以在寫入數(shù)據(jù)庫數(shù)據(jù)時,使用布隆過濾器做個標記,然后在用戶請求到來時,業(yè)務線程確認緩存失效后,可以通過查詢布隆過濾器快速判斷數(shù)據(jù)是否存在,如果不存在,就不用通過查詢數(shù)據(jù)庫來判斷數(shù)據(jù)是否存在。
即使發(fā)生了緩存穿透,大量請求只會查詢 Redis 和布隆過濾器,而不會查詢數(shù)據(jù)庫,保證了數(shù)據(jù)庫能正常運行,Redis 自身也是支持布隆過濾器的。
TCP/UDP 詳解,區(qū)別
作用
首先,tcp和udp都是工作再傳輸層,用于程序之間傳輸數(shù)據(jù)的。數(shù)一般包含:文件類型,視頻類型,jpg圖片等。
圖片
區(qū)別
TCP是基于連接的,而UDP是基于非連接的。
tcp傳輸數(shù)據(jù)穩(wěn)定可靠,適用于對網(wǎng)絡通訊質(zhì)量要求較高的場景,需要準確無誤的傳輸給對方,比如,傳輸文件,發(fā)送郵件,瀏覽網(wǎng)頁等等。
udp的優(yōu)點是速度快,但是可能產(chǎn)生丟包,所以適用于對實時性要求較高但是對少量丟包并沒有太大要求的場景。比如:域名查詢,語音通話,視頻直播等。udp還有一個非常重要的應用場景就是隧道網(wǎng)絡,比如:vpn,VXLAN。
以人與人之間的通信為例:UDP協(xié)議就相當于是寫信給對方,寄出去信件之后不能知道對方是否收到信件,信件內(nèi)容是否完整,也不能得到及時反饋,而TCP協(xié)議就像是打電話通信,在這一系列流程都能得到及時反饋,并能確保對方及時接收到。如下圖:
圖片
三次握手
當客戶端向服務端發(fā)起連接時,會先發(fā)一包連接請求數(shù)據(jù),過去詢問一下,能否與你建立連接?這包數(shù)據(jù)稱之為SYN包,如果對端同意連接,則回復一包SYN+ACK包,客戶端收到之后,發(fā)送一包ACK包,連接建立,因為這個過程中互相發(fā)送了三包數(shù)據(jù),所以稱之為三次握手。
圖片
為什么要三次握手而不是兩次握手?
這是為了防止,因為已失效的請求報文,突然又傳到服務器,引起錯誤,這是什么意思?
假設采用兩次握手建立連接,客戶端向服務端發(fā)送一個syn包請求建立連接,因為某些未知的原因,并沒有到達服務器,在中間某個網(wǎng)絡節(jié)點產(chǎn)生了滯留,為了建立連接,客戶端會重發(fā)syn包,這次的數(shù)據(jù)包正常送達,服務端發(fā)送syn+ack之后就建立起了連接,但是第一包數(shù)據(jù)阻塞的網(wǎng)絡突然恢復,第一包syn包又送達到服務端,這是服務端會認為客戶端又發(fā)起了一個新的連接,從而在兩次握手之后進入等待數(shù)據(jù)狀態(tài),服務端認為是兩個連接,而客戶端認為是一個連接,造成了狀態(tài)不一致,如果在三次握手的情況下,服務端收不到最后的ack包,自然不會認為連接建立成功,所以三次握手本質(zhì)上來說就是為了解決網(wǎng)絡信道不可靠的問題,為了在不可靠的信道上建立起可靠的連接,經(jīng)過三次握手之后,客戶端和服務端都進入了數(shù)據(jù)傳輸狀態(tài)。
四次揮手
圖片
處于連接狀態(tài)的客戶端和服務端,都可以發(fā)起關閉連接請求,此時需要四次揮手來進行連接關閉。
假設客戶端主動發(fā)起連接關閉請求,他給服務端發(fā)起一包FIN包,標識要關閉連接,自己進入終止等待1裝填,服務端收到FIN包,發(fā)送一包ACK包,標識自己進入了關閉等待狀態(tài),客戶端進入終止等待2狀態(tài)。這是第二次揮手,服務端此時還可以發(fā)送未發(fā)送的數(shù)據(jù),而客戶端還可以接受數(shù)據(jù),待服務端發(fā)送完數(shù)據(jù)之后,發(fā)送一包FIN包,最后進入確認狀態(tài),這是第3次揮手,客戶端收到之后恢復ACK包,進入超時等待狀態(tài),經(jīng)過超時時間后關閉連接,而服務端收到ACK包后,立即關閉連接,這是第四次揮手。
為什么客戶端要等待超時時間?
這是為了保證對方已經(jīng)收到ACK包,因為假設客戶端發(fā)送完最后一包ACK包后釋放了連接,一旦ACK包在網(wǎng)絡中丟失,服務端將一直停留在 最后確認狀態(tài),如果等待一段時間,這時服務端會因為沒有收到ack包重發(fā)FIN包,客戶端會響應 這個FIN包進行重發(fā)ack包,并刷新超時時間,這個機制跟第三次握手一樣。也是為了保證在不可靠的網(wǎng)絡鏈路中進行可靠的連接斷開確認。
本文轉載自微信公眾號「 程序員升級打怪之旅」,作者「小韜&王中陽」,可以通過以下二維碼關注。
轉載本文請聯(lián)系「 程序員升級打怪之旅」公眾號。