可重复读底层实现

为了解决不可重复读,或者为了实现可重复读,MySQL 采用了 MVVC (多版本并发控制) 的方式。

我们在数据库表中看到的一行记录可能实际上有多个版本,每个版本的记录除了有数据本身外,还要有一个表示版本的字段,记为 row trx_id,而这个字段就是使其产生的事务的 id,事务 ID 记为 transaction id,它在事务开始的时候向事务系统申请,按时间先后顺序递增。

preview

按照上面这张图理解,一行记录现在有 3 个版本,每一个版本都记录这使其产生的事务 ID,比如事务A的transaction id 是100,那么版本1的row trx_id 就是 100,同理版本2和版本3。

在上面介绍读提交和可重复读的时候都提到了一个词,叫做快照,学名叫做一致性视图,这也是可重复读和不可重复读的关键,可重复读是在事务开始的时候生成一个当前事务全局性的快照,而读提交则是每次执行语句的时候都重新生成一次快照。

对于一个快照来说,它能够读到那些版本数据,要遵循以下规则:

  1. 当前事务内的更新,可以读到;
  2. 版本未提交,不能读到;
  3. 版本已提交,但是却在快照创建后提交的,不能读到;
  4. 版本已提交,且是在快照创建前提交的,可以读到;

利用上面的规则,实现可重复读就可以实现了。

TCP报文中时间戳的作用

TCP可选字段中维TCP预留有时间戳功能,时间戳选项占10个字节= kind(1字节) + length(1字节) + info (8字节),其中kind=8,length=10,info由timestamp和timestamp echo两个值组成,各4个字节的长度。

timestamp和timestamp echo的功能解释,下面我们通过一个例子解释,假如我们有两台主机,a主机向b主机发送一个报文

  • timestamp存放的字段内容:a主机向b主机发送报文s1,在s1报文中timestamp存储的是a主机发送s1时的内核时刻ta1
  • timestamp echo字段中存放的内容:b主机收到s1报文并向a主机发送含有确认ack的报文s2,在s2报文中,timestamp为b主机此时的内核时刻tb,而timestamp echo字段为从s1报文中解析出的ta1

他们的作用是什么呢:

第一个就是计算往返延时RTT:

当a主机接收到b主机发送过来的确认ack报文s2时,a主机此时内核时刻为ta2.a主机从s2报文的timestamp echo选项中可以解析出该确认ack确认的报文的发送时刻为ta1.那么:RTT=接收ack报文的时刻-发送报文的时刻=ta2 -ta1.ta2和ta1都来自a主机的内核,所以不需要在tcp连接的两端进行任何时钟同步的操作

第二个就是防止回绕的序号:

我们知道TCP报文的序列号只有32位,而没增加2^32个序列号后就会重复使用原来用过的序列号。假设我们有一条高速网络,通信的主机双方有足够大的带宽涌来快速的传输数据。例如1Gb/s的速率发送报文,则不到35秒报文的序号就会重复。这样对TCP传输带来混乱的情况。而采用时间戳选项,可以很容易的分辨出相同序列号的数据报,哪个是最近发送,哪个是以前发送的

Go语言局部变量分配在栈还是堆

我们是如何得知局部变量是分在栈上面还是堆上面,这在go中是不明确的,因为go使用内存逃逸分析来分配局部变量的内存地址。下面是go官方对这个问题的解释

From a correctness standpoint, you don’t need to know. Each variable in Go exists as long as there are references to it. The storage location chosen by the implementation is irrelevant to the semantics of the language.

The storage location does have an effect on writing efficient programs. When possible, the Go compilers will allocate variables that are local to a function in that function’s stack frame. However, if the compiler cannot prove that the variable is not referenced after the function returns, then the compiler must allocate the variable on the garbage-collected heap to avoid dangling pointer errors. Also, if a local variable is very large, it might make more sense to store it on the heap rather than the stack.

In the current compilers, if a variable has its address taken, that variable is a candidate for allocation on the heap. However, a basic escape analysis recognizes some cases when such variables will not live past the return from the function and can reside on the stack.

这段话的主要意思就是你不需要知道是怎么分配存储的,因为这个你使用哪个语法没有关系。如果程序能够保证变量在函数return之后不被引用的话,那么会被分配在栈上。反之则会放在堆上。

缓存穿透,缓存雪崩的概念?如何避免

缓存穿透

一般的缓存系统,都是按照 key 去缓存查询,如果不存在对应的 value,就应该去后端系统查找(比如DB)。一些恶意的请求会故意查询不存在的 key,请求量很大,就会对后端系统造成很大的压力。这就叫做缓存穿透。

如何避免

   1:对查询结果为空的情况也进行缓存,缓存时间设置短一点,或者该 key 对应的数据 insert 了之后清理缓存。

   2:对一定不存在的 key 进行过滤。可以把所有的可能存在的 key 放到一个大的 Bitmap 中,查询时通过该 bitmap 过滤。

缓存雪崩

  当缓存服务器重启或者大量缓存集中在某一个时间段失效,这样在失效的时候,会给后端系统带来很大压力。导致系统崩溃。

如何避免? 

   1:在缓存失效后,通过加锁或者队列来控制读数据库写缓存的线程数量。比如对某个 key 只允许一个线程查询数据和写缓存,其他线程等待。

   2:做二级缓存,A1 为原始缓存,A2 为拷贝缓存,A1 失效时,可以访问 A2,A1 缓存失效时间设置为短期,A2 设置为长期

   3:不同的 key,设置不同的过期时间,让缓存失效的时间点尽量均匀

UDP如何实现可靠传输

概述

UDP不属于连接协议,具有资源消耗少,处理速度快的优点,所以通常音频,视频和普通数据在传送时,使用UDP较多,因为即使丢失少量的包,也不会对接受结果产生较大的影响。

传输层无法保证数据的可靠传输,只能通过应用层来实现了。实现的方式可以参照tcp可靠性传输的方式,只是实现不在传输层,实现转移到了应用层。

最简单的方式是在应用层模仿传输层TCP的可靠性传输。下面不考虑拥塞处理,可靠UDP的简单设计。

  • 1、添加seq/ack机制,确保数据发送到对端
  • 2、添加发送和接收缓冲区,主要是用户超时重传。
  • 3、添加超时重传机制。

详细说明:送端发送数据时,生成一个随机seq=x,然后每一片按照数据大小分配seq。数据到达接收端后接收端放入缓存,并发送一个ack=x的包,表示对方已经收到了数据。发送端收到了ack包后,删除缓冲区对应的数据。时间到后,定时任务检查是否需要重传数据。

目前有如下开源程序利用udp实现了可靠的数据传输。分别为RUDP、RTP、UDT

移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。

如果一块石头的 同行或者同列 上有其他石头存在,那么就可以移除这块石头。

给你一个长度为 n 的数组 stones ,其中 stones[i] = [xi, yi] 表示第 i 块石头的位置,返回 可以移除的石子 的最大数量。

这道题一开始本来以为可以简单的用遍历做,后面发现的确也可以用遍历做,但是这道题目考察的是并查集和图,我实在是没看出来哪里考察图了,我们先用深度优先遍历做一次:

func removeStones(stones [][]int) int {
    n := len(stones)
    graph := make([][]int,n)
    for i, p := range stones {
        for j, q := range stones {
            if p[0] == q[0] || p[1] == q[1] {
                graph[i] = append(graph[i],j)
            }
        }
    }
    vis := make([]bool, n)
    var dfs func(int)
    dfs = func(w int) {
        vis[w] = true
        for _, v := range graph[w]{
            if !vis[v] {
                dfs(v)
            }
        }
    }
    cnt := 0
    for i, v := range vis {
        if !v {
            cnt++
            dfs(i)
        }
    }
    return n - cnt
}

只要有数字相同,那么就说明在同一行或者同一列,所以我们将在同一行的放在一起,遍历的时候将第几个坐标代表的vis转换成true,最后再去看哪个位置不为true就说明这个位置是独立的。

而去用并查集去做,官方的解释是

根据可以移除石头的规则:如果一块石头的 同行或者同列 上有其他石头存在,那么就可以移除这块石头。可以发现:一定可以把一个连通图里的所有顶点根据这个规则删到只剩下一个顶点。

为什么这么说呢?既然这些顶点在一个连通图里,可以通过遍历的方式(深度优先遍历或者广度优先遍历)遍历到这个连通图的所有顶点。那么就可以按照遍历的方式 逆向 移除石头,最后只剩下一块石头。所以:最多可以移除的石头的个数 = 所有石头的个数 – 连通分量的个数。

删到最后,留在图中的顶点一定位于不同的行和不同的列。因此,并查集里的元素是 描述「横坐标」和「纵坐标」的数值。因此我们需要遍历数组 stones,将每个 stone 的横坐标和纵坐标在并查集中进行合并。理解合并的语义十分重要。

「合并」的语义
「合并」的语义是:所有横坐标为 x 的石头和所有纵坐标为 y 的石头都属于同一个连通分量。

这里还有一个问题,就是如何区分横纵坐标,因为我们的位置是二维的,而并查集是一维的,所以怎么区分横纵坐标,或者怎么去用?

例如:如果一块石头的坐标为 [3, 3] ,那么所有横坐标为 3 的石头和所有纵坐标为 3 的石头都在一个连通分量中,但是我们需要在并查集里区分「横坐标」和「纵坐标」,它们在并查集里不能相等,根据题目的提示 ,可以把其中一个坐标 映射 到另一个与 [0, 10000] 不重合的区间,可以的做法是把横坐标全部减去 10001或者全部加上 10001

这是什么生意呢?就是防止横纵坐标重复,所以得舍去一个。然后我们开始上并查集模板:

func removeStones(stones [][]int) int {
    fa, rank := map[int]int{}, map[int]int{}
    var find func(int) int
    find = func(x int) int {
        if _, has := fa[x]; !has {
            fa[x], rank[x] = x, 1
        }

        if fa[x] != x {
            fa[x] = find(fa[x])
        }
        return fa[x]
    }

    union := func(x, y int) {
        fx, fy := find(x), find(y)
        if fx == fy {
            return
        }
        if rank[fx] < rank[fy] {
            fx, fy = fy, fx
        }
        rank[fx] += rank[fy]
        fa[fy] = fx
    }
    for _, p := range stones {
        union(p[0],p[1]+10000)
    }
   ans := len(stones)
    for x, fx := range fa {
        if x == fx {
            ans--
        }
    }
    return ans
}

可被5整除的二进制前缀

给定由若干 0 和 1 组成的数组 A。我们定义 N_i:从 A[0] 到 A[i] 的第 i 个子数组被解释为一个二进制数(从最高有效位到最低有效位)。

返回布尔值列表 answer,只有当 N_i 可以被 5 整除时,答案 answer[i] 为 true,否则为 false。

func prefixesDivBy5(A []int) []bool {
    ans := make([]bool,len(A))
    r := 0
    for i, v := range A {
        r = (r << 1) % 10 + v
        ans[i] = (r % 5 == 0)
    }
    return ans
}

TCP连接为什么三次握手而不是两次握手

这个问题记得还是地平线问的,为什么是三次握手而不是两次握手?那时候是第一次遇到,所以回答的很差,只说了保证可靠传输啥的,其它的是一概都没说到。

这次突然想到,查了一下,明白了。按照我理解的呢,假如A为客户端,B为服务端,传输开始前,A和B都知道自己的序列号。第一次握手,B知道了A的序列号,第二次握手,A知道了B知道A的序列号,第三次握手,B知道A知道自己的序列号。

我还看到了另外一种言论,其他文章提到的没有第三次会浪费资源的问题是建立在三次请求才会建立连接的基础上才会出现的问题,这不是设计三次请求的原因,而是如果设计成两次请求会出现的错误,而真正设计成三次就是为了消息的保真和有序,同时能避免那个问题而已

这个言论也很巧妙,很精准。

如果没有三次,B是无法知道A是否已经接收到了自己的同步信号,如果这个同步信号丢失,A和B的序列号就无法达成一致。

epoll原理

设想一个场景:有100万用户同时与一个进程保持着TCP连接,而每一时刻只有几十个或几百个TCP连接是活跃的(接收TCP包),也就是说在每一时刻进程只需要处理这100万连接中的一小部分连接。那么,如何才能高效的处理这种场景呢?进程是否在每次询问操作系统收集有事件发生的TCP连接时,把这100万个连接告诉操作系统,然后由操作系统找出其中有事件发生的几百个连接呢?实际上,在Linux2.4版本以前,那时的select或者poll事件驱动方式是这样做的。

  这里有个非常明显的问题,即在某一时刻,进程收集有事件的连接时,其实这100万连接中的大部分都是没有事件发生的。因此如果每次收集事件时,都把100万连接的套接字传给操作系统(这首先是用户态内存到内核态内存的大量复制),而由操作系统内核寻找这些连接上有没有未处理的事件,将会是巨大的资源浪费,然后select和poll就是这样做的,因此它们最多只能处理几千个并发连接。而epoll不这样做,它在Linux内核中申请了一个简易的文件系统,把原先的一个select或poll调用分成了3部分:

int epoll_create(int size);  
int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);  
int epoll_wait(int epfd, struct epoll_event *events,int maxevents, int timeout);

1. 调用epoll_create建立一个epoll对象(在epoll文件系统中给这个句柄分配资源);

2. 调用epoll_ctl向epoll对象中添加这100万个连接的套接字;

3. 调用epoll_wait收集发生事件的连接。

  这样只需要在进程启动时建立1个epoll对象,并在需要的时候向它添加或删除连接就可以了,因此,在实际收集事件时,epoll_wait的效率就会非常高,因为调用epoll_wait时并没有向它传递这100万个连接,内核也不需要去遍历全部的连接。

1.epoll原理详解

当某一进程调用epoll_create方法时,Linux内核会创建一个eventpoll结构体,这个结构体中有两个成员与epoll的使用方式密切相关,如下所示:

struct eventpoll {
  ...
  /*红黑树的根节点,这棵树中存储着所有添加到epoll中的事件,
  也就是这个epoll监控的事件*/
  struct rb_root rbr;
  /*双向链表rdllist保存着将要通过epoll_wait返回给用户的、满足条件的事件*/
  struct list_head rdllist;
  ...
};

我们在调用epoll_create时,内核除了帮我们在epoll文件系统里建了个file结点,在内核cache里建了个红黑树用于存储以后epoll_ctl传来的socket外,还会再建立一个rdllist双向链表,用于存储准备就绪的事件当epoll_wait调用时,仅仅观察这个rdllist双向链表里有没有数据即可。有数据就返回,没有数据就sleep,等到timeout时间到后即使链表没数据也返回。所以,epoll_wait非常高效。

  所有添加到epoll中的事件都会与设备(如网卡)驱动程序建立回调关系,也就是说相应事件的发生时会调用这里的回调方法。这个回调方法在内核中叫做ep_poll_callback,它会把这样的事件放到上面的rdllist双向链表中。

  在epoll中对于每一个事件都会建立一个epitem结构体,如下所示:

struct epitem {
  ...
  //红黑树节点
  struct rb_node rbn;
  //双向链表节点
  struct list_head rdllink;
  //事件句柄等信息
  struct epoll_filefd ffd;
  //指向其所属的eventepoll对象
  struct eventpoll *ep;
  //期待的事件类型
  struct epoll_event event;
  ...
}; // 这里包含每一个事件对应着的信息。

当调用epoll_wait检查是否有发生事件的连接时,只是检查eventpoll对象中的rdllist双向链表是否有epitem元素而已,如果rdllist链表不为空,则这里的事件复制到用户态内存(使用共享内存提高效率)中,同时将事件数量返回给用户。因此epoll_waitx效率非常高。epoll_ctl在向epoll对象中添加、修改、删除事件时,从rbr红黑树中查找事件也非常快,也就是说epoll是非常高效的,它可以轻易地处理百万级别的并发连接。

总结:

  • 执行epoll_create()时,创建了红黑树和就绪链表;
  • 执行epoll_ctl()时,如果增加socket句柄,则检查在红黑树中是否存在,存在立即返回,不存在则添加到树干上,然后向内核注册回调函数,用于当中断事件来临时向准备就绪链表中插入数据;
  • 执行epoll_wait()时立刻返回准备就绪链表里的数据即可。

2.epoll的两种触发模式

epoll有两种触发模式,LT是默认的触发模式,ET是高速模式,当然这个高速的模式是相对的。

  • LT(水平触发模式),只要这个文件描述符还有数据可读,每次 epoll_wait都会返回它的事件,提醒用户程序去操作;
  • ET(边缘触发)模式下,在它检测到有 I/O 事件时,通过 epoll_wait 调用会得到有事件通知的文件描述符,对于每一个被通知的文件描述符,如可读,则必须将该文件描述符一直读到空,让 errno 返回 EAGAIN 为止,否则下次的 epoll_wait 不会返回余下的数据,会丢掉事件。如果ET模式不是非阻塞的,那这个一直读或一直写势必会在最后一次阻塞。

解释起来就是et模式只有数据来了它才触发,数据没来,即使你缓存区可能还存在数据,它也不会去读

而lt则是只要缓存区还有数据,那么它就一直触发,直到没数据。

这里就会遇到一个问题,为什么要et模式啊?

我们考虑一种情况如果缓存区一直都有数据,但是呢,现在的我不需要它去处理了,它可以等下再去处理,我需要对某一种数据或者自己想要的数据去处理,但是呢,这些没用的数据,它们每次调用epoll_wait都会返回,所以会导致我们想要的数据处理的比较拉跨。这里我们就可以使用et,那些我们不关心的数据,它只提醒一次,不会再来打扰你。

Redis 分布式锁

使用过 Redis 分布式锁么,它是什么回事?

先拿 setnx 来争抢锁,抢到之后,再用 expire 给锁加一个过期时间防止锁忘记了 

释放。

这时候对方会告诉你说你回答得不错,然后接着问如果在 setnx 之后执行 expire

之前进程意外 crash 或者要重启维护了,那会怎么样?

这时候你要给予惊讶的反馈:唉,是喔,这个锁就永远得不到释放了。紧接着你 

需要抓一抓自己得脑袋,故作思考片刻,好像接下来的结果是你主动思考出来的,

然后回答:我记得 set 指令有非常复杂的参数,这个应该是可以同时把 setnx 和 

expire 合成一条指令来用的!对方这时会显露笑容,心里开始默念:摁,这小子 

还不错。