八股文

[TOC]

map

map 的底層實現(xiàn)原理是什么 - 碼農(nóng)桃花源 (gitbook.io)

底層數(shù)據(jù)結(jié)構(gòu)

// A header for a Go map.
type hmap struct {
    // 元素個數(shù)兰吟，調(diào)用 len(map) 時祟印，直接返回此值
    count     int
    flags     uint8
    // buckets 的對數(shù) log_2
    B         uint8
    // overflow 的 bucket 近似數(shù)
    noverflow uint16
    // 計算 key 的哈希的時候會傳入哈希函數(shù)
    hash0     uint32
    // 指向 buckets 數(shù)組，大小為 2^B
    // 如果元素個數(shù)為0，就為 nil
    buckets    unsafe.Pointer
    // 擴容的時候，buckets 長度會是 oldbuckets 的兩倍
    oldbuckets unsafe.Pointer
    // 指示擴容進度惭蹂，小于此地址的 buckets 遷移完成
    nevacuate  uintptr
    extra *mapextra // optional fields
}

B：buckets數(shù)組的長度的對數(shù)，也就是說 buckets 數(shù)組的長度就是 2^B萨醒。bucket 里面存儲了 key 和 value

buckets是一個指針烧栋，最終指向bmap這個數(shù)據(jù)結(jié)構(gòu)

type bmap struct {
    tophash [bucketCnt]uint8
}

// 但上述只是表面(src/runtime/hashmap.go)的結(jié)構(gòu)写妥，編譯期間會給它加料，動態(tài)地創(chuàng)建一個新的結(jié)構(gòu)：
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap：即常說的桶审姓。
1. 桶里面最多裝8個key珍特，會根據(jù) key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個位置
2. 如若有第九個key進來，會再創(chuàng)建一個bucket魔吐，通過overflow指針連接
3. bmap的內(nèi)存模型扎筒，是key/key/.../value/value/...，這樣可以減少額外的內(nèi)存對齊所需要的空間
map的創(chuàng)建：
1. map創(chuàng)建出來是一個指針酬姆，因此在作為函數(shù)參數(shù)傳入時嗜桌，內(nèi)部的改動也會影響到map自身
2. slice是一個結(jié)構(gòu)體，因此作為函數(shù)參數(shù)傳入時辞色，不會影響到數(shù)據(jù)自身骨宠，但是由于數(shù)據(jù)是指針，因此可以改變指向的數(shù)據(jù)
map的遍歷：是隨機的

go中range遍歷map淫僻，不是固定的從bucket0開始遍歷诱篷，每次會隨機一個bucket開始遍歷，并且bucket內(nèi)也是會隨機一個cell遍歷

map擴容

為避免大量key落在一個桶中雳灵，退化成鏈表棕所，導(dǎo)致查詢效率變?yōu)镺(n)，裝載因子被提出悯辙，用來衡量該情況琳省。

loadFactor := count / (2^B)

count : map中元素個數(shù)

B：2^B表示buckets數(shù)目

觸發(fā)擴容的時機：在向map中插入元素時，符合下面兩個條件躲撰，會觸發(fā)擴容
1. 裝載因子超出閾值6.5（元素塞滿了bucket）
2. overflow的bucket過多：（元素沒有塞滿bucket了针贬，bucket冗余空間過多）
  
  當(dāng) B 小于 15，也就是 bucket 總數(shù) 2^B 小于 2^15 時拢蛋，如果 overflow 的 bucket 數(shù)量超過 2^B桦他；當(dāng) B >= 15，也就是 bucket 總數(shù) 2^B 大于等于 2^15谆棱，如果 overflow 的 bucket 數(shù)量超過 2^15
擴容的邏輯：“漸進式”擴容快压，原有的 key 并不會一次性搬遷完畢，每次最多只會搬遷 2 個 bucket垃瞧。
1. 分配新的buckets
2. 搬遷到新的buckets蔫劣，發(fā)生在插入、修改和刪除時个从，會先檢查oldbuckets是否為nil（nil則搬遷完成脉幢，不需要再搬遷了）
擴容后的容量：針對擴容觸發(fā)的條件1和2歪沃，有兩種策略
1. buckets數(shù)目翻倍：
  
  要重新計算 key 的哈希，才能決定它到底落在哪個 bucket嫌松。
2. buckets數(shù)目相等：
  
  從老的 buckets 搬遷到新的 buckets沪曙，由于 bucktes 數(shù)量不變，因此可以按序號來搬豆瘫，比如原來在 0 號 bucktes珊蟀，到新的地方后，仍然放在 0 號 buckets外驱。

context

context作用

在一組 goroutine 之間傳遞共享的值
取消goroutine
防止goroutine泄露

不要將 Context 塞到結(jié)構(gòu)體里育灸。直接將 Context 類型作為函數(shù)的第一參數(shù)，而且一般都命名為 ctx昵宇。

不要向函數(shù)傳入一個 nil 的 context磅崭，如果你實在不知道傳什么，標(biāo)準(zhǔn)庫給你準(zhǔn)備好了一個 context：todo瓦哎。

不要把本應(yīng)該作為函數(shù)參數(shù)的類型塞到 context 中砸喻，context 存儲的應(yīng)該是一些共同的數(shù)據(jù)。例如：登陸的 session蒋譬、cookie 等割岛。

同一個 context 可能會被傳遞到多個 goroutine，別擔(dān)心犯助，context 是并發(fā)安全的癣漆。

context 主要用來在 goroutine 之間傳遞上下文信息，包括：取消信號剂买、超時時間惠爽、截止時間、k-v 等瞬哼。
隨著 context 包的引入婚肆，context 幾乎成為了并發(fā)控制和超時控制的標(biāo)準(zhǔn)做法。

context.Value

type valueCtx struct {
    Context
    key, val interface{}
}

key要求是可比較的
屬于一個樹結(jié)構(gòu)

<img src="C:\Users\Supreme\AppData\Roaming\Typora\typora-user-images\image-20220220230609169.png" alt="image-20220220230609169" style="zoom:50%;" />
取值過程坐慰，是會向上查找的
允許存在相同的key丛晌，向上查找會找到最后一個key相等的節(jié)點个盆，即層數(shù)高的節(jié)點

Goroutine

M必須擁有P才可執(zhí)行G中的代碼译秦，P含有一個包含多個G的隊列裤纹，P可以調(diào)度G交由M執(zhí)行
所有可執(zhí)行g(shù)o routine都放在隊列中：
- 全局隊列（GRQ）：存儲全局可運行的goroutine（從系統(tǒng)調(diào)用中恢復(fù)的G）；
- 本地可運行隊列（LRQ）：存儲本地（分配到P的）可運行的goroutine
workingschedule：各個P中維護的G隊列很可能是不均衡的把跨；空閑的P會查詢?nèi)株犃校羧株犃幸部照铀溃瑒t會從其他P中竊取G（一般每次取一半）着逐。

goroutine和線程的區(qū)別

內(nèi)存占用：goroutine默認棧為2KB，線程至少需要1MB
創(chuàng)建和銷毀：goroutine由go runtime管理，屬于用戶級別的耸别，消耗薪“拧；線程是操作系統(tǒng)創(chuàng)建的秀姐，是內(nèi)核級別的慈迈，消耗巨大
切換：goroutine切換只需要保存三個寄存器，線程切換需要寄存器

M:N模型（M個線程省有，N個goroutine）

go runtime負責(zé)管理goroutine痒留，Runtime會在程序啟動的時候，創(chuàng)建M個線程（CPU執(zhí)行調(diào)度的單位）蠢沿，之后創(chuàng)建的N個goroutine都會依附在這M個線程上執(zhí)行伸头。
同一時刻，一個線程只能跑一個goroutine舷蟀，當(dāng)goroutine發(fā)生阻塞時恤磷，runtime會把它調(diào)度走，讓其他goroutine來執(zhí)行野宜，不讓線程閑著

系統(tǒng)調(diào)用

同步調(diào)用

G1即將進入系統(tǒng)調(diào)用時扫步，M1將釋放P，讓某個空閑的M2獲取P并繼續(xù)執(zhí)行P隊列中剩余的G（即M2接替M1的工作）匈子；M2可能來源于M的緩存池河胎，也可能是新建的。當(dāng)G1系統(tǒng)調(diào)用完成后旬牲，根據(jù)M1能否獲取到P仿粹，將對G1做不同的處理：

有空閑的P，則獲取一個以繼續(xù)執(zhí)行G1原茅；
無空閑P吭历，將G1放入全局隊列，等待被其他P調(diào)度擂橘；M1進入緩沖池睡眠

異步調(diào)用

M 不會被阻塞晌区，G 的異步請求會被“代理人” network poller 接手，G 也會被綁定到 network poller
等到系統(tǒng)調(diào)用結(jié)束通贞，G 才會重新回到 P 上朗若。
M 由于沒被阻塞，它因此可以繼續(xù)執(zhí)行 LRQ 里的其他 G昌罩。

Redis：

slot

在redis集群內(nèi)部哭懈，采用slot槽位的邏輯管理方式，集群內(nèi)部共有16384(2的14次方)個Slot茎用，集群內(nèi)每個Redis Instance負責(zé)其中一部分的Slot的讀寫遣总。一個Key到底屬于哪個Slot睬罗，由分片算法：

crc16(key) % 16384

決定。也正是通過此分片算法旭斥，將不同的key以相對均勻的方式分配到不同的slot上容达。

watch：當(dāng)執(zhí)行多鍵值事務(wù)操作時，Redis不僅要求這些鍵值需要落在同一個Redis實例上垂券，還要求落在同一個slot上花盐。

官方介紹MULTI 、 EXEC 菇爪、 DISCARD 和 WATCH 是 Redis 事務(wù)相關(guān)的命令算芯，事務(wù)可以一次執(zhí)行多個命令，但是必須滿足2個條件：

事務(wù)是一個單獨的隔離操作：事務(wù)中的所有命令都會序列化娄帖、按順序地執(zhí)行也祠。事務(wù)在執(zhí)行的過程中，不會被其他客戶端發(fā)送來的命令請求所打斷近速。
事務(wù)是一個原子操作：事務(wù)中的命令要么全部被執(zhí)行诈嘿，要么全部都不執(zhí)行。執(zhí)行和是否成功是2個概念削葱，并不是一個失敗報錯等奖亚，其他就失敗。redis對事務(wù)是部分支持析砸。如果最開始語法等就有提交錯誤昔字，就相當(dāng)于java的編譯器都過不了，那么肯定全部不執(zhí)行首繁。如果在執(zhí)行過程中報錯作郭，已經(jīng)全部執(zhí)行了，但是誰報錯找誰弦疮，其他正常執(zhí)行放行夹攒。各取所需！這里的事務(wù)并不是要么全部成功胁塞，要么全部失敗咏尝，全部執(zhí)行和全部成功（或者都失敗）是2個概念啸罢。

hashtag

Hash Tag原理是：當(dāng)一個key包含 {} 的時候编检，不對整個key做hash，而僅對 {}包括的字符串做hash扰才。

Hash Tag可以讓不同的key擁有相同的hash值允懂，從而分配在同一個槽里；這樣針對不同key的批量操作(mget/mset等)衩匣，以及事務(wù)累驮、Lua腳本等都可以支持酣倾。不過Hash Tag可能會帶來數(shù)據(jù)分配不均的問題，這時需要：(1)調(diào)整不同節(jié)點中槽的數(shù)量谤专，使數(shù)據(jù)分布盡量均勻；(2)避免對熱點數(shù)據(jù)使用Hash Tag午绳，導(dǎo)致請求分布不均置侍。

bigkey

涉及到bigkey的操作，網(wǎng)卡會成為瓶頸
若需要刪除bigkey拦焚，直接del蜡坊，被操作的實例可能會直接卡死
業(yè)務(wù)上對bigkey取余，將數(shù)據(jù)分散赎败，避免生成bigkey

高可用

主從復(fù)制

一臺redis服務(wù)的數(shù)據(jù)秕衙，復(fù)制到多臺redis服務(wù)器。前者稱為主節(jié)點僵刮，后者為從節(jié)點
數(shù)據(jù)的復(fù)制是單向的据忘，只能從主節(jié)點復(fù)制到從節(jié)點

作用：
1. 數(shù)據(jù)冗余：實現(xiàn)了數(shù)據(jù)的熱備份，是持久化之外的數(shù)據(jù)冗余方式
2. 故障恢復(fù)：主節(jié)點失效搞糕，叢節(jié)點提供服務(wù)
3. 負載均衡：實現(xiàn)讀寫分離勇吊，主節(jié)點寫，叢節(jié)點讀
4. 高可用的基礎(chǔ)：主從復(fù)制是哨兵和集群模式能夠?qū)嵤┑幕A(chǔ)
數(shù)據(jù)同步：
1. 主從節(jié)點連接建立后窍仰，便開始數(shù)據(jù)同步汉规。
2. 根據(jù)主從節(jié)點當(dāng)前狀態(tài)，分為全量和部分復(fù)制
3. 具體執(zhí)行方式：從節(jié)點朝主節(jié)點發(fā)送psync命令驹吮，開始同步
命令傳播：

主從數(shù)據(jù)同步完成后针史，主節(jié)點將自己執(zhí)行的寫命令發(fā)送給叢節(jié)點（該過程是異步的），保證數(shù)據(jù)的一致性碟狞。

哨兵

能夠自動完成故障發(fā)現(xiàn)和轉(zhuǎn)移啄枕，從而實現(xiàn)高可用
由一組哨兵節(jié)點和一組（或多組）主從復(fù)制節(jié)點組成

心跳機制
故障轉(zhuǎn)移
1. 每個 Sentinel 都會定時進行心跳檢查，當(dāng)發(fā)現(xiàn)主節(jié)點出現(xiàn)心跳檢測超時的情況時篷就，此時認為該主節(jié)點已經(jīng)不可用射亏，這種判定稱為主觀下線。
2. 哨兵節(jié)點開始投票竭业，當(dāng)超過半數(shù)認為該主節(jié)點故障智润，會將其下線：基于raft算法，選取一個哨兵節(jié)點來執(zhí)行該過程
  - 選取一個從節(jié)點作為主節(jié)點未辆，將其他從節(jié)點和該節(jié)點綁定
  - 原來的主節(jié)點更新為從節(jié)點窟绷，對其監(jiān)控，等恢復(fù)后咐柜，命令其去復(fù)制新的主節(jié)點

cluster集群

由多個主從復(fù)制的結(jié)構(gòu)組成
每個主從復(fù)制的結(jié)構(gòu)看做一個節(jié)點

持久化

RDB

優(yōu)勢：

RDB 是一個非常緊湊（compact）的二進制文件兼蜈，體積小攘残，因此在傳輸速度上比較快，因此適合災(zāi)難恢復(fù)为狸。
數(shù)據(jù)恢復(fù)速度比aof快

劣勢：

rdb出現(xiàn)故障丟的數(shù)據(jù)會比aof多歼郭。你通常會每隔5分鐘或者更久做一次完整的保存,萬一在 Redis 意外宕機,你可能會丟失幾分鐘的數(shù)據(jù)。
rdb需要fork子進程來保存數(shù)據(jù)到硬盤辐棒，當(dāng)數(shù)據(jù)集比較大時病曾， fork比較耗時，從而導(dǎo)致redis主線程在一些毫秒級別內(nèi)無法響應(yīng)客戶端

AOF