Mysql

索引

• 生成索引，建立二叉查找树进行二分查找
  • 树的深度太深，IO太频繁
• 生成索引，建立B-Tree结构进行查找
• 生成索引，建立B±Tree结构进行查找
• 生成索引，建立Hash结构进行查找

• B-Tree
• 根节点至少包括两个孩子
• 树中每个节点最多含有m个孩子（m>=2）
• 除根节点和叶节点外，其他每个节点至少有ceil(m/2）个孩子
• 所有叶子节点都位于同一层
• 假设每个非终端结点中包含有n个关键字信息，其中
  • Ki(i=1…n)为关键字，且关键字按顺序升序排序K(i-1）<Ki
  • b）关键字的个数n必须满足：[ceil(m/2)-1]<=n<=m-1
  • c）非叶子结点的指针：P[1]，P[2]，.……P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]
• 指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1]，K[i])的子树

• B+tree
• B+树是B树的变体，其定义基本与B树相同，除了：
  • 非叶子节点的子树指针与关键字个数相同
  • 非叶子节点的子树指针P[i]，指向关键字值[K[i]，K[i+1]）的子树
  • 非叶子节点仅用来索引，数据都保存在叶子节点中
  • 所有叶子节点均有一个链指针指向下一个叶子结点
• 优势
  • 可以存储更多的关键字
  • B+树的磁盘读写代价更低
  • B+树的查询效率更加稳定
  • B+树更有利于对数据库的扫描
    • 范围查询
      

• Hash索引缺点
  • 仅仅能满足“="，“IN"，不能使用范围查询
  • 无法被用来避免数据的排序操作
  • 不能利用部分索引键查询
  • 不能避免表扫描
  • 遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高
• BitMap索引
  • 粒度大

• 密集索引和稀疏索引的区别
  • 密集索引文件中的每个搜索码值都对应一个索引值
  • 稀疏索引文件只为索引码的某些值建立索引项
• InnoDB
  • 若一个主键被定义，该主键则作为密集索引
  • 若没有主键被定义，该表的第一个唯一非空索引则作为密集索引
  • 若不满足以上条件，innodb内部会生成一个隐藏主键（密集索引）
  • 非主键索引（叶节点）不存储行索引的物理地址，存储相关键位和其（行索引）对应的主键值，包含两次查找
  • 数据和索引分开存储，三个文件

慢查询

show variables like '%quer%';
show status like '%slow_queries%'
set global slow_query_log=on;
set global long_ query_time=1;

explain

• type

system>const>eq_ref>ref>fulltext>ref or_null>index merge>unique_subquery>index_ subquery>range>index>all

• extra
  
• FORCE INDEX 强制索引

• 最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到**范围查询（>、<、between、like)**就停止匹配，比如a=3 andb=4 andc>5 and di=6如果建立（a,b，c，d)顺序的索引，d是用不到索引的，如果建立（a,b，d，c)的索引则都可以用到，a,b，d的顺序可以任意调整。
• =和in可以乱序，比如a=1and b=2 andc=3建立（a,b,c）索引可以任意顺序，mysql的查询优化器会帮你优化成索引可以识别的形式

• 数据量小的表不需要建立索引，建立会增加额外的索引开销
• 数据变更需要维护索引，因此更多的索引意味着更多的维护成本
• 更多的索引意味着也需要更多的空间

• for update 排他锁
• lock in share mode 共享锁
• Innodb在没有使用索引的时候用的是表级锁
  

• MyISAM适合的场景
  • 频繁执行全表count语句
  • 对数据进行增删改的频率不高，查询非常频繁
  • 没有事务

• 按锁的粒度划分，可分为表级锁、行级锁、页级锁
• 按锁级别划分，可分为共享锁、排它锁
• 按加锁方式划分，可分为自动锁、显式锁
• 按操作划分，可分为DML锁、DDL锁
• 按使用方式划分，可分为乐观锁、悲观锁

• 原子性（Atomic)
• 一致性（Consistency)
• 隔离性（Isolation)
• 持久性（Durability)

• 更新丢失—-mysql所有事务隔离级别在数据库层面上均可避免
• 脏读——READ-COMMITTED事务隔离级别以上可避免
• 不可重复读——REPEATABLE-READ事务隔离级别以上可避免
• 幻读——SERIALIZABLE事务隔离级别可避免
  

InnoDB可重复读隔离级别下如何避免幻读

• 表象：快照读（非阻塞读）–伪MVCC 多版本控制
• 内在：next-key锁（行锁+gap锁）
• 当前读：select…lock in share mode,select…for update
• 当前读：update，delete，insert
• 快照读：不加锁的非阻塞读，select

RC、RR级别下的InnoDB的非阻塞读如何实现

• 数据行里的DB_TRX_ID、DB_ROLL_PTR、DB_ROW_ID字段
• undo日志
• read view

对主键索引或者唯一索引会用Gap锁吗

• 如果where条件全部命中，则不会用Gap锁，只会加记录锁
• 如果where条件部分命中或者全不命中，则会加Gap锁。部分则部分加Gap锁

Gap锁会用在非唯一索引或者不走索引的当前读中
非唯一索引

不走索引

• GROUP BY
  • 满足“SELECT子句中的列名必须为分组列或列函数
  • 列函数对于group by子句定义的每个组各返回一个结果
  • 如果用group by，那么你的Select语句中选出的列要么是你groupby里用到的列，要么就是带有之前我们说的如sum min等列函数的列
  • WHERE过滤行，HAVING过滤组
  • 出现在同一sql的顺序：WHERE>GROUP BY>HAVING

Redis

Memcache和Redis的区别

• Memcache：代码层次类似Hash
  • 支持简单数据类型
  • 不支持数据持久化存储
  • 不支持主从
  • 不支持分片
• Redis
  • 数据类型丰富
  • 支持数据磁盘持久化存储
  • 支持主从
  • 支持分片

FD:File Descriptor,文件描述符：一个打开的文件通过唯一的描述符进行引用，该描述符是打开文件的元数据到文件本身的映射

• Redis采用的IVO多路复用函数：epoll/kqueue/evport/select
• 优先选择时间复杂度为O（1)的I/O多路复用函数作为底层实现
• 以时间复杂度为O(n)的select作为保底
• 基于react设计模式监听I/O事件
• Redis是基于内存的操作，CPU不是Redis的瓶颈，Redis的瓶颈最有可能是机器内存的大小或者网络带宽。既然单线程容易实现，而且CPU不会成为瓶颈
• Redis使用的是非阻塞IO，IO多路复用，使用了单线程来轮询描述符，将数据库的开、关、读、写都转换成了事件，减少了线程切换时上下文的切换和竞争

• String：最基本的数据类型，二进制安全
• Hash：String元素组成的字典，适合用于存储对象
• List：列表，按照String元素插入顺序排序
• Set:String元素组成的无序集合，通过哈希表实现，不允许重复
• Sorted Set:通过分数来为集合中的成员进行从小到大的排序
• 用于计数的HyperLogLog，用于支持存储地理位置信息的Geo

从海量Key里查询出某一固定前缀的Key

• KEYS pattern：查找所有符合给定模式pattern的key
• SCAN cursor [MATCH pattern] [COUNT count]
  • 基于游标的迭代器，需要基于上一次的游标延续之前的迭代过程
  • 以O作为游标开始一次新的迭代，直到命令返回游标0完成一次遍历
  • 不保证每次执行都返回某个给定数量的元素，支持模糊查询
  • 一次返回的数量不可控，只能是大概率符合count参数

如何通过Redis实现分布式锁

• 分布式锁需要解决的问题
  • 互斥性
  • 安全性
  • 死锁
  • 容错

SETNX key value:如果key不存在，则创建并赋值

• 时间复杂度：O（1)
• 返回值：设置成功，返回1；设置失败，返回0。
• EXPIRE key seconds
  • 设置key的生存时间，当key过期时（生存时间为0），会被自动删除
• SET key value [EX seconds][PX milliseconds][NXIXX]
  • EX second：设置键的过期时间为second秒
  • PXmillisecond：设置键的过期时间为millisecond 毫秒
  • NX：只在键不存在时，才对键进行设置操作
  • XX：只在键已经存在时，才对键进行设置操作
  • SET操作成功完成时，返回OK，否则返回nil

• 大量的key同时过期的注意事项
  • 集中过期，由于清除大量的key很耗时，会出现短暂的卡顿现象
  • 解放方案：在设置key的过期时间的时候，给每个key加上随机值

异步队列

• 使用List作为队列，RPUSH生产消息，LPOP消费消息
  • 缺点：没有等待队列里有值就直接消费
  • 弥补：可以通过在应用层引入Sleep机制去调用LPOP重试
• BLPOP key [key…] timeout:阻塞直到队列有消息或者超时
• 缺点：只能供一个消费者消费
• pub/sub：主题订阅者模式
  • 发送者（pub)发送消息，订阅者（sub)接收消息
  • 订阅者可以订阅任意数量的频道
  • 缺点：消息的发布是无状态的，无法保证可达
    

持久化

RDB(快照）持久化：保存某个时间点的全量数据快照

• SAVE：阻塞Redis的服务器进程，直到RDB文件被创建完毕
• BGSAVE：Fork出一个子进程来创建RDB文件，不阻塞服务器进程
• 通过lastsave 查看是否保存工程
• 自动化触发RDB持久化的方式
• 根据redis.conf配置里的SAVEmn定时触发（用的是BGSAVE)
• 主从复制时，主节点自动触发
• 执行Debug Reload
• 执行Shutdown且没有开启AOF持久化

Bgsave

• 系统调用fork0：创建进程，实现了Copy-on-Write
• 如果有多个调用者同时要求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本给该调用者，而其他调用者所见到的最初的资源仍然保持不变
• 缺点
  • 内存数据的全量同步，数据量大会由于I/O而严重影响性能
  • 可能会因为Redis挂掉而丢失从当前至最近一次快照期间的数据

AOF

AOF(Append-Only-File)持久化：保存写状态

• 记录下除了查询以外的所有变更数据库状态的指令
• 以append的形式追加保存到AOF文件中（增量）

• 日志重写解决AOF文件大小不断增大的问题，原理如下：
  • 调用fork)，创建一个子进程
  • 子进程把新的AOF写到一个临时文件里，不依赖原来的AOF文件
  • 主进程持续将新的变动同时写到内存和原来的AOF里
  • 主进程获取子进程重写AOF的完成信号，往新AOF同步增量变动
  • 使用新的AOF文件替换掉旧的AOF文件
    
• RDB和AOF的优缺点
  • RDB优点：全量数据快照，文件小，恢复快
  • RDB缺点：无法保存最近一次快照之后的数据
  • AOF优点：可读性高，适合保存增量数据，数据不易丢失
  • AOF缺点：文件体积大，恢复时间长
• RDB-AOF混合持久化方式
  • BGSAVE做镜像全量持久化，AOF做增量持久化

Pipe

Pipeline和Linux的管道类似
Redis基于请求/响应模型，单个请求处理需要一一应答
Pipeline批量执行指令，节省多次I0往返的时间
有顺序依赖的指令建议分批发送
主从同步
全同步过程

• Salve发送sync命令到Master
• Master启动一个后台进程，将Redis中的数据快照保存到文件中
• Master将保存数据快照期间接收到的写命令缓存起来
• Master完成写文件操作后，将该文件发送给Salve
• 使用新的AOF文件替换掉旧的AOF文件
• Master将这期间收集的增量写命令发送给Salve端
  增量同步过程
• Master接收到用户的操作指令，判断是否需要传播到Slave
• 将操作记录追加到AOF文件
• 将操作传播到其他Slave：1、对齐主从库；2、往响应缓存写入指令
• 将缓存中的数据发送给Slave

Redis Sentinel
解决主从同步Master宕机后的主从切换问题：

• 监控：检查主从服务器是否运行正常
• 提醒：通过API向管理员或者其他应用程序发送故障通知
• 自动故障迁移：主从切换

流言协议Gossip

• 每个节点都随机地与对方通信，最终所有节点的状态达成一致
• 种子节点定期随机向其他节点发送节点列表以及需要传播的消息
• 不保证信息一定会传递给所有节点，但是最终会趋于一致

Redis的集群原理

• 如何从海量数据里快速找到所需？
• 分片：按照某种规则去划分数据，分散存储在多个节点上
• 常规的按照哈希划分无法实现节点的动态增减
• 一致性哈希算法：对2^32取模，将哈希值空间组织成虚拟的圆环
• 将数据key使用相同的函数Hash计算出哈希值
• 引入虚拟节点解决数据倾斜的问题