Windard +
Github Zhihu RSS

后端面试总结

2019-11-24

常见面试题

  1. Java集合主要是hashmap实现原理
  2. 多线程问AQS源码、并发工具类源码、锁的实现原理、阻塞队列源码、线程池实现原理、
  3. jvm问内存结构和垃圾回收机制加jvm优化参数配置
  4. Spring问ioc和aop原理，bean的生命周期
  5. redis问数据类型、线程模型、持久化机制、主从复制原理、高可用原理、redis cluster，分布式锁、消息中间件、hash一致性算法
  6. mq问可靠性、幂等性、可用性、持久化机制、以及优缺点和使用场景
  7. zk问使用场景和分布式锁实现
  8. dubbo问底层通信原理，负载均衡方式和集群容错方式和代理方式和spi机制
  9. 如何保证分布式幂等性、redis和mysql数据一致性、防止redis并发写，缓存雪崩和缓存穿透、限流、降级、熔断。
  10. 一大堆算法题。

算法常问

线程模型

线程有系统线程和用户线程

系统线程也称 内核线程(Kernel-Level Thread)，是系统内核支持的线程，由内核完成线程切换，有调度器进行线程切换，将线程任务映射到处理器上。 优点：有系统调用，更加方便，不用关心。 缺点：由系统调度，需要在内核态和用户态之间切换，耗费资源。

用户线程(User Thread) 由应用自己创建，同步，销毁，调度的线程，完全在用户态中，不需要系统帮助。 优点：用户调用，资源消耗少，可以大批量生成调度 缺点：管理复杂，处理困难。

Java 的线程模型是 轻量级进程 ，与系统线程是 1:1 映射。

使用系统线程也不是直接使用，而是使用系统线程接口，轻量级进程来实现的(Light Weight Process),这种模型有内核线程是 1:1 用户线程可以直接完全由自己控制，与内核线程 1:N 的映射，但是非常的复杂 或者用户线程对接轻量级进程，自己控制线程创建，系统线程控制调度，实现 M:N 的关系。

线程

线程切换由系统控制，在单个 CPU 上给每个线程一定的时间片长度操作，在时间片用完后仍未结束的线程，将会被保存线程空间，切换为下一个线程。

在其他语言中的时间片长度为毫秒级，在 python 中的时间片长度为 100行字节码，但是如果遇到 io 阻塞，也会进行线程切换，等待 io。

在多线程中，CPU 密集型的线程数应该小于 io 密集型的线程数。CPU 密集型的应该使用多进程来挖掘计算机性能。

线程数选择

并发和并行

并发是指你有并发执行的能力，可以同时接受多个任务，但并不一定真的同时进行.

并行需要同时执行多个任务。

CPU调度策略

在 CPU 并发时，同时有多件任务等待执行，需要在多任务间进行切换，多任务调度策略

真实的 CPU 调度是 优先级调度，划分多个队列，同一队列中优先级相同，在队列中采用先到先执行策略。

同步异步阻塞和非阻塞

同步就是等待事件完成，不管事件是有数据返回，还是没有数据返回，比如 udp 就是异步的，他不用等待事件返回，就可以做其他的的事情。

使用异步的话，也不用等待事件返回，可以使用注册回调函数，来等时间有返回之后进行操作。这是对于调用方而言的。

阻塞的含义是对于接收而言的，对于 io 而言，如果一直等待缓存区存满才有数据返回，这是阻塞的。如果缓存区没满就返回一个没有，这是非阻塞的，但是非阻塞的也不行，还是需要数据的。

用多路复用，就是去轮询非阻塞的多个 socket，那个 socket 有返回就使用谁，这是同步的多路复用。

Linux 的五种 io 模型

同步的概念是io操作还是同步的，需要客户端同步的进行数据拷贝，如果可以说一句开始，然后就不管，数据就自己去拷贝到结束为止再通知客户端，就是异步的。就算是信号量通知，也还是需要同步的进行操作。

同步的概念是事件的处理，如果事件可以自己处理，完全不用关心的话，就是异步事件。哪些事件是怎么开始的，是通知还是回调，还是多路复用都是非阻塞的，但还是同步的。

Linux的五种IO模型

BIO&NIO&AIO

对于socket缓存区来说，如果需要等待，就是阻塞的，NIO 不需要等待，所以是非阻塞的，但是还是需要不停的去校验。io 复用只不过是把这个过程交给了另一个线程专门去处理等待，然后通知哪个准备就绪了。

异步不但不需要等待，连读取都是异步的，只需要注册回调函数，指示读完之后的行为就可以了。

BIO 就是最基础的 同步模型，使用多线程，或者线程是来进行优化。 NIO 是使用 多路复用，在 Linux 上 2.6 之前使用 select, poll 进行事件循环，在 2.6 之后使用 epoll 。 NIO 对于事件监听时 非阻塞的，但是对于选择器来说是 阻塞的。选择器的函数是阻塞的，选择器有结果的时候，肯定是一个准备就绪的结果，而不会返回一个空值。 所以对于 NIO 使用单线程轮询就绪的事件，执行事件处理器即可。io 多路复用，只是有人替你负重前行。节约线程，节省资源，没有线程切换，可以处理海量连接。 NIO 的关键在于 事件分发器，也就是选择器。事件选择器可以使用 Reactor ，在选择器的部分还是阻塞的，使用 客户线程去处理读写时间，Proactor 则进行时间回调，可以先注册读写事件，当选择器有准备就绪的 文件描述符的时候，就可以调用客户线程进行处理。

NIO 的具体实现有 netty，是一个事件驱动模型，避免多线程，单线程处理多任务，非阻塞io，多路复用io。

同步和异步，阻塞和非阻塞是在不同的两个阶段的术语 对于一次 io 操作，将数据从磁盘拷贝到内存，第一次阶段是磁盘io准备好，分为阻塞和非阻塞，第二个阶段是拷贝，从磁盘拷贝到内存，分为同步和异步。 对于一次 socket 操作，将数据从远端接收到内存，第一次是等待网络 io 有返回，分为阻塞和非阻塞，第二个阶段是拷贝，从 socket 读取到内存，分为同步和异步。

其实以上两个操作都是文件操作，在 Unix 中一切皆文件。

文件拷贝是从磁盘到内存，但是文件负责，从磁盘到内存再到磁盘，可以使用 zero-copy 技术。零拷贝技术。

抽象

抽象 的两种形式，接口或者抽象类。

  1. 接口更加抽象，抽象类有部分实现
  2. 接口可以多重实现，抽象类只能单重继承

python 中没有接口，只有类和继承，如何实现抽象。

抽象的目的

  1. 禁止直接实例化，必须实现子类
  2. 部分方法必须重写，不能直接继承

可以使用 abc 的库里 ABCMeta 元类 来实现。

  1. 至于子类检查，可以使用 isinstance 或者 issubclass 直接检查即可
  2. 至于方法实现，根据鸭子模型，只要实现功能接口，python 的反射非常简单，双重校验 hasattr 和 callable 检查即可。

在 Java 中接口多重继承，或者抽象类单独继承，在重名方法都没有问题，那 python 里多重继承同名方法怎么办?

python 中的父类查找顺序叫 MRO 算法，可以通过 E.mro 来查看父类继承顺序。简单来说，对于正常继承使用 DFS ，对于菱形继承使用 BFS 。

负数的表示

对于无符号数，一个字节可以表示 0~255 的整数 对于有符号数，一个字节可以表示 -128~127 的整数

负数的表示是二进制首位用负数表示

  1. 负数的首位肯定是1，正数的首位肯定不是1
  2. 负数的首位的1表示的是 -(2**(n-1)) ,比如八位的情况下，就是 -2**(8-1) = -128
  3. 负数的其他位数还是正数的，负数的最小值，就是首位1，其他都是0，即 -(2**(n-1)) ，负数的最大值，就是全1，即为 -1
  4. 正数的首位都是0，正数的最小值即为全0，就是正0，正数的最大值，就是首位0，其他全是1，就是 2**(n-1)-1
  5. 所以对于有符号数，负数的范围要比正数的范围大1，但是负数没有0，正数有0，所以可以表示的数字个数是相同的
  6. 只有正0，没有负0
  7. 正数到负数的转换，是先取反，再加1, -n = ~n + 1
0b00001000 = 8
0b10001000 = -128+8 = -120
0b10000000 = -128
0b11111111 = -128 + 127 = -1
0b01111111 = 127
0b10000001 = -128 + 1 = -127

位运算

python 中支持位运算(Bitwise Operation) , 主要有六种操作

按位取反值的再讲一讲，比如 1 的按位取反。

0b00000001 = 1
0b11111110 = ~1 = -2**(8-1) + 126 = -2

按位取反

，按位取反

逻辑运算

位运算和逻辑运算是不一样的。逻辑运算只有三种

正常的逻辑运算符返回的都是布尔值，但是 Python 的运算法返回的是运算结果，而且是短路运算结果。

>>> 0 or False or 3
3
>>> 0 or 1 or 2
1
>>> 1 and 2 and 3
3

Python 运算符
一篇读懂Python中的位运算

尾递归优化

众所周知，递归比循环更消耗内存，每次进入一个新的递归调用，需要先将当前环境的上下文变量放入栈帧中(Stack Frame)，如果递归过多，会造成内存溢出(Out Of Memory)。

但是当一个递归调用在函数尾部的时候，因为进入递归之后已经完全不需要当前函数的上下文，实际上并不需要保存当前环境，可以减少内存占用，某些编程语言可以在此处内存存储优化，但是 python 不会。

一个常见的例子，斐波那契数列的尾递归优化写法和非优化写法。

# coding=utf-8

def fib(n):
    """
    无法尾递归优化
    :param n:
    :return:
    """
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)


def fib_optimize(n, a, b):
    """
    可以尾递归优化
    :param n:
    :param a:
    :param b:
    :return:
    """
    if n < 2:
        return a
    return fib_optimize(n-1, b, a+b)

但是非常可惜的是，python 官方并不支持尾递归优化，不过重点是在不用将数据放入堆栈，其实就是类似于循环调用，可以自己实现尾递归优化。

注意，以下装饰器只能用于尾递归函数调用，如果是正常递归会有问题。最多只会生成三个栈帧。

#!/usr/bin/env python2.4
# This program shows off a python decorator(
# which implements tail call optimization. It
# does this by throwing an exception if it is
# it's own grandparent, and catching such
# exceptions to recall the stack.
 
import sys


class TailRecurseException:
    def __init__(self, args, kwargs):
        self.args = args
        self.kwargs = kwargs
 

def tail_call_optimized(g):
    """
    This function decorates a function with tail call
    optimization. It does this by throwing an exception
    if it is it's own grandparent, and catching such
    exceptions to fake the tail call optimization.
 
    This function fails if the decorated
    function recurses in a non-tail context.
    """
    def func(*args, **kwargs):
        f = sys._getframe()
        # 为什么是grandparent, 函数默认的第一层递归是父调用,
        # 对于尾递归, 不希望产生新的函数调用(即:祖父调用),
        # 所以这里抛出异常, 拿到参数, 退出被修饰函数的递归调用栈!(后面有动图分析)
        if f.f_back and f.f_back.f_back \
            and f.f_back.f_back.f_code == f.f_code:
            # 抛出异常
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException, e:
                    # 捕获异常, 拿到参数, 退出被修饰函数的递归调用栈
                    args = e.args
                    kwargs = e.kwargs
    func.__doc__ = g.__doc__
    return func


@tail_call_optimized
def fib_optimize(n, a, b):
    """
    可以尾递归优化
    :param n:
    :param a:
    :param b:
    :return:
    """
    if n < 2:
        return a
    return fib_optimize(n-1, b, a+b)

开启尾递归优化之后的代码，再也不怕 python 的超出最大递归层次的限制了。

在其他语言都没有这种限制，只有根据内存分配的栈大小，超出栈内存的异常，stack overflow 。

比如说在 Java 里，可以根据 JVM 参数来设置分配给栈的内存大小。

线程安全

ConcurrentHashMap 并发安全的 HashMap 是线程不安全的

StringBuffer 是 线程安全的 StringBuilder 是 线程不安全的

想要线程安全，只需要加一个 synchronized 即可。

HashMap

HashMap 与 HashTable 的区别，主要有两点

  1. HashMap 不是线程安全的，而 HashTable 是线程安全的，但是其线程安全主要是通过 synchronized 实现的，所以现在就算是在并发的场景下也很少用到 HashTable
  2. HashMap null 可以为键，也可以为值，甚至可以为多个值，但是 HashTable 中都不可以。

ConcurrentHashMap 的线程安全实现不是通过 synchronized 关键字实现的。

简而言之，是通过将哈希表分段，通过分段锁来实现的。默认是将其分成16个桶，并发性能提高16倍，而且只有在写的时候才会锁，读取的时候并不会锁。

Java 1.7 的版本是通过 Segment 分段锁实现，而 Java 1.8 是采用了 CAS + synchronized 来保证并发安全性。

List

List 接口有三个实现，ArrayList, LinkedList, Vector .

ArrayList 与 LinkedList 的区别在于一个是数组实现的，一个是链表实现的。

Vector 也是数组实现的，但是其 add 方法和 remove 方法都被 synchronized 包裹，是线程安全的。

java 性能调优

原则

参数

synchronized

synchronized 的三种用法

实际上是使用 monitorenter 和 monitorexit 来监控对象头部信息来实现锁。

synchronized 实现

synchronized 是 Java 底层实现的关键字，在不同情况下有不同的具体实现。

设计模式

面向切面编程

AOP 在面向切面编程中，将代码分为核心功能区和辅助功能区，辅助功能区包括权限校验，性能分析，日志处理，异常捕获等，辅助功能可以被剥离出来，通过切面包装在核心功能之外，而且辅助功能可以被复用。

简单工厂模式

简单工厂模型，又称静态工厂模式，通过一个一个静态方法，返回同一个类的不同子类实现，通常通过 if else 来判断。

控制反转

控制反转(Inversion of Control, IOC),也被称为 依赖倒置，根据面向对象编程五大法则中的依赖倒置原则，在编程中不应该依赖于接口的实现，而应该依赖于接口，由 spring 容器管理接口的实现类，并在我们调用接口都时候，soring 从容器中到接口的实现类，自动将接口调用换成对类的调用。实现真正的解耦，达到面向接口编程。

观察者模式

当对象间存在一对多关系时，当某个对象的变更需要通知到所有它的依赖对象。

即当一个目标对象(被观察者，目标对象)状态发生改变时，所有的依赖对象，(观察者对象) 都将会收到通知。

zookeeper 是一个典型的观察者模式实现。

ZooKeeper

zookeeper 是一个分布式配置中心，用于配置分发，服务注册，服务发现等场景。它是一个基于观察者模式设计的分布式服务管理框架，它负责存储和管理大家都关心的数据，然后接收观察者的注册，一旦这些数据的状态发生变化，zookeeper 就负责通知已经注册的观察者们。

存储结构

zookeeper 是按照树结构进行存储的，每一个节点被称为 znode。

znode 的结构

znode 的状态

选举流程

半数以上通过才能选举称为 master 节点，如果同时有多个候选人，则等待一段时间后再次发起投票，每个候选的等待时间都不一样，随机时间。

分布式锁

因为 CAP 原则，数据是弱一致性的。如果需要最新数据，需要进行同步获得数据。

慢查询优化

  1. 不要做类型转换，varchar 和 integer 类型，MySQL 会自动转换，但是索引会失效。
  2. 不要在 where 语句中 函数操作，这样会导致放弃使用索引而采用全表扫描，比如存储 datetime，不要转换为 timestamp 对比。
  3. 在 InnoDB 存储引擎下，bigint 的效率高于 datetime 和 varchar

explain 参数说明

mysql> explain select * from railway where name='K86';
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-------+
| id | select_type | table   | partitions | type | possible_keys   | key             | key_len | ref   | rows | filtered | Extra |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-------+
|  1 | SIMPLE      | railway | NULL       | ref  | ix_railway_name | ix_railway_name | 194     | const |    1 |   100.00 | NULL  |
+----+-------------+---------+------------+------+-----------------+-----------------+---------+-------+------+----------+-------+

type 是访问类型，是一个较为重要的指标，结果从好到坏依次是

system > const > eqref > ref > fulltext > refornull > indexmerge > uniquesubquery > indexsubquery > range > index > ALL ，一般来说，得保证查询至少达到range级别，最好能达到ref。

输入 URL 回车后做了什么

-1. 浏览器的智能联想与推荐，这是在回车前，可以不论。

  1. 浏览器解析协议类型，准备发起请求，据我所知的协议类型就有 ftp，http，https，ws，wss等
  2. DNS 将请求域名转换为 IP 地址，浏览器会首先通过 arp 协议找到局域网内路由器网关所在IP，然后通过网关向外发送 DNS 请求，网关会通过端口映射等方式将请求再次封装向外请求。
  3. DNS拿到目标IP之后与目标IP通过三次握手建立tcp链接。
    1. client -> target: syn=1,seq=x,进入 SYN_SENT 状态
    2. target -> client: ack=x+1, syn=1,seq=y, 进入 SYN_RCVD 状态
    3. client -> target: ack=y+1, seq=x+1
  4. 建立 tcp 链接后，发送 http 请求。目标返回 http 响应。
    1. 可能会返回 302 跳转到 https 地址，则还需要对 https 做证书验签校验。浏览器和系统自带 ca 根证书，对目标地址返回的证书进行证书链循环校验。
    2. 可能升级 http 协议至 ws 协议或者 http 2.0 协议。
  5. 浏览器解析返回数据，首先根据 http response headers 里的 Content-Type 判断返回类型是 HTML 还是 json 数据，如果是 HTML 则使用使用浏览器引擎渲染页面，比如 Chrome 使用的 Blink，Safari 用的 webkit。
  6. 在 HTML 页面里如果还需要其他资源数据，比如 css，js，image，video 等，如果之前的HTTP请求头里有 keep-alive，则使用同一个 tcp 连接，否则的话会新建一个 tcp 连接，再次开始时发起请求。

二分查找

  1. 注意细节
  2. 防止溢出
  3. 左查找和右查找
  4. start <= end

索引的最佳实践

  1. 整形索引的性能强于字符串，比如 timestamp 强于 datetime
  2. 筛选粒度小的列，不用索引，比如性别
  3. 组合索引注意最左匹配原则

数据库规范

  1. 禁止使用游标
  2. 禁止使用函数
  3. 禁止使用外键
  4. 行数大于2kw，大小超过50g，必须归档或者分表
  5. 单SQL不能超过20w行，不能超过5m，否则必须使用分页

线程与进程的区别

  1. 线程共享内存和系统资源，进程内存不共享
  2. 线程管理控制由用户实现，进程由系统管理控制
  3. 线程不能独立存在，它必须是进程的一部分
  4. 线程是比进程更小执行单位，各进程是相互独立的，而线程则不一定。
  5. 进程是资源分配的最小单位，线程是任务执行的最小单位，可以与其他线程同享同一个进程。

创建线程的两种方式

  1. 实现 Runnable 接口
  2. 继承 Thread 类

一个是接口，一个是类，一般来说接口比类要好一些。

  1. 接口更灵活，减少耦合性
  2. 面向接口编程也是设计模式的六大原则之一
  3. 可以同时实现多个接口，但是不能多重继承

抽象类可以写具体实现，接口也能使用 default 来写方法实现，不一定全是接口定义。

快速排序

# coding=utf-8


def quick_sort(nums):s
    if len(nums) < 2:
        return nums
    index = nums[0]
    left = []
    right = []
    for n in nums[1:]:
        if n < index:
            left.append(n)
        else:
            right.append(n)

    return quick_sort(left) + [index] + quick_sort(right)


if __name__ == '__main__':
    print quick_sort([4,6,67,12,7,12,6,9,1245,52])
    print quick_sort([1,2,5,7,8,678,23,67,1,677,24,7,23])

线程

线程的生命周期

thread

select/poll/epoll

三者都用于 多路io复用，且都是同步非阻塞的。

select 跨平台，Linux 2.6 之前是 poll ，之后是 epoll。

select

select 跨平台，能够监视多个文件描述符，但是有数量限制，在Linux上最多1024个，虽然也可以改。

select 存储维护大量文件描述符，每次进行一个文件扫描操作，返回准备就绪的描述符。

缺点

  1. 每次调用需要将文件描述符从用户态复制到内核态，开销太大
  2. 每次循环会遍历所有的文件描述符，时间随数量线性增长
  3. 有最大扫描数量限制

优点

  1. 跨平台
  2. 超时时间微秒，poll 的超时时间是毫秒

poll

poll 没有最大文件数量的限制。

但是同样的维护大量的文件描述符，在内核态和用户态之间切换。

每次进行一个文件扫描，随着文件描述符的数量增加而时间消耗也线性增长。

select 和 poll 都是水平触发，即某个文件准备就绪后告知用户，如果用户未处理，下次仍会继续统计该文件通知用户。

缺点

  1. 每次从用户态到内核态的拷贝
  2. 每次的轮询遍历
  3. 水平触发

优点

  1. 使用链表来存储文件描述符，没有最大文件限制

epoll

Linux 2.6 之后最高的多路 io 复用方案。

边缘触发，如果某个文件描述符准备就绪后，用户未处理，则下一次就不会通知。

同时支持水平触发和边缘触发。

epoll 不返回准备就绪的文件描述符，而是返回文件描述符的数量，需要用户去内核态寻找文件描述符的位置，省去了文件描述符在内核态和用户态复制的开销。

还有 epoll 也不对所监视的文件描述符进行线性扫描，而是通过注册该文件描述符，通过系统级 callback 回调通知。

优点

  1. 没有最大文件描述符限制
  2. 没有内存拷贝，使用mmap内存映射，返回文件描述符地址
  3. 没有循环遍历，使用系统级 io callback，类似于异步

Linux下I/O多路复用系统调用(select, poll, epoll)介绍

设计模式的六大原则

面向对象的三大特征

面向对象的五大原则

面向对象(OOP) 的五大原则 (SOLID)

单例模式

单例模式的两种实现

Java设计模式（十） 你真的用对单例模式了吗？

如何保证代码质量

首先从三个层面来说， 1. 代码规范，python 的话符合 pep8 的规定，Java 符合阿里的编程规约，使用编程规范扫描工具或插件，勤写注释，保证代码可读性。 2. 单元测试和功能测试，自己在代码里写测试用例，测试驱动开发，保证通过测试样例 3. 测试人员接入，测试接口功能和展示样式 然后在上线前根据预估QPS进行压测，挖掘接口瓶颈，在上线时注意监控指标和业务埋点。在上线一段时间后关注数据报表和业务大盘。

SOA 流程

可回滚，可降级，可灰度

tcp 与 udp 的区别

  1. tcp 是保持一个长连接，udp 则没有建立连接
  2. tcp 保证数据到达，保证可靠性的，udp 不保证数据不会丢失
  3. tcp 数据是有序的，有序号保证，可以重传，udp 数据是无序的
  4. tcp 是面向连接的，udp 是面向数据的，即 udp 的传输数据是有大小的，tcp 则理论无限制

传输控制协议

用户数据报协议

TCP

TCP 协议是在 IP 协议之上的，在 TCP/IP 协议族中属于传输层。

TCP 协议是 面向连接的，提供可靠传输的，全双工通信，面向字节流的传输层协议。

tcp_ip_protocol_family

ip 协议和 tcp 协议头，固定大小都是20字节，在传输过程中被层层打包。

ip 头20字节，tcp 头20字节，所以一个 tcp 请求最少需要40字节。

具体看下 TCP 协议的头

tcp_protocol_header

可以看到其实有一个 seq 序号， ack 确认号，还有一个 ACK 确认标志和一堆其他的标志位。所以 20 字节的TCP 协议头，包括2字节的源端口，2字节的目标端口，4字节的序号，4字节的确认号，2字节的标志位，2字节的窗口大小，2字节的校验和，2字节的紧急指针。

序列号 seq 是自己和上一次的请求序列号相比加一。确认号 ack 是和对方请求过来的序列号加一。

TCP 三次握手

TCP 建立连接需要三次握手

three_open_handshake_in_tcp

  1. client -> target: syn=1, seq=x,进入 SYN_SENT 状态
  2. target -> client: ack=x+1, syn=1, seq=y, 进入 SYN_RCVD 状态
  3. client -> target: ack=y+1, seq=x+1

SYN_SENT 和 SYN_RCVD 都是半打开状态，其中 SYN_SENT 是主动打开的，因为是客户端主动想要建立连接，SYN_RCVD 是被动打开的，因为需要接受连接。

SYN Flood 泛洪攻击，即大量的攻击者假装建立 TCP 连接，发送 SYN 请求之后，服务器端返回 ACK ，然后就会将连接放入 syn 连接池中，等待下一步 ack ，但是攻击者不再继续发送下一步请求。

服务器端最多会为此次连接握手等待 63秒，所以当大量的无效连接占满 syn 连接池时，正常请求就无法访问。

处理

  1. 缩短 SYN 等待时间
  2. 增加 syn 连接池大小
  3. syn cookie 技术

TCP 四次握手

TCP 断开连接需要四次握手

four_close_handshake_tcp

  1. client -> server: fin client 进入 Fin Wait 1
  2. server -> client: ack server 进入 Close Wait，client 进入 Fin Wait 2
  3. server -> client: fin server 进入 Last Ack
  4. client -> server: ack client 进入 Time Wait，等待两个2msl，server 进入 close

tcp 断开连接的四次握手不是你来我往的依次轮回，而是服务器端和客户端都需要确认，两次分别确认。

所以服务器端的第二步和第三步不能合并，需要发一个 ACK，表示确认可以断开连接，当服务器端准备好之后再发送 SYN ，表示准备断开连接。

也有人说可以二三步合并。。。四次挥手合并为三次。

所以客户端和服务器端可以同时开启发起 SYN ，同时结束连接。

从 TCP 三次握手说起 – 浅析 TCP 协议中的疑难杂症
漫画：一招学会TCP的三次握手和四次挥手
HTTP报文格式、TCP、IP报头，以及连接过程总结
TCP的报文格式与连接

流量控制和拥塞控制

流量控制：滑动窗口 拥塞控制：慢启动，快重传，快恢复

TCP可靠传输的实现

MySQL 和 PostgreSQL

MySQL

主流关系型数据库，主流存储产品，灵活轻量级，有成熟的运维和使用文档

PostgreSQL

经典关系型数据库，丰富的数据类型(json,geoe,array,range)，多种索引(btree,hash,brin,gist,gin)，多种查询组合关系(hash join,merge json,seq sacn) 复杂SQL处理效果比 MySQL 好

但是 表容易膨胀，需要定期维护，单标 tps 不要太大，不能超过 3000

适用场景，多表join，json 类速查，geo 存储，图像或者内容的模糊查询或相似查询，中等量的数据分析。

MongoDB

经典的文档型数据库，快速开发，简单高可用。

计数

使用 count(*) 即可，这是 rfc 标准定义的，虽然 InnoDB 会扫描全表，但是实际上是有优化的。

count(1) 其实是和 count(*) 一样的，counnt(columname) 会过滤掉 null 的值。

redis

redis 是一个高性能的 kv 分布式内存数据库，是一个基于内存运行并支持持久化的 nosql 数据库，其显著优点有

  1. 支持数据持久化
  2. 支持多种数据结构
  3. 可以分布式集群部署

数据结构

字符串

字符串使用 SDS(Simple Dynamic String) 简单动态字符串来存储，也可以存储数字。使用一个字符数组来存储，最大可以存储 512M 。

哈希表

字符串组成的字段，用来存储对象，或者用来存储session信息。

列表

列表按字符串插入顺序排序，是一个有序列表，具有栈的特性，先进后出。基于列表页可以实现简单的消息队列功能，还有基于 redis 的分片功能。

集合

字符串构成的无序列表，通过哈希表实现，不允许重复，Redis 还提供了求并集，交集，差集等操作。

有序集合

通过分数排序来实现由小到大的集合，可以用来做排行榜，记录 topN，或者可以用来做范围查找。

缓存选型

Redis 作为非关系型数据库，NoSQL 的一种，常与 MongoDB 齐名，但是 MongoDB 常用来做文档数据库，而 Redis 常用来做缓存。

缓存数据库中与 Redis 齐名的是 memcache ，但是 memcache 比较简单，类似于哈希表，与 Redis 的对比如下

memcache

  1. 只有简单的数据类型
  2. 不支持数据持久化
  3. 不支持主从
  4. 不支持分片

redis

  1. 数据类型丰富
  2. 支持磁盘持久化存储
  3. 支持主从
  4. 支持分片

性能

redis 官方给出支持单机 QPS 100000+ ，这是因为

  1. redis 完全基于内存，大部分请求是纯内存操作，执行效率高
  2. redis 使用单进程单线程模型，没有上下文切换和锁的竞争，执行效率高
  3. 使用 io 多路复用来支持高并发操作，属于同步非阻塞模型
  4. 数据结构简单，数据操作也简单，存储结构就是键值对，没有太复杂的关系限制

事务

Redis 的 pipeline 不能完整的支持事务。使用 multi 开启事务，输入命令后进入收集阶段，再输入的命令不会被立刻执行，在 exec 命令之后才会开始一次性全部执行。

redis 开启事务之后，会进入事务状态，将接收到的客户端命令放入队列，返回 QUEUED，直到接收 exec 命令，才会将事务中的命令按照FIFO(先进先出)的方式执行。

在事务中 exec，multi，discard，watch 是特殊命令，会立即执行。

带监视的事务，watch 命令用来在事务开始前监视任意数量的key，当调用 exec 执行事务时，如果任意一个被监视的key已被其他客户端修改，那么整个事务不再执行，直接返回失败。

redis 的 watch 类似于 CAS 乐观锁,用于解决并发编程中的原子性问题。

Java 中的CAS是通过 CPU 指令，将比较并替换使用一个指令完成，所以不会被多线程打断。redis 也有 CAS ，使用 watch 指令，其实现是在 redis 中存在一个 watched_keys 字段，其中保存了需要被监视的key，每个key后面跟着监视的客户端链表。在对任何数据库键空间的修改操作之后，都会调用 touchWatchedKey 函数，检查监视情况，如果监视的key已经被修改，则将监视的客户端 REDIS_DIRTY_CAS 选项打开，在事务执行前对检查这个选项，因为 redis 是单进程单线程执行，所以能够使用检查链表的方式来实现 CAS 。

比如 redis 的单个命令都是原子性的，虽然不能保证事务的原子性，我们用事务来实现一个 incr 函数。

watch key
val = get key
val = val + 1
multi
set key $val
exec

分布式锁

分布式锁，是在分布式系统中，通过锁住同一个资源，来达到不同应用对同一个资源的抢占锁定。

分布式锁是控制分布式系统之间共同访问共享资源的一种锁的实现。如果一个系统，或者不同系统的不同主机之间需要共享某个资源时，往往需要互斥来排除干扰，满足数据一致性。

分布式锁的特点

  1. 互斥性 任意时刻只能有一个客户端或得到锁，不能有两个客户端同时持有锁
  2. 安全性 锁只能被持有该锁的客户端删除，不能被其他客户端删除
  3. 避免死锁 如果获得锁的客户端异常宕机不能正常释放锁，其他客户端再也不能获得锁时，就会发生死锁，需要有特殊机制来避免死锁的发生
  4. 容错 如果某个Redis节点宕机时，不影响锁的正常获取和释放

分布式锁实现是通过 setnx 命令来实现的，setnx=set not exist 即在 Redis 中设置一个值，如果设置成功返回1，如果该值已存在返回0。

setnx 是原子性操作，设置简单好用，但是如果持有锁的客户端宕机，该锁就永远无法释放，所以需要设置一个默认的过期时间。

但是如果需要两条指令来获得锁并设置过期时间，不能满足原子性，在 redis 2.6 的版本开始，set 操作可以在同一条语句中同时设置过期时间。

set key value [ex seconds] [px milliseconds] [nx|xx]

在获取锁的时候 setnx = set + nx 才能保持原子操作，在释放锁的时候需要 get + del 其实也需要原子操作，但是这里的两步不可避免。

所以一般在释放锁的时候会使用 LUA 脚本来实现原子性的释放。

setnx 只能在 Redis 上单机上实现分布式锁，但是现代的 Redis 都是集群部署，而且单机的 Redis 稳定性也不可靠。

因为在集群上的 setnx ，然后在同步至 slave 机器时故障，则主动切换，然后从节点无锁信息，所以需要用 redlock 在多个机器上都获取成功。

在集群的模式下，使用 RedLock 的实现分布式锁，在 Redis 文档中有详细的介绍。

简而言之，RedLock 就是在多台 Redis 实例上进行 setnx 操作，有一半以上的机器操作成功即可认为获取到锁。

消息订阅

Redis 也带消息订阅功能，使用 pub 和 sub 来分别发布和订阅一个频道 channel。

消息即时发送给所有的订阅者，没有消息持久化机制。

持久化

持久化，即将 Redis 数据持久化到磁盘上，因为 Redis 是纯内存数据库，如果断电或者宕机就会造成数据丢失，为了数据的可靠性，需要一些持久化机制。

Redis 持久化有两种 rdb 和 aof，rdb 是将 Redis 某个时刻的全量数据生成快照保存至磁盘，在数据恢复时根据 rdb文件 中的快照恢复数据。aof 是保存 Redis 的操作记录，在数据恢复时，根据操作记录回放来恢复数据。

快照持久化

rdb 即 Redis Database，rdb 持久化会在某个特定的时间间隔保存该时刻的全量数据的快照。

rdb 的创建有 save 和 bgsave 两个命令。

save 命令会阻塞 Redis 服务器进程，无法进行其他操作，直到 rdb 文件创建完成。该命令很少被使用，因为会阻塞主流程来保证快照的写入，阻塞客户端请求。

bgsave 会 fork 一个新的子进程来创建 rdb 文件，不阻塞服务器进程。子进程创建 rdb 快照并写入文件，主进程继续接收客户端的请求。

* 为什么用子进程，而不用子线程？因为有文件写入，如果是用一个进程中，会有大量的上下文切换，从用户态到内核态的切换会影响主进程。 * 在 bgsave 的时候，主进程继续接收到的请求数据会被存储么？不会，bgsave 保存的是快照，并不保证是全量的最新数据，而是当时的全量数据。

rdb 执行条件

rdb 文件生成流程

  1. 生成临时文件，并写入数据
  2. 完成数据写入，并替换原文件
  3. 删除原文件

rdb 持久化的优点

  1. rdb 快照数据恢复较快
  2. rdb 文件体积较小，适合数据备份，便于保存。
  3. 使用子进程完成数据备份，对服务器性能影响较小

rdb 的几个缺点

  1. 数据持久化的间隔较短，频繁的写入文件，对Redis服务器性能有影响，持久化间隔时间较长，间隔时间内的数据丢失。
  2. save 命令会阻塞服务器进程
  3. bgsave 命令在生成 子进程时，也会阻塞请求。
  4. 数据全量数据存储，在数据量大的情况下会严重影响 io 性能

保存写状态

aof 持久化是保存 Redis 的请求指令来记录数据库的。aof 持久化会记录除了查询之外的所有变更数据库的操作，以增量的形式追加保存到 aof 文件中。

aof 没有指令可以手动操作，需要在配置文件中开启。

aof 文件记录每一条更改记录，随着时间的推移，文件会越来越大，Redis 支持 aof 文件重写，文件重写命令 bgrewriteaof，将指令进行合并精简。redis 也是通过创建一个子进程来完成文件重写，在文件重写的时候，主流程继续接受客户端强求，并将数据请求同时写入至内存和原aof文件中，子线程重写的是原aof文件的副本，在子线程完成重写后，主线程将缓存区中的指令同步至新 aof 文件中。使用新的 aof 文件替换原 aof 文件。

rdb 子线程写入快照 和 aof 子线程指令重写的时候，使用的都是 Copy-On-Write 写时拷贝，表示多个线程对同一片内存或者同一个文件的操作，只有当文件发生改变时，才会生成一个文件的副本，来保证读取的内容不变。

aof 和 rdb 对比

Redis 4.0 之后采用 rdb-aof 混合持久化，使用 rdb 保存全量数据，使用 aof 保存增量数据。在该策略下，会先将 Redis 中的全量数据写入 rdb 文件中，然后将增量数据以 aof 的方式追加到 rdb 的数据后面，所以在这种策略写的持久化文件，前半部分是 rdb 格式的全量数据，后半部分是 aof 格式的增量数据。

数据恢复，在 Redis 服务器启动时，会先检查 aof 文件是否存在，如果存在则根据 aof 文件来恢复，否则检查 rdb 文件是否存在，如果存在则根据 rdb 文件来恢复，如果都没有，则无历史数据。

集群管理

Redis 有两种集群模式，一种集群模式，一种哨兵模式，两种模式也可以一起使用，在集群模式下，再分主从，主从的数据是一致的，在不同集群里的数据是不一致的。

集群模式

cluster 集群部署才是常见的 redis 部署方案，按照 hash(key) 做 shard 或者用 哈希一致性算法做 shard 。

主从模式

Redis 使用一个 Master 主节点来进行数据写入，使用多个 Slave 从节点来进行读操作。

  1. 数据备份是在从节点上完成，这样可以保证柱节点的性能，发挥从节点的作用，保证数据的弱一致性和最终一致性。
  2. 主从节点之间的数据并不是实时同步的，而是在一段时间之后的趋于同步，只保证最终一致性。

主从之间全同步的过程

  1. 从节点向主节点发出同步请求
  2. 主节点创建子进程，开始生成 rdb 快照文件
  3. 主节点将生成快照期间的命令缓存起来
  4. 快照数据写入文件完成后将其发送给从节点
  5. 主节点将快照期间内的增量命令也发送给从节点
  6. 主节点将增量命令保存至 aof 文件并替换原 aof 文件

主从之间增量同步的过程

  1. 主节点接收用户请求，如果没有写入操作则无需同步
  2. 主节点将操作记录追加至 aof 文件
  3. 将 aof 文件发送至从节点，同步主库，如果有写入操作则放入缓存
  4. 将缓存中的写入命令同步至从节点

哨兵模式

Redis Sentinel 哨兵。在主从模式中，如果主节点宕机，则无法执行写入操作，哨兵节点监控主节点并自动切换。

哨兵主要用来解决主从模式时主节点宕机后的主从切换问题

通讯协议

Redis 的通讯协议是文本协议，在客户端向服务器端请求时是原始值，在服务器端返回的结果是 RESP 协议序列化的值。

RESP(Redis Serialization Protocol) 协议非常简单，易于阅读理解，可以通过 Telnet 来完成与 Redis 服务器端的交互。

服务器端返回的响应数据格式

删除策略

当一个键处于过期的状态，Redis 并不是立刻将其删除，而是根据一定的删除策略来删除过期的键。主要有三种删除策略，redis 采用的是 定期删除 + 惰性删除。

  1. 定时删除，在创建键的过期时间的同时，创建一个定时器，让定时在在指定时间会后对键进行检查删除。影响 CPU 性能，在单线程单进程的 Redis 中并不太好。
  2. 惰性删除，放任键过期不管，在下次读取该键的时候，先检查键是否过期，如果过期则删除该键。对 CPU 友好，但是影响内存占用。
  3. 定期删除，每隔一段时间，定期对数据库进行一次清理，删除过期的键。折中整合，通过调整定期时间和删除策略，达到最佳效果。

定期删除和惰性删除的使用，redis 默认每100ms 进行检查，有过期的key则删除，但是需要注意的是，并不是检查全部key，而是抽取一部分key检查并删除，所以还需要惰性删除，在查找获取某个key的时候，还会检查是否过期，如果过期则也会被删除。

但是某个数据，即没有被定期删除抽中，也没有再次请求被惰性删除，也不会一直占用内存，redis 还有一套内存淘汰机制。

内存淘汰策略

# maxmemory-policy volatile-lru

注意，

  1. 如果没有设置给key设置过期时间，其实 volatile-lru,volatile-random,volatile-ttl 和 noeviction 没有区别，所以在使用 redis 的时候，注意一定要加上过期时间。
  2. 在内存空间不足的时候，为什么考虑的条件都是设置了过期时间的key，而不是已过期的key，因为其实这种条件就是 volatile-ttl

内存回收机制

redis 内存回收机制主要包括过期删除策略和内存淘汰策略两部分，redis 是基于内存的数据库，所有数据都保存在内存中，内存不能无限使用，所以在插入数据的时候可以设置过期时间，redis 会对内存数据做一定的淘汰删除回收操作。

过期删除策略有

  1. 定时删除
  2. 惰性删除
  3. 定期删除

过期删除策略的原理，redis server 在启动时就注册了一个 serverCron 的任务，每隔100ms就会抽取 expires 字典中的部分 key 进行删除，清理时间不能超过 CPU 时间的 25%，否则会立刻终止，从而实现定期删除，在 redis 每一次访问 key 的时候，都会先调用 expireIfNeeded 函数，判断 key 是否过期，然后清理过期的key。

但是如果过期的key较多，定期删除漏掉了一部分，也没有新的访问请求，即也没有惰性删除，那么将会有大量的过期key堆积在内存中，导致内存耗尽。那么当 redis 的内存达到 maxmemory 内存极限之后，会使用内存淘汰策略来清理部分数据，用以保证新数据的写入。

* 什么时候执行内存淘汰策略？redis 在每一次处理命令时，processCommand 函数都会调用 freeMemoryIfNeeded 函数来判断当前内存占用是否达到内存的最大限制，如果达到，则使用配置的算法来处理需要删除的key。

LRU(Latest Recently Used) 最近最少使用

python 实现的话，使用一个双端队列，将每次读取的key从队列中取出，放止队列尾部，当队列长度超出限制时，从队列首部删除数据，时间复杂度是 O(n), redis 的原生实现是记录每个 redisObject 的最近访问时间。

缓存穿透

三大 Redis 问题

缓存穿透

大量请求访问到一个无效值，这是一个不存在的key，会直接请求到数据库，数据库没有返回记录，并没有设置缓存。在大量无效数据的请求下，会打挂数据库。

重点在于 无效 key 或者说 不存在的值

解决方案

  1. 过滤无效请求数据
  2. 为空值也设置缓存
  3. 布隆过滤器

缓存击穿

大量请求同时查询同一个 key，刚好失效，大量请求到数据上。

重点在于 大量请求同一个 Key, 高并发在单个值上

解决方案

  1. 数据库查询加互斥锁
  2. 不设置过期时间，异步缓存更新
  3. 做并发控制，防并发请求，可以用分布式锁或者其他的机制防并发

缓存雪崩

缓存的过期时间大量设置在同一时刻，造成缓存大量在同一时刻失效，大流量请求达到数据库，导致数据库压力骤增，引起雪崩。

重点在于 大量 key 同时过期，请求直接打到数据库

解决方案：

  1. 不要将大量的数据缓存失效时间设置相同，使其随机分布在一个时间段内，可以在设置缓存过期时间的时候加上一个随机数。

热点 key

热点 key 问题是指 部分热点数据经常大量的被请求访问，导致部分集群机器CPU负载较高。解决方案

  1. 服务器本地缓存
  2. 热点数据复制，多个集群查询
  3. 一致性哈希，均衡负载

事务

单个逻辑单元的一系列操作，支持 ACID 属性的一系列操作。MySQL 的 innoDB 支持事务，MyISAM 存储引擎不支持事务。

在 MySQL 中 事务 是默认开启，自动提交的。可以通过 show variables like 'AUTOCOMMIT'; 查看，可以通过 SET AUTOCOMMIT = 0/1; 设置。

MySQL 的事务由 BEGIN 或者 START TRANSACTION 显式的开启，由 COMMIT 提交事务,由 ROLLBACK 回滚事务。

在 MySQL 的默认事务中，能够保证同一个事务的读可重复，都是一致的。但是更新或者删除操作会锁表，对于同一个数据的操作，会等待事务的完成。

事务的一个典型应用场景是，同时处理多个数据库表，或者同一个表的先插入再查找，可以保证同一个事务中的可见性，避免主动延迟。

Atomicity

原子性，事务中的所有操作，要么全部成功，要么全部失败。

Consistency

一致性，数据库从一个状态变换到另一个状态，不会存在中间状态，不会变成其他状态，数据库的完整性不会遭到破坏，事务开始前的状态是一致的，事务结束后的状态也是一致的。

比如说，在一个事务里，先扣除用户账户余额，再扣除商品库存，在事务开始之前，余额和库存是一致的，在事务结束之后，扣除余额和库存之后，数据也是保持一致。在服务突然崩溃之后，会使用 undolog 回滚。

Undo Log 实现一致性，undo log 记录更新之前的日志，用来做回滚.

数据库的主从集群，主集群新增数据之后，从数据库也会插入这条数据，使用 binlog 用来主从同步。这是分布式一致性的问题，CAP 原则，不能保证强一致性。

数据库的 log 时序

新增一行数据 -> 更新到内存 -> 写入 redolog, undolog，状态prepare -> 写入 binlog -> commit 事务

Isolation

隔离性，一个事务操作不会对其他的操作有影响，通常来说，一个事务的操作在最终提交修改前，对其他事务是不可见的。

事务的隔离性有四个等级

隔离性依次递增，select @@transaction_isolation; 查看默认隔离等级，MySQL 默认 Repeatable Read.

数据库事务的三个术语

简而言之，脏读是读取到了已修改未提交的事务，不可重复读是对同一行在同一个事务的两次查询数据不一致，因为另一个事务已经进行修改提交了。

幻读是正常的，幻读并不是读到了什么，而是确实没读到什么，在同一个事务里读到的数据都是一致的，但是另一个事务里已经把某些数据修改了，此时在事务再修改或者删除数据的时候，如果另一个事务未提交，那么当前事务会等待，如果另一个事务已提交，那么当前事务的修改变更会基于最新的数据结果，而不是基于读取到的数据结果。幻读的意思是说，你读到的数据是一致的，不会变的，但是是不准确的，只是一层幻觉，看的到，摸不到。

那么如何避免幻读的，因为在读取数据的时候使用的是共享锁，在更新插入数据的时候使用的互斥锁，所以在这里的时候，读取没问题不代表写入没问题。可以在事务里读取时就使用互斥锁，比如在 select 语句的后面加上 for update 即会使用互斥读写锁，这样在另一个事务里无法对锁定的数据进行更新删除，或者使用间隙锁。

间隙锁或者临键锁都是互斥锁，也都是通过 for update 来使用。

在一个事务中对数据加互斥锁之后，其他事务无法同时操作这些数据，在事务中会等待前一个事务的完成之后进行操作，等待超时时间 50s。

详解 MySql InnoDB 中的三种行锁（记录锁、间隙锁与临键锁）

通过 MVCC (Multi-Version Concurrent Control) 多版本并发控制，通过给每一个设置三个隐藏列来实现

创建 transaction_id, create_version, delete_version 三列来实现事务隔离，但是 MySQL 的 MVCC 只能实现 Repeatable Read 和 Read Commit 层的隔离性。

MVCC 的重点在于 永不删除数据 ，删除操作实际上是增加删除版本号，更新操作实际上是增加删除版本号，并新增一条记录，所以才能做到 可重复读。

数据永不删除，磁盘一直占用，使用 alter table tablename engine=InnoDB 清理磁盘，整理碎片。

解决不可重复读需要锁行，或者按照 MVCC 来解决，解决幻读 需要锁表。

Durability

持久性，事务一旦提交，所有的修改都会存储到数据库中，即使数据库故障，数据也不会丢失。

Redo Log 实现持久性，redo log 记录更新之后的值，用来做重放。

Mysql 事务-你想知道都在这

线程池创建指南

java 的线程池 Executor 创建 有六个参数

    public ThreadPoolExecutor(int corePoolSize,
                              int maximumPoolSize,
                              long keepAliveTime,
                              TimeUnit unit,
                              BlockingQueue<Runnable> workQueue,
                              RejectedExecutionHandler handler) {
        this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,
             Executors.defaultThreadFactory(), handler);
    }

线程创建流程。

  1. 如果当前线程数未超过 corePoolSize ，则直接创建
  2. 如果当前线程数已超过 corePoolSize ，则将线程放入队列。
  3. 如果当前线程数已超过 corePoolSize ，而且队列已满，则创建新线程。
  4. 如果当前线程数已超过 corePoolSize ，而且队列已满，而且线程数超过 maximumPoolSize 。则根据丢弃策略抛弃请求。

线程池默认提供了三种常用的线程池

    public static ExecutorService newCachedThreadPool() {
        return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                                      60L, TimeUnit.SECONDS,
                                      new SynchronousQueue<Runnable>());
    }

    public static ExecutorService newSingleThreadExecutor() {
        return new FinalizableDelegatedExecutorService
            (new ThreadPoolExecutor(1, 1,
                                    0L, TimeUnit.MILLISECONDS,
                                    new LinkedBlockingQueue<Runnable>()));
    }

    public static ExecutorService newFixedThreadPool(int nThreads) {
        return new ThreadPoolExecutor(nThreads, nThreads,
                                      0L, TimeUnit.MILLISECONDS,
                                      new LinkedBlockingQueue<Runnable>());
    }

这三种线程池的丢弃策略都是一致的，主要的区别在核心线程数，最大线程数和队列模型。

先将队列模型，SynchronousQueue 和 BlockingQueue 分别是同步队列和阻塞队列。

阻塞队列很常见，就是正常的队列，分别有 LinkedBlockingQueue 和 ArrayBlockingQueue，一个是由链表实现，一个是由数组实现。

同步队列就很神奇。同步队列是专门为异步场景准备的。

  1. 同步队列也是阻塞队列，每个 put 必须等待一个 take 后才能完成，也就是说单线程无法使用，因为在 put 之后就阻塞。
  2. 同步队列没有任何容量，peek 永远返回为空，isEmpty 永远返回 true。
  3. 线程安全，绝对阻塞。
  4. put 放元素之后，就会进入 wait 等待其他线程取走元素。
  5. offer 放入元素后会立即返回，如果正好有其他线程取走元素则返回 true，否则返回false。
  6. take 取走队首元素，如果没有元素则一直等待。
  7. poll 取走队首元素并立即返回，如果正好有其他线程放入元素则返回内容，否则返回 null。

有了队列基础，我们再来分析线程池的几种排队策略。

丢弃策略

线程池有五种状态

关于线程池有两个问题很有意思

  1. 线程池中，线程数量大于核心线程数之后，会将任务放入队列中，当队列已满之后，会重新开启新的线程执行，直到最大线程数，那么执行最新的任务么？还是执行队列里的第一个任务？
  2. 线程池中的线程，是否能够复用？还是每个任务会新起线程？

答案

  1. 执行新的任务
  2. 会复用

消息队列

常见的消息队列有 rabbitMQ，Kafaka,rocketMQ 等，常用的使用场景有

  1. 异步处理
  2. 应用解耦
  3. 流量削峰
  4. 消息通讯

选型

消息幂等

消息模型

常用的消息模型有 P2P(Point to Point) 点对点 和 Pub/Sub(Publish/Subscribe) 发布订阅 。

点对点模型

点对点消息模型主要包括三个角色：消息队列(Queue),发送者(Sender),接收者(Receiver),每个消息都被发送到一个特定队列，接收者从队列中获取消息，队列保持着消息，直到被消费或者超时。

特点

  1. 每个消息只有一个消费者，一旦被消费则不在消息队列中
  2. 发送者和接收者之间解耦，没有时间上的依赖性，发送者发送消息后无需等待接受者消费即可继续发送消息
  3. 接收者在接收到消息后需要发送应用成功到队列中

如果希望每个消息都被成功处理的话，可以采用 P2P 模型

发布订阅模型

点对点模型主要也包括三个角色：主题(Topic),发布方(Publisher),订阅方(Subscriber)，多个发布方将消息发布至主题，由多个订阅方消费。

特点

  1. 每个消息可以有多个订阅者
  2. 消费者只能消费订阅之后的消息，为了继续消费消息，订阅者必须保持运行
  3. 发布方和订阅者之间有依赖关系，只有存在订阅者之后才能发布消息，或者使用消息持久化策略

如果存在多个消息消费方的话，可以使用发布订阅模型。

消息队列的事务

  1. 丢失检测
  2. 消息重发

并发编程的问题

  1. 原子性 - 一个操作在 CPU 中不可中断，要么执行完成，要么不执行
  2. 可见性 - 一个变量在多线程中访问时，如果被某个线程修改，在其他线程中能够立刻看到。但是因为 CPU 的多级缓存，是看不到的。
  3. 顺序性 - 程序执行的顺序按照代码的先后顺序执行，但是因为 Java 的处理器优化，会造成执行重排，执行顺序和代码顺序不一致。

为了保证共享内存的正确性，内存模型定义了共享内存系统中多线程执行的读写操作行为规范。

synchronized 是万能的，但是使用锁的话，是比较影响性能的，类似于使用悲观锁。推荐是用 CAS ，底层是用 volatile 实现，即 Java 提供的具有原子性操作的类。

主要在解决并发编程的问题时有两个思路

  1. 限制编译器优化，happens-before 限制重排优化，甚至禁止重排优化，根据代码顺序执行。
  2. 内存屏障，使用内存数据，而不是使用缓存数据。

进程

进程间通信

多进程

死锁

是在并发编程中，多进程中，因竞争资源而发生的相互等待现象。

死锁的四个条件

死锁的避免

CAS

CAS 一般代表 CompareAndSwap 或者 CompareAndSet 比较并替换或者比较并交换,常用于乐观锁。

它是一个原子操作，用来比较一个内存位置的值，对比的是内存偏移量位置的值，并且值有相等时才将其设置为新值，保证了新值总是基于最新的值计算的，如果有其他线程在这期间改变了这个值则 CAS 失效。

lock 或者 synchronized 是一种悲观锁，认为竞争抢占总是存在的,一定会发生冲突。CAS 则是乐观策略，认为竞争很少出现，如果出现冲突，就一直重试，直到成功，重试操作也被称为原地自旋。

lock 和 synchronized 都是可重用锁，意思是说在一个锁里再次调用锁，得到的还是同一个锁，比如两重 synchronized 函数调用。

可多次锁住的叫信号量。

CAS 因为没有加锁带来的开销，所以比锁更方便高效。

注意，CAS 不是获得内存中变量的值，而是获得内存中改内存位置的值。所以变量需要使用 volatile 关键字，使得其对其他线程实现可见性。

在 Java 中的 CAS 实现是通过一个原子命令 cmpxchgl 实现的。

因为 volatile 不能保证原子性，所以 CAS 需要 volatile ，但是还不够。CAS 也可以通过锁来实现。

* 为什么非要原子性，没有原子性行不行？

不行，没有原子性，你读的时候确实取到了内存里的最新的值，但是因为线程切换，在另一个线程中也取到了这个值并加一，然后再回到原来的线程，继续进行加一操作，所以对于多线程中的累加器，一般出现的都是结果小于预期，而不是结果大于预期。

* 但是现在还有一点问题，在 Java 并发编程中，无论是线程还是进程，其实都是进程，线程是微型进程，在多核CPU上是可以利用多核的优势的，所以可以统称为Java并发编程，而在多核CPU上因为多级缓存的存在所以会出现可见性问题，但是对于 python 来说，多线程其实还是在一个进程中，也不会在多个CPU中执行，为什么还是会出现变量冲突，变量共享的问题的呢？

我知道了，在 python 中是没有可见性问题，但是还是会有原子性问题，只要你的操作不是原子性的，就算是同一个变量，也会因为顺序性或者原子性而错乱。

锁的选择

Lock 和 synchronized 都是锁，但是使用上

  1. lock 是一个接口，synchronized 是Java语言的内置关键字，是语言层面上的实现
  2. lock 可以自己控制，synchronized 是自动控制，所以 lock 需要手动释放，否则可能会死锁，synchronized 会在死锁时自动释放。
  3. lock 可以知道是否成功获得锁，synchronized 只会一直等待锁
  4. lock 能够响应中断事件，及时停止，synchronized 会一直进行下去

手写代码

  1. 边界检查，空值检查，空数组检查
  2. index += 1
  3. == 不要写成 =
  4. 增长 或者 降低 序列，数组，都要明确是否包括相等
  5. 求数量时，是否包含相等元素

一致性哈希算法

一致性哈希算法，常用来做数据分流，具有较高的容错性和扩展性。其实现是将 哈希值空间组成一个虚拟的圆环，将服务主机置于某些哈希节点，对于请求对象，首先求得其哈希值在圆环上的位置，然后根据顺时针继续前进，直到找到第一个主机。

这样无论是某台服务器宕机，或者新增一台服务器，都不会影响其他服务器，只会影响其后的第一台服务器。

服务设计

系统架构演变流程

  1. 单机单体应用 前期使用语言自带的 web 容器，比如 Tomcat 或者 wsgi ，后期可以引入 NGINX 做反向代理。
  2. 服务分离
    1. 动静分离，对于前端静态文件或者图片视频等媒体资源，可以引入 cdn 和 oss 分离部署，服务只负责静态化内容。
    2. 前后端分离，使用 restapi 进行前后端交互，后端服务提供接口，前端使用单页式布局。
  3. 集群化
    1. 应用集群部署，后端代码部署多台机器，使用 NGINX 做负载均衡。
    2. 服务集群化部署，NGINX 也可以独立部署多台，组成 web 集群，MySQL 也可以迁出独立部署。
  4. 引入缓存和消息队列，引入缓存可以有效的提高服务性能，减少数据库操作。在处理异步调用或者大容量请求时，可以使用队列服务。
  5. 数据库优化
    1. 数据库读写分离
    2. 数据库分库分表
  6. 应用拆分，微服务架构

集群化的问题

  1. DNS 轮询，用户请求域名如何平均的达到不同的 NGINX 服务器上。使用 NDS 轮询，给同一个域名配置多条 A 记录，域名服务商会逐一分配到不同的 IP 上。
  2. 负载均衡，后端不同的服务，如何进行流量分配。使用 NGINX 负载均衡策略进行分发，可以平均分发或者按权重分发或者按性能分配。
  3. 会话问题，对于同一个请求，到达不同的应用服务，如何保持同一个会话。使用 session ，前端在 cookie 里带上 session id ，后端从缓存或者数据库中读取会话信息。

数据库优化的问题

  1. 数据库读写分离，对读库可以继续采用集群化部分，数据主从之间同步。但是主从同步会有延时的问题，对于前依赖数据的接口，可以采用读主库的策略。
  2. 数据库分库分表.
    1. 垂直切分，对不同的数据表分别划分至不不同的数据库中，甚至对同一个数据表中，将常用字段和不常用字段进行切分到不同的表里。
    2. 水平切分，按照表中的某一个字段作为分片的键 sharding key，根据哈希取模或者时间划分等策略进行划分至不同表中，在数据读写的时候必须带上 sharding 字段。

微服务拆分的问题

  1. 服务治理，服务发现，需要引入分布式配置服务中心 zookeeper。
  2. soa 框架选型，Java 可以选择 dubbo ， spring cloud ，grpc 等，python 可以选择 thrift ，grpc 等。
  3. 微服务话拆分之后，各个服务独立部署，独立开发，独立维度，提供整体系统的稳定性。

树

🌲，一种基本的数据结构，树的进化流程。

树 -> 二叉树 -> 二叉搜索树 -> 高度平衡二叉搜索树 -> B树(B-树) -> B+树 -> B*树 -> 红黑树

二叉搜索树

二叉搜索树，又称二叉排序树，其特点有

二叉搜索树的插入是从根节点开始的，所以从左节点小于根节点可以推断出，左子树全部小于根节点，从右节点大于根节点可以推断出，右子树全部大于根节点。

满二叉树

二叉树的所有叶子节点都在同一个层级上

完全二叉树

二叉树的所有节点位置和 满二叉树 是同样的，即除了最后一层，以上层级都是满二叉树，最后一级从前往后也是满的。

高度平衡二叉搜索树

高度平衡二叉树即 AVL 树，也是二叉搜索树，而且左子树和右子树的高度相等或者相差一个。

因为在二叉搜索树中，搜索节点的最好情况是 O(logn) 但是在最差情况下是 O(n),因为这是和高度相关的。高度平衡的二叉搜索树的话，高度限制，使得查找的最好情况和最差情况都是 O(logn) 但是在删除和插入的时候，就需要旋转来平衡高度，调整树的结构，在插入和删除的时候都需要 O(logn) 的时间复杂度来调整。

B树

B树就是B-树，🤣，大概是因为其英文(B-Tree) 所以被误解为有一种B-树的结构吧。

B树又称多路搜索树，和二叉搜索树最大的差别就在多路，可以有多个子节点，这样可以降低树高，提高搜索速度。

有 m 个子节点的B树也称m阶B树。

B 树的特点

说到 B树 就要先从索引开始讲起，索引是为了更快的找到数据，数据查找最快的办法就是哈希表 HashMap ，它的键存的就是数据的索引，查找的时间复杂度是 O(1)。

* 那为什么用树，而不用索引呢？ 1. 索引太大，占用内存，在数据量较小的时候可以用索引，数据量大就不方便，而使用树，可以按节点依次读入内存即可。 2. 哈希表的结构复杂，特别是在扩容的时候，不方便，树就更加的灵活。

* 那就用二叉搜索树即可，为什么要用B树呢？ 1. B树可以有多个子节点，为了降低树高，树的时间复杂度就是在树高 O(logmn) m 为子节点数目，h为树高，子节点树最大为 2h

* 那为什么子节点树不能无限大呢？ 1. 子节点树无限大，树高为1，但是这样就成了有序数组，还是同样的问题，查找效率还会降低。

B+树

B树和B+树最大的区别就在于 B树的节点存储索引和数据，但是在查找的时候，内存中无需读入索引的数据，只需要存储索引比较即可，可以减少内存占用。

B树的索引和数据在同一个节点上，父节点的索引是子节点的索引分界点，即每个索引只会在节点中出现一次。

但是B+树的索引是会从根节点传至子节点，B+树的根节点中最大索引即为整个B+树的最大索引。

B+树的子节点只存储索引，所有的数据都存在叶子节点上。所以所有的索引也都在叶子节点上，叶子节点的数量即为索引数量，也为数据数量。

B+树的特点

B+ 树与 B 树的区别

  1. B树的元素个数等于子节点个数减一，B+树的节点个数和元素个数相等
  2. B树的节点上也带有数据，B+树的数据都在叶子节点
  3. B+树的叶子节点之间通过指针相连，建立链表
  4. B树的元素只会在节点中出现一次，B+树的元素会从根节点往下传递

B*树

B*树的和B+树的特点是，所有同层节点之间都加指针相连了，而不是仅在叶子节点。还有就是每个非叶子节点的子节点数最少为 2/3m 而非 1/2m

特点

红黑树

红黑树即 自平衡二叉搜索树，不要求左子树和右子树高度相等。在高度平衡二叉树和二叉搜索树之间找到的平衡，降低了对高度旋转的要求。

红黑树的特点

  1. 二叉树
  2. 节点是红色或者黑色
  3. 根节点是黑色
  4. 叶子节点是黑色(叶子节点是null)
  5. 每个红节点下必须要有两个黑色节点(红色节点不能相邻)
  6. 从任一节点到每个叶子节点都包含有相同数量的黑色节点

红黑树在查找，插入，删除时都可以保证 O(logn) 的时间复杂度，任何的不平衡都会在三次旋转内解决，需要重绘和翻转来保证红黑树的特性。整体性能优于 AVL 树。

雪花算法

分布式 ID ，趋势递增

snowflower 是一个 64 位的长整形，由 Twitter 提出。

-----------------------------------------------------------------------------------
|   0   |000000000000000000000000000000000000000 |  00000  |  00000  |000000000000|
-----------------------------------------------------------------------------------
| 固定值 |        41bit 的毫秒值，可以用69年        |  数据中心 | 机器编号 | 毫秒内序列号|
-----------------------------------------------------------------------------------

索引

聚簇索引

聚簇索引 也被称为聚集索引.索引分为以下几种

  1. 唯一索引 唯一索引是在表上的某个字段或者组合字段建立的索引，唯一索引不能重复，一般比如主键会自动创建唯一索引

  2. 非唯一索引 非唯一索引，即索引字段可以重复

  3. 主键索引 主键索引属于唯一索引，表创建主键时自动创建的索引，一个表只能有一个主键索引。
  4. 辅助索引 非主键索引，其他字段或组合字段创建的索引。

聚簇索引是主键索引，一个表中只能有一个聚簇索引，聚簇索引中表中记录的物理顺序与索引的排列顺序保持一致。

如果没有主键，数据库会自动采用第一个组成列都 not null 的唯一索引为聚簇索引，如果表中没有这样的列，MySQL 会自动创建一个隐藏列为聚簇索引。

每个 innodb 有且仅有一个聚簇索引，其实就是主键索引。

除了聚簇索引，其他的都是非聚簇索引，或者叫辅助索引。所有非聚簇索引必须要包含主键，即聚簇索引的列。

聚簇索引的索引顺序与数据的物理排列顺序保持一致，所以查询速度快，连续索引的值一定紧随其后。但是插入比较慢，为了保持物理顺序与索引顺序一致。在插入时需要进行物理顺序重排。

聚簇索引和非聚簇索引都是采用 B+ 树的结构，但是聚簇索引的叶子节点上就是数据节点，非聚簇索引的叶子并不是数据，而是数据的指针，指向数据的位置。

* 辅助索引保存主键值，而非数据位置的原因，当聚簇索引进行重排移动时，无需更改辅助索引。 * 聚簇索引叶子节点保存数据，可以更快的查询到数据，读取叶子节点即为数据节点。

MyISAM 都是采用非聚簇索引的方式，索引和数据并不是放在一起，索引的叶子节点是一个指向数据位置的指针。MyISAM 中的主键索引和非主键索引结构上没有区别。

InnoDB 采用的是聚簇索引，主键索引的叶子节点上挂载数据，非主键索引的叶子节点上是主键。从非主键索引中查找数据需要进行两次 B+ 树搜索。

索引使用 InnoDB 的话，主键索引不宜采用过长的字段作为主键，不宜采用非单调的字段作为主键。因为如果主键时非单调的，当插入新的数据时，会进行大量的数据重排和移动，使用自增字段作为主键是一个很好的选择。

索引建立原则

  1. 最左匹配原则，将常用的搜索字段建立索引，如果常用复合查询，则建立联合索引。查询条件直到遇到 > < between, like 就停止匹配。对于a = 1 and b = 2 and c > 3 and d = 4这样的查询条件，则建立 a,b,c 的联合索引
  2. 使用区分度高的字段作为索引，否则即相当于扫描全表。扫描的记录越少，查找匹配的时候就可以过滤更多的行。
  3. 不要在查询条件中使用 函数或者运算，这样不会使用索引，全表扫描。
  4. 不要让数据库做隐式转换，这样也不会用到索引，全表扫描。
  5. like 的查询条件中，右模糊会采用索引like me% ，左模糊查询或者全模糊查询不会使用索引，like %me 或者 like %me%，造成全表扫描。

数据库引擎

使用 show engines 查看数据库支持的引擎列表，详细指出了不同数据库引擎的优劣。

比如 InnoDB 支持事务，有行级锁，支持外键，是 MySQL 的默认存储引擎。


mysql> show engines;
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| Engine             | Support | Comment                                                        | Transactions | XA   | Savepoints |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+
| ARCHIVE            | YES     | Archive storage engine                                         | NO           | NO   | NO         |
| BLACKHOLE          | YES     | /dev/null storage engine (anything you write to it disappears) | NO           | NO   | NO         |
| MRG_MYISAM         | YES     | Collection of identical MyISAM tables                          | NO           | NO   | NO         |
| FEDERATED          | NO      | Federated MySQL storage engine                                 | NULL         | NULL | NULL       |
| MyISAM             | YES     | MyISAM storage engine                                          | NO           | NO   | NO         |
| PERFORMANCE_SCHEMA | YES     | Performance Schema                                             | NO           | NO   | NO         |
| InnoDB             | DEFAULT | Supports transactions, row-level locking, and foreign keys     | YES          | YES  | YES        |
| MEMORY             | YES     | Hash based, stored in memory, useful for temporary tables      | NO           | NO   | NO         |
| CSV                | YES     | CSV storage engine                                             | NO           | NO   | NO         |
+--------------------+---------+----------------------------------------------------------------+--------------+------+------------+

MyISAM

  1. 事务上，MyISAM 不提供事务支持，查询速度比 InnoDB 更快。
  2. MyISAM 不支持外键。
  3. 只支持表锁，MyISAM 适用于查询更多的情况。
  4. MyISAM 支持全文索引
  5. 允许存在没有主键的表，因为主键索引和辅助索引都是一样的
  6. MyISAM 有计数器存储了表的最大行数，直接查询表行数并不会扫描全表

InnoDB

  1. 事务上，提供事务支持，还有各种事务隔离等级。
  2. InnoDB 支持外键，虽然一般也不用
  3. 支持表锁和行锁，默认是行锁，行锁大幅度增加了多用户并发操作的性能。InnoDB 适用于插入和更新更多的情况。
  4. InnoDB 不支持全文索引，在 5.6 之后的版本才开始支持全文索引 (fulltext)
  5. InnoDB 如果没有设定主键，会自动生成一个六字节的主键，用户不可见
  6. InnoDB 没有存储表的行数，会扫描全表来计算行数。

topK

top K 大数的常用算法

分布式事务的问题

分布式事务用来保证在分布式系统中的不同节点的数据一致性问题。

事务的四大原则 ACID，分布式事务有三大问题 CAP

鱼与熊掌不可兼得，三者只能保证两个。

CA: 传统 oracle 数据库 AP: 大多数网站架构选型 CP: redis, mongodb

CAP 的核心理论是：一个分布式系统不可能很好的同时满足强一致性，高可用性和分区容错性，最多只能同时较好的满足两个。

为了解决关系型数据库强一致性引起的性能下降，可用性降低的解决方案。

不要求强一致性，只要求 BASE。

它的思想是放松对强一致性的要求，来换取系统整体收缩性和性能上的改观，只要求最终一致性。 最终一致性的具体实现 paxos，raft，zab 等。

两阶段提交

分布式事务的的实现中比较有名的是 oracle 提出的 XA 分布式事务协议。XA 协议主要包括 两阶段提交 和 三阶段提交。

两阶段提交流程

三阶段提交

TCC(Try, Comfirm, Cancel)

流量控制算法

限流器可以使用 Redis incr 计数限流实现最简单的限流器。标准实现是 令牌桶和漏桶。

限流器，首先是 计数器，其次是滑动窗口，这两个才是最常用的。

https://blog.biezhi.me/2018/10/rate-limit-algorithm.html

令牌桶

以固定的速率往桶里放令牌，请求拿到令牌之后，才能真正的被执行。令牌桶也能够实现一定量的突发请求，但是会对服务造成冲击，因为服务可能无法接收这么大量的请求速率。

Google的Guava包中的RateLimiter类就是令牌桶算法的解决方案。

令牌桶可以突发，服务会遇到突发的大流量请求。

漏桶

请求放到漏桶里，漏桶的大小是固定的，可以容忍一定量的突发请求。漏桶以固定流速出水，即固定速率处理请求，强行限制请求速率。

不太能突发，服务的请求速率是固定，削峰限流。

http

http2

https

java 内存模型

java 内存模型(Java Memory Model, JMM)

运行时数据区域：方法区，JVM堆，程序计数器，虚拟机栈，本地方法栈。

java 垃圾回收

垃圾回收可以有效的防止内存泄露，避免内存占用，有效的使用空闲内存。

垃圾回收常用算法

  1. 引用计数，但是无法计算循环引用
  2. 可达性分析，从 GC Root 开始，不能被访问到的对象将被删除

GC root 主要包括

垃圾收集算法

  1. 标记清除，简单方便，但是容易产生内存碎片
  2. 标记整理，适用于存活对象多，垃圾少的情况
  3. 复制，适用于存活对象少，垃圾多的情况，再开辟内存区间放存活的对象

java的分代回收机制

堆内存空间主要分为三块

  1. 新生代，刚创建的对象，在代码运行时会持续不断的创造新的对象，这些对象会被统一放在一起，因为很多局部变量在创建完成后很快就会变成不可达对象快速死去。所以新生代的特点是存活对象少，垃圾多。
  2. 老年代，存活了一段时间的对象，比如类变量，这些对象早早的就被创建出来，并且一直存活下来，这些存活时间较长的对象放在一起就是老年代。老年代的特点是存活对象多，垃圾少。
  3. 永久代，永远存在的对象，比如静态变量，这些变量不需要垃圾回收，永远存在。不过在 Java8 里已经把 永久代删除了，用来存放元空间。

主要是新生代和老年代的内存回收，新生代采用复制回收机制，老年代采用标记整理机制。新生代/老年代 = 1/2

python 垃圾回收

python 语言默认的垃圾回收机制是 引用计数，以 分代回收为辅，python 的分代回收中，将对象分为三代。同样的通过复制算法将对象复制到下一代。python 中也有标记清除法，从根对象开始，对没有标记的非活跃对象进行回收。

秒杀系统设计架构

限流 + 削峰 + 异步处理 + 内存缓存

BitMap

可以使用 BitMap 对 40亿数据排序，每个数占一个比特位 Bit, 大概需要 500M

32 位的系统，大概可以使用 4G 内存，内存比特位总长度 343 亿，可以用来做数据排序，去重，查询，将数字放到数字对应的内存位置上。

BloomFilter

布隆过滤器,常用于URL过滤，核心思想是使用多个哈希算法，对哈希值进行依次比较，只有当全部相等时，即认为有重复。

布隆过滤器会出现误判，但不会出现漏判。

jwt

JWT(json web token) 有的时候会用到 jwt 维持登陆态或者临时授权，简单记录一下。

其实使用 jwt 最常用的场景是在 iframe 中，无法存储 Cookies 在另一个站点域名下。所以使用 jwt 维持登陆态。

jwt 的优点

  1. 防用户篡改，使用私钥签名
  2. 失效控制，需要有过期时间
  3. 无需服务器端维护，减少服务器端存储
  4. 能够解决 Cookies 的跨域问题

jwt 的缺点

  1. 敏感信息泄露，jwt payload 使用 base64 编码，未加密
  2. jwt 无法强制失效，在有效期内可以一直使用，jwt 遭遇泄露无法在服务器端失效。

蓄水池抽样算法

蓄水池抽样算法(Reservoir Sampling) 很神奇，简而言之，从无限的字符流中，随机选出 10 个字符。

详细问题：给定一个数据流，数据流长度N很大，且N直到处理完所有数据之前都不可知，请问如何在只遍历一遍数据O(N)的情况下，能够随机选出M个不同的数据。

分为两个部分，当 n <= M 的时候，直接选入；当 n > M 的时候，选取 [0,n) 的随机数 d，如果 d < M 则将当前值替换第d个位置的结果，否则继续。

# coding=utf-8

import random


class RandomStream(object):

    def __init__(self, M):
        self.M = M
        self.count = 0
        self.result = []

    def stream(self, N):
        if self.count < self.M:
            self.result.append(N)
        else:
            d = random.randint(0, self.count)
            if d <= self.M - 1:
                self.result[d] = N
        self.count += 1

蓄水池抽样算法（Reservoir Sampling）

面试经历

面了几家，感觉还可以，就是有一点很神奇，永远都是面试官上来让你做自我介绍，然后呼呼开始面试，就从来没有面试官的自我介绍，也不知道面试官的名字。

最终通过头条面试，准备入职。

参考资料

笔试面试知识整理
数据结构与算法/leetcode/lintcode题解
Redis从入门到精通，至少要看看这篇！
事务
一文学会 Java 垃圾回收机制
Java并发编程：Lock
老生常谈的 Redis 雪崩、击穿、穿透、预热、降级一次全安排

本文固定链接：https://windard.com/project/2019/11/24/Interview-In-Backend
原创文章,转载请注明出处：后端面试总结 By Windard

纯享阅读~ Click me
headlogo   Windard

但行好事，莫问前程

Blog

Opinion

Project

页阅读量:  ・  站访问量:  ・  站访客数: