Algorithm
146. LRU 緩存
使用雙向鏈表存儲先后順序
type LinkNode struct {
key, value int
Pre, Next *LinkNode
}
type LRUCache struct {
cacheMap map[int]*LinkNode
head, tail *LinkNode
maxSize int
currentSize int
}
func Constructor(capacity int) (lruCache LRUCache) {
cacheMap := make(map[int]*LinkNode)
head := LinkNode{}
tail := LinkNode{}
head.Next = &tail
tail.Pre = &head
lruCache = LRUCache{
cacheMap: cacheMap,
head: &head,
tail: &tail,
maxSize: capacity,
currentSize: 0,
}
return
}
func (this *LRUCache) Get(key int) (result int) {
linkNode, ok := this.cacheMap[key]
if ok {
result = linkNode.value
// 刪除節(jié)點(diǎn)
linkNode.Pre.Next = linkNode.Next
linkNode.Next.Pre = linkNode.Pre
// 挪到最前面
linkNode.Next = this.head.Next
this.head.Next.Pre = linkNode
this.head.Next = linkNode
linkNode.Pre = this.head
}
if !ok {
result = -1
}
return
}
func (this *LRUCache) Put(key int, value int) {
linkNode, ok := this.cacheMap[key]
if ok {
// 更新值
linkNode.value = value
// 刪除節(jié)點(diǎn)
linkNode.Pre.Next = linkNode.Next
linkNode.Next.Pre = linkNode.Pre
// 挪到最前面
linkNode.Next = this.head.Next
this.head.Next.Pre = linkNode
this.head.Next = linkNode
linkNode.Pre = this.head
}
if !ok {
linkNode = &LinkNode{
value: value,
key: key,
}
if this.currentSize < this.maxSize {
this.cacheMap[key] = linkNode
// 挪到最前面
linkNode.Next = this.head.Next
this.head.Next.Pre = linkNode
this.head.Next = linkNode
linkNode.Pre = this.head
this.currentSize += 1
} else {
lastNode := this.tail.Pre
// 刪除map
delete(this.cacheMap, lastNode.key)
// 刪除節(jié)點(diǎn)
lastNode.Pre.Next = lastNode.Next
lastNode.Next.Pre = lastNode.Pre
// 增加map
this.cacheMap[key] = linkNode
// 挪到最前面
linkNode.Next = this.head.Next
this.head.Next.Pre = linkNode
this.head.Next = linkNode
linkNode.Pre = this.head
}
}
}
Review
Understanding the Go Scheduler and discovering how it works
本篇文章作者帶著我們從頭實(shí)現(xiàn)了一個(gè)簡易版本的gmp調(diào)度器斜棚，淺顯易懂的向讀者解釋了為什么GMP這樣子設(shè)計(jì)。
首先實(shí)現(xiàn)一個(gè)協(xié)程調(diào)度器，有幾個(gè)比較重要的點(diǎn)或者需求：
- 協(xié)程需要時(shí)輕量級的，要比操作系統(tǒng)提供的線程更加輕量級。
- 協(xié)程要能夠處理system call和IO操作。
- 要能夠?qū)崿F(xiàn)真正的并行
- 協(xié)程的調(diào)度要足夠公平，避免同一個(gè)function一直搶占CPU時(shí)間片
- 最后是控制創(chuàng)建的協(xié)程數(shù)量印蔬，避免過多搶占操作系統(tǒng)資源。
為了實(shí)現(xiàn)上訴需求脱衙，我們可以一步一步迭代一個(gè)協(xié)程調(diào)度器侥猬。
- 首先最簡單的版本，我們實(shí)現(xiàn)的協(xié)程和線程之間為1：1的映射關(guān)系捐韩，也就是我們?yōu)槊總€(gè)協(xié)程創(chuàng)建一個(gè)線程退唠。這里顯而易見的，是不夠輕量的荤胁。需要進(jìn)一步迭代瞧预。
- 我們做一點(diǎn)改進(jìn)，我們讓協(xié)程和線程之間改成M:N的映射關(guān)系。也就是我們前置性的創(chuàng)建M個(gè)線程垢油，然后用戶需要創(chuàng)建的N個(gè)協(xié)程任務(wù)每次都分配給這M個(gè)線程進(jìn)行處理盆驹。為了實(shí)現(xiàn)這個(gè)機(jī)制，我們引入global task queue秸苗，每次用戶創(chuàng)建的協(xié)程任務(wù)都push到queue里面召娜，并且每個(gè)線程都統(tǒng)一從這個(gè)queue中取任務(wù)去執(zhí)行运褪。因?yàn)槭嵌鄠€(gè)線程從一個(gè)global queue里面取任務(wù)惊楼，為了保證并發(fā)安全，我們需要對每次的取任務(wù)加上mutex鎖秸讹。
- 在上訴步驟里面檀咙，為了保障并發(fā)安全我們給global queue加上了鎖，隨著我們的push和pop queue的操作越來越頻繁璃诀，global queue的鎖成為我們的并發(fā)性能瓶頸弧可。為了解決這個(gè)問題，這時(shí)候我們引入了local task queue劣欢，也就是每個(gè)線程維護(hù)自己的local queue棕诵。每次線程都從自己的local queue里面取任務(wù)執(zhí)行，同時(shí)因?yàn)槊總€(gè)線程操作自己的queue也就不存在并發(fā)安全了凿将，不需要加鎖校套。
- 為了保障每個(gè)線程不會空轉(zhuǎn)，我們還可以引入了Work Stealing的機(jī)制牧抵。也就是每個(gè)線程自己的queue如果空了笛匙，這時(shí)候就可以嘗試去其他線程的queue里面取任務(wù)進(jìn)行執(zhí)行。
- 上面實(shí)現(xiàn)的調(diào)度器有個(gè)比較大的問題就是無法處理system call或者IO function犀变，如果某個(gè)協(xié)程的任務(wù)是需要進(jìn)行IO讀寫的話妹孙，這時(shí)候?qū)?yīng)的線程就會處于sleep狀態(tài)（需要等內(nèi)存中斷處理結(jié)束）。為了解決這個(gè)問題获枝，引入了Processors的概念蠢正。具體來說就是我們現(xiàn)在每個(gè)local task queue對應(yīng)的核心處理單元不再是線程而是processor，每個(gè)processor可以對應(yīng)多個(gè)線程省店。這樣子我們調(diào)度器在遇到IO 協(xié)程任務(wù)的時(shí)候嚣崭，要做的就是在正式處理任務(wù)之前new 一個(gè)新的線程，然后老線程去處理IO操作并sleep萨西，而processor可以用新的線程繼續(xù)從local task queue中取任務(wù)并處理有鹿。
TIP
這周在工作過程使用到了bosun，并初步接觸了比較基礎(chǔ)的bosun語法谎脯。bosun queckstart
Share
學(xué)習(xí)mysql 45講
33 | 我查這么多數(shù)據(jù)葱跋， 會不會把數(shù)據(jù)庫內(nèi)存打爆？
全表掃描對server層的影響
在執(zhí)行select語句的時(shí)候，服務(wù)端并不需要保存一個(gè)完整的結(jié)果集娱俺，也就是說稍味， MySQL是“邊讀邊發(fā)的”。 取數(shù)據(jù)和發(fā)數(shù)據(jù)的流程是這樣的：
- 獲取一行荠卷， 寫到net_buffer中模庐。 這塊內(nèi)存的大小是由參數(shù)net_buffer_length定義的， 默認(rèn)是16k油宜。
- 重復(fù)獲取行掂碱， 直到net_buffer寫滿， 調(diào)用網(wǎng)絡(luò)接口發(fā)出去慎冤。
- 如果發(fā)送成功疼燥， 就清空net_buffer， 然后繼續(xù)取下一行蚁堤， 并寫入net_buffer醉者。
- 如果發(fā)送函數(shù)返回EAGAIN或WSAEWOULDBLOCK， 就表示本地網(wǎng)絡(luò)棧（socket send buffer） 寫滿了披诗， 進(jìn)入等待撬即。 直到網(wǎng)絡(luò)棧重新可寫， 再繼續(xù)發(fā)送
全表掃描對InnoDB的影響
WAL機(jī)制呈队， 當(dāng)事務(wù)提交的時(shí)候剥槐， 磁盤上的數(shù)據(jù)頁是舊的， 如果這時(shí)候馬上有一個(gè)查詢要來讀這個(gè)數(shù)據(jù)頁掂咒， 不需要馬上把redo log應(yīng)用到磁盤數(shù)據(jù)頁才沧，而是直接讀取Buffer Pool數(shù)據(jù)的內(nèi)容即可，因此Buffer Pool的緩存命中率越高對mysql查詢效率提升越大绍刮。
InnoDB管理Buffer Pool的LRU算法温圆， 是用雙向鏈表來實(shí)現(xiàn)的。并且InnoDB對LRU算法做了改進(jìn)孩革，具體改進(jìn)點(diǎn)為在InnoDB實(shí)現(xiàn)上岁歉， 按照5:3的比例把整個(gè)LRU鏈表分成了young區(qū)域和old區(qū)域。 LRU_old指向的就是old區(qū)域的第一個(gè)位置膝蜈， 是整個(gè)鏈表的5/8處锅移。 也就是說， 靠近鏈表頭部的5/8是young區(qū)
域饱搏， 靠近鏈表尾部的3/8是old區(qū)域非剃。
每次有新的數(shù)據(jù)都會先置到LRU_old節(jié)點(diǎn)，同時(shí)old區(qū)域的數(shù)據(jù)如果存在超過1S沒有被淘汰的話推沸，就會移動到y(tǒng)oung區(qū)域的head節(jié)點(diǎn)备绽。
這個(gè)策略最大的收益券坞， 就是在掃描這個(gè)大表的過程中， 雖然也用到了Buffer Pool肺素， 但是對young區(qū)域完全沒有影響恨锚， 從而保證了Buffer Pool響應(yīng)正常業(yè)務(wù)的查詢命中率。
