目录一、Redis:1. 缓存穿透2. 缓存击穿3. 缓存雪崩4. 缓存更新双写一致性5. redis持久化6. redis数据过期策略7. redis数据淘汰策略8. 分布式锁9. 消息队列MQ10. Feed流11. 主从集群12. 哨兵13. 分片集群14. redis是单线程为什么这么快15. 阻塞I/O模型16. 非阻塞I/O模型17. I/O多路复用模型18. 信号驱动I/O19. 异步I/O20. redis 命令处理单线程网络I/O多线程模型21. SDS数据结构22. Dict键值对数据结构23. IntSet升序集合24. ZipList双端队列25. QuickList26. SkipList27. String数据类型28. List数据类型29. Set数据类型30. SortedSet\ZSet31. Hash32. BitMap、GEO二、MySQL1. 慢查询SQL语句执行慢定位问题2. 什么是索引3. 什么是聚簇索引、什么是二级索引非聚簇索引4. 回表查询5. 覆盖索引6. limit超大分页查询7. 索引创建的原则8. 联合索引失效的情况9. SQL优化10. 事务的特性11.MySQL读写锁12. 并发事务隔离性问题13.事务隔离级别14.MySQL服务器结构15.InnoDB存储引擎16.MVCC17.单表数据量较大时分表一、Redis:1. 缓存穿透缓存未命中会查询数据库并将查询结果写入redis但是当查询不存在的数据时例如api/getById/-1用户用不存在的用户id来发送请求mysql查询失败就不会写到缓存缓存失效导致每次查询都会访问数据库。解决方法1.缓存空对象尽管某个请求获取的数据在数据库和缓存中都不存在那么也会在缓存中缓存一个null值但大量null值会消耗额外的内存且有短期的数据不一致问题缓存更新。2.布隆过滤bitMap数据结构bit为单位的数组string类型最大512M对于数据库中的数据基于某种哈希算法计算出3次哈希值将哈希值转换成二进制位存储到bitMap对应的位。当判断数据库中的数据是否存在时通过判断bit数组中对应位置是0还是1以此判断请求的数据是否存在空间占用小。当布隆过滤器返回“不存在”时那么请求的数据100%不存在。但是当布隆过滤器返回“存在”时由于bit数组空间有限不同数据会有hash值冲突请求的数据也不一定存在。3.缓存空对象和布隆过滤都是出现缓存穿透后被动的进行处理。完全可以通过主动的方式来避免缓存穿透增强id的复杂度在此基础上做好数据的基础格式校验在格式校验阶段就能拦截接触不到数据库。2. 缓存击穿高并发访问且缓存重建较为复杂的key过期时由于MySQL写入缓存耗时很长当线程1重建缓存的过程中其他多个线程此时要高并发的查询相同的信息查询缓存还是会未命中所以都会访问数据库。解决方法1.SETNX互斥锁本质是SETNX是一个单命令原子操作重建缓存过程前上锁重建完成释放锁保证访问相同信息的所有线程中只能有一个请求重建缓存其他请求由于获取锁失败暂时阻塞。2.逻辑过期 不给热key设置TTL而是给key添加一个expire的value当expire时间减为0那么第一个访问该key的线程会获取锁并开辟异步线程访问数据库重建缓存主线程直接返回过期数据异步线程重建缓存后释放锁。重建缓存过程中如果有其他线程访问该key那么直接返回缓存中过期的数据。3. 缓存雪崩在同一时间大量的缓存key同时过期或者Redis服务宕机导致大量请求到达数据库。解决方法1.给不同key的TTL添加随机值或添加多级缓存防止大量缓存key同时失效。2.利用redis集群确保一直有redis可用防止因某一redis宕机引起的缓存雪崩。3.当redis宕机时牺牲部分服务不允许这些请求到达数据库实现限流策略。4. 缓存更新双写一致性读操作缓存命中则直接返回缓存未命中则查询数据库写入缓存。如果是热key那么使用缓存击穿方案来限制查询数据库的线程量如果不是热key那么允许多个线程同时查数据库并写入缓存。写操作1.spring事务确保数据库与缓存操作要么全执行要么全不执行 原子性2.先写数据库后删除缓存 隔离性写操作后不会有一致性问题但是在写操作期间会有数据不一致问题如果要求数据的强一致性那么对于写操作完成前的数据不一致问题可以使用读写锁共享锁排他锁1. 共享锁读操作会上锁期间允许其他读操作但是不允许任何写操作但这种方法写操作就饥饿了吧虽然解决了数据不一致问题但写操作执行晚了数据没法及时更新还是有脏数据吧。2. 排他锁写操作上锁期间不允许其他的读写操作感觉这个好既能解决写操作完成前的数据不一致问题又能保证数据及时更新。延时双删在写操作期间依然会有数据不一致问题且延时双删多访问了数据库唯一的优势仅在该情境下“写请求在写数据期间没有读操作那么写数据库后删除缓存前的读操作不会读到脏数据”。5. redis持久化RDB将内存中的所有数据记录到磁盘的rdb文件中redis在停机前会自动保存rdb数据到磁盘当前项目工作目录下然后才会执行停机指令。当启动redis时会自动读取当前工作目录下的rdb文件并加载到内存中。save命令由redis主进程来执行会阻塞所有命令适合正常redis手动停机时使用bgsave命令会fork redis主进程得到一个异步子进程执行持久化与主进程共享内存空间fork过程中主进程阻塞子进程创建后主进程正常工作子进程创建后会读取内存数据写入一个新的rdb文件并将新的rdb文件覆盖旧的rdb文件适合redis运行过程中持久化内存数据可以防止redis宕机导致的数据丢失。触发频率900s内如果至少有1个key被修改10 300s内如果至少有10个key被修改60s内如果至少有10000个key被修改则执行bgsave命令触发频率高那么频繁创建子进程和写rdb文件非常影响性能时间设置太长会出现向内存写入数据后触发还未执行redis就宕机导致数据丢失。AOF与RDB将内存数据存储到磁盘中不同AOF是将redis执行的每一条写命令以追加的方式记录在磁盘的aof日志文件中当服务宕机重启后通过重新执行这些写命令来完成数据恢复默认触发频率是将写命令暂存到OS为redis分配的缓冲区每隔1s将缓冲区的所有命令写入aof文件。bgrewriteaof可以对aof文件执行重写功能减少无效命令的记录也是使用fork开辟异步线程来执行覆写功能6. redis数据过期策略过期策略和淘汰策略用来避免内存存储达到上限。redisDB维护两个Dictdict记录所有redisObject-内存首址键值对、expires记录设置了过期时间的redisObject-过期时间键值对。1.惰性删除在访问key时执行首先根据key从dict中找到对应的redisObject然后检查key记录在expires中的TTL如果过期那么释放key的内存空间但是如果key过期了但是永远不会被访问那么惰性删除策略下该key的内存空间永远不会被释放。2.周期删除为所有key设置同一个定时任务周期性的抽样部分key检查是否过期如果过期执行删除操作。SLOW模式redis单线程初始化时初始化epoll阶段每100ms定期检查并清理过期key不在主线程main函数中执行周期为100ms执行清理耗时不能超过25%即25ms首先逐个遍历db每次取20个key检查并清理过期key如果时间未达到25ms且刚才检查的过期key比例超过10%再取20个key检查并清理。FAST模式每次redis单线程调用epoll_wait阻塞前都会先检查并清理部分过期key因为位于主线程的main代码中所以执行周期为两次调用epoll_wait的间隔FAST间隔不能低于2ms每次清理耗时不能超过1ms。7. redis数据淘汰策略淘汰策略就是Redis内存使用达到阈值时主动挑选部分key删除以释放内存在主线程解析命令后处理命令前执行。默认不淘汰任何key内存满时不允许写入新数据。其他方案1.对设置了TTL的key淘汰TTL越小越先被淘汰。2.对全体/设置了TTL的key当前时间减最近一次访问时间值越大优先淘汰。3.对全体/设置了TTL的key访问次数越少优先淘汰使用8bit记录逻辑访问次数范围0~255基于随机数逻辑访问次数越大计数器越难1。key的访问次数和访问时间都会封装在redisObject对象中。8. 分布式锁synchronized悲观互斥锁只能保证单个JVM内部的多个线程之间的互斥因为synchronized本质是竞争JVM中目标对象关联的Monitor的Owner身份无法保证集群下多个JVM之间的进程互斥。而分布式锁是集群模式下所有线程都可见的锁。本质还是利用了SETNX原子操作的互斥性使用SET key thread NX原子命令来对某个key加锁并设置EX超时时间防止死锁使用DEL userlock释放锁。这么做有三个问题不可重入、不可重试、超时释放。不可重入问题是持有锁的线程无法再次获取锁可以通过给key增加state字段重复获取锁state释放锁state–如果state减为0那么执行DEL userlock但问题是if判断是否持有锁和state是两条指令具有线程安全问题所以需要使用Lua脚本来确保原子操作使用hincrby来进行自增自减。超时释放问题是锁提前释放会导致其他线程提前获取锁有线程安全问题可以为每个锁设置定时任务当上锁成功时启动watchdog每TTL/3重置锁的TTL释放锁时停止watchDog。不可重试问题是获取锁只尝试一次失败就返回false没有重试机制可以通过发布订阅模式在获取锁失败后在等待的最长时间内subscribe其他线程释放锁的信号等待获得释放锁的信号而不是盲目的重试占用CPU资源持有锁的线程在释放锁时通过publish发出信号等待线程等到信号才会重新尝试获取锁感觉这里有竞争设置成等待队列先到先得比较好。 然后Redisson中其他的亮点就是对每个锁用了单例模式每个锁对应map中的一个锁对象锁对象中维护定时任务因此不会频繁的创建锁对象和定时任务线程切换只要修改锁对象的value就行了。主从一致性用红锁。9. 消息队列MQ阻塞队列位于JVM受到内存上限的限制且没有持久化机制队列中的信息有丢失的风险。消息队列位于JVM之外存入的信息具有持久化机制包含消息队列、生产者、消费者。1.List结构双向链表lpush和brpop模拟阻塞队列缺点是出队后写数据库之前服务器宕机还是会有信息丢失风险。2.PubSub基于发布订阅模式消费者可以订阅一个或多个channel生产者向channel存入信息后订阅该channel的消费者都能收到相关信息消息可以指定发送给1个消费者也可以同时发送给多个消费者缺点是redis不支持对该模型的数据持久化。3.Stream数据类型读消息后消息并不会出队而是依然保存在Stream中不仅支持持久化也没有信息丢失风险其中消费者组维护一个id指针每次读取消息后指针后移防止漏读消费者组还维护一个pending-list记录每个已消费但未处理的信息当信息被处理后通过XACK标记信息为已处理并从pending-list中移除防止信息丢失。10. Feed流为用户持续推送消息的一种方式推送内容按照内容发布时间排序或利用推荐算法推送用户感兴趣的内容。1.拉模式每个用户只需维护发件箱用户A发消息时服务器都会将该消息保存到用户A的发件箱中。用户B想要查看消息时会从用户A的发件箱中获取消息。2.推模式每个用户只需维护收件箱用户A发消息时服务器都会将该消息推送到用户B的收件箱中。用户B想要查看消息时只需要从自己的收件箱中获取消息。3.读写混合每个用户需维护发件箱和收件箱若用户A的粉丝太多那么采用拉模式若用户B是用户A的特别关注那么将用户A的数据采用推模式到用户b的收件箱僵尸粉用拉模式。若用户A的粉丝很少采用推模式到所有粉丝的收件箱。活跃用户用推模式。11. 主从集群主从集群主要是解决redis高并发读问题多个从节点用来处理读请求主节点完成写请求并将数据同步到从节点。1.从节点首先发送replid和offset给主节点主节点判断replid是否是自己如果不是那么还没有确定主从关系需要全量同步并返回自己的replid和offset给从节点如果是自己的那么根据offset做增量同步。2.如果是全量同步从节点保存返回的replid和offset确定主从关系主节点将RDB文件发送给从节点从节点清空本地数据后读取主节点的RDB文件。3.主节点将从节点读取RDB文件期间执行的其他数据操作命令发送给从节点确保数据一致。4.确定主从关系后从节点每次重启后都需要做一次增量同步主节点从repl_baklog文件(线性队列环形数组)中获取offset之后的数据发送给从节点。特别的当从节点断连太久可能会出现环形数组中尚未同步的数据被覆盖此时可能需要重新做全量同步。12. 哨兵从节点断连后可以使用全量同步或增量同步找主节点更新数据哨兵用来解决主节点断连的数据一致性问题。为了防止单哨兵故障所以哨兵也是集群1.哨兵每隔1s向集群的每个节点发送ping命令若哨兵集群中超过指定数量的哨兵都未收到该节点的响应则认定该节点客观下线。2.排除断连的节点后根据优先级筛选出优先级最高的一批节点选出其中offset最大的slave作为master节点。3.哨兵向选中的slave节点发送slaveof no one命令让该节点成为新的master向其他所有节点发送slaveof newIp newPort命令修改这些slave节点的master并强制修改故障节点为slave节点。13. 分片集群主从集群解决了redis高并发读问题Redis分片集群为了解决redis高并发写问题和海量数据存储。分片集群中有多个master每个master独立保存数据每个master都可以搭建主从集群分配多个slave节点master之间通过ping监测彼此状态在主节点出现故障时能够自动主从切换不需要哨兵。分片集群下多个master节点共同分配16384个hash插槽每个master节点只能操作自己的插槽。数据key不与master节点绑定而是与插槽绑定。当操作某个key时先对key使用CRC16计算hash值再取余16384得到slot值然后判断该插槽属于哪个master节点redirect到该节点来操作key避免了手动选择master同时某一master故障时直接由从节点继承这部分数据保证数据不会丢失。主从切换从节点通知主节点拒绝任何客户端请求主节点将offset后的数据给从节点做同步从节点广播自己是主节点的消息给其他节点。14. redis是单线程为什么这么快redis是纯内存操作内存执行速度很快。单线程避免线程切换开销。使用非阻塞I/O多路复用模型。15. 阻塞I/O模型redis执行过程为接收网络请求-执行命令-返回响应结果由于执行命令是内存操作所以限制redis速度的就是接受网络请求和返回响应结果。单线程阻塞I/O模型服务器只有一个线程用来监听所有客户端线程每次调用recvfrom系统调用只能监听一个客户端的数据如果该客户端没有数据会一直阻塞直到该客户端的数据到达内核缓冲区无法处理其他客户端早已写入内核缓冲区的数据性能差。16. 非阻塞I/O模型非阻塞I/O虽然不需要阻塞等待某一客户端的请求并且可以同时while轮询监听多个客户端的请求但是while轮询会查询所有客户端的数据是否到达线程一直占用CPU导致CPU利用率低且轮询所有客户端性能也较差。17. I/O多路复用模型I/O多路复用是利用单个线程同时监听多个socket的网络I/O请求。与阻塞I/O不同的是I/O多路复用使用的是select、poll、epoll系统调用函数阻塞状态下可以同时监听多个socket当某一个socket的数据到达时就会唤醒阻塞线程回到用户态线程调用recvfrom来读取已经到达的数据到用户空间并处理。与非阻塞I/O不同的是当没有数据可到达时线程会阻塞并让出CPU。select为读请求、写请求、异常事件创建三个独立的数组每个数组有32个元素每个元素占32bit使用bit位作为标记因此每个数组可监听1024个请求其中请求来自不同的线程。通过timeout设定select阻塞等待的超时时间。但是需要频繁的修改用户空间和内核空间中的fd_set在用户态需要遍历原fd_set和修改后的fd_set才能知道那些数据就绪监听数量不超过1024。poll仍然使用数组的方式监听不同的请求但数组中每个元素都是一个结构体记录了请求的文件描述符fdsocket、客户端、请求类型events、返回值revents。单线程在内核中监听时等待中断响应在超时时间内若监听到某个文件描述符的中断响应就将响应类型记录到revents中否则revents置0表示未收到响应。epoll维护一棵红黑树和一个链表红黑树记录要监听的文件描述符fd就绪链表记录已就绪的文件描述符fd。与select最大的不同在于epoll在内核态初始化epoll_create系统调用不会频繁的在用户态和内核态拷贝。Redis中的I/O多路复用可以理解为复用epoll同时监听客户端连接请求、客户端读请求、服务器向客户端的写请求就绪的请求都会放到就绪链表中并每隔一段时间接收多条请求针对不同请求使用不同的分支监听处理函数、读处理函数、写处理函数处理请求。1.复用就绪链表接收三类不同的请求请求客户端连接请求从初始化epoll开始调用epoll_create在内核态创建红黑树和就绪链表创建监听socket后调用epoll_ctl向红黑树中添加监听socket的fd设为可读状态并添加回调函数。当连接请求由网卡到达内核缓冲区会触发中断触发回调函数将监听socket从红黑树添加到就绪链表设为读请求。客户端读请求在建立连接后会调用epoll_ctl将该客户端的fd添加到红黑树设为可读状态该客户端的读请求到达后会被写入为该客户端分配的内核缓冲区触发中断触发回调函数将该客户端socket添加到就绪链表设为读请求。服务器向客户端的写请求在线程接收客户端读请求并处理后如果该客户端的内核发送缓冲区有足够的空闲那么将数据直接发送到内核缓冲区会异步发送数据给客户端否则就会将该客户端socket加入到pending_write链表中并调用epoll_ctl将红黑树中客户端的fd并设为可读可写类型当内核缓冲区有空闲也就是发送数据后会引发中断触发回调函数将客户端的fd添加到就绪链表并设为写请求。2.复用单线程处理三类不同的请求请求线程调用epoll_wait进入内核态检查就绪链表是否有数据如果有直接将就绪链表拷贝到用户态并处理如果没有回让出CPU并阻塞直到就绪链表有数据或超过等待时长会进入就绪态等待分配CPU回到用户态。回到用户态会遍历就绪链表依次处理每个请求客户端连接请求会调用之前添加的监听处理函数建立连接调用epoll_ctl将客户端fd加入到红黑树设为可读并添加回调函数和读处理函数。客户端读请求会调用之前添加的读处理函数执行数据中的命令例如get key并将结果发送到内核发送缓冲区否则就会将该客户端socket加入到pending_write链表中调用epoll_ctl将红黑树中客户端的fd并设为可读可写类型。服务器向客户端的写请求会调用send从pending_write链表中取该客户端数据将数据写入客户端的内核发送缓冲区发送后如果pending_write链表已经没有当前客户端的数据那么调用epoll_ctl将客户端的fd状态修改为可读类型。18. 信号驱动I/O信号驱动I/O通过sigaction()系统调用对fd设置回调函数此时线程立即返回用户态执行其他任务。当fd的数据到达内核缓存时会触发回调函数将就绪的fd拷贝到用户态的信号队列并通知线程。线程调用recvfrom进入内核态将数据拷贝到用户内存。由于信号驱动I/O下每有一个fd就绪内核线程都会执行内核态与用户态切换通知用户线程影响性能。19. 异步I/O异步I/O整个过程都是非阻塞的用户进程调用aio_read()系统调用函数声明要读的fd和读到用户内存空间的地址就直接返回到用户态进行其他任务。而读取数据和将数据从内核缓存拷贝到用户内存的任务完全交由内核线程来完成。异步I/O比I/O多路复用更高效因为用户线程对I/O操作完全解耦可以实现更高并发的处理请求但由于所有任务都交由内核完成每个任务内核都要开辟新线程来处理对内核负载太大。20. redis 命令处理单线程网络I/O多线程模型redis的执行过程为接收网络请求-执行命令-返回响应结果。执行命令部分在内存完成速度快且为了保证原子操作必须要求单线程。接收请求时redis单线程阻塞等待并行的网络请求由内核的中断处理程序并行处理性能很强但是redis单线程返回用户态后需要串行执行read系统调用将数据从内核态读到用户态且需要频繁切换用户态和内核态这是主要瓶颈。返回响应时由redis单线程串行调用send()函数发送响应且需要频繁切换用户态和内核态这是主要瓶颈。最关键的是接受请求和返回响应没有并发安全问题所以这两部分可以设置为多线程多个子线程将数据从内核态读到用户态然后由主单线程依次处理就绪链表中的请求最后由多个子线程调用send系统调用将返回结果从用户态读到内核态。21. SDS数据结构len字符串保存的总字节数、alloc字符串申请的总字节数、flag字符串最大可保存的字节数25、28、216、232、264字节、buf字符数组。内存预分配目的是减少扩容次数如果追加后总字符串小于1MB则扩容至字符串长度*21如果追加后总字符串大于1MB则扩容至字符串长度1MB1。22. Dict键值对数据结构Dict包含2个哈希表每个哈希表存储多个哈希节点每个哈希节点存储多个键值对不需要连续内存空间但指针会占用额外内存空间。无哈希冲突增删改查O(1)有哈希冲突增O(1)删改查O(k)。插入hashsizemask然后头插更新used。如果负载因子used/size5或1且无bgsave\bgrewriteaof子进程触发rehash将元素插入到ht[1]而不再是ht[0]且不更新ht[0]的used确保后面的查询映射不会出错。删除删除节点used-1删除后如果负载因子0.1size4时触发rehash。rehash计算新hash表的size插入引发的rehash是第一个大于等于ht[0].size1的2^n删除是第一个大于等于ht[0].size的2^n并为ht[1]分配内存空间设一个指针遍历ht[0]中的哈希节点每次crud都将当前指针指向的哈希节点的链表重新计算hash值转移到ht[1]直到全部转移将ht[0]指向ht[1]ht[1]置空如果rehash过程中有插入操作那么一律插入到ht[1]如果有查询操作依次查询ht[1]和ht[0]。23. IntSet升序集合基于整数数组实现连续存储不可重复可变长升序排序。包含整数数组、数组元素个数、每个元素允许的最大字节数encoding。增删O(n)查询二分O(logn)如果新插入的元素占用空间大于encoding那么执行InSet升级升级encoding为可以容纳该元素的大小根据所需空间扩容整数数组倒序依次将数组中的元素拷贝到扩容后的正确位置。24. ZipList双端队列连续内存块组成为了保证连续只能在两端进行插入、删除。ZipList不像SDS和IntSet每个元素都占用相同的内存空间而是会根据每个元素大小分配不同的内存空间。zltail记录列表中节点所占总字节数用来作为偏移量得到表尾节点zlend(全11B所以所有属性不能出现11111111的情况)地址。双端队列中每个元素记录当前节点的长度方便获取后一个节点的首地址记录前一个节点的长度方便获取前一个节点的首地址使用线性表实现链表的效果。每个元素还需要使用encoding记录数据类型encoding前两个bit为00、01、10时表示当前Entry是字符串类型00时encoding占用1字节即8bit其中2bit用来记录数据类型剩余6bit记录当前节点的长度因此当前元素可保存的字符串最大28-2-1字节。01时encoding占2个字节…。10时encoding占用5字节即40bit其中8bit用来记录数据类型剩余32bit记录当前节点的长度这里使用霍夫曼编码的思想是方便11编码。encoding前两个bit为11时表示当前Entry是整数类型。1100表示整数最大2字节最大值216-11101是4字节1110是8字节11110是3字节11111110是1字节11110001~11111101时直接用encoding后四位用来保存数据同样根据前缀码的思想此时保存的数据只能是(0001~1101)。注意所有数据在计算机中字节默认以小端方式存储。连锁更新问题的本质是每个元素都要记录前一个元素的长度当前一个元素长度变化可能会导致当前元素的长度变化最坏情况引发连锁的扩容。25. QuickListZipList虽节省内存但连续空间会产生碎片且扩容困难。QuickList通过限制ZipList大小来减少内存碎片通过双向链表串联多个ZipList来解决单ZipList容量限制问题。因为大部分时间是对ZipList的首尾进行操作因此可以压缩其他位置的节点来进一步减少内存占用。增删改查复杂度O(n).26. SkipList根据score查value查询效率O(logn)节点维护一个score字段使得节点之间能够进行升序排序每个节点可以包含多个跨度不同的后向指针可以理解成是一个双向链表其中每个节点还额外有多个后向指针。27. String数据类型string\int\float字节数组形式存储最大不会超过512MB。String对象通过指针指向SDS对象和数据的逻辑存储空间不连续若SDS长度小于44字节则会采用EMBSTR编码此时对象与数据连续存储。若存储的是整数值并在LONG_MAX范围内则会采用INT编码不再需要SDS直接用ptr指针位置8字节用来保存数据。28. List数据类型List是一个双端队列基于QuickList数据结构实现。29. Set数据类型无序、value唯一性、支持并交差集。要保证查询效率为O(1)使用Dict数据结构key来存储元素value置空。当存储的数据都是整数且元素数量不超过set-max-intset-entries时为了节省内存Dict指针占用太多内存默认使用IntSet数据结构此时查询效率O(logn)。在每次插入元素时都会判断是否满足IntSet的两个要求不满足会转换为Dict。30. SortedSet\ZSet效率最优SkipListDictSkipList中score作为keyelement作为value实现排序Dict中element作为keyscore作为value实现element唯一性和element查score。排序复杂度O(logn)O(1)element唯一性O(1)element查scoreO(1)。内存最优当元素数量小于128且每个元素都小于64字节时会使用ZipList数据结构实现ZSetscore和element分别作为两个相邻元素存储element在前score在后score越小越接近队首score越大越接近队尾。但在插入过程中会判断如果某一个条件不满足那么会自动转为DictSkipList。排序复杂度O(logn)O(n)element唯一性检查O(n)element查score O(n)。31. Hashkey-field-value查找O(1)field唯一性。效率最优Dict内存最优当元素数量少于512且每个元素都小于64字节时使用ZipListZipList中相邻两个元素分别保存field和value。但在插入过程中会判断如果某一个条件不满足那么会自动转为Dict。32. BitMap、GEOBitMapString实现一个bit取值0/1可以记录一个状态GEOsortedSet实现其中经纬度会被换算为score字段member唯一标识作为value字段。二、MySQL1. 慢查询SQL语句执行慢定位问题通过配置slow_query_log开启慢日志查询慢日志查询会记录所有执行时间超过10s的所有sql语句会增加数据库压力仅在调试阶段使用。对于某条sql语句在开头添加EXPLAIN字段可以查看sql语句的分析结果通过key和key_len检查是否命中了索引尽量使用索引。通过type字段查看是否存在全索引扫描和全盘扫描尽量控制在唯一索引查询、索引查询、范围查询。通过extra字段判断是否出现回表查询如果出现了可以尝试添加索引和修改查询字段。2. 什么是索引没有索引的话查询会逐一比对每条记录复杂度是O(n)索引就是为了提高查找速度的避免了全表扫描MySQL索引底层是B树实现是一棵多路查找树查询复杂度基于二分查找O(logn)并且由于B树的非叶结点都是索引节点一个page能存更多键值对减少了磁盘I/O只有叶结点才需要进行I/O其次b树叶结点有序且基于双向链表连接便于范围查询。3. 什么是聚簇索引、什么是二级索引非聚簇索引使用主键构造的B树就是聚簇索引如果没有主键使用第一个标注了UNIQUE的字段构造聚簇索引如果也没有UNIQUE字段那么会自动生成rowid构造聚集索引。聚簇索引有且只能有一个每个结点存储的是整行元素。除聚簇索引字段外的其他字段构造的B树就是二级索引每个结点存储的是聚簇索引值如果聚簇是基于主键那么二级索引结点存储的就是主键值。4. 回表查询查询条件where不是聚簇索引的字段时会首先查询二级索引的B树得到聚簇索引值如果仍然有未知的字段那么需要根据聚簇索引值查询聚簇索引的B树得到对应的行这个过程就是回表查询。select id,a,b where b首先查询b的二级索引只能得到id和b需要回表才能得到a5. 覆盖索引查询二级索引时不需要回表查询就是覆盖索引、查询聚簇索引就是覆盖索引覆盖索引一次索引扫描就能获取查询的字段速度快。因为聚簇索引节点包含了整行的信息直接就能获得需要的字段值二级索引例如select id,name where name对name的二级索引查询此时二级索引的查询结果是idid和name都有了就不需要进行回表也属于覆盖索引。6. limit超大分页查询当执行select id,a,time order by time limit 900 0000,10时会首先获取并排序前900 0010条记录然后返回900 0000~900 0010这10条记录因为time二级索引本身就是有序的所以会首先查询time二级索引找到前900 0010条记录然后对每条记录回表查询聚簇索引获取字段a的值然后截取第900 0000~900 0010条记录影响sql执行速度的最大瓶颈是对900 0010条记录依次回表查询先回表获取记录再截取。所以应该使用覆盖索引子查询优化select t.id, t.a, t.time from table t, (select id from table order by time limit 9000000, 10) tmp where t.id tmp.id; 首先使用子查询获取前900 0010条记录由于查询的是id所以不需要对每条记录回表查询直接截取第900 0000~900 0010条记录然后使用关联查询回表查询这10条记录相比于回表查询900 0010条速度会快很多。先截取再回表获取记录也可以对id,a,time建立联合索引create index idx_time_covering on table(time, id, a);这样不需要进行回表了是覆盖索引。7. 索引创建的原则数据量较大的表建立索引。对经常作为where/order by/group by条件的字段建立索引。尽量选择区分度高的列建立索引尽量建立unique索引。如果是字符串类型的字段字段长度较长考虑建立前缀索引。 尽量使用联合索引可以保证覆盖索引避免回表查询。控制索引数量。如果索引列不能存储null值最好在创建表时使用not null约束这样当有多个可用索引时mysql会更容易自动选择最优索引。8. 联合索引失效的情况对于联合索引index (a,b,c)由于联合索引是按照索引顺序构造B树的首先按照a字段排序如果a相同则按照b排序如果b也相同则按照c排序所以a、ab、abc作为条件时会走该索引但是ac、bc、b、c不走该索引因为B树排序失效。对于联合索引范围查询时右边的列会失效。例如where a1 and b2时b2不会走索引因为a是范围查询会首先查询a1的结果集合但是结果集合由于a不同所以不同a的b是无序的无序就无法对b进行索引查询在索引列上进行运算操作where substring(a,3,2)时索引会失效。字符串不加单引号索引会失效。以%开头的like模糊查询where a like ‘%666’索引会失效。9. SQL优化insert优化批量插入每次批量插入的数据不超过1000条。多次批量插入时手动事务提交避免每次批量插入都重复开启和提交事务。按主键插入。主键优化降低主键长度减少二级索引叶结点的空间占用尽量使用自增主键减少修改逐渐防止叶分裂和页合并。orderby优化尽量使用索引直接返回排序结果否则会进行全表扫描然后在排序缓冲区进行排序。当对多个字段依次进行升序和降序排序时应构造升序-降序索引。limit优化覆盖索引子查询优化先截取再回表获取记录防止过多次回表查询。count()优化使用count(*)和count(1) 避免额外取值和判空操作。update优化基于主键和有索引的字段进行更新避免行锁升级为表锁。10. 事务的特性原子性要求事务要么全部成功要么全部失败属于线程内某一操作失败必须回滚。隔离性要求同一事务、不同事物在多线程下串行执行无并发安全问题属于线程之间对该事物的操作不能相互干扰。一致性要求事务完成后数据保持一致。持久性要求事务操作后数据是永久修改的。内存中有undo log缓冲区用来记录事务执行前的旧数据。在逻辑存储结构中每行数据都有一个roll pointer指向undo log文件中的旧数据当事务需要执行回滚时直接根据该行数据的roll pointer指针就可以从undo log缓冲区读取到旧数据进行恢复从而保证了原子性和一致性。内存中有redo log缓冲区用来记录正常提交的事务对页的增删改操作并由log thread异步线程在每次事务提交后将其持久化到磁盘的redo log file中当write thread写脏页到磁盘发生错误时就可以用redo log file做数据恢复保证了持久性。类似redis中的aof在RR隔离级别中使用临键写锁临键读锁来确保同一事物、不同事物的当前读和写操作之间串行访问某行数据写操作之间串行访问。使用临键写锁MVCC确保写操作过程中写操作之间串行访问、写操作不会影响快照读的结果脏读、两次读结果不同保证隔离性。11.MySQL读写锁锁机制用来保证多线程同一事务、不同事务之间并发访问同一行数据引发的数据隔离性问题。共享锁和排它锁在事务提交后释放。全局锁对整个数据库实例加锁一般用于备份整个数据库时使用防止涉及多表更新的业务在备份文件中出现数据不一致问题。备份主库则写操作相关的业务会全部阻塞备份从库则备份期间无法执行主库同步来的数据导致主从延迟。在InnoDB中通过添加-single-transaction参数可以实现不加锁的一致性数据备份。表级锁分为三类表锁对整张表加锁解决DML之间的并发冲突基于读写锁实现。元数据锁解决DML和DDL的并发冲突DML申请元数据共享锁DDL申请元数据排它锁。意向锁解决表锁和行锁的冲突线程申请行锁时同时申请对应的意向锁线程申请表锁时仅意向锁为空或意向锁和申请的表锁都是共享锁才可以申请。行级锁分为三类InnoDB中的数据存储结构是索引所以行锁是对记录在索引B树上的索引项加锁而不是对记录加锁。行锁锁定单个索引项写操作会上排它锁期间任何对该索引项的线程都被阻塞。读操作默认不上锁上共享锁时其他对该索引项的读线程可以重复申请锁阻塞写线程。间隙锁锁定索引项之间的间隙防止其他线程在间隙进行insert解决幻读问题在RR隔离级别中。临键锁同时锁定单个索引项和索引项前的间隙也是RR隔离级别SQL执行时若针对unique索引的B树进行搜索且是等值匹配时会降级为行锁。SQL执行时若针对unique索引的B树进行搜索且是等值匹配且索引项不存在时会降级为间隙锁。例如索引项1,2,4,5此时对索引项3进行增删改会先将2,4之间的间隙上锁。SQL执行时若针对非unique索引的B树进行搜索且是等值匹配且索引项不存在时会降级为间隙锁。例如索引项1,2,2,4,5此时对索引项3进行增删改会先将2,4之间的间隙上锁。SQL执行时若不走任何索引那么会升级为表锁。12. 并发事务隔离性问题并发事务指的是不同事物并发操作同一数据引起的问题本质是为了提高并发而不使用读写锁引发的问题打破了读写操作的隔离性。脏读一个事物读取到另外一个事物还没有提交的数据。例如事务A执行update但事务A在commit前事务B就读取了事务A修改的数据那么事务B读到的就是脏数据因为A可能会回滚。不可重复读一个事物先后查询同一条记录由于另一个事务的更新操作导致两次读到不同的数据。例如事务A先后读取同一数据但是在两次读取之间事务B修改了数据导致事务A两次读到的数据不一致。幻读一个事物先后查询同一条记录由于另一个事务的插入操作导致两次读到不同的数据。13.事务隔离级别MySQL的事务隔离级别就是解决不同事物之间并发操作同一记录引起的并发事务问题。默认级别是可重复读可以解决脏读和不可重复读问题。在任何隔离级别下select lock in share mode、update、delete、insert操作共享锁和排它锁在事务提交后释放。在序列化隔离级别下普通的select操作会自动添加lock in share mode后缀。在读未提交、读已提交、可重复读隔离级别下普通的select操作不会加锁或加锁后select执行完毕立即释放。读未提交增删改查操作都不加锁可能发生脏读、不可重复读和幻读。序列化写操作对记录的索引加临键写锁阻塞对当前记录的读写操作解决脏读。读操作加临键读锁并在事务提交后释放读操作事务提交前允许其他读操作但阻塞对当前记录的写操作解决了不可重复读和幻读问题。读已提交写操作加临键写锁阻塞当前读读的是记录对应的索引允许快照读读的不是记录而是undo log所以不会被阻塞且undo log中都是已提交的数据解决了脏读问题。读操作不加锁两次当前读期间允许写操作所以当前读仍然有不可重复读和幻读问题两次读到的数据不一致。由于快照读两次读的不是同一个readview所以快照读仍然有不可重复读和幻读问题。可重复读写操作加临键写锁阻塞当前读读的是记录对应的索引允许快照读读的不是记录而是undo log所以不会被阻塞且undo log中都是已提交的数据解决了脏读问题。考虑到写操作饥饿问题InnoDB并没有为读操作加共享锁而是采用MVCC如果在RR中使用当前读则类似于序列化隔离模式读操作加临键读锁解决了不可重复读和幻读问题。关键是对于快照读对同一个事物的多个快照读都使用第一个快照读的readview这样每次读的数据都是一样的解决了不可重复读和幻读问题。14.MySQL服务器结构连接层用于校验JDBC发来的用户名和密码确认客户端使用的用户名的权限。服务层暴露统一接口检查并处理SQL、存储过程、视图、触发器生成引擎能理解的指令序列。引擎层控制数据的逻辑存储结构接收服务层的指令序列并执行从而操作存储层数据索引、事务、锁在该层维护。存储层就是磁盘物理存储结构存储数据和日志等持久化数据。15.InnoDB存储引擎服务层对外暴露统一接口将sql、存储过程、视图、触发器解析为引擎能理解的指令序列引擎层负责维护表中数据的逻辑存储结构不同的引擎有不同的逻辑存储结构所以引擎层基于自己的存储方式执行传来的指令序列并从磁盘读取数据且过程中可能会涉及的索引、事务、锁都由引擎层自己实现。存储引擎是基于表的每张表可以设置不同的存储引擎。逻辑存储结构为B树(表空间)-页结点总和、非叶结点总和(2个Segment)-结点(Page)-数据行(Row)-列col、trx id(对该记录行执行写操作且未提交的事务id)、roll pointer(指向事务执行前保存在undo log日志缓冲区中的旧数据)内存结构缓冲池存储B树种经常使用的部分结点减少磁盘I/OB树存储在磁盘中虽然和数据库表都存储在磁盘中但相较于存储在磁盘中的表查询时间复杂度O(logn)O(n)要低。采用双向链表结构。Page有三种状态空闲页、被使用的页但数据未被修改、数据被修改的脏页与磁盘数据不一致。Change Buffer仅针对非unique的索引用来减少增删改操作的磁盘I/O。因为unique索引需要检查唯一性执行增删改操作时如果缓冲池没有对应结点就必须立即读磁盘获取结点到缓冲池但是非unique结点的索引列不需要判断唯一性所以当执行增删改操作时若需要的结点不在缓冲池中时不会立即磁盘I/O读取该结点而是将增删改操作缓存到Change Buffer中直到其他线程对该结点执行读操作时必须要从磁盘中读取数据到缓冲池了才会执行Change Buffer中的操作修改缓冲池中的数据。这样的话磁盘上的节点数据仍然是旧数据但缓冲池中的结点数据是新的这样的话缓冲池中的这个页就变成了脏页unique索引将页读到缓冲池并修改后也是脏页不会立即写回磁盘。自适应哈希索引是为了提高查询速度的。正常查询流程首先InnoDB有一个页哈希表页号-缓冲池位置 来根据页号定位该页结点在缓冲池中的位置所以需要根据sql条件遍历B树获取页号页结点因为并不是所有结点都存储在缓冲池所以二分查找到不在缓冲池中的页时需要进行磁盘I/O将部分非叶结点读取到页缓冲池最后得到叶结点的页号基于页号查页哈希表得到该页在缓冲池的位置不在缓冲池就需要磁盘I/O读到缓冲池并更新页哈希表。可以看出即使所需要的页在缓冲池中查询操作也需要搜索B树查询效率很低因此InnoDB维护了一个自适应哈希表sql条件-缓冲池位置存储了高频使用的sql条件(where id1)可以直接根据sql条件来找到该页在缓冲池中的位置不用搜索B树。如果该页后来被淘汰出缓冲池那么在自适应哈希表的内容也会被移除。自适应哈希索引只对等值查询有效。日志缓冲区redo log缓冲区记录正常提交的事务对页的增删改操作用于数据库宕机恢复数据。undo log缓冲区记录增删改操作时的旧数据用于事务执行失败时回滚其中每个写事物执行前都会将旧数据保存到uodo log中并指向上一个操作该条记录的事务保存的旧数据形成链表结构记录行row的逻辑存储结构中的roll pointer指向undo log缓冲区中最新写该记录的事务保存的旧数据。磁盘结构系统表空间存储Change Buffer中的数据为了防止服务器宕机导致change buffer中暂存的增删改操作丢失。文件表空间存储所有ibd文件每张表都会对应一个.ibd文件存储了表结构、数据、索引。撤销表空间存储undo log日志文件。双写缓冲区为了保证数据不丢失在将缓冲池中的脏页写回磁盘的ibd文件前会先写入双写缓冲区文件中。redo log记录增删改操作发生错误时便于进行数据恢复。后台线程Master Thread负责将change buffer中的操作更新到缓冲池。read thread负责从磁盘中读页结点到缓冲池。write thread将脏页写回磁盘。log thread将日志缓冲区内容写回磁盘。purge thread清理undo log缓冲区中失效的数据。page cleaner thread判断缓冲池中哪些页是脏页将脏页交给write thread线程写回磁盘。16.MVCCMVCC全称多版本并发控制。由于序列化隔离级别下写锁能够解决脏读问题读锁能解决不可重复读和幻读问题而InnoDB的RR隔离级别为了读并发量和写饥饿并没有用读锁所以仍然具有不可重复读和幻读问题。MVCC为了提高读并发在写操作过程中允许快照读因为快照读读的是undo log而不是记录对应的索引而锁锁的是索引所以读操作并不会被阻塞。具体来说每条记录都有一个row结构来存储该行数据其中trx id记录当前执行写操作且未提交的事务的idroll pointer指针指向undo log缓冲区中该事物保存的旧数据行。当其他读操作事务执行select时会生成readview记录操作该行记录的所有未提交事务的id集合m_ids遍历row中的roll pointer指向的的undo log链表来找出最新已提交的旧数据trx id不在m_ids中或自己更新的未提交数据trx idcreator trx id从而能够在写操作阶段允许快照读提高读并发。为了解决写饥饿快照读不会上锁所以写操作可以获取锁。但不可重复读和幻读问题还没有解决所以MVCC对于同一事物的多次快照读只对第一个快照读创建readview该事物所有快照读都基于同一个readview所以从undo log中读到的都是链表中同一个结点的数据解决了多次读数据不一致的不可重复读和幻读问题对于脏读问题快照读读的不是表且undo log中的数据都是已提交的数据所以不会读到未提交的数据就不会有脏读问题。本质是第二次读的是undo log中的旧数据从而保证了两次读操作的结果一致。因为RR隔离级别下读到的数据可能是旧数据所以如果要在RR级别下使用当前读那么在同一事务中就不要出现快照读就不会出现并发问题。使用当前读本质上就升级为序列化隔离级别。17.单表数据量较大时分表垂直分表以字段为依据根据字段含义将不同组合的数据拆分到多个表中同时降不常用的字段单独放到一张表中将占用空间较大的字段单独拆为一张表并在多个表中都加入id确认一对一关系。水平分表将一张表的数据按照id%1,2,3的方式拆分到多张表中以此来确认查询时操作哪张表。