Java常见面试题总结

JAVA基础

Java的collection接口继承关系

jdk1.7 用的是哪种垃圾回收机制 1.8用的是啥

jdk1.6 用的是 UseParallelGC， ParallelGCThreads=4
jdk1.8

$ java -XX:+PrintCommandLineFlags -version
-XX:InitialHeapSize=134217728 
-XX:MaxHeapSize=2147483648 
-XX:+PrintCommandLineFlags 
-XX:+UseCompressedClassPointers 
-XX:+UseCompressedOops 
-XX:+UseParallelGC
java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)

UseParallelGC 即 Parallel Scavenge + Serial Old, 再查看详细信息

java -XX:+PrintGCDetails -version
java version "1.8.0_181"
Java(TM) SE Runtime Environment (build 1.8.0_181-b13)
Java HotSpot(TM) 64-Bit Server VM (build 25.181-b13, mixed mode)
Heap
 PSYoungGen      total 38400K, used 1331K [0x0000000795580000, 0x0000000798000000, 0x00000007c0000000)
  eden space 33280K, 4% used [0x0000000795580000,0x00000007956cce48,0x0000000797600000)
  from space 5120K, 0% used [0x0000000797b00000,0x0000000797b00000,0x0000000798000000)
  to   space 5120K, 0% used [0x0000000797600000,0x0000000797600000,0x0000000797b00000)
 ParOldGen       total 87552K, used 0K [0x0000000740000000, 0x0000000745580000, 0x0000000795580000)
  object space 87552K, 0% used [0x0000000740000000,0x0000000740000000,0x0000000745580000)
 Metaspace       used 2233K, capacity 4480K, committed 4480K, reserved 1056768K
  class space    used 243K, capacity 384K, committed 384K, reserved 1048576K

List和Array的区别，添加和删除元素的时间复杂度怎样

1) 因为Array是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。

2) 相对于ArrayList，LinkedList插入是更快的。因为LinkedList不像ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是ArrayList最坏的一种情况，时间复杂度是O(n)，而LinkedList中插入或删除的时间复杂度仅为O(1)。ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

3) 类似于插入数据，删除数据时，LinkedList也优于ArrayList。

4) LinkedList需要更多的内存，因为ArrayList的每个索引的位置是实际的数据，而LinkedList中的每个节点中存储的是实际的数据和前后节点的位置。

5） Array和List都属于顺序表。Array、ArrayList是一段连续的存储结构

红黑树添加元素和获取元素的时间复杂度

插入一个元素到红黑树的时间为 O(log(N))*，其中 *N 为当前红黑树的元素个数，因此，采用插入方式构建元素个数为N的红黑树的时间复杂度为:

log(1) + log(2) + log(N-1) = log((N-1)!) = Nlog(N)

那么采用迭代器遍历一棵红黑树的时间复杂度是多少呢？是 O(N) 。也就是说非递归遍历一棵红黑树的时间复杂度和遍历数组的时间复杂度是一样的

原文链接：https://blog.csdn.net/gongyiling3468/article/details/47804223

CMS垃圾收集器

线程池原理，增长策略，拒绝策略哪几种，四种线程池分别有什么优缺点，有什么坑，线程池使用该怎么选择

线程池原理：
复用Thead线程，减少创建和回收的CPU、内存资源消耗，过多任务加入等待队列或拒绝
增长策略：
当前线程数 < 核心线程 : 直接开启新线程执行任务
当前线程数 > 核心线程 : 加入等待队列
队列已满& 当前线程数 < 最大线程 : 开启新线程
队列已满& 当前线程数 > 最大线程 : 执行拒绝策略
拒绝策略
1. CallerRunsPolicy：只要线程池没有被关闭，那么由提交任务的线程自己来执行这个任务
2. AbortPolicy：不管怎样，直接抛出 RejectedExecutionException 异常，这个是默认的策略，如果我们构造线程池的时候不传相应的 handler 的话，那就会指定使用这个
3. DiscardPolicy：不做任何处理，直接忽略掉这个任务
4. DiscardOldestPolicy：这个相对霸道一点，如果线程池没有被关闭的话，把队列队头的任务(也就是等待了最长时间的)直接扔掉，然后提交这个任务到等待队列中
线程池对比
- FixedThreadPool是一个典型且优秀的线程池，它具有线程池提高程序效率和节省创建线程时所耗的开销的优点。但在线程池空闲时，即线程池中没有可运行任务时，它不会释放工作线程，还会占用一定的系统资源。
- CachedThreadPool的特点就是在线程池空闲时，即线程池中没有可运行任务时，它会释放工作线程，从而释放工作线程所占用的资源。但是，但当出现新任务时，又要创建一新的工作线程，又要一定的系统开销。并且，在使用CachedThreadPool时，一定要注意控制任务的数量，否则，由于大量线程同时运行，很有会造成系统瘫痪

锁粗化、锁消除

锁粗化(程序员控制)
通常情况下，为了保证多线程间的有效并发，会要求每个线程持有锁的时间尽可能短，但是大某些情况下，一个程序对同一个锁不间断、高频地请求、同步与释放，会消耗掉一定的系统资源，因为锁的轻求、同步与释放本身会带来性能损耗，这样高频的锁请求就反而不利于系统性能的优化了，虽然单次同步操作的时间可能很短。

锁粗化就是告诉我们任何事情都有个度，有些情况下我们反而希望把很多次锁的请求合并成一个请求，以降低短时间内大量锁请求、同步、释放带来的性能损耗。

一种极端的情况如下：

public void doSomethingMethod(){
    synchronized(lock){
        //do some thing
    }
    //这是还有一些代码，做其它不需要同步的工作，但能很快执行完毕
    synchronized(lock){
        //do other thing
    }
}

上面的代码是有两块需要同步操作的，但在这两块需要同步操作的代码之间，需要做一些其它的工作，而这些工作只会花费很少的时间，那么我们就可以把这些工作代码放入锁内，将两个同步代码块合并成一个，以降低多次锁请求、同步、释放带来的系统性能消耗，合并后的代码如下:

public void doSomethingMethod(){
    //进行锁粗化：整合成一次锁请求、同步、释放
    synchronized(lock){
        //do some thing
        //做其它不需要同步但能很快执行完的工作
        //do other thing
    }
}

注意：这样做是有前提的，就是中间不需要同步的代码能够很快速地完成，如果不需要同步的代码需要花很长时间，就会导致同步块的执行需要花费很长的时间，这样做也就不合理了。

锁消除
锁消除是发生在编译器级别的一种锁优化方式。有时候我们写的代码完全不需要加锁，却执行了加锁操作。虚拟机即时编译器在运行时，对一些代码上要求同步，但是被检测到不可能存在共享数据竞争的锁进行削除。
锁削除的主要判定依据来源于逃逸分析的数据支持，如果判断到一段代码中，在堆上的所有数据都不会逃逸出去被其他线程访问到，那就可以把它们当作栈上数据对待，认为它们是线程私有的，同步加锁自然就无须进行。

锁消除前提是java必须运行在server模式（server模式会比client模式作更多的优化），同时必须开启逃逸分析:

1	-server -XX:+DoEscapeAnalysis -XX:+EliminateLocks

其中+DoEscapeAnalysis表示开启逃逸分析，+EliminateLocks表示锁消除。

异步thrift原理

服务方起草接口标准，负责实现，RPC框架生成服务端和客户端代理，服务端代理自启动，客户端代理绑定调用方，调用方按照接口标准，调用客户端代理，等价于RPC远程调用服务方实现

定义一个Thrift Service

//1. IDL编写的接口
service AddService {
  int add(1:int n1, 2:int n2)
}

Thrift Service方法会提供两种类型的实现：

Iface
AsyncIface

//2. thrift.exe生成接口的客户端代理 - 异步实现
class AddService{
  static class AsyncClient {
    void add(int n1, int n2, AsyncMethodCallback callback) {
      ...
    }
}

//3. 接口的服务端实现
class AddServiceImpl implements AddService.Iface {
	 int add(int n1, int n2) 
	   return n1 + n2;
	 }
}

//4. 服务端监听
TNonblockingServerSocket socket = new TNonblockingServerSocket(9090);
TServer server = new TNonblockingServer(socket, AddServiceImpl);
server.start();

外部的调用过程就是，先获得一个CallBack，然后调用start方法。

//5. 客户端请求
TNonblockingTransport socket = new TNonblockingSocket("localhost", 9090);
AddService.AsyncClient client = new AddService.AsyncClient(socket);
client.add(1,2,new AsynCallback(this){
        void onComplete() {
            ...
        }
        void onError(Exception exception) {
            ...
        }
     }
});

异步使用原则
如果使用了AsynIface实现Service，需要注意几点：

不能直接在方法内处理req，req需要和handler（callback）封装交给另外的线程进行处理（暂且把这些线程叫做worker线程）
worker线程只做计算逻辑，也就是根据req的要求进行操作，在操作req结束以后获得的resp或者error，不能直接调用handler（callback）的方法（因为callback中的方法是一个网络IO的操作，有可能会block当前线程，如果网络IO操作是一个异步操作的话就不会block当前线程）

讲几个jvm优化的案例

堆外内存泄漏怎么排查

异常堆栈
top信息

一定时间过后，java 进程内存增长到接近 90%，服务器报警。此时 old 区内存在 50%左右，由于未达到 CMS GC 的阈值，因此不会触发 CMS GC，而导致服务器内存溢出崩溃。

堆外内存计算方式
- 广义堆外内存为：进程内存 - (Young 区占用 + Old 区占用)，可通过直接内存大小参数: -神器:MaxDirectMemorySize 设置, JVM申请直接内存时，会判断是否超过可申请的直接内存阈值，如果超过则会调用 System.gc() 触发GC，如果 GC 后内存还是不足，则抛出 OutOfMemoryError 异常
- 狭义堆外内存为：java.nio.DirectByteBuffer 创建的时候分配的内存
查看堆内存命令

jstat -gc 1000 : 每秒输出堆内存实际大小信息
jstat -gcutil 1000 : 每秒输出堆内存百分比信息
jvisual VM可视化监控内存实时情况，通过dump文件可以找到对象的引用根节点。
jmeter压测；
为了分析堆外内存到底是谁占用了，不得不安装google-perftools工具进行分析，它的原理是在java应用程序运行时，当调用 malloc 时换用它的libtcmalloc.so，这样就能做一些统计了

原文链接：https://blog.csdn.net/u012099869/article/details/82757999

Tomcat响应web请求的过程

Service -> Connector(Socket) -> Container (HttpServletRequest) -> Engine -> Host -> Context -> WrapServlet

Pipeline-Valve-责任链模式

StandardEnginePipeValve
StandardHostPipeValve
StandardContextPipeValve
StandardWraperPipeValve

CopyOnWriteArrayList、CopyOnWriteArraySet

CopyOnWriteArrayList原理：

在写的时候不对原集合进行修改，而是重新复制一份，修改完之后，再移动指针

CopyOnWriteArrayList add()方法：

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;//重入锁
    lock.lock();//加锁啦
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);//拷贝新数组
        newElements[len] = e;
        setArray(newElements);//将引用指向新数组  1
        return true;
    } finally {
        lock.unlock();//解锁啦
    }
}

add()在添加集合的时候加上了锁，保证了同步，避免了多线程写的时候会Copy出N个副本出来.

有这么一种情况，当一个线程刚好调用完add()方法，也就是刚好执行到上面1处的代码，也就是刚好将引用指向新数组，而此时有线程正在遍历呢？会不会报错呢？
答案是不会的，因为你正在遍历的集合是旧的。

优缺点

缺点：
- 1、耗内存（集合复制）
- 2、实时性不高
优点：
- 1、数据一致性完整，为什么？因为加锁了，并发数据不会乱
- 2、解决了像ArrayList、Vector这种集合多线程遍历迭代问题，记住，Vector虽然线程安全，只不过是加了synchronized关键字，迭代问题完全没有解决！

使用场景

读多写少（白名单，黑名单，商品类目的访问和更新场景），为什么？因为写的时候会复制新集合
集合不大，为什么？因为写的时候会复制新集合
实时性要求不高，为什么，因为有可能会读取到旧的集合数据

项目中使用延迟队列的场景，延迟队列是如何实现的

DelayQueue基本原理
DelayQueue是一个没有边界BlockingQueue实现，加入其中的元素必需实现Delayed接口。当生产者线程调用put之类的方法加入元素时，会触发Delayed接口中的compareTo方法进行排序，也就是说队列中元素的顺序是按到期时间排序的，而非它们进入队列的顺序。排在队列头部的元素是最早到期的，越往后到期时间赿晚。

/** 
 * 消息体定义 实现Delayed接口就是实现两个方法即compareTo 和 getDelay
 * 最重要的就是getDelay方法，这个方法用来判断是否到期
 */  
 @Data
public class Message implements Delayed {  
    private int id;  
    private String body; // 消息内容  
    // 延迟时长，这个是必须的属性因为要按照这个判断延时时长。  
    private long excuteTime;  
  
    public Message(int id, String body, long delayTime) {  
        this.id = id;  
        this.body = body;  
        this.excuteTime = TimeUnit.NANOSECONDS.convert(delayTime, 
            TimeUnit.MILLISECONDS) + System.nanoTime();  
    }  
  
    // 自定义实现比较方法返回 1 0 -1三个参数  
    @Override  
    public int compareTo(Delayed delayed) {  
        Message msg = (Message) delayed;  
        return Integer.valueOf(this.id) > Integer.valueOf(msg.id) ? 1  
                : (Integer.valueOf(this.id) < Integer.valueOf(msg.id) ? -1 : 0);  
    }  
  
    // 延迟任务是否到时就是按照这个方法判断如果返回的是负数则说明到期否则还没到期  
    @Override  
    public long getDelay(TimeUnit unit) {  
        return unit.convert(this.excuteTime - System.nanoTime(), TimeUnit.NANOSECONDS);  
    }  
}

消费者线程查看队列头部的元素，注意是查看不是取出。然后调用元素的getDelay方法，如果此方法返回的值小０或者等于０，则消费者线程会从队列中取出此元素，并进行处理。如果getDelay方法返回的值大于0，则消费者线程wait返回的时间值后，再从队列头部取出元素，此时元素应该已经到期。

DelayQueue是Leader-Followr模式的变种，消费者线程处于等待状态时，总是等待最先到期的元素，而不是长时间的等待。消费者线程尽量把时间花在处理任务上，最小化空等的时间，以提高线程的利用效率。

消费者线程的数量要够，处理任务的速度要快。否则，队列中的到期元素无法被及时取出并处理，造成任务延期、队列元素堆积等情况。

应用场景
- 关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭之。
- 清理过期数据业务上。比如缓存中的对象，超过了空闲时间，需要从缓存中移出。
- 任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求。
- 下单之后如果三十分钟之内没有付款就自动取消订单。
- 订餐通知:下单成功后60s之后给用户发送短信通知。
- 当订单一直处于未支付状态时，如何及时的关闭订单，并退还库存
- 如何定期检查处于退款状态的订单是否已经退款成功
- 新创建店铺，N天内没有上传商品，系统如何知道该信息，并发送激活短信
- 定时任务调度：使用DelayQueue保存当天将会执行的任务和执行时间，一旦从DelayQueue中获取到任务就开始执行。

参考链接：
https://juejin.im/post/5b5e52ecf265da0f716c3203
https://blog.csdn.net/dkfajsldfsdfsd/article/details/88966814

内存溢出的排除、定位，虚拟机参数；

查看堆占用情况：

jmap 查看heap内存使用情况

$ jmap -heap 30124
Attaching to process ID 30124, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 25.152-b16

using thread-local object allocation.
Parallel GC with 4 thread(s)

Heap Configuration:
   MinHeapFreeRatio         = 0
   MaxHeapFreeRatio         = 100
   MaxHeapSize              = 4215275520 (4020.0MB)
   NewSize                  = 88080384 (84.0MB)
   MaxNewSize               = 1405091840 (1340.0MB)
   OldSize                  = 176160768 (168.0MB)
   NewRatio                 = 2
   SurvivorRatio            = 8
   MetaspaceSize            = 21807104 (20.796875MB)
   CompressedClassSpaceSize = 1073741824 (1024.0MB)
   MaxMetaspaceSize         = 17592186044415 MB
   G1HeapRegionSize         = 0 (0.0MB)

Heap Usage:
PS Young Generation
Eden Space:
   capacity = 490733568 (468.0MB)
   used     = 197747880 (188.58707427978516MB)
   free     = 292985688 (279.41292572021484MB)
   40.296383393116486% used
From Space:
   capacity = 12058624 (11.5MB)
   used     = 8982888 (8.566749572753906MB)
   free     = 3075736 (2.9332504272460938MB)
   74.49347454568614% used
To Space:
   capacity = 30932992 (29.5MB)
   used     = 0 (0.0MB)
   free     = 30932992 (29.5MB)
   0.0% used
PS Old Generation
   capacity = 275251200 (262.5MB)
   used     = 53956432 (51.45686340332031MB)
   free     = 221294768 (211.0431365966797MB)
   19.60261462983631% used

可以查看到MetaspaceSize, CompressedClassSpaceSize, MaxMetaSize

jmap和jdk版本有关系，有些jdk版本会查看不到内存信息，可以使用jstat来查看统计信息

jstat 收集统计信息

# 占用大小
$ jstat -gc 30124
 S0C    S1C    S0U    S1U      EC       EU        OC         OU       MC     MU    CCSC   CCSU   YGC     YGCT    FGC    FGCT     GCT   
29696.0 6656.0  0.0   6144.1 462848.0 95727.6   268800.0   52699.8   63320.0 61816.0 7552.0 7224.3     15    0.327   3      0.626    0.953

# 占用比例
$ jstat -gcutil 30124
  S0     S1     E      O      M     CCS    YGC     YGCT    FGC    FGCT     GCT   
  0.00  92.31  28.60  19.61  97.62  95.66     15    0.327     3    0.626    0.953

-Xms 堆初始内存
-Xmx 堆最大内存
-XX:+UseG1GC/CMS 垃圾回收器
-XX:+DisableEx神器icitGC 禁止显示GC
-XX:MaxDirectM神器orySize 设置最大堆外内存，默认是:进程内存 - (Young 区占用 + Old 区占用)
-Xss：每个线程的堆栈大小，默认1M
-Xmn: 年轻代大小（eden区 + 2 * survivor）
-XX:NewRatio=4 年轻代与老年代1:4
-XX:survivorRa神器o=8 Eden区与survivor大小比值

具体步骤：

jps找到进程id
jstat -gc -gcutil确认堆占用情况及是否频繁full gc
jmap -histo:live pid | head 找到最多的几个instance
jmap dump:live,format=b,file=head.hprof pid dump出存活的实例堆栈信息
jvisualvm载入dump文件，从类信息栏找到占用内存最大的类，点击查询实例详情，进一步找到引用对象

ZooKeeper

zk选主的详细过程

在Zookeeper集群中，主要分为三者角色，而每一个节点同时只能扮演一种角色，这三种角色分别是：

Leader
接受所有Follower的提案请求并统一协调发起提案的投票，负责与所有的Follower进行内部的数据交换(同步);
Follower
直接为客户端服务并参与提案的投票，同时与Leader进行数据交换(同步);
Observer
直接为客户端服务但并不参与提案的投票，同时也与Leader进行数据交换(同步); Observer的作用是为了拓展系统，提高读取速度。

Server工作过程中四种状态

LOOKING：竞选状态，当前Server不知道leader是谁，正在搜寻。
LEADING：领导者状态，表明当前服务器角色是leader。
FOLLOWING：随从状态，表明当前服务器角色是follower，同步leader状态，参与投票。
OBSERVING，观察状态，表明当前服务器角色是observer，同步leader状态，不参与投票。

选主机制
Zookeeper的核心是原子广播，这个机制保证了各个Server之间的同步。实现这个机制的协议叫做Zab协议。

Zab协议有两种模式，它们分别是：

恢复模式（选主）
广播模式（同步

当服务启动或者在领导者崩溃后，Zab就进入了恢复模式，当领导者被选举出来，且大多数Server完成了和leader的状态同步以后，恢复模式就结束了。

状态同步保证了leader和Server具有相同的系统状态。
leader选举是保证分布式数据一致性的关键

当zk集群中的一台服务器出现以下两种情况之一时，就会开始leader选举。

（1）服务器初始化启动。
（2）服务器运行期间无法和leader保持连接。

而当一台机器进入leader选举流程时，当前集群也可能处于以下两种状态。

（1）集群中本来就已经存在一个leader。
（2）集群中确实不存在leader。

首先第一种情况，通常是集群中某一台机器启动比较晚，在它启动之前，集群已经正常工作，即已经存在一台leader服务器。当该机器试图去选举leader时，会被告知当前服务器的leader信息，它仅仅需要和leader机器建立连接，并进行状态同步即可。

下面重点看第二种情况，即集群中leader不存在的情况下如何进行leader选举。

数据模型
投票信息中包含两个最基本的信息。

sid: 即server id，用来标识该机器在集群中的机器序号；
zxid: 即zookeeper事务id。ZooKeeper状态的每一次改变, 都对应着一个递增的Transaction id, 该id称为zxid. 由于zxid的递增性质, 如果zxid1小于zxid2, 那么zxid1肯定先于zxid2发生. 创建任意节点, 或者更新任意节点的数据, 或者删除任意节点, 都会导致Zookeeper状态发生改变, 从而导致zxid的值增加.
electionEpoch：逻辑时钟，用来判断多个投票是否在同一轮选举周期中，该值在服务端是一个自增序列，每次进入新一轮的投票后，都会对该值进行加1操作;
state：当前服务器的状态;

以（sid，zxid）的形式来标识一次投票信息。例如，如果当前服务器要推举sid为1，zxid为8的服务器成为leader，那么投票信息可以表示为（1，8）

规则
集群中的每台机器发出自己的投票后，也会接受来自集群中其他机器的投票。每台机器都会根据一定的规则，来处理收到的其他机器的投票，以此来决定是否需要变更自己的投票。
规则如下：

（1）初始阶段，都会给自己投票。
（2）当接收到来自其他服务器的投票时，都需要将别人的投票和自己的投票进行pk，规则如下：
- 优先检查zxid, zxid比较大的服务器优先作为leader;
- 如果zxid相同的话，就比较sid，sid比较大的服务器作为leader;

总结：

首先判断该投票的有效性，如检查是否是本轮投票、是否来自LOOKING状态的服务器。如果发现该外部选票的选举轮次小于当前服务器的，那么忽略该外部投票，同时立即发送自己的内部投票。
第二轮根据第一轮比较结果再次向集群中所有机器发出上一次投票信息即可。
一旦确定了Leader，每个服务器就会更新自己的状态，如果是Follower，那么就变更为FOLLOWING，如果是Leader，就变更为LEADING
在3.4.0后的Zookeeper的版本只保留了TCP版本的FastLeaderElection选举算法
electionEpoch：逻辑时钟，用来判断多个投票是否在同一轮选举周期中，该值在服务端是一个自增序列，每次进入新一轮的投票后，都会对该值进行加1操作。

链接：https://www.jianshu.com/p/75e48405d678

Redis

redispool线程池工作原理，JDK怎么实现

复用socket连接，存储到LinkedBlockingDeque中
imeBetweenEvictionRunsMillis毫秒秒检查一次连接池中空闲的连接,把空闲时间超过minEvictableIdleTimeMillis毫秒的连接断开,直到连接池中的连接数到minIdle为止

redis 事务 MULTI

严格意义来讲,redis的事务和我们理解的传统数据库(如mysql)的事务是不一样的。

Redis中的事务（transaction）是一组命令的集合。

事务的原理是先将属于一个事务的命令发送给Redis，然后再让Redis依次执行这些命令。

如果在发送EXEC命令前客户端断线了，则Redis会清空事务队列，事务中的所有命令都不会执行。而一旦客户端发送了EXEC命令，所有的命令就都会被执行，即使此后客户端断线也没关系，因为Redis中已经记录了所有要执行的命令。

除此之外，Redis的事务还能保证一个事务内的命令依次执行而不被其他命令插入。试想客户端A需要执行几条命令，同时客户端B发送了一条命令，如果不使用事务，则客户端B的命令可能会插入到客户端A的几条命令中执行。如果不希望发生这种情况，也可以使用事务。

和传统的mysql事务不同的事，即使我们的加钱操作失败,我们也无法在这一组命令中让整个状态回滚到操作之前。

语法错误
语法错误指命令不存在或者命令参数的个数不对，比如跟在MULTI命令后执行了3个命令：一个是正确的命令，成功地加入事务队列；其余两个命令都有语法错误。而只要有一个命令有语法错误，执行EXEC命令后Redis就会直接返回错误，连语法正确的命令也不会执行。
运行错误
运行错误指在命令执行时出现的错误，比如使用散列类型的命令操作集合类型的键，这种错误在实际执行之前Redis是无法发现的，所以在事务里这样的命令是会被Redis接受并执行的。如果事务里的一条命令出现了运行错误，事务里其他的命令依然会继续执行，Redis的事务没有关系数据库事务提供的回滚（rollback）功能。为此开发者必须在事务执行出错后自己收拾剩下的摊子。

redis watch机制

WATCH命令可以监控一个或多个键，一旦其中有一个键被修改（或删除），之后的事务就不会执行。监控一直持续到EXEC命令（事务中的命令是在EXEC之后才执行的，所以在MULTI命令后可以修改WATCH监控的键值）

利用watch实现incr
具体做法如下:

WATCH mykey
val = GET mykey
val = val + 1
MULTI
SET mykey $val
EXEC

注意点
由于WATCH命令的作用只是当被监控的键值被修改后阻止之后一个事务的执行，而不能保证其他客户端不修改这一键值，所以在一般的情况下我们需要在EXEC执行失败后重新执行整个函数。

执行EXEC命令后会取消对所有键的监控，如果不想执行事务中的命令也可以使用UNWATCH命令来取消监控。

Redis为什么扩容时会产生超时

skiplist与平衡树、哈希表的比较

skiplist和各种平衡树（如AVL、红黑树等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做单个key的查找，不适宜做范围查找。所谓范围查找，指的是查找那些大小在指定的两个值之间的所有节点。
在做范围查找的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。
从内存占用上来说，skiplist比平衡树更灵活一些。一般来说，平衡树每个节点包含2个指针（分别指向左右子树），而skiplist每个节点包含的指针数目平均为1/(1-p)，具体取决于参数p的大小。如果像Redis里的实现一样，取p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
查找单个key，skiplist和平衡树的时间复杂度都为O(logN)，大体相当；而哈希表在保持较低的哈希值冲突概率的前提下，查找时间复杂度接近O(1)，性能更高一些。所以我们平常使用的各种Map或dictionary结构，大都是基于哈希表实现的。
从算法实现难度上来比较，skiplist比平衡树要简单得多。

链接：https://juejin.im/post/57fa935b0e3dd90057c50fbc

redis跳跃表

各种搜索结构提高效率的方式都是通过空间换时间得到的；
跳表最终形成的结构和搜索树很相似；
跳表通过随机的方式来决定新插入节点来决定索引的层数；
跳表搜索的时间复杂度是 O(logn)，插入/删除也是；

为了满足自身的功能需要， Redis 基于 William Pugh 论文中描述的跳跃表进行了以下修改：

允许重复的 score 值：多个不同的 member 的 score 值可以相同。
进行对比操作时，不仅要检查 score 值，还要检查 member ：当 score 值可以重复时，单靠 score 值无法判断一个元素的身份，所以需要连 member 域都一并检查才行。
每个节点都带有一个高度为 1 层的后退指针，用于从表尾方向向表头方向迭代：当执行 ZREVRANGE 或 ZREVRANGEBYSCORE 这类以逆序处理有序集的命令时，就会用到这个属性。

实例

redis> ZADD s 6 x 10 y 15 z
(integer) 3

redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底层实现中， Redis 为 x 、 y 和 z 三个 member 分别创建了三个字符串，值分别为 double 类型的 6 、 10 和 15 ，然后用跳跃表将这些指针有序地保存起来，形成这样一个跳跃表：

跳跃表是一种随机化数据结构，查找、添加、删除操作都可以在对数期望时间下完成。
跳跃表目前在 Redis 的唯一作用，就是作为有序集类型的底层数据结构之一，另一个构成有序集的结构是字典。
为了满足自身的需求，Redis 基于 William Pugh 论文中描述的跳跃表进行了修改，包括：
- score 值可重复，经典skiplist中是不允许的；
- 对比一个元素需要同时检查它的 score 和 memeber；
- 每个节点带有高度为 1 层的后退指针，双向链表，用于从表尾方向向表头方向迭代；
- 在skiplist中可以很方便地计算出每个元素的排名(rank)；

实际上，Redis中sorted set的实现是这样的：

当数据较少时，sorted set是由一个ziplist来实现的。
当数据多的时候，sorted set是由一个dict + 一个skiplist来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。

网络

tcp确认机制

在TCP确认机制中，无法有效处理非连续TCP片段。确认号表明所有低于该编号的sequence number已经被发送该编号的设备接收。如果我们收到的字节数落在两个非连续的范围内，则无法只通过一个编号来确认。这可能导致潜在严重的性能问题，特别是高速或可靠性较差的网络。

仅重传超时片段
每个片段发送后，发送端都有一个计时器，在一定时间内没有收到包含该片段的ack信息，就认为该片段接收超时。
这是一种更加保守的方式，仅重传超时的片段，希望其他片段都能够成功接收。如果该片段之后的其他片段实际上接收到了，这一方式是最佳的，如果没接收到，就无法正常执行。后者的情况每一个片段需要单独计时并重传。
假设上述最坏情况下，所有20个500字节片段都丢失了。我们需要等片段1超时并重传。这一片段也许会得到确认，但之后我们需要等待片段2超时并重传。这一过程会重复多次。
重传所有片段
这是一种更激进或者说更悲观的方式。无论何时一个片段超时了，不仅重传该片段，还有所有其他尚未确认的片段。这一方式确保了任何时间都有一个等待确认的停顿时间，在所有未确认片段丢失的情况下，会刷新全部未确认片段，以使对端设备多一次接收机会。在所有20个片段都丢失的情况下，相对于第一种方式节省了大量时间。这种方式的问题在于可能这些重传是不必要的。如果第一个片段丢失而其他19个实际上接收到了，也得重传那9500字节数据。

由于TCP不知道其他片段是否接收到，所以它也无法确认哪种方法更好，但只能选择一种方式。解决方式是对TCP滑动窗口算法进行扩展，添加允许设备分别确认非连续片段的功能。这一功能称为选择确认（selective acknowledgment, SACK）。

选择确认：
通过SACK，连接的两方设备必须同时支持这一功能，通过连接时使用的SYN片段来协商是否允许SACK。这一过程完成之后，任一设备都可以在常规TCP片段中使用SACK选项。
这一选项包含一个关于 已接收但未确认片段数据sequence number范围的列表，由于它们是非连续的。

各设备对重传队列进行修改，如果该片段已被选择确认过，则该片段中的SACK比特位置为1。该设备使用图2中激进方式的改进版本，一个片段重传之后，之后所有片段也会重传，除非SACK比特位为1。

例如，在4个片段的情况下，如果客户端接收到片段4而没有接收到片段3，当它发回确认号为201（片段1和片段2）的确认信息，其中包含一个SACK选项指明：“已接收到字节361至500，但尚未确认”。如果片段4在片段1和2之后到达，上述信息也可以通过第二个确认片段来完成。服务器确认片段4的字节范围，并为片段4打开SACK位。当片段3重传时，服务器看到片段4的SACK位为1，就不会对其重传。

在片段3重传之后，片段4的SACK位被清除。这是为了防止客户端出于某种原因改变片段4已接收的想法。客户端应当发送确认号为501或更高的确认信息，正式确认片段3和4接收到。如果这一情况没有发生，服务器必须接收到片段4的另一条选择确认信息才能将它的SACK位打开，否则，在片段3重传时或计时器超时的情况下会对其自动重传。

https://wizardforcel.gitbooks.io/network-basic/9.html

为什么tcp是可靠协议，怎么做到不丢包的？

窗口滑动协议
重传机制

将TCP与UDP这样的简单传输协议区分开来的是它传输数据的质量。TCP对于发送数据进行跟踪，这种数据管理需要协议有以下两大关键功能：

可靠性：保证数据确实到达目的地。如果未到达，能够发现并重传；
数据流控：管理数据的发送速率，以使接收设备不致于过载；

要完成这些任务，整个协议操作是围绕滑动窗口确认机制来进行的。

TCP面向流的滑动窗口确认机制:
每一条消息都有一个识别编号，每一条消息都能够被独立地确认，因此同一时刻可以发送多条信息。设备B定期发送给A一条发送限制参数，制约设备A一次能发送的消息最大数量。设备B可以对该参数进行调整，以控制设备A的数据流。

为了提高速度，TCP并没有按照字节单个发送而是将数据流划分为片段。片段内所有字节都是一起发送和接收的，因此也是一起确认的。确认机制没有采用message ID字段，而是使用的片段内最后一个字节的sequence number。因此一次可以处理不同的字节数，这一数量即为片段内的sequence number。

发送窗口
整个过程关键的操作在于接收方允许发送方一次能容纳的未确认的字节数，有时也称为窗口。该窗口决定了发送方允许传送的字节数。
可用窗口
考虑到正在传输的数据量，发送方仍被允许发送的数据量。

https://wizardforcel.gitbooks.io/network-basic/7.html

七层负载均衡和四层负载均衡的区别

二层负载均衡会通过一个虚拟 MAC 地址接收请求，然后再分配到真实的 MAC 地址；
三层负载均衡会通过一个虚拟 IP 地址接收请求，然后再分配到真实的 IP 地址；
四层通过虚拟 IP + 端口接收请求，然后再分配到真实的服务器；
七层通过虚拟的 URL 或主机名接收请求，然后再分配到真实的服务器。

所谓的四到七层负载均衡，就是在对后台的服务器进行负载均衡时，依据四层的信息或七层的信息来决定怎么样转发流量。

对于一般的应用来说，有了Nginx就够了。Nginx可以用于七层负载均衡。但是对于一些大的网站，一般会采用DNS+四层负载+七层负载的方式进行多层次负载均衡。

对比：
负载均衡器通常称为四层交换机或七层交换机。

四层交换机主要分析 IP 层及 TCP/UDP 层，实现四层流量负载均衡。
七层交换机除了支持四层负载均衡以外，还有分析应用层的信息，如 HTTP 协议 URI 或 Cookie 信息。
负载均衡分为 L4 Switch（四层交换），即在 OSI第4层工作，就是 TCP层。
此种 Load Balancer 不理解应用协议（如 HTTP/FTP/MySQL 等等）。例子：LVS，F5。
L7 Switch（七层交换），OSI 的最高层，应用层。
此时，该 Load Balancer 能理解应用协议。例子： HAProxy，MySQL Proxy。

注意：上面的很多 Load Balancer 既可以做四层交换，也可以做七层交换。

常用负载均衡工具

Nginx/LVS/HAProxy是目前使用最广泛的三种负载均衡软件。

LVS
LVS（Linux Virtual Server），也就是Linux虚拟服务器, 是一个由章文嵩博士发起的自由软件项目。使用LVS技术要达到的目标是：通过LVS提供的负载均衡技术和Linux操作系统实现一个高性能、高可用的服务器群集，它具有良好可靠性、可扩展性和可操作性。从而以低廉的成本实现最优的服务性能。

LVS主要用来做四层负载均衡。
Nginx
Nginx（发音同engine x）是一个网页服务器，它能反向代理HTTP, HTTPS, SMTP, POP3, IMAP的协议链接，以及一个负载均衡器和一个HTTP缓存。

Nginx主要用来做七层负载均衡。
HAProxy
HAProxy是一个使用C语言编写的自由及开放源代码软件，其提供高可用性、负载均衡，以及基于TCP和HTTP的应用程序代理。

Haproxy主要用来做七层负载均衡。

负载均衡算法可以分为两类：静态负载均衡算法和动态负载均衡算法。

静态负载均衡算法包括：轮询，比率，优先权

动态负载均衡算法包括: 最少连接数, 最快响应速度，观察方法，预测法，动态性能分配，动态服务器补充，服务质量，服务类型，规则模式。

https://cloud.tencent.com/developer/article/1082047

微信网页扫码登陆的通信过程是什么样的；

OAuth2协议

 +----------+
 | Resource |
 |   Owner  |
 |          |
 +----------+
      ^
      |
     (B)
 +----|-----+          Client Identifier      +---------------+
 |         -+----(A)-- & Redirection URI ---->|               |
 |  User-   |                                 | Authorization |
 |  Agent  -+----(B)-- User authenticates --->|     Server    |
 |          |                                 |               |
 |         -+----(C)-- Authorization Code ---<|               |
 +-|----|---+                                 +---------------+
   |    |                                         ^      v
  (A)  (C)                                        |      |
   |    |                                         |      |
   ^    v                                         |      |
 +---------+                                      |      |
 |         |>---(D)-- Authorization Code ---------'      |
 |  Client |          & Redirection URI                  |
 | (Web后端)|                                             |
 |         |<---(E)----- Access Token -------------------'
 +---------+       (w/ Optional Refresh Token)

Note: The lines illustrating steps (A), (B), and (C) are broken into two parts as they pass through the user-agent.

算法

求一个int数二进制形式中1出现的个数

位运算
(1) count = n & 1; n>>1; 循环32次
(2) n & (n-1), 每次可把最低位1变成 0；

一个二叉树某一个路径和等于某值

回溯算法

字符串倒转的时间复杂度和空间复杂度

双指针法一次遍历，使用 O(1) 的额外空间

public void reverseString(char[] s) {
    char temp;
    for(int i = 0, j = s.length - 1; i <= j; i++, j--){
        temp = s[j];
        s[j] = s[i];
        s[i] = temp;
    }
}

时间复杂度：O(N)*，执行了 *N/2 次的交换。
空间复杂度：O(1)，只使用了常数级空间

两个链表分别表示两个数，求和

双队列法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<ListNode>();
        Stack<ListNode> stack2 = new Stack<ListNode>();
        while(l1 != null){
            stack1.add(l1);
            l1 = l1.next;
        }
        while(l2 != null){
            stack2.add(l2);
            l2 = l2.next;
        }

        ListNode h0 = new ListNode(0);
        ListNode cur1 , cur2;
        int re = 0;
        while(!stack1.isEmpty() || !stack2.isEmpty()){
            cur1 = null;
            cur2 = null;
            if(!stack1.isEmpty()){
                cur1 = stack1.pop();
            }
            if(!stack2.isEmpty()){
                cur2 = stack2.pop();
            }
            
            if(cur1 == null){
                cur1 = cur2;
            } else if(cur2 != null){
                cur1.val += cur2.val; 
            }
            cur1.val += re;

            int temp = cur1.val;
            cur1.val = temp % 10;
            re = temp / 10;
            cur1.next = h0.next;
            h0.next = cur1;
        }

        if(re != 0){
            ListNode node = new ListNode(re);
            node.next = h0.next;
            h0.next = node;
        }
        return h0.next;
    }
}

递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    int flow=0;
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode res1=l1,res2=l2;
        int len1=0,len2=0;
        while(l1!=null){
            len1++;
            l1=l1.next;
        }
        while(l2!=null){
            len2++;
            l2=l2.next;
        }

        ListNode res=len1>len2?add(res1,res2,len1,len2):add(res2,res1,len2,len1);
        if(flow==1) {
            res1=new ListNode(1);
            res1.next=res;
            return res1;
        }
        return res;
    }
    public ListNode add(ListNode l1, ListNode l2,int len1,int len2) {
        int temp;
        if((len1==1)&&(len2==1)){
            temp=l1.val;
            l1.val=(l1.val+l2.val)%10;
            flow=(temp+l2.val)/10;
        } else if(len1>len2) {
            temp=l1.val;
            l1.next=add(l1.next, l2, len1-1, len2);
            l1.val=(temp+flow)%10;
            flow=(temp+flow)/10;
        } else {
            l1.next=add(l1.next, l2.next, len1-1, len2-1);
            temp=l1.val;
            l1.val=(temp+flow+l2.val)%10;
            flow=(temp+flow+l2.val)/10;
        }
        return l1;

    }
}

两个list分别表示两个数，求和

paxo算法是啥，zab算法

怎么对ip进行限流，比如某个ip 1小时最多访问1万次，写出代码；

从A、B两个数组中各取一个数，求两数差值最小

N个数组中取两个数差值最小， N个数组中取两个数差值最小

电梯算法

每层有一个value表示可上或可下value层，求A层到B层的最短按键数

实现一个栈，有push pop 获取最小值三个方法要求快！

直播间在线人数统计

有一个日志文件，一个人进入直播间会有一个uid和进入时间，退出直播间会有一个uid和退出时间，一次直播的过程中同一时刻最多的在线人数怎么求？

一次遍历，第一次出现 +1，第二次出现 -1；

接上一题，如果日志文件不是按照时间排序的，那在o(n)时间内求同一时刻最多的在线人数