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
// 删除节点
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
// 删除节点
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)
// 删除节点
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
本篇文章作者带着我们从头实现了一个简易版本的gmp调度器，浅显易懂的向读者解释了为什么GMP这样子设计。
首先实现一个协程调度器，有几个比较重要的点或者需求：
- 协程需要时轻量级的，要比操作系统提供的线程更加轻量级。
- 协程要能够处理system call和IO操作。
- 要能够实现真正的并行
- 协程的调度要足够公平，避免同一个function一直抢占CPU时间片
- 最后是控制创建的协程数量，避免过多抢占操作系统资源。
为了实现上诉需求，我们可以一步一步迭代一个协程调度器。
- 首先最简单的版本，我们实现的协程和线程之间为1：1的映射关系，也就是我们为每个协程创建一个线程。这里显而易见的，是不够轻量的。需要进一步迭代。
- 我们做一点改进，我们让协程和线程之间改成M:N的映射关系。也就是我们前置性的创建M个线程，然后用户需要创建的N个协程任务每次都分配给这M个线程进行处理。为了实现这个机制，我们引入global task queue，每次用户创建的协程任务都push到queue里面，并且每个线程都统一从这个queue中取任务去执行。因为是多个线程从一个global queue里面取任务，为了保证并发安全，我们需要对每次的取任务加上mutex锁。
- 在上诉步骤里面，为了保障并发安全我们给global queue加上了锁，随着我们的push和pop queue的操作越来越频繁，global queue的锁成为我们的并发性能瓶颈。为了解决这个问题，这时候我们引入了local task queue，也就是每个线程维护自己的local queue。每次线程都从自己的local queue里面取任务执行，同时因为每个线程操作自己的queue也就不存在并发安全了，不需要加锁。
- 为了保障每个线程不会空转，我们还可以引入了Work Stealing的机制。也就是每个线程自己的queue如果空了，这时候就可以尝试去其他线程的queue里面取任务进行执行。
- 上面实现的调度器有个比较大的问题就是无法处理system call或者IO function，如果某个协程的任务是需要进行IO读写的话，这时候对应的线程就会处于sleep状态（需要等内存中断处理结束）。为了解决这个问题，引入了Processors的概念。具体来说就是我们现在每个local task queue对应的核心处理单元不再是线程而是processor，每个processor可以对应多个线程。这样子我们调度器在遇到IO 协程任务的时候，要做的就是在正式处理任务之前new 一个新的线程，然后老线程去处理IO操作并sleep，而processor可以用新的线程继续从local task queue中取任务并处理。
TIP
这周在工作过程使用到了bosun，并初步接触了比较基础的bosun语法。bosun queckstart
Share
学习mysql 45讲
33 | 我查这么多数据， 会不会把数据库内存打爆？
全表扫描对server层的影响
在执行select语句的时候，服务端并不需要保存一个完整的结果集，也就是说， MySQL是“边读边发的”。 取数据和发数据的流程是这样的：
- 获取一行， 写到net_buffer中。 这块内存的大小是由参数net_buffer_length定义的， 默认是16k。
- 重复获取行， 直到net_buffer写满， 调用网络接口发出去。
- 如果发送成功， 就清空net_buffer， 然后继续取下一行， 并写入net_buffer。
- 如果发送函数返回EAGAIN或WSAEWOULDBLOCK， 就表示本地网络栈（socket send buffer） 写满了， 进入等待。 直到网络栈重新可写， 再继续发送
全表扫描对InnoDB的影响
WAL机制， 当事务提交的时候， 磁盘上的数据页是旧的， 如果这时候马上有一个查询要来读这个数据页， 不需要马上把redo log应用到磁盘数据页，而是直接读取Buffer Pool数据的内容即可，因此Buffer Pool的缓存命中率越高对mysql查询效率提升越大。
InnoDB管理Buffer Pool的LRU算法， 是用双向链表来实现的。并且InnoDB对LRU算法做了改进，具体改进点为在InnoDB实现上， 按照5:3的比例把整个LRU链表分成了young区域和old区域。 LRU_old指向的就是old区域的第一个位置， 是整个链表的5/8处。 也就是说， 靠近链表头部的5/8是young区
域， 靠近链表尾部的3/8是old区域。
每次有新的数据都会先置到LRU_old节点，同时old区域的数据如果存在超过1S没有被淘汰的话，就会移动到young区域的head节点。
这个策略最大的收益， 就是在扫描这个大表的过程中， 虽然也用到了Buffer Pool， 但是对young区域完全没有影响， 从而保证了Buffer Pool响应正常业务的查询命中率。
