IO大集合？

答：

1. 异步、同步

同步，就是调用某个东西是，调用方得等待这个调用返回结果才能继续往后执行。异步，和同步相反 调用方不会理解得到结果，而是在调用发出后调用者可用继续执行后续操作，被调用者通过状体来通知调用者，或者通过回掉函数来处理这个调用.。
同步本质： 同步跟异步的区别在于数据从内核空间拷贝到用户空间是否由用户线程完成，这里又分为同步阻塞跟同步非阻塞两种。1. 同步阻塞： 此时一个线程维护一个连接，该线程完成数据到读写跟处理到全部过程，数据读写时时线程是被阻塞的。2. 同步非阻塞： 非阻塞的意思是用户线程发出读请求后，读请求不会阻塞当前用户线程，不过用户线程还是要不断的去主动判断数据是否准备OK了。此时还是会阻塞等待内核复制数据到用户进程。他与同步BIO区别是使用一个连接全程等待
异步本质： 对于异步来说，用户进行读或者写后，将立刻返回，由内核去完成数据读取以及拷贝工作，完成后通知用户，并执行回调函数（用户提供的callback），此时数据已从内核拷贝到用户空间，用户线程只需要对数据进行处理即可，不需要关注读写，用户不需要等待内核对数据的复制操作，用户在得到通知时数据已经被复制到用户空间。我们以如下的真实异步非阻塞为例。

2. 异步IO、同步IO

区别在于是否等待IO执行的结果。
好比你去麦当劳点餐，你说“来个汉堡”，服务员告诉你，对不起，汉堡要现做，需要等5分钟，于是你站在收银台前面等了5分钟，拿到汉堡再去逛商场，这是同步IO。
你说“来个汉堡”，服务员告诉你，汉堡需要等5分钟，你可以先去逛商场，等做好了，我们再通知你，这样你可以立刻去干别的事情（逛商场），这是异步IO。

3. 阻塞

阻塞

阻塞IO情况下，当用户调用read后，用户线程会被阻塞，等内核数据准备好并且数据从内核缓冲区拷贝到用户态缓存区后read才会返回。可以看到是阻塞的两个部分。

1. CPU把数据从磁盘读到内核缓冲区。
2. CPU把数据从内核缓冲区拷贝到用户缓冲区。

4. 非阻塞

非阻塞

非阻塞IO发出read请求后发现数据没准备好，会继续往下执行，此时应用程序会不断轮询polling内核询问数据是否准备好，当数据没有准备好时，内核立即返回EWOULDBLOCK错误。直到数据被拷贝到应用程序缓冲区，read请求才获取到结果。并且你要注意！这里最后一次 read 调用获取数据的过程，是一个同步的过程，是需要等待的过程。这里的同步指的是内核态的数据拷贝到用户程序的缓存区这个过程。

5. IO多路复用

IO多路复用

I/O 多路复用相当于将「遍历所有文件描述符、通过非阻塞 I/O 查看其是否就绪」的过程从用户线程移到了内核中，由内核来负责轮询。

进程可以通过 select、poll、epoll 发起 I/O 多路复用的系统调用，这些系统调用都是同步阻塞的：如果传入的多个文件描述符中，有描述符就绪，则返回就绪的描述符；否则如果所有文件描述符都未就绪，就阻塞调用进程，直到某个描述符就绪，或者阻塞时长超过设置的 timeout 后，再返回。使用非阻塞 I/O 检查每个描述符的就绪状态。

如果 timeout 参数设为 NULL，会无限阻塞直到某个描述符就绪；如果 timeout 参数设为 0，会立即返回，不阻塞。

I/O 多路复用引入了一些额外的操作和开销，性能更差。但是好处是用户可以在一个线程内同时处理多个 I/O 请求。如果不采用 I/O 多路复用，则必须通过多线程的方式，每个线程处理一个 I/O 请求。后者线程切换也是有一定的开销的。这部分内容可以查看最下文 Redis 的线程模型。

非阻塞情况下无可用数据时，应用程序每次轮询内核看数据是否准备好了也耗费CPU，能否不让它轮询，当内核缓冲区数据准备好了，以事件通知当机制告知应用进程数据准备好了呢？应用进程在没有收到数据准备好的事件通知信号时可以忙写其他的工作。此时IO多路复用就派上用场了。
IO多路复用中文比较让人头大，IO多路复用的原文叫 I/O multiplexing，这里的 multiplexing 指的其实是在单个线程通过记录跟踪每一个Sock(I/O流)的状态来同时管理多个I/O流. 发明它的目的是尽量多的提高服务器的吞吐能力。
实现一个线程监控多个IO请求，哪个IO有请求就把数据从内核拷贝到进程缓冲区，拷贝期间是阻塞的！现在已经可以通过采用mmap地址映射的方法，达到内存共享效果，避免真复制，提高效率。 像select、poll、epoll 都是I/O多路复用的具体的实现。

• select:
  1. select 会修改传入的参数数组，这个对于一个需要调用很多次的函数，是非常不友好的。
  2. select 如果任何一个sock(I/O stream)出现了数据，select 仅仅会返回，但不会告诉是那个sock上有数据，只能自己遍历查找。
  3. select 只能监视1024个链接
  4. select 不是线程安全的，如果你把一个sock加入到select, 然后突然另外一个线程发现这个sock不用，要收回，这个select 不支持的。
• poll:
  1. poll 去掉了1024个链接的限制。
  2. poll 从设计上来说不再修改传入数组。
• epoll: epoll 可以说是 I/O 多路复用最新的一个实现，epoll 修复了poll 和select绝大部分问题， 比如：
  1. epoll 现在是线程安全的。
  2. epoll 现在不仅告诉你sock组里面数据，还会告诉你具体哪个sock有数据，你不用自己去找了。
  3. epoll 内核态管理了各种IO文件描述符， 以前用户态发送所有文件描述符到内核态，然后内核态负责筛选返回可用数组，现在epoll模式下所有文件描述符在内核态有存，查询时不用传文件描述符进去了。

异步IO

异步IO

然后你会发现上面的提到过的操作都不是真正的异步，因为两个阶段总要等待会儿！而真正的异步 I/O 是内核数据准备好和数据从内核态拷贝到用户态这两个过程都不用等待。
很庆幸，Linux给我们准备了aio_read跟aio_write函数实现真实的异步，当用户发起aio_read请求后就会自动返回。内核会自动将数据从内核缓冲区拷贝到用户进程空间，应用进程啥都不用管。

简述Token验证方式？

参考
参考
详细参考
答：

一、token存在哪？

客户端收到服务器返回的 JWT，可以储存在 Cookie 里面，也可以储存在 localStorage。

二、token发送的时候放在哪？

1. 当用户希望访问一个受保护的路由或者资源的时候，可以把它放在 Cookie 里面自动发送，但是这样不能跨域，所以更好的做法是放在 HTTP 请求头信息的 Authorization 字段里，使用 Bearer 模式添加 JWT。优点： 1、用户的状态不会存储在服务端的内存中，这是一种 无状态的认证机制。2、服务端的保护路由将会检查请求头 Authorization 中的 JWT 信息，如果合法，则允许用户的行为。3、由于 JWT 是自包含的，因此减少了需要查询数据库的需要4、JWT 的这些特性使得我们可以完全依赖其无状态的特性提供数据 API 服务，甚至是创建一个下载流服务。5、因为 JWT 并不使用 Cookie ，所以你可以使用任何域名提供你的 API 服务而不需要担心跨域资源共享问题（CORS）
2. 跨域的时候，可以把 JWT 放在 POST 请求的数据体里。
3. 通过 URL 传输

• 过程

1.用户通过用户名和密码发送请求。
2.程序验证。
3.程序返回一个签名的token 给客户端。
4.客户端储存token,并且每次用于每次发送请求。
5.服务端验证token并返回数据。

• 优点

1.无状态： token 自身包含了身份验证所需要的所有信息，使得我们的服务器不需要存储 Session 信息，这显然增加了系统的可用性和伸缩性，大大减轻了服务端的压力。但是，也正是由于 token 的无状态，也导致了它最大的缺点：当后端在token 有效期内废弃一个 token 或者更改它的权限的话，不会立即生效，一般需要等到有效期过后才可以。因为我们服务器端并没有存储Token，只有客户端才有。
2.有效避免了CSRF 攻击： 那么究竟什么是跨站请求伪造呢？说简单用你的身份去发送一些对你不友好的请求。举个简单的例子：
小壮登录了某网上银行，他来到了网上银行的帖子区，看到一个帖子下面有一个链接写着“科学理财，年盈利率过万”，小壮好奇的点开了这个链接，结果发现自己的账户少了10000元。这是这么回事呢？原来黑客在链接中藏了一个请求，这个请求直接利用小壮的身份给银行发送了一个转账请求,也就是通过你的 Cookie 向银行发出请求。
导致这个问题很大的原因就是： Session 认证中 Cookie 中的 session_id 是由浏览器发送到服务端的，借助这个特性，攻击者就可以通过让用户误点攻击链接，达到攻击效果。

3. 因为 JWT 并不使用 Cookie 的，所以你可以使用任何域名提供你的 API 服务而不需要担心跨域资源共享问题（CORS）

• 那为什么 token 不会存在这种问题呢？

一般情况下我们使用 JWT 的话，在我们登录成功获得 token 之后，一般会选择存放在 local storage 中。然后我们在前端通过某些方式会给每个发到后端的请求加上这个 token,这样就不会出现 CSRF 漏洞的问题。因为，即使有个你点击了非法链接发送了请求到服务端，这个非法请求是不会携带 token 的，所以这个请求将是非法的（因为Token的添加是需要你前端代码主动添加的）。

问题存在：
1. 注销登录等场景下 token 还有效
这个问题不存在于 Session 认证方式中，因为在 Session 认证方式中，遇到这种情况的话服务端删除对应的 Session 记录即可。但是，使用 token 认证的方式就不好解决了。我们也说过了，token 一旦派发出去，如果后端不增加其他逻辑的话，它在失效之前都是有效的。那么，我们如何解决这个问题呢？查阅了很多资料，总结了下面几种方案：

• 将 token 存入内存数据库： 将 token 存入 DB 中，redis 内存数据库在这里是是不错的选择。如果需要让某个 token 失效就直接从 redis 中删除这个 token 即可。但是，这样会导致每次使用 token 发送请求都要先从 DB 中查询 token 是否存在的步骤，而且违背了 JWT 的无状态原则。
• 黑名单机制： 和上面的方式类似，使用内存数据库比如 redis 维护一个黑名单，如果想让某个 token 失效的话就直接将这个 token 加入到 黑名单 即可。然后，每次使用 token 进行请求的话都会先判断这个 token 是否存在于黑名单中。
• 修改密钥 (Secret) : 我们为每个用户都创建一个专属密钥，如果我们想让某个 token 失效，我们直接修改对应用户的密钥即可。但是，这样相比于前两种引入内存数据库带来了危害更大，比如：1、如果服务是分布式的，则每次发出新的 token 时都必须在多台机器同步密钥。为此，你需要将必须将机密存储在数据库或其他外部服务中，这样和 Session 认证就没太大区别了。2、如果用户同时在两个浏览器打开系统，或者在手机端也打开了系统，如果它从一个地方将账号退出，那么其他地方都要重新进行登录，这是不可取的。
• 保持令牌的有效期限短并经常轮换 ： 很简单的一种方式。但是，会导致用户登录状态不会被持久记录，而且需要用户经常登录。

2. token 的续签问题

因为安全问题，token 有效期一般都建议设置的不太长，那么 token 过期后如何认证，如何实现动态刷新 token，避免用户经常需要重新登录？
我们先来看看在 Session 认证中一般的做法：假如 session 的有效期30分钟，如果 30 分钟内用户有访问，就把 session 有效期被延长30分钟。

• 类似于 Session 认证中的做法： 这种方案满足于大部分场景。假设服务端给的 token 有效期设置为30分钟，服务端每次进行校验时，如果发现 token 的有效期马上快过期了，服务端就重新生成 token 给客户端。客户端每次请求都检查新旧token，如果不一致，则更新本地的token。这种做法的问题是仅仅在快过期的时候请求才会更新 token ,对客户端不是很友好。
• 每次请求都返回新 token ： 这种方案的的思路很简单，但是，很明显，开销会比较大。
• token 有效期设置到半夜 ： 这种方案是一种折衷的方案，保证了大部分用户白天可以正常登录，适用于对安全性要求不高的系统。
• 用户登录返回两个 token ： 第一个是 acessToken ，它的过期时间 token 本身的过期时间比如半个小时，另外一个是 refreshToken 它的过期时间更长一点比如为1天。客户端登录后，将 accessToken和refreshToken 保存在本地，每次访问将 accessToken 传给服务端。服务端校验 accessToken 的有效性，如果过期的话，就将 refreshToken 传给服务端。如果有效，服务端就生成新的 accessToken 给客户端。否则，客户端就重新登录即可。该方案的不足是：1、需要客户端来配合；2、用户注销的时候需要同时保证两个 token 都无效；3、重新请求获取 token 的过程中会有短暂 token 不可用的情况（可以通过在客户端设置定时器，当accessToken 快过期的时候，提前去通过 refreshToken 获取新的accessToken）。

排序算法的优略性？

答：

图片

简述漏桶算法和令牌桶算法？

答：

• 漏桶算法： 漏桶算法面对限流，就更加的柔性，不存在直接的粗暴拒绝。它的原理很简单，可以认为就是注水漏水的过程。往漏桶中以任意速率流入水，以固定的速率流出水。当水超过桶的容量时，会被溢出，也就是被丢弃。因为桶容量是不变的，保证了整体的速率。

1. 流入的水滴，可以看作是访问系统的请求，这个流入速率是不确定的。
2. 桶的容量一般表示系统所能处理的请求数。
3. 如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）
4. 流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。

在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。

• 令牌桶算法： 面对突发流量的时候，我们可以使用令牌桶算法限流。

1. 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。
2. 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
3. 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；
4. 如果拿不到令牌，就直接拒绝这个请求。

这个时候如果我们要提高反应速度的时候，就可以提高令牌的数量，这样吞吐量自然就上去了

Restful api和soap api的区别？

答：soap协议就是简单对象传输协议，如同他的名字，他就是通过传输整个对象来传输数据，并且错误码，还有其他附加信息，比如编码规则，都是放在这个对象里面，是基于XML实现了，首先可想而知这个协议是比较重量级的，因为在传输的时候我们需要定义自己的标签去实现特定的功能。

1. 底层协议： SOAP本身便是基于HTTP而发展的协议。REST与HTTP几乎一样，REST规范没有强制的要求。
2. 数据格式： SOAP只依靠XML来提供消息传递服务。在某些情况下，消息传递服务可能变得极其复杂。例如，通过javascript访问Web服务，REST可以语言自由的选择易解析的数据格式。例如，CSV、JSON、XML、YAML等等。
3. 有状态： SOAP Web服务是无状态的，但是可以通过修改服务器上的代码轻松变为有状态的。RESTful Web服务是完全无状态的。对话状态的管理完全由客户端进行控制。服务端不保留任何状态信息。也就是我们通常所说的，客户端的每次请求必须携带所有可能用到的信息。
4. HTTP的方法使用： SOAP可以对HTTP协议进行绑定。当绑定HTTP协议时，所有的SOAP请求都通过HTTP POST发送。REST主要使用HTTP协议。通过HTTP GET、POST、PUT、DELETE和PATCH方法进行CRUD操作。
5. 安全： SOAP通过WS-SECURITY对安全进行了很好的标准化，并且XML本身就是一种格式标准非常严格的协议，所以比较安全。REST主要使用HTTP协议，HTTP本身是非常不安全的，但通过TLS它可以支持基础的身份认证和通信加密，即HTTPS。此外，在服务器上还可以进一步实施安全措施。

REST和SOAP区别： 因为SOAP并不假定传输数据的下层协议，因此必须设计为能在各种协议上运行。即使绝大多数SOAP是运行在HTTP上，使用URI标识服务，SOAP也仅仅使用POST方法发送请求，用一个唯一的URI标识服务的入口。举一个图书馆在线查询管理系统为例，服务提供者必须为每一本书提供一个内部标识，然后可能定义一个listBooks操作来返回一系列图书，一个getBook操作来返回指定的图书，一个createBook操作来向数据库加入新增的图书，一个deleteBook操作来删除作废的图书，每个操作都有各自的参数，尤其是用内部标识来标识操作的图书。这种设计被诟病之处，在于deleteBook操作也要用POST方法来发送，而其实HTTP协议有更和逻辑的DELETE方法可用。 REST正是这样设计的，REST为每一个资源（此处是图书）指定一个唯一的URI，而用HTTP的4种方法GET、POST、PUT、DELETE直观地表示获取、创建、更新和删除图书。同时图书集合也是和单本的图书不同的资源，如果用/books来代表图书列表，/books/ID来代表标识为ID的图书，那么对/books的GET操作就代表返回整个图书列表，对/books/ID的DELETE操作代表删除指定的图书，等等。

堆数据结构？

答：大顶堆，小顶顿，添加：将数据添加到数组的最后，然后上浮 删除：删除堆顶节点，然后将最后一个元素放到堆顶，下沉

B树的基本性质、红黑树的基本性质？

答：

• 平衡树的基本性质：

1. 树的左右两边的层级数相差不会大于1；也就是说只有每一次排满后才能到下一层存放数据

• 红黑树的基本性质：

1. 每个节点都有红色或黑色

2. 树的根始终是黑色的 (可以理解为黑土地孕育黑树根0.0)

3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）

4. 从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

hash冲突有哪些方法？

答：

1. 开放地址方法(再散列法)

可以通俗理解为所有的地址都对所有的数值开放，而不是链式地址法的封闭方式，一个数值固定在一个索引地址位置。

p1=hash(key)如果冲突就在p1地址的基础上+1或者散列处理，p2=hash(p1)....

（1）线性探测： 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上往后加一个单位，直至不发生哈希冲突。
（2）再平方探测： 按顺序决定值时，如果某数据的值已经存在，则在原来值的基础上先加1的平方个单位，若仍然存在则减1的平方个单位。随之是2的平方，3的平方等等。直至不发生哈希冲突。和线性探测相比就是改变探测了步长。因为如果都是+1来探测在数据量比较大的情况下，效率会很差。
（3）伪随机探测： 按顺序决定值时，如果某数据已经存在，通过随机函数随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突。

2. 链式地址法（HashMap的哈希冲突解决方法）

3. 建立公共溢出区： 建立公共溢出区存储所有哈希冲突的数据。

4. 再哈希法： 对于冲突的哈希值再次进行哈希处理，直至没有哈希冲突。可以理解为p=hash(key)如果冲突就p=hash2(key)

MySQL索引下推？

答：
索引下推（index condition pushdown ）简称ICP，在Mysql5.6的版本上推出，用于优化查询。
在不使用ICP的情况下，在使用非主键索引（又叫普通索引或者二级索引）进行查询时，存储引擎通过索引检索到数据，然后返回给MySQL服务器，服务器然后判断数据是否符合条件 。
在使用ICP的情况下，如果存在某些被索引的列的判断条件时，MySQL服务器将这一部分判断条件传递给存储引擎，然后由存储引擎通过判断索引是否符合MySQL服务器传递的条件，只有当索引符合条件时才会将数据检索出来返回给MySQL服务器 。
索引条件下推优化可以减少存储引擎查询基础表的次数，也可以减少MySQL服务器从存储引擎接收数据的次数。

总结： 充分利用所给的条件，减少无效回表，等所有能用上的条件都用上去排除了之后，再去回表查询具体数据，例子

图例子

SELECT * from user where name like '陈%' and age=20
会忽略age这个字段，直接通过name进行查询，在(name,age)这课树上查找到了两个结果，id分别为2,1，然后拿着取到的id值一次次的回表查询，因此这个过程需要回表两次。

图例子

InnoDB并没有忽略age这个字段，而是在索引内部就判断了age是否等于20，对于不等于20的记录直接跳过，因此在(name,age)这棵索引树中只匹配到了一个记录，此时拿着这个id去主键索引树中回表查询全部数据，这个过程只需要回表一次。

怎么实现幂等？