redis常见问题
[TOC]
基础概念相关
1.什么是redis
2.redis的特点有哪些
3.memcache与redis的区别有哪些
4.redis相比memcache有哪些优势
5.如何实现本地缓存？请描述一下使用方式
6.redis的通讯协议是什么？有什么特点
8.redis过期策略
9.redis事件模型
10.redis与memcache有什么不同
11.redis在bgsave时会提高负载因子，为什么？
redis数据结构及指令相关
1.redis支持的数据类型
2.redis常用的命令有哪些
3.一个字符串类型的值最大容量是多少
4.redis各个数据类型最大存储量分别是多少
5.请介绍一下redis的数据类型sorted set及其底层实现
6.redis事务相关命令有哪些？
7.什么是redis事务？原理是什么？
8.redis事务需要注意的有哪些
9.redis事务为什么不支持回滚
10.请介绍一下pipeline及使用场景
11.请说明一下redis的批量命令与pipeline有什么不同
12.请介绍一下redis的发布订阅功能
13.redis的链表数据结构特征有哪些？
14.请介绍一下redis的string类型底层实现
15.redis的string类型使用ssd方式实现的好处
16.设置键的生存时间和过期时间有哪些命令
17.zset为什么选用跳跃表而不是二叉平衡树
18.redis hash结构的扩容与rehash的关系
当我们在访问一个hash对象时，会检查是否需要扩容
1.如果当前处于rehash中，不扩容
2.如果当前dict未分配内存，通过扩容来分配内存
3.如果负载因子>=1且允许扩容则进行扩容 (负载因子=哈希表的entry数/哈希表大小)
4.如果负载因子>=5则强制扩容
hash期间如果生成子进程，则会造成大量拷贝，原因是生成子进程时，子进程与父进程由于COW的原因共享内存，如果此时进行rehash，则会对修改的内存空间做复制
子进程脏页内存统计
redis高并发处理策略相关问题
1.为什么redis需要把所有数据放到内存中
2.redis是单线程的吗
3.redis为什么设计成单线程的
4.什么是缓存穿透?怎么解决
5.什么是缓存雪崩？怎么解决
6.缓存的更新策略有几种?
7.请介绍几个可能导致redis阻塞的原因
8.怎么去发现redis阻塞异常情况
redis集群相关问题
1.redis集群架构模式有哪几种
2.redis集群最大节点个数是多少
3.redis集群的这多年该复制模型是怎样的
4.请介绍一下redis集群实现方案
5.redis集群会有些写操作丢失吗？为什么？
6.redis慢查询是什么？通过什么配置？
7.redisDe慢查询修复经验有哪些？怎么修复的？
8.如何优化redis服务的性能？
9.redis的主从复制模式有什么优缺点
10.redis sentinel模式优缺点
11.如何设置redis的最大连接数？查看redis的最大连接数？查看redis当前连接数？
12介绍一些redis常用的安全设置
redis缓存管理及持久化机制相关问题
1.redis持久化机制有哪些？
2.redis持久化机制AOF和RDB有哪些不同之处
3.请介绍一下RDB持久化机制的优缺点
4.请介绍一下AOF持久化机制的优缺点
5.如果AOF文件数据出现异常，redis服务怎么处理
6.常见的淘汰算法有哪些？
7.redis淘汰策略有哪些？
9.redis如何做内存优化？
10.什么是bigkey?有什么影响？
11.怎么发现bigkey?
12.redis的内存消耗分类有哪些？内存统计使用什么命令
13.简单介绍一下redis的内存管理方式有哪些？
14.如何设置redis的内存上限？有什么作用？
15.redis报内存不足该怎么办
redis应用场景设计相关问题
2.redis常用的业务场景有哪些？
3.什么是分布式锁？有什么用？
4.分布式锁可以通过什么来实现？
5.介绍一下分布式锁实现需要注意的事项
6.redis怎么实现分布式锁
7.缓存命中率表示什么?
1.redis适用场景有哪些？
8.怎么提高缓存命中率
php
1.php7有哪些改进，为什么相比php5有提升？
链接
- 底层数据类型的优化
zval: 总体积降低(16字节)，主要是3个字段value,u1,u2
zend_string: 所有数据一次申请，在连续的内存中存放value: 可以保存一个指针或者long/double u1: 保存类型信息，标识zval的类型 u2: 保存辅助信息，必须hash的next
zend_array:php5 array使用链表加hash表实现，有以下问题 每个bucket都需要一次内存分配 为保障数组两个语义，每个bucket需要维护4个指向bucket的指针,每个bucket将为这4个指针付出16/32字节内存成本 php7 array使用连续内存实现逻辑链表，所有bucket及索引表都分配在一块连续的内存上
2.php内存管理
3.php的垃圾回收机制
es问题
1.查询年龄大于17 且名称不等于zhagnsan的记录
mysql
事务
1.innodb ACID特性
2.事务隔离等级
索引
1.innodb索引结构
2.如何减少回表
3.对于不满足最左原则语句的执行流程
4.mysql为什么数据量变大查询会变慢
当数据量变大时B+树高度会变大
比如2层的B+树，非叶子节点每个元素12字节，叶子节点与实际字段占用空间综合有关，比如50，这样的话
非叶子节点 指针+int值 8+4=12字节 (理想情况，正常可能是字符串而非int值，占用字节会大)
叶子基地那 指针+表字段占用空间和 比如200字节
数据和指针大概占80%
叶子节点可容纳元素数 16384/12 * 0.8 = 1000
非叶子节点可容纳元素书 16384/200 * 0.8 = 100
两层可容纳数据量 = 1000*100 = 100000
三层可容纳数据量 = 100000*1000 = 100000000 (1亿)
意思是超过1亿数据量后，B+树高度变为4，
https://www.bo56.com/%E5%A6%82%E4%BD%95%E8%8E%B7%E5%8F%96-mysql-innodb-%E7%9A%84-btree-%E7%9A%84%E9%AB%98%E5%BA%A6/
http://zhongmingmao.me/2017/05/06/innodb-table-logical-structure/
性能排查
1.explain
2.短连接风暴
3.慢查询
主从
1.主从数据同步机制(流程图)
2.主从延迟及其解决办法
原因
* 备库性能差于主库
* 备库压力大
* 网络闪断
* 大事务
解决办法
* 多线程复制
* 一主多从
* 提升备库性能
* 减少大事务使用
go
运行时
1.GPM模型
2.G的三种状态
3.work stealing
4.sysmon
5.抢占式调度
标准库
1.如何发送一个带有超时的请求？请求如何设置header，如何设置body，query?
参见task/lib/std/net/http_test.go
面试题
分布式系统
分布式系统与集群的区别
分布式是指通过网络连接的多个组件，通过交换信息协作而形成的系统。而集群，是指同一种组件的多个实例，形成的逻辑上的整体。
两个概念并不完全冲突，分布式系统也可以是一个集群，比如zookeeper等，它的特征是服务之间会互相通信协作。举个是分布式系统但不是集群的情况，比如多个不同组件构成的系统；是集群而不是分布式系统的情况，比如多个经过负载均衡的HTTP服务器，它们之间不会互相通信。
谈谈业务中使用分布式的场景
分布式主要是提供可扩展性及高可用性，业务中使用分布式的场景主要有分布式存储及分布式计算
- 分布式存储将数据分片到多个节点上，不仅可以提高性能,同时也可以使用多个节点对同一份数据进行备份
- 分布式计算将一个大的计算分解为小任务分配到多台节点上去执行，再汇总小任务的执行结果到最终结果，例如mapreduce
CAP理论与BASE原则
分布式事务
分布式事务产生的原因
1.service层面上微服务，一次事务需要不同业务方操作处理
2.resource层面上分库分表，一次事务需要操作多个数据库
分布式事务方案
1.确认是否真正需要分布式事务
对于service层面微服务导致的事务问题，可以考虑将需要事务的微服务聚合成一个单机服务，使用数据库本地服务解决，这样有助于降低复杂度
如果确认需要引入分布式事务，通常有几种方案
基于XA的两阶段提交
- 准备阶段: 事务管理器向每个参与者发送prepare消息，每个参与者要么直接返回失败，要么本地执行事务，写本地redolog和undolog，但不提交。
- 提交阶段: 事务管理器如果收到参与者失败或超时消息，直接给每个参与者发送回滚(rollback)消息，否则，发送提交消息(commit)消息；参与者根据事务管理器指令执行提交或回滚操作，释放所有事务处理过程中使用的锁资源
其中提交阶段是一个耗时极短的操作
优缺点
优点: 方案比较简单，成本较低
缺点:
- 同步阻塞，比起一阶段提交，两阶段提交再执行同样的事务时耗费更多事件。事务执行时间的延长意味着锁资源发生冲突的概率增加，当事务并发量达到一定数量时，就会出现大量事务积压甚至出现死锁，系统性能就会严重下滑
- 数据不一致，比如第二阶段资源管理器发出commit通知，但因为网络问题导致仅一部分参与者收到并执行了commit操作，这时候就产生了数据不一致问题
- 单点问题，事务管理器是单点
>
Mysql5.7后可靠使用
出错回滚
TCC(try-confirm-cancel)
消息中间件
使用MQ有几个问题需要考虑
1.如何保障mysql与MQ的一致性，即写入mysql后一定写入mq的一致性问题
2.如何保障消费端只消费一次，即幂等性问题
事务开始
- 给支付宝账户zhangsan,扣100元
- 给事件表插入一条记录事务结束此时是对同一数据库的两张表操作，因此可以用数据库的事务进行保证。另外，起一个定时程序，定时扫描事务表，发现一个状态为’UNFINISHED’的事件，就进行封装为消息，发送到消息中间件，然后将状态改为’FINISHED’.
- 消费方通过队列拿到数据，处理完后，对消息手动提交确认
老生常谈——利用消息队列处理分布式事务
Kafka消息消费一致性
https://www.jianshu.com/p/6233d5341dfe
负载均衡算法及实现
- 轮训
- 加权轮训
- 最少连接
- 随机
分布式锁
锁的意义
- 提升效率，保证一个任务没有必要被执行两次
- 保证正确，使用锁来保证任务按照正确的步骤执行，防止两个节点操作同一份数据
实现
- redis分布式锁
- redlock
- zookeeper分布式锁
分布式session
1
分布式ID生成器
消息队列(kafka)
引入中间件的目的
解耦、异步、削峰
如何保障消息只消费一次
- 生产者至少写入一次
- 消费者幂等，做好唯一性判定
如何保证消息的可靠性传输
如何保证消息的顺序性
需要了解 kafka partion内部有序，且一个partion只会被consumer group中的一个consumer消费
于是在生产者写入消息时，对需要保证顺序的消息设置key值，保证相同key值写入同一个partion
如何保障消息不丢失
1.producer的ack机制
2.发送消息
生产者有两种模式，同步和异步
异步模式下生产者一侧会有本地buffer，累计至一定数量后批量发送，可以大幅提升性能，这里有可能会丢消息
如果对可靠性要求高，那么这里可以设置为同步发送producer.type=sync，默认是 sync
3.如果需要高可靠性，需要显示提交offset，也就是当业务处理完毕后，再手动提交offset。这样会导致重复消费，需要提供幂等性接口
kafka为什么这么快
1.顺序写磁盘
顺序写磁盘是随机写磁盘的N倍，磁盘不再是瓶颈
2.page cache
kafka利用了操作系统的page cache,通过page cache,kafka的读写操作基本上是基于内存的，读写速度得到极大提升
3.零拷贝技术
零拷贝技术可以有效减少上下文切换和拷贝次数
工作模型
分区
选举
操作系统
系统设计
设计一个短链系统
es
es如何实现扩容
es文档对应的shard不变，扩容后shard在node上迁移
亮点
复习二叉树
整理亮点项目
技术选项思考
话题阅读数讨论数
难点
如何在有限的资源下承接23WQPS
由于是公司级基础服务，如何保障平均RT低于10MS
如何在热点事件情况下保障服务的可靠性
如何实现服务配置动态下发
如何进行服务监控及报警
整个项目架构
为什么不选择php技术栈
我认为使用php来处理高并发场景不合适
1.动态脚本语言执行效率低效(opcache的性能依旧与静态语言等有差距)
2.php执行是阻塞的
php-fpm模型 master-worker多进程模型，一个进程处理一个连接
nginx与php-fpm之间默认通过短连接，每次请求都需要重新建立连接，可以通过fastcgi的`fastcgi_keep_conn`选项来开启长连接。(不过对于nginx与php-fpm在同一台机器上的情况而言，对性能影响很小，可以忽略)
当所有进程都在处理请求时，后续请求存在于backlog队列中，如果超过nginx factcgi超时时间，返回504响应码
3.php-fpm短连接
技术选型
对比php or go swoole java nodejs
性能 低 高 较高 高
开发效率 高 较高 中等 未知 中等 未知
学习成本 低 低 高 高
文档 好 好 好 差
运维成本
openresty高性能
1.天生
站在巨人肩膀上，基于nginx开发(基于epoll实现的reactor模型)
lua-jit
cosocket(非阻塞网络io库)
2.最佳实践
串行改并行
连接池
缓存shareddict(类似yac)
高性能DB
禁止使用阻塞函数
热搜表态
有限资源内存储5亿用户数据
异步刷
同步刷
异步应用
es
网络协议
tcp
1.tcp数据报文首部构成及其意义
链接
1.time wait状态意义
2.发现大量time wait状态连接
3.慢启动
4.发送方窗口/接收方窗口/拥塞窗口
http
响应码
499 client had closed connection
502 bad gateway
504 gateway timeout
资料
helper
1.使用golang生成一个n*n的二维切片
2.从索引m到索引n总共m-n+1个数
数据结构
二叉树
1.什么是二叉树，二叉树的性质
性质1: 在二叉树的第i层上**至多**有2^(i-1)个结点
性质2: 深度为i的二叉树**至多**有2^i-1个结点
性质3: 对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2，则n0=n2+1
性质4: 具有n个结点的完全二叉树的深度为[log2n]+1 []表示取整
性质5: 如果一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，对任一结点1(1<=i<=n)有:
(1)如果i=1,则结点i是二叉树的根,无双亲；如果i>1，则其双亲是结点[i/2]
(2)如果2i>n,则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i
(3)如果2i+1>n,则结点i无右孩子;否则其右孩子是结点2i+1
2.什么是完全二叉树/满二叉树/斜树
3.什么是二叉查找树 性质
定义: 二叉查找树，又称二叉查找树。它或者是一棵空树，或者是具有下列性质的二叉树。
* 若它的左子树不空，则`左子树`上所有结点的值均小于它的根结构的值
* 若它的右子树不空，则`右子树`上所有结点的值均大于它的根结点的值
* 它的左右子树叶分别是 二叉查找树
二叉查找树进行中序遍历可得到一个有序序列
4.二叉树遍历 广度优先遍历 深度优先遍历
算法
1.冒泡排序实现及时间复杂度
时间复杂度最好O(n) 最差O(n^2)
2.堆排序实现及时间复杂度
要点: heapify buildHeap heapSort
* 建堆后并无法保证有序
3.归并排序实现及时间复杂度
要点: 先拆分再有序重组
4.快速排序实现及时间复杂度
<<<<<<< Updated upstream
* 递归二分，每次确定一个点位置
* 递归要有出口
分治法
5.什么是稳定排序，什么是不稳定排序
稳定排序(位置1，2都是a,排序后位置1还是原位置1的a，位置2还是原位置2的a)
冒泡
归并
不稳定(快选堆希)
快速排序
堆排序
=======
* 递归二分，每次确定一个点位置
* 递归要有出口
分治法
5.什么是稳定排序，什么是不稳定排序
稳定排序(位置1，2都是a,排序后位置1还是原位置1的a，位置2还是原位置2的a)
冒泡
归并
不稳定(快选堆希)
快速排序
堆排序
Stashed changes
leetcode
设计
146.LRUcache
1206.跳表
贪心
135.分发糖果
数学
9.回文数
数组/字符串
1.两数之和
15.三数之和
注意base在略过重复数字时判断是在下一个循环，所以要和上一个数作比较
674.最长连续递增序列
双指针ij,i表示连续序列开始位置，j表示当前扫描位置，如果nums[j]<=nums[j-1]，则构成长度j-i的连续递增序列，解法类似leetcode3
3.无重复字符的最长子串
- 双指针(i,j)圈定字符串
- 借助字典hm记录已访问的字符
- 当每次发现重复元素时，要做判断，是否重复的位置index>=i,如果成立则i= index+1 (这里不能单纯i++,新开始的字符串需要不包含刚才重复的字符串),maxLength = max(maxLength,j-i)
4.寻找两个有序数组的中位数
54.螺旋矩阵
59.螺旋矩阵2
33.搜索旋转排序数组
14.最长公共前缀
* 输入是字符串切片[]string，要求返回这些字符串最长公共前缀
* 以第一个字符串v为基准，遍历所有字符串si，如果v不是si的前缀字符串，那么v = v[:len(v)-1]
151.翻转字符串里的单词 未解决
209.长度最小的子数组
滑动窗口 时间复杂度O(n)
字典序
440.字典序的第k小数字
* 十叉树，前序遍历
动态规划
base case+状态转移方程+备忘录字典
5.最长回文子串
如果一个字符串首尾字符相等且子串是回文字符串，那么该字符串也是回文字符串
使用二维数组作为备忘字典
字符串s的倒数第i个字符的索引位置是len(s)-i, 长度为5的字符串倒数第3个字符索引为5-3=2
53.最大子序和
- 很容易想到利用字典方式解决，再进一步思考，每个位置的最大值只和当前值及上一个位置的最大值有关，所以使用变量maxToCurrent代替字典m，可以有效提升时间及空间复杂度
> f(x) = max(nums[x],nums[x]+f(x-1))
* 很容易想到利用字典方式解决，再进一步思考，每个位置的最大值只和当前值及上一个位置的最大值有关，所以使用变量maxToCurrent代替字典m，可以有效提升时间及空间复杂度
Stashed changes
121.买卖股票的最佳时机
* 同53，利用字典解决，后发现只与之前最小购买价格有关，使用变量minv替换m
122.买卖股票的最佳时机 II
* 将所有的上升段加在一起，就是最大利润
链表
helper
求链表长度
求链表中间节点
合并有序链表
求倒数第k个元素
查找第N个节点，需要查N-1次(有dummy节点的话需要N次)
141.环形链表
142.环形链表2
返回入环的第一个节点(相交节点)
为什么有环的情况下二者一定会相遇呢？因为fast先进入环，在slow进入之后，如果把slow看作在前面，fast在后面每次循环都向slow靠近1，所以一定会相遇，而不会出现fast直接跳过slow的情况。
https://www.cnblogs.com/hiddenfox/p/3408931.html
160.两链表的交叉节点
19.删除链表倒数第K个元素
* 双指针pq
链表中值
206.反转链表
92.反转链表2(翻转子串)
2.两数相加
- 利用carry记录进位
445.两数相加2
* 链表头插法 (与之相对还有尾插法)
24.两两交换链表中的节点
206/92/24解题思路类似，都是增设dummynode,圈定翻转范围，循环执行翻转
25.kgroup
* 2020年1月日卡在确定需要翻转的范围上，如果采用递归实现的话，只需确认当次函数执行需要翻转的范围
* 2020年1月日 范围翻转后head变为翻转子链表的尾元素，连接下一个翻转子串的首元素
* 2020年2月3日 翻转范围字符串，操作需要使用prev,current两个指针实现，返回翻转后链表首元素
* 2020年3月25日 24/25两者都有递归和非递归两种解法 非递归解法全部使用了dn
* 2021年3月18日 卡在reverse 区域子链表翻转上
21.合并两有序链表
* 递归
- 非递归
23.合并K个有序链表
* 分治法 将k个合并的问题利用二分法转化为两两合并问题 与归并排序同理
148.链表排序
* 采用归并排序的思路，不断二分切割链表，进而归并切割后的链表，最后转化为链表两两合并的问题
* 链表找寻中点
* 2021年3月18日 忘了list1,list2需要走递归生成
203.移除链表元素
* 2020年3月25日 注意如果当前节点是要删除的节点，那么prev本次循环不会改变
哨兵节点:哨兵节点广泛应用于树和链表中，如伪头、伪尾、标记等，它们是纯功能的，通常不保存任何数据，其主要目的是使链表标准化，如使链表永不为空、永不无头、简化插入和删除。
61.旋转链表
本质上是将尾部向前数第K个元素作为头，原来的头接到原来的尾上
1.求出链表的长度len
2.k = k%len取余就是我们要右移的距离。
3.找到倒数第k+1个节点p(倒数第k个节点的前驱节点)及尾节点q。可以使用双指针法。
4.将尾结点Next指向头结点，构造循环链表
5.保留p.Next节点(倒数第k个节点)并从p处断开循环链表，返回之前保留的倒数第k个节点
2020年3月18日 offset计算出错
注意4,5的顺序，先构建循环链表再断开，否则可能有麻烦
二叉搜索树
树的问题大多可以通过分治法解决.
分治法的设计思想是：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法。
分治法在每一层递归上都有三个步骤：
step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；
step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
step3 合并：将各个子问题的解合并为原问题的解。
450.删除二叉搜索树中的节点
* 获取bst子树最小节点
* 获取bst子树最大节点
* 删除树最小节点并返回树的新根节点
> 2021年4月15日 再次学习 卡在获取bst子树最小节点 删除最小节点并返回操作后的树的
98.验证二叉搜索树(判断是否是有效的二叉搜索树)
|
|
426.将二叉搜索树转化为排序的双向循环链表
<<<<<<< Updated upstream
- 将二叉搜索树转化为排序的双向循环链表
Stashed changes
* 递归 出口 Right作为后继指针 Left作为前驱指针 1.中序遍历BST，构建有序双向链表 2.双向链表头尾相连，返回头结点
333.最大BST树
<<<<<<< Updated upstream
二叉树
104.二叉树的最大深度
536.从字符串生成二叉树
对于括号类的题目，基本第一眼就要想到stack，stack中存放节点指针，栈的最后一位是下一个要插入节点的父节点
663.均匀树划分
|
|
=======
最大BST树
- 获取二叉树节点数
- 检查是否是有效的BST
二叉树
- 二叉树的最大深度
从字符串生成二叉树
- 对于括号类的题目，基本第一眼就要想到stack，stack中存放节点指针，栈的最后一位是下一个要插入节点的父节点
均匀树划分
给定一棵有 n 个结点的二叉树，你的任务是检查是否可以通过去掉树上的一条边将树分成两棵，且这两棵树结点之和相等
题意转化下:
以x为根的树所有结点值的和为sum(x)
如果sum(a)==sum(root)/2,那么可以以a节点开始切割，行程的两棵树的节点和相等，返回true，否则返回falseStashed changes
662.二叉树最大宽度
Stashed changes
1
/ \
3 2
/ \ \
5 3 9
<<<<<<< Updated upstream
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
199.二叉树的右视图
解释: 最大值出现在树的第 3 层，宽度为 4 (5,3,null,9)。
- 二叉树的右视图
Stashed changes
层序遍历,方法同662利用size记录层中剩余元素，当size为0时，即到达当前层最右侧，将此刻节点收集起来
94.二叉树的中序遍历
* 递归法
* 借助栈
543.二叉树的直径
* 二叉树直径等于所有顶点"直径"的最大值，某顶点的"直径"等于左子树最大路径加右子树最大路径
* 与124不同的是，直径指的是路径长度，路径和指的是节点权重和
* 解题思路与124类似，都是通过dfs解决
124.二叉树的最大路径和
* 思考如何找到以root为转折点的最大路径
* 思考如何利用dfs找到整棵树的最大路径和
112.路径之和
* 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
* 分治法
113.路径总和2
* dfs+回溯
* 给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先
最近的意思即符合条件的深度最大的节点，也意味着我们需要通过dfs方式由下向上回溯
回溯时有
如果root等于p\q那么意味着已经找到了最近公共祖先，直接返回，
如果root==nil表示到达最深度也没有找到pq，返回nil
如果root有值但是不等于pq，那么在root左子树及右子树中查找，
如果left,right都找到，则root就是最近公共祖先
如果在left中找到，right中未找到，则最近公共祖先为left中回溯返回的节点
如果在right中找到，left中未找到，则最近公共祖先为left中回溯返回的节点
回溯
46.全排列
47.全排列2
|
|
1.两数之和
2.两数相加
4.两个有序数组的中位数
5.最长回文子串
7.翻转整数
如何翻转
边界问题
9.整数是否是回文数
11.盛最多水的容器
14.最长公共前缀
15.三数之和
20.有效的括号
21.合并两个有序链表
26.删除排序数组中的重复项
33.搜索旋转排序数组
46.全排列
回溯
47.有重复数字的全排列
54.螺旋矩阵
59.螺旋矩阵2
61.旋转链表
62.不同路径
70.爬梯子
78.子集
88.合并两个有序数组
98.验证二叉搜索树
235.二叉搜索树的最近公共祖先
236.二叉树的最近公共祖先
24.链表两两翻转
25.k group
常见面试算法
1.topk频率
最近一小时内 访问量最高前10个的ip
2.现在有一个nginx log文件A，请在linux下用命令从文件A中计算包含”img.gif”的行数，并算出最大QPS
算最大QPS用uniq -c
3.正则
4.加强motan掌控程度
5.transfer单点控制
6.dockerfile RUN CMD ENTRYPOINT区别
RUN程序中直接执行
CMD程序默认执行命令，docker run 时候跟命令会覆盖原有CMD命令
ENTRYPOINT直接执行，docker run 时候新命令会作为ENTRYPOINT的参数传入
7.覆盖索引
指的用到的索引覆盖到了所有要查询的字段
存留问题
1.算法层面需要继续准备
比如 1亿条中找出数量最多的几个
2.对于自身项目优势仍然不够有说服力
阅读数讨论数实现 阅读数讨论数库多大
3.覆盖索引
表t有id A B C 三个字段
在ABC上有联合索引
第一种情况: select A from t where A=1 and B=2 and C=3
1 SIMPLE t NULL ref idx idx 775 const,const,const 1 100.00 Using index
结果: type是ref，而且用到了覆盖索引
第二种情况: select * from t where A=1 and B=2 and C=3
1 SIMPLE t NULL ref idx idx 775 const,const,const 1 100.00 NULL
结果: type是ref，但extra是NULL 没有用到覆盖索引，(个人认为是通过索引拿到了主键，然后通过主键再回聚簇索引查询)
第三种情况: select A from t where B=2 and C=3
1 SIMPLE film_copy NULL index NULL idx 775 NULL 1001 1.00 Using where; Using index
结果: type是index，extra是Using where;Using index,type是index表示超级慢
总结
- 过滤条件用到的索引如果覆盖所有查询字段，则使用覆盖索引Using index
- 如果查询字段中包含非索引字段，则不能使用覆盖索引
网络安全XSS CSRF
潜在问题 话题阅读数讨论数redis快满了？
8台主 每个主配有3个从 每个主容量为6G
批量查询 提前分片 缓存 多线程
require “motan” .init_worker_motan_client() 什么意思？
查查33机器上motan怎么跑的
工作内容梳理
工作描述
核心工作方向话题管理方向，也会泛一些热搜的相关开发工作。然后整个话题管理方向目前有5个人，我是该方向的技术负责人，周会，code review等等都由我来组织，对于工作内容来说，功能性及非功能性开发
功能性模块
话题管理
话题干预
话题应用
话题推荐流
话题榜
话题单元
非功能性模块
一致性相关
我们是链路上一个环节，在本地处理完毕后，需要消息通知其他服务，比如状态变更、数据更改等等，假如本地处理完未进行同之前崩溃，则这条消息不会自动推送，被遗漏
这块按照场景区分对待:分为一致性敏感场景与非敏感场景
敏感场景
流内干预、网信办操作
目前采用transfer进行实现数据可靠传输，采用本地消息表+MQ/接口等方式进行消息重试，语义上是至少传输一次，幂等性需要靠双方一同来保障。
这种方式的优点是可以利用现有组件实现，另外，瓶颈在于本地消息表，可以采用分表方式缓解压力
非敏感场景
日志传输
对于非敏感场景，直接使用消息队列传输
可用性相关
降级
触发方式: 手动降级-自动降级
实现: 以服务读取本地配置文件形式，具体根据项目有多种形式
1.or项目，以定时器方式动态加载至共享内存
2.php项目，使用dconf定期同步配置中心配置
效果:
分为多级降级 依服务不同采用不同策略，
1.降幅服务整体RT及资源开销
分级丢弃个性化信息
降低数据更新频率，增加缓存
2.不丢弃广告
流量调度
触发方式: 手动-自动
实现:
属于间接的流量调度
2.微服务扩容
效果:
扩容面向的是大的服务池，扩容资源来自云机房，扩容后云机房流量占比升高，变相降低自建机房流量压力，实
1.七层扩容现流量调度
动态峰值应对
触发方式: 被动策略触发
策略面向服务RT QPS
实现方式:
数据收集 logtailer graphite
数据处理 shield
反馈控制 dconf vintage or
隔离建设
面向不同服务，目前会按多种方式拆分建设
1. 按照保障等级建设 核心池、非核心池，核心池承接搜索业务，非核心池供给公司外部门使用
2. 按照机房拆分，多机房分别部署服务
服务超时处理优化
1.多次重试
2.backup request
3.缓存
4.推进链路性能优化
可观测性相关
日志聚合服务
收集方式: udp http 文件
实现: filebeat/udp/http + logstash + elasitcsearch
效果:
实现对搜索部门服务的日志聚合服务，通过kibana进行数据观测
应用指标
收集方式: 收集处理本地access日志
实现: logtailer + graphite + graphana
效果: 收集数据后在graphana中展现处理
健康检查
检查方式: http port 文件 队列监控
实现:
效果
webshell
指定机器 执行命令 不用登陆机器
服务通信相关
微服务
引入motan
部署相关
autopublish：
效果: 模板+打包+上线
基础设施相关
vintage
graphite
graphana
motan
go
复制切片的方法
dfs
从下至上处理实现
从上至下处理实现
高性能服务建设
核心目标是提升服务整体容量
1.增加机器数
2.解决资源均衡问题
3.提升单机容量
可靠性建设
1.解决资源均衡问题
背景
高负载情况下，有业务方反馈服务不可用，监控排查后发现某些机器cpu资源消耗光，这是由于流量不均导致
上层流量通过DNS分发至服务机房，机房分为多个，假设每个机房流量及机器数相同，那么理论上单机承载流量相同，但是事实上不是这样，这块有两个问题
1.机房机器数是变动的，比如扩容场景、或者常态服务机器增加/减少
2.单机性能存在差异，木桶效应，存在浪费
最初解决思路
最初解决问题的思路比较粗暴，依靠增加机器数保持尽可能多的冗余来解决问题
针对第二点的话，就是服务机器调配问题
退机器，换机器
服务间机器调配
改进
自建7层调度
采用软件实现7层调度，技术栈为openresty，服务设计上与用户状态无关，7层直接采用轮训策略
服务容量整体提升，可降低服务
2.热点应对
3.响应时间
1.提升整体容量
1.7层建设
背景
热点事件时期部门
上层流量通过DNS分发至服务机房，机房分为多个，假设每个机房流量及机器数相同，那么理论上单机承载流量相同，但是事实上不是这样，这块有两个问题
1.机房机器数是变动的，比如扩容场景、或者常态服务机器增加/减少
2.单机性能存在差异，木桶效应，存在浪费
最初解决思路
最初解决问题的思路比较粗暴，依靠增加机器数保持尽可能多的冗余来解决问题
针对第二点的话，就是服务机器调配问题
退机器，换机器
服务间机器调配
改进
自建7层调度
采用软件实现7层调度，技术栈为openresty，服务设计上与用户状态无关，7层直接采用轮训策略
服务容量整体提升，可降低服务
一致性建设
可观测性建设
热搜表态
管理平台
应用服务
资源服务
高性能服务建设
技术选型
开源
基于Nginx
高性能
进程模型
IO模型
可靠性
大量成熟公司使用
同步非阻塞编程
上手难度
开发效率
如何保障保性能
同步非阻塞编程
长连接
redis
多线程
子请求
coroutine
IO复用+事件驱动编程
保障性建设(graphite+logtailer)
监控报警
服务
单独机器
QPS/RT
集群整体
QPS/RT/5XX错误率
机器
CPU使用率
IDLE占比
负载
网络带宽
内存
扩缩容
常态冗余
联动扩缩容
自动扩缩容
header接口
qps大于800 扩容
qps小于500 缩容
降级
冗余度
治理建设
服务注册发现(vintage+dconf)
注册中心
动态配置下发
报警阈值是如何测算出来的？