设计模式
设计原则
工厂方法模式
抽象工厂模式
单例模式
建造者模式
原型模式
适配器模式
装饰器模式
代理模式
外观模式
桥接模式
组合模式
享元模式
策略模式
模板方法模式
观察者模式
迭代子模式
责任链模式
命令模式
备忘录模式
状态模式
访问者模式
中介者模式
解释器模式
负载均衡
负载均衡 建立在现有网络结构之上，它提供了一种廉价有效透明的方法扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。
四层负载均衡 vs 七层负载均衡
四层负载均衡（目标地址和端口交换）
主要通过报文中的目标地址和端口，再加上负载均衡设备设置的服务器选择方式，决定最终选择的内部服务器。
以常见的 TCP 为例，负载均衡设备在接收到第一个来自客户端的 SYN 请求时，即通过上述方式选择一个最佳的服务器，并对报文中目标 IP 地址进行修改(改为后端服务器 IP），直接转发给该服务器。TCP 的连接建立，即三次握手是客户端和服务器直接建立的，负载均衡设备只是起到一个类似路由器的转发动作。在某些部署情况下，为保证服务器回包可以正确返回给负载均衡设备，在转发报文的同时可能还会对报文原来的源地址进行修改。实现四层负载均衡的软件有：
*_F5_：硬件负载均衡器，功能很好，但是成本很高。
*_lvs_：重量级的四层负载软件。
*_nginx_：轻量级的四层负载软件，带缓存功能，正则表达式较灵活。
*_haproxy_：模拟四层转发，较灵活。
七层负载均衡（内容交换）
所谓七层负载均衡，也称为“内容交换”，也就是主要通过报文中的真正有意义的应用层内容，再加上负载均衡设备设置的服务器选择方式，决定最终选择的内部服务器。七层应用负载的好处，是使得整个网络更智能化。例如访问一个网站的用户流量，可以通过七层的方式，将对图片类的请求转发到特定的图片服务器并可以使用缓存技术；将对文字类的请求可以转发到特定的文字服务器并可以使用压缩技术。实现七层负载均衡的软件有：
haproxy*：天生负载均衡技能，全面支持七层代理，会话保持，标记，路径转移； nginx*：只在http* 协议和mail*协议上功能比较好，性能与haproxy*差不多； apache*：功能较差
*_Mysql proxy_：功能尚可。
负载均衡算法/策略
轮循均衡（Round Robin）
每一次来自网络的请求轮流分配给内部中的服务器，从 1 至 N 然后重新开始。此种均衡算法适合于服务器组中的所有服务器都有相同的软硬件配置并且平均服务请求相对均衡的情况。
权重轮循均衡（Weighted Round Robin）
根据服务器的不同处理能力，给每个服务器分配不同的权值，使其能够接受相应权值数的服务请求。例如：服务器 A 的权值被设计成 1，B 的权值是 3，C 的权值是 6，则服务器 A、B、C 将分别接受到 10%、30％、60％的服务请求。此种均衡算法能确保高性能的服务器得到更多的使用率，避免低性能的服务器负载过重。
随机均衡（Random）把来自网络的请求随机分配给内部中的多个服务器。
权重随机均衡（Weighted Random）
此种均衡算法类似于权重轮循算法，不过在处理请求分担时是个随机选择的过程。
响应速度均衡（Response Time 探测时间）
负载均衡设备对内部各服务器发出一个探测请求（例如 Ping），然后根据内部中各服务器对探测请求的最快响应时间来决定哪一台服务器来响应客户端的服务请求。此种均衡算法能较好的反映服务器的当前运行状态，但这最快响应时间仅仅指的是负载均衡设备与服务器间的最快响应时间，而不是客户端与服务器间的最快响应时间。
最少连接数均衡（Least Connection）
最少连接数均衡算法对内部中需负载的每一台服务器都有一个数据记录，记录当前该服务器正在处理的连接数量，当有新的服务连接请求时，将把当前请求分配给连接数最少的服务器，使均衡更加符合实际情况，负载更加均衡。此种均衡算法适合长时处理的请求服务，如 FTP。
处理能力均衡（CPU、内存）
此种均衡算法将把服务请求分配给内部中处理负荷（根据服务器 CPU 型号、CPU 数量、内存大小及当前连接数等换算而成）最轻的服务器，由于考虑到了内部服务器的处理能力及当前网络运行状况，所以此种均衡算法相对来说更加精确，尤其适合运用到第七层（应用层）负载均衡的情况下。
DNS 响应均衡（Flash DNS）
在此均衡算法下，分处在不同地理位置的负载均衡设备收到同一个客户端的域名解析请求，并在同一时间内把此域名解析成各自相对应服务器的 IP 地址并返回给客户端，则客户端将以最先收到的域名解析 IP 地址来继续请求服务，而忽略其它的 IP 地址响应。在种均衡策略适合应用在全局负载均衡的情况下，对本地负载均衡是没有意义的。
哈希算法
一致性哈希一致性 Hash，相同参数的请求总是发到同一提供者。当某一台提供者挂时，原本发往该提供者的请求，基于虚拟节点，平摊到其它提供者，不会引起剧烈变动。
IP 地址散列（保证客户端服务器对应关系稳定）
通过管理发送方 IP 和目的地 IP 地址的散列，将来自同一发送方的分组(或发送至同一目的地的分组)统一转发到相同服务器的算法。当客户端有一系列业务需要处理而必须和一个服务器反复通信时，该算法能够以流(会话)为单位，保证来自相同客户端的通信能够一直在同一服务器中进行处理。
URL 散列
通过管理客户端请求 URL 信息的散列，将发送至相同 URL 的请求转发至同一服务器的算法。
LVS
LVS 原理
*_IPVS_
LVS 的 IP 负载均衡技术是通过 IPVS 模块来实现的，IPVS 是 LVS 集群系统的核心软件，它的主要作用是：安装在 Director Server 上，同时在 Director Server 上虚拟出一个 IP 地址，用户必须通过这个虚拟的 IP 地址访问服务器。这个虚拟 IP 一般称为 LVS 的 VIP，即 Virtual IP。访问的请求首先经过 VIP 到达负载调度器，然后由负载调度器从 Real Server 列表中选取一个服务节点响应用户的请求。 在用户的请求到达负载调度器后，调度器如何将请求发送到提供服务的 Real Server 节点，而 Real Server 节点如何返回数据给用户，是 IPVS 实现的重点技术。
ipvs ： 工作于内核空间，主要用于使用户定义的策略生效 ipvsadm : 工作于用户空间，主要用于用户定义和管理集群服务的工具
ipvs 工作于内核空间的 INPUT 链上，当收到用户请求某集群服务时，经过 PREROUTING 链，经检查本机路由表，送往 INPUT 链；在进入 netfilter 的 INPUT 链时，ipvs 强行将请求报文通过ipvsadm 定义的集群服务策略的路径改为 FORWORD 链，将报文转发至后端真实提供服务的主机。
LVS NAT 模式
①.客户端将请求发往前端的负载均衡器，请求报文源地址是 CIP(客户端 IP),后面统称为 CIP)，目标地址为 VIP(负载均衡器前端地址，后面统称为 VIP)。
②.负载均衡器收到报文后，发现请求的是在规则里面存在的地址，那么它将客户端请求报文的目标地址改为了后端服务器的 RIP 地址并将报文根据算法发送出去。
③.报文送到 Real Server 后，由于报文的目标地址是自己，所以会响应该请求，并将响应报文返还给 LVS。
④.然后 lvs 将此报文的源地址修改为本机并发送给客户端。
注意：在 NAT 模式中，Real Server 的网关必须指向 LVS，否则报文无法送达客户端特点：
1、NAT 技术将请求的报文和响应的报文都需要通过 LB 进行地址改写，因此网站访问量比较大的时候 LB 负载均衡调度器有比较大的瓶颈，一般要求最多之能 10-20 台节点
2、只需要在 LB 上配置一个公网 IP 地址就可以了。
3、每台内部的 realserver 服务器的网关地址必须是调度器 LB 的内网地址。
4、NAT 模式支持对 IP 地址和端口进行转换。即用户请求的端口和真实服务器的端口可以不一致。
优点：
集群中的物理服务器可以使用任何支持 TCP/IP 操作系统，只有负载均衡器需要一个合法的 IP 地址。
缺点：
扩展性有限。当服务器节点（普通 PC 服务器）增长过多时,负载均衡器将成为整个系统的瓶颈，因为所有的请求包和应答包的流向都经过负载均衡器。当服务器节点过多时，大量的数据包都交汇在负载均衡器那，速度就会变慢！
LVS DR 模式（局域网改写 mac 地址）
①.客户端将请求发往前端的负载均衡器，请求报文源地址是 CIP，目标地址为 VIP。
②.负载均衡器收到报文后，发现请求的是在规则里面存在的地址，那么它将客户端请求报文的源 MAC地址改为自己DIP的MAC地址，目标MAC改为了RIP的MAC地址，并将此包发送给RS。 ③.RS 发现请求报文中的目的 MAC 是自己，就会将次报文接收下来，处理完请求报文后，将响应报文通过 lo 接口送给 eth0 网卡直接发送给客户端。
注意：需要设置 lo 接口的 VIP 不能响应本地网络内的 arp 请求。
总结：
1、通过在调度器 LB 上修改数据包的目的 MAC 地址实现转发。注意源地址仍然是 CIP，目的地址仍然是 VIP 地址。
2、请求的报文经过调度器，而 RS 响应处理后的报文无需经过调度器 LB，因此并发访问量大时使用效率很高（和 NAT 模式比）
3、因为 DR 模式是通过 MAC 地址改写机制实现转发，因此所有 RS 节点和调度器 LB 只能在一个局域网里面
4、RS 主机需要绑定 VIP 地址在 LO 接口（掩码 32 位）上，并且需要配置 ARP 抑制。
5、RS 节点的默认网关不需要配置成 LB，而是直接配置为上级路由的网关，能让 RS 直接出网就可以。
6、由于 DR 模式的调度器仅做 MAC 地址的改写，所以调度器 LB 就不能改写目标端口，那么 RS 服务器就得使用和 VIP 相同的端口提供服务。
7、直接对外的业务比如 WEB 等，RS 的 IP 最好是使用公网 IP。对外的服务，比如数据库等最好使用内网 IP。
优点：
和 TUN（隧道模式）一样，负载均衡器也只是分发请求，应答包通过单独的路由方法返回给客户端。与 VS-TUN 相比，VS-DR 这种实现方式不需要隧道结构，因此可以使用大多数操作系统做为物理服务器。
DR 模式的效率很高，但是配置稍微复杂一点，因此对于访问量不是特别大的公司可以用
haproxy/nginx取代。日1000-2000W PV或者并发请求1万一下都可以考虑用haproxy/nginx。
缺点：所有 RS 节点和调度器 LB 只能在一个局域网里面
LVS TUN 模式（IP 封装、跨网段）
①.客户端将请求发往前端的负载均衡器，请求报文源地址是 CIP，目标地址为 VIP。
②.负载均衡器收到报文后，发现请求的是在规则里面存在的地址，那么它将在客户端请求报文的首部再封装一层 IP 报文,将源地址改为 DIP，目标地址改为 RIP,并将此包发送给 RS。
③.RS 收到请求报文后，会首先拆开第一层封装,然后发现里面还有一层 IP 首部的目标地址是自己 lo 接口上的 VIP，所以会处理次请求报文，并将响应报文通过 lo 接口送给 eth0 网卡直接发送给客户端。
注意：需要设置 lo 接口的 VIP 不能在共网上出现。
总结：
1.TUNNEL 模式必须在所有的 realserver 机器上面绑定 VIP 的 IP 地址
2.TUNNEL 模式的 vip ———>realserver 的包通信通过 TUNNEL 模式，不管是内网和外网都能通信，所以不需要 lvs vip 跟 realserver 在同一个网段内。
3.TUNNEL 模式 realserver 会把 packet 直接发给 client 不会给 lvs 了
4.TUNNEL 模式走的隧道模式，所以运维起来比较难，所以一般不用。
优点：
负载均衡器只负责将请求包分发给后端节点服务器，而 RS 将应答包直接发给用户。所以，减少了负载均衡器的大量数据流动，负载均衡器不再是系统的瓶颈，就能处理很巨大的请求量，这种方式，一台负载均衡器能够为很多 RS 进行分发。而且跑在公网上就能进行不同地域的分发。
缺点：
隧道模式的 RS 节点需要合法 IP，这种方式需要所有的服务器支持”IP Tunneling”(IP
Encapsulation)协议，服务器可能只局限在部分 Linux 系统上。
LVS FULLNAT 模式
无论是 DR 还是 NAT 模式，不可避免的都有一个问题：LVS 和 RS 必须在同一个 VLAN 下，否则
LVS 无法作为 RS 的网关。这引发的两个问题是：
1、同一个 VLAN 的限制导致运维不方便，跨 VLAN 的 RS 无法接入。
2、LVS 的水平扩展受到制约。当 RS 水平扩容时，总有一天其上的单点 LVS 会成为瓶颈。
Full-NAT 由此而生，解决的是 LVS 和 RS 跨 VLAN 的问题，而跨 VLAN 问题解决后，LVS 和 RS 不再存在 VLAN 上的从属关系，可以做到多个 LVS 对应多个 RS，解决水平扩容的问题。
Full-NAT 相比 NAT 的主要改进是，在 SNAT/DNAT 的基础上，加上另一种转换，转换过程如下：
- 在包从 LVS 转到 RS 的过程中，源地址从客户端 IP 被替换成了 LVS 的内网 IP。内网 IP 之间可以通过多个交换机跨 VLAN 通信。目标地址从 VIP 修改为 RS IP.
- 当 RS 处理完接受到的包，处理完成后返回时，将目标地址修改为 LVS ip，原地址修改为 RS IP，最终将这个包返回给 LVS 的内网 IP，这一步也不受限于 VLAN。
- LVS 收到包后，在 NAT 模式修改源地址的基础上，再把 RS 发来的包中的目标地址从 LVS 内网 IP 改为客户端的 IP,并将原地址修改为 VIP。
Full-NAT 主要的思想是把网关和其下机器的通信，改为了普通的网络通信，从而解决了跨 VLAN 的问题。采用这种方式，LVS 和 RS 的部署在 VLAN 上将不再有任何限制，大大提高了运维部署的便利性。
总结
- FULL NAT 模式不需要 LBIP 和 realserver ip 在同一个网段；
- full nat 因为要更新 sorce ip 所以性能正常比 nat 模式下降 10%
Keepalive
keepalive 起初是为 LVS 设计的，专门用来监控 lvs 各个服务节点的状态，后来加入了 vrrp 的功能，因此除了 lvs，也可以作为其他服务（nginx，haproxy）的高可用软件。VRRP 是 virtual router redundancy protocal（虚拟路由器冗余协议）的缩写。VRRP 的出现就是为了解决静态路由出现的单点故障，它能够保证网络可以不间断的稳定的运行。所以 keepalive 一方面具有 LVS cluster node healthcheck 功能，另一方面也具有 LVS director failover。
Nginx 反向代理负载均衡
普通的负载均衡软件，如LVS，其实现的功能只是对请求数据包的转发、传递，从负载均衡下的节点服务器来看，接收到的请求还是来自访问负载均衡器的客户端的真实用户；而反向代理就不一样了，反向代理服务器在接收访问用户请求后，会代理用户 重新发起请求代理下的节点服务器，最后把数据返回给客户端用户。在节点服务器看来，访问的节点服务器的客户端用户就是反向代理服务器，而非真实的网站访问用户。
upstream_module 和健康检测
ngx_http_upstream_module 是负载均衡模块，可以实现网站的负载均衡功能即节点的健康检查，upstream 模块允许 Nginx 定义一组或多组节点服务器组，使用时可通过 proxy_pass 代理方式把网站的请求发送到事先定义好的对应 Upstream 组 的名字上。
| upstream模块内参数 | 参数说明 |
|---|---|
| weight | 服务器权重 |
| max_fails | Nginx 尝试连接后端主机失败的此时，这是值是配合 proxy_next_upstream、 fastcgi_next_upstream 和 memcached_next_upstream 这三个参数来使用的。当 Nginx 接收后端服务器返回这三个参数定义的状态码时，会将这个请求转发给正常工作的的后端服务器。如 404、503、503,max_files=1 |
| fail_timeout | max_fails 和 fail_timeout 一般会关联使用，如果某台 server 在 fail_timeout 时间内出现了 max_fails 次连接失败，那么 Nginx 会认为其已经挂掉，从而在 fail_timeout 时间内不再去请求它，fail_timeout 默认是 10s，max_fails 默认是 1，即默认情况只要是发生错误就认为服务器挂了，如果将 max_fails 设置为 0，则表示取消这项检查 |
| backup | 表示当前 server 是备用服务器，只有其它非 backup 后端服务器都挂掉了或很忙才会分配请求给它 |
| down | 标志服务器永远不可用，可配合 ip_hash 使用 |
upstream lvsServer{ server 191.168.1.11 weight=5 ; server 191.168.1.22:82; server example.com:8080 max_fails=2 fail_timeout=10s backup;#域名的话需要解析的哦，内网记得 hosts}
proxy_pass 请求转发
proxy_pass 指令属于 ngx_http_proxy_module 模块，此模块可以将请求转发到另一台服务器，在实际的反向代理工作中，会通过 location 功能匹配指定的 URI，然后把接收到服务匹配 URI 的请求通过 proyx_pass 抛给定义好的 upstream 节点池。
location /download/ { proxy_pass http://download/vedio/;}#这是前端代理节点的设置
交给后端 upstream 为 download 的节点
| proxy模块参数 | 说明 |
|---|---|
| proxy_next_upstream | 什么情况下将请求传递到下一个 upstream |
| proxy_limite_rate | 限制从后端服务器读取响应的速率 |
| proyx_set_header | 设置 http 请求 header 传给后端服务器节点，如：可实现让代理后端的服务器节点获取访问客户端的这是 ip |
| client_body_buffer_size | 客户端请求主体缓冲区大小 |
| proxy_connect_timeout | 代理与后端节点服务器连接的超时时间 |
| proxy_send_timeout | 后端节点数据回传的超时时间 |
| proxy_read_timeout | 设置 Nginx 从代理的后端服务器获取信息的时间，表示连接成功建立后，Nginx 等待后端服务器的响应时间 |
| proxy_buffer_size | 设置缓冲区大小 |
| proxy_buffers | 设置缓冲区的数量和大小 |
| proyx_busy_buffers_size | 用于设置系统很忙时可以使用的 proxy_buffers 大小，推荐为 proxy_buffers*2 |
| proxy_temp_file_write_size | 指定 proxy 缓存临时文件的大小 |
HAProxy
数据库
存储引擎
概念
数据库存储引擎是数据库底层软件组织，数据库管理系统（DBMS）使用数据引擎进行创建、查询、更新和删除数据。不同的存储引擎提供不同的存储机制、索引技巧、锁定水平等功能，使用不同的存储引擎，还可以 获得特定的功能。现在许多不同的数据库管理系统都支持多种不同的数据引擎。存储引擎主要有： 1. MyIsam , 2. InnoDB, 3. Memory, 4. Archive, 5. Federated 。
InnoDB（B+树）
InnoDB 底层存储结构为B+树， B树的每个节点对应innodb的一个page，page大小是固定的，一般设为 16k。其中非叶子节点只有键值，叶子节点包含完成数据。
适用场景：
1）经常更新的表，适合处理多重并发的更新请求。
2）支持事务。
3）可以从灾难中恢复（通过 bin-log 日志等）。
4）外键约束。只有他支持外键。
5）支持自动增加列属性 auto_increment。
TokuDB（Fractal Tree-节点带数据）
TokuDB 底层存储结构为 Fractal Tree,Fractal Tree 的结构与 B+树有些类似, 在 Fractal Tree
中，每一个 child 指针除了需要指向一个 child 节点外，还会带有一个 Message Buffer ，这个
Message Buffer 是一个 FIFO 的队列，用来缓存更新操作。
例如，一次插入操作只需要落在某节点的 Message Buffer 就可以马上返回了，并不需要搜索到叶子节点。这些缓存的更新会在查询时或后台异步合并应用到对应的节点中。
TokuDB 在线添加索引，不影响读写操作, 非常快的写入性能， Fractal-tree 在事务实现上有优势。 他主要适用于访问频率不高的数据或历史数据归档。
MyIASM
MyIASM是MySQL默认的引擎，但是它没有提供对数据库事务的支持，也不支持行级锁和外键，因此当 INSERT(插入)或 UPDATE(更新)数据时即写操作需要锁定整个表，效率便会低一些。
ISAM 执行读取操作的速度很快，而且不占用大量的内存和存储资源。在设计之初就预想数据组织成有固定长度的记录，按顺序存储的。—-ISAM 是一种静态索引结构。
缺点是它不 支持事务处理。
Memory
Memory（也叫 HEAP）堆内存：使用存在内存中的内容来创建表。每个 MEMORY 表只实际对应一个磁盘文件。MEMORY 类型的表访问非常得快，因为它的数据是放在内存中的，并且默认使用 HASH 索引。但是一旦服务关闭，表中的数据就会丢失掉。 Memory 同时支持散列索引和 B 树索引，B树索引可以使用部分查询和通配查询，也可以使用<,>和>=等操作符方便数据挖掘，散列索引相等的比较快但是对于范围的比较慢很多。
索引
索引（Index）是帮助 MySQL 高效获取数据的数据结构。常见的查询算法,顺序查找,二分查找,二叉排序树查找,哈希散列法,分块查找,平衡多路搜索树 B 树（B-tree）
常见索引原则有
*_1._选择唯一性索引
1． 唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录。
*_2._为经常需要排序、分组和联合操作的字段建立索引：
*_3_．为常作为查询条件的字段建立索引。
*_4_．限制索引的数目：
越多的索引，会使更新表变得很浪费时间。
尽量使用数据量少的索引
6． 如果索引的值很长，那么查询的速度会受到影响。
尽量使用前缀来索引
7． 如果索引字段的值很长，最好使用值的前缀来索引。
*_7_．删除不再使用或者很少使用的索引
*_8 ._ 最左前缀匹配原则，非常重要的原则。
10* .* 尽量选择区分度高的列作为索引
区分度的公式是表示字段不重复的比例
11* .*索引列不能参与计算，保持列“干净”：带函数的查询不参与索引。
12* .*尽量的扩展索引，不要新建索引。
数据库三范式
范式是具有最小冗余的表结构。3 范式具体如下：
第一范式(1st NF －列都是不可再分)
第一范式的目标是确保每列的原子性:如果每列都是不可再分的最小数据单元（也称为最小的原子单元），则满足第一范式（1NF）
第二范式(2nd NF－每个表只描述一件事情)
首先满足第一范式，并且表中非主键列不存在对主键的部分依赖。 第二范式要求每个表只描述一件事情。
第三范式(3rd NF－ 不存在对非主键列的传递依赖)
第三范式定义是，满足第二范式，并且表中的列不存在对非主键列的传递依赖。除了主键订单编号外，顾客姓名依赖于非主键顾客编号。
数据库是事务
事务(TRANSACTION)是作为单个逻辑工作单元执行的一系列操作，这些操作作为一个整体一起向系统提交，要么都执行、要么都不执行 。事务是一个不可分割的工作逻辑单元 事务必须具备以下四个属性，简称 ACID 属性：
原子性（*_Atomicity_）
- 事务是一个完整的操作。事务的各步操作是不可分的（原子的）；要么都执行，要么都不执行。
一致性（*_Consistency_）
- 当事务完成时，数据必须处于一致状态。
隔离性（*_Isolation_）
- 对数据进行修改的所有并发事务是彼此隔离的，这表明事务必须是独立的，它不应以任何方式依赖于或影响其他事务。
永久性（*_Durability_）
- 事务完成后，它对数据库的修改被永久保持，事务日志能够保持事务的永久性。
存储过程(特定功能的 SQL 语句集)
一组为了完成特定功能的 SQL 语句集，存储在数据库中，经过第一次编译后再次调用不需要再次编译，用户通过指定存储过程的名字并给出参数（如果该存储过程带有参数）来执行它。存储过程是数据库中的一个重要对象。
存储过程优化思路：
- 尽量利用一些 sql 语句来替代一些小循环，例如聚合函数，求平均函数等。
- 中间结果存放于临时表，加索引。
- 少使用游标。sql 是个集合语言，对于集合运算具有较高性能。而 cursors 是过程运算。比如对一个 100 万行的数据进行查询。游标需要读表 100 万次，而不使用游标则只需要少量几次读取。
- 事务越短越好。sqlserver 支持并发操作。如果事务过多过长，或者隔离级别过高，都会造成并发操作的阻塞，死锁。导致查询极慢，cpu 占用率极地。
- 使用 try-catch 处理错误异常。
- 查找语句尽量不要放在循环内。
触发器(一段能自动执行的程序)
触发器是一段能自动执行的程序，是一种特殊的存储过程，触发器和普通的存储过程的区别是：触发器是当对某一个表进行操作时触发。诸如：update、insert、delete 这些操作的时候，系统会自动调用执行该表上对应的触发器。SQL Server 2005 中触发器可以分为两类：DML 触发器和 DDL 触发器，其中 DDL 触发器它们会影响多种数据定义语言语句而激发，这些语句有 create、 alter、drop 语句。
数据库并发策略
并发控制一般采用三种方法，分别是乐观锁和悲观锁以及时间戳。
乐观锁
乐观锁认为一个用户读数据的时候，别人不会去写自己所读的数据；悲观锁就刚好相反，觉得自己读数据库的时候，别人可能刚好在写自己刚读的数据，其实就是持一种比较保守的态度；时间戳就是不加锁，通过时间戳来控制并发出现的问题。
悲观锁
悲观锁就是在读取数据的时候，为了不让别人修改自己读取的数据，就会先对自己读取的数据加锁，只有自己把数据读完了，才允许别人修改那部分数据，或者反过来说，就是自己修改某条数据的时候，不允许别人读取该数据，只有等自己的整个事务提交了，才释放自己加上的锁，才允许其他用户访问那部分数据。
时间戳
时间戳就是在数据库表中单独加一列时间戳，比如“TimeStamp”，每次读出来的时候，把该字段也读出来，当写回去的时候，把该字段加1，提交之前 ，跟数据库的该字段比较一次，如果比数据库的值大的话，就允许保存，否则不允许保存，这种处理方法虽然不使用数据库系统提供的锁机制，但是这种方法可以大大提高数据库处理的并发量，
以上悲观锁所说的加“锁”，其实分为几种锁，分别是：排它锁（写锁）和共享锁（读锁）。
数据库锁
行级锁
行级锁是一种排他锁，防止其他事务修改此行；在使用以下语句时，Oracle 会自动应用行级锁：
- INSERT、UPDATE、DELETE、SELECT … FOR UPDATE [OF columns] [WAIT n | NOWAIT];
- SELECT … FOR UPDATE 语句允许用户一次锁定多条记录进行更新
- 使用 COMMIT 或 ROLLBACK 语句释放锁。
表级锁
表示对当前操作的整张表加锁，它实现简单，资源消耗较少，被大部分 MySQL 引擎支持。最常使用的 MYISAM 与 INNODB 都支持表级锁定。表级锁定分为表共享读锁（共享锁）与表独占写锁（排他锁）。
页级锁
页级锁是 MySQL 中锁定粒度介于行级锁和表级锁中间的一种锁。表级锁速度快，但冲突多，行级冲突少，但速度慢。所以取了折衷的页级，一次锁定相邻的一组记录。BDB 支持页级锁
基于 Redis 分布式锁
- 获取锁的时候，使用 setnx（SETNX key val：当且仅当 key 不存在时，set 一个 key 为 val 的字符串，返回 1；若 key 存在，则什么都不做，返回 0）加锁，锁的 value 值为一个随机生成的 UUID，在释放锁的时候进行判断。并使用 expire 命令为锁添加一个超时时间，超过该时间则自动释放锁。
- 获取锁的时候调用 setnx，如果返回 0，则该锁正在被别人使用，返回 1 则成功获取锁。 还设置一个获取的超时时间，若超过这个时间则放弃获取锁。
- 释放锁的时候，通过 UUID 判断是不是该锁，若是该锁，则执行 delete 进行锁释放。
分区分表
分库分表有垂直切分和水平切分两种。
垂直切分(*按照功能模块)*
§ 将表按照功能模块、关系密切程度划分出来，部署到不同的库上。例如，我们会建立定义数据库 workDB、商品数据库 payDB、用户数据库 userDB、日志数据库 logDB 等，分别用于存储项目数据定义表、商品定义表、用户数据表、日志数据表等。
水平切分(*按照规则划分存储)*
§ 当一个表中的数据量过大时，我们可以把该表的数据按照某种规则，例如 userID 散列，进行划分，然后存储到多个结构相同的表，和不同的库上。
两阶段提交协议
分布式事务是指会涉及到操作多个数据库的事务,在分布式系统中，各个节点之间在物理上相互独立，通过网络进行沟通和协调。
XA 就是 X/Open DTP 定义的交易中间件与数据库之间的接口规范（即接口函数），交易中间件用它来通知数据库事务的开始、结束以及提交、回滚等。 XA 接口函数由数据库厂商提供。
二阶段提交(Two-phaseCommit)是指，在计算机网络以及数据库领域内，为了使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的一种算法(Algorithm)。通常，二阶段提交也被称为是一种协议(Protocol))。在分布式系统中，每个节点虽然可以知晓自己的操作时成功或者失败，却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时，为了保持事务的 ACID 特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。因此，二阶段提交的算法思路可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者的反馈情报决定各参与者是否要提交操作还是中止操作。
准备阶段
事务协调者(事务管理器)给每个参与者(资源管理器)发送 Prepare 消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的 redo 和 undo 日志，但不提交，到达一种“万事俱备，只欠东风”的状态。
提交阶段
如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
缺点
同步阻塞问题
1、 执行过程中，所有参与节点都是事务阻塞型的。
单点故障
2、 由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。
数据不一致（脑裂问题）
3、 在二阶段提交的阶段二中，当协调者向参与者发送 commit 请求之后，发生了局部网络异常或者在发送 commit 请求过程中协调者发生了故障，导致只有一部分参与者接受到了 commit 请求。于是整个分布式系统便出现了数据部一致性的现象(脑裂现象)。
二阶段无法解决的问题（数据状态不确定）
4、 协调者再发出 commit 消息之后宕机，而唯一接收到这条消息的参与者同时也宕机了。那么即使协调者通过选举协议产生了新的协调者，这条事务的状态也是不确定的，没人知道事务是否被已经提交。
三阶段提交协议
三 阶 段 提 交 （ Three-phase commit ） ， 也 叫 三 阶 段 提 交 协 议 （ Three-phase commit protocol），是二阶段提交（2PC）的改进版本。
与两阶段提交不同的是，三阶段提交有两个改动点。
1、引入超时机制。同时在协调者和参与者中都引入超时机制。
2、在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。也就是说，除了引入超时机制之外，3PC 把 2PC 的准备阶段再次一分为二，这样三阶段提交就有 CanCommit、PreCommit、DoCommit 三个阶段。
CanCommit 阶段
协调者向参与者发送 commit 请求，参与者如果可以提交就返回 Yes 响应，否则返回 No 响应。
PreCommit 阶段
协调者根据参与者的反应情况来决定是否可以继续进行，有以下两种可能。假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行假如有任何一个参与者向协调者发送了 No 响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。
doCommit 阶段
该阶段进行真正的事务提交，主要包含 1.协调这发送提交请求 2.参与者提交事务 3.参与者响应反馈（ 事务提交完之后，向协调者发送 Ack 响应。）4.协调者确定完成事务。
柔性事务
柔性事务
在电商领域等互联网场景下，传统的事务在数据库性能和处理能力上都暴露出了瓶颈。在分布式领域基于 CAP 理论以及 BASE 理论，有人就提出了 柔性事务 的概念。CAP（一致性、可用性、分区容忍性）理论大家都理解很多次了，这里不再叙述。说一下 BASE 理论，它是在 CAP 理论的基础之上的延伸。包括 基本可用（Basically Available）、柔性状态（Soft State）、最终一致性（Eventual Consistency）。
通常所说的柔性事务分为：两阶段型、补偿型、异步确保型、最大努力通知型几种。
两阶段型
1、 就是分布式事务两阶段提交，对应技术上的 XA、JTA/JTS。这是分布式环境下事务处理的典型模式。
补偿型
2、 TCC 型事务（Try/Confirm/Cancel）可以归为补偿型。
WS-BusinessActivity 提供了一种基于补偿的 long-running 的事务处理模型。服务器 A 发起事务，服务器 B 参与事务，服务器 A 的事务如果执行顺利，那么事务 A 就先行提交，如果事务 B 也执行顺利，则事务 B 也提交，整个事务就算完成。但是如果事务 B 执行失败，事务 B 本身回滚，这时事务 A 已经被提交，所以需要执行一个补偿操作，将已经提交的事务 A 执行的操作作反操作，恢复到未执行前事务 A 的状态。这样的 SAGA 事务模型，是牺牲了一定的隔离性和一致性的，但是提高了 long-running 事务的可用性。
3、 通过将一系列同步的事务操作变为基于消息执行的异步操作, 避免了分布式事务中的同步阻塞操作的影响。
4、 这是分布式事务中要求最低的一种, 也可以通过消息中间件实现, 与前面异步确保型操作不同的一点是, 在消息由 MQ Server 投递到消费者之后, 允许在达到最大重试次数之后正常结束事务。
CAP
CAP 原则又称 CAP 定理，指的是在一个分布式系统中， Consistency（一致性）、 Availability
（可用性）、Partition tolerance（分区容错性），三者不可得兼。
一致性（C）：
- 在分布式系统中的所有数据备份，在同一时刻是否同样的值。（等同于所有节点访问同一份最新的数据副本）
可用性（A）：
- 在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。（对数据更新具备高可用性）
分区容忍性（P）：
- 以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在 C 和 A 之间做出选择。
一致性算法
Paxos
Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。zookeeper 使用的 zab 算法是该算法的一个实现。 在 Paxos 算法中，有三种角色：Proposer，Acceptor，Learners
Paxos 三种角色：Proposer，Acceptor，Learners
*_Proposer_：
只要 Proposer 发的提案被半数以上 Acceptor 接受，Proposer 就认为该提案里的 value 被选定了。
*_Acceptor_：
只要 Acceptor 接受了某个提案，Acceptor 就认为该提案里的 value 被选定了。
*_Learner_：
Acceptor 告诉 Learner 哪个 value 被选定，Learner 就认为那个 value 被选定。
Paxos 算法分为两个阶段。具体如下：
阶段一（准*_leader_确定 ）：
(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。 (b) 如果一个 Acceptor 收到一个编号为 N 的 Prepare 请求，且 N 大于该 Acceptor 已经响应过的所有 Prepare 请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给 Proposer，同时该 Acceptor 承诺不再接受任何编号小于 N 的提案。
阶段二（*_leader_确认）：
(a) 如果 Proposer 收到半数以上 Acceptor 对其发出的编号为 N 的 Prepare 请求的响应，那么它就会发送一个针对[N,V]提案的 Accept 请求给半数以上的 Acceptor。注意：V 就是收到的响应中编号最大的提案的 value，如果响应中不包含任何提案，那么 V 就由 Proposer 自己决定。
(b) 如果 Acceptor 收到一个针对编号为 N 的提案的 Accept 请求，只要该 Acceptor 没有对编号大于 N 的 Prepare 请求做出过响应，它就接受该提案。
Zab
ZAB( ZooKeeper Atomic Broadcast , ZooKeeper 原子消息广播协议）协议包括两种基本的模式：崩溃恢复和消息广播
- 当整个服务框架在启动过程中，或是当 Leader 服务器出现网络中断崩溃退出与重启等异常情况时，ZAB 就会进入恢复模式并选举产生新的 Leader 服务器。
- 当选举产生了新的 Leader 服务器，同时集群中已经有过半的机器与该 Leader 服务器完成了状态同步之后，ZAB 协议就会退出崩溃恢复模式，进入消息广播模式。
- 当有新的服务器加入到集群中去，如果此时集群中已经存在一个 Leader 服务器在负责进行消息广播，那么新加入的服务器会自动进入数据恢复模式，找到 Leader 服务器，并与其进行数据同步，然后一起参与到消息广播流程中去。
以上其实大致经历了三个步骤：
1.*崩溃恢复：主要就是Leader* 选举过程
2.*数据同步：Leader*服务器与其他服务器进行数据同步
3.*消息广播：Leader*服务器将数据发送给其他服务器说明：zookeeper 章节对该协议有详细描述。
Raft
与 Paxos 不同 Raft 强调的是易懂（Understandability），Raft 和 Paxos 一样只要保证 n/2+1 节点正常就能够提供服务；raft 把算法流程分为三个子问题：选举（Leader election）、日志复制
（Log replication）、安全性（Safety）三个子问题。
1. 角色
Raft 把集群中的节点分为三种状态：Leader、 Follower 、Candidate，理所当然每种状态负责的任务也是不一样的，Raft 运行时提供服务的时候只存在 Leader 与 Follower 两种状态；
Leader*（领导者-*日志管理）
负责日志的同步管理，处理来自客户端的请求，与 Follower 保持这 heartBeat 的联系；
Follower*（追随者-*日志同步）
刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求，把请求到 Follower 的事务转发给 Leader；
Candidate*（候选者-*负责选票）
负责选举投票，Raft 刚启动时由一个节点从 Follower 转为 Candidate 发起选举，选举出
Leader 后从 Candidate 转为 Leader 状态；
2. Term（任期）
在 Raft 中使用了一个可以理解为周期（第几届、任期）的概念，用 Term 作为一个周期，每个 Term 都是一个连续递增的编号，每一轮选举都是一个 Term 周期，在一个 Term 中只能产生一个 Leader；当某节点收到的请求中 Term 比当前 Term 小时则拒绝该请求。
3. 选举（Election）
选举定时器
Raft 的选举由定时器来触发，每个节点的选举定时器时间都是不一样的，开始时状态都为 Follower 某个节点定时器触发选举后 Term 递增，状态由 Follower 转为 Candidate，向其他节点发起 RequestVote RPC 请求，这时候有三种可能的情况发生：
1：该RequestVote请求接收到n/2+1（过半数）个节点的投票，从Candidate 转为Leader，向其他节点发送 heartBeat 以保持 Leader 的正常运转。
2：在此期间如果收到其他节点发送过来的 AppendEntries RPC 请求，如该节点的 Term 大则当前节点转为 Follower，否则保持 Candidate 拒绝该请求。
3：Election timeout 发生则 Term 递增，重新发起选举
在一个 Term 期间每个节点只能投票一次，所以当有多个 Candidate 存在时就会出现每个 Candidate 发起的选举都存在接收到的投票数都不过半的问题，这时每个 Candidate 都将 Term 递增、重启定时器并重新发起选举，由于每个节点中定时器的时间都是随机的，所以就不会多次存在有多个 Candidate 同时发起投票的问题。
在 Raft 中当接收到客户端的日志（事务请求）后先把该日志追加到本地的 Log 中，然后通过 heartbeat 把该 Entry 同步给其他 Follower，Follower 接收到日志后记录日志然后向 Leader 发送 ACK，当 Leader 收到大多数（n/2+1）Follower 的 ACK 信息后将该日志设置为已提交并追加到本地磁盘中，通知客户端并在下个 heartbeat 中 Leader 将通知所有的 Follower 将该日志存储在自己的本地磁盘中。
4. 安全性（Safety）
安全性是用于保证每个节点都执行相同序列的安全机制如当某个 Follower 在当前 Leader commit Log 时变得不可用了，稍后可能该 Follower 又会倍选举为 Leader，这时新 Leader 可能会用新的 Log 覆盖先前已 committed 的 Log，这就是导致节点执行不同序列；Safety 就是用于保证选举出来的 Leader 一定包含先前 commited Log 的机制；
选举安全性（Election Safety）：每个 Term 只能选举出一个 Leader
Leader 完整性（Leader Completeness）：这里所说的完整性是指 Leader 日志的完整性， Raft 在选举阶段就使用 Term 的判断用于保证完整性：当请求投票的该 Candidate 的 Term 较大或 Term 相同 Index 更大则投票，该节点将容易变成 leader。
5. raft 协议和 zab 协议区别相同点
§ 采用 quorum 来确定整个系统的一致性,这个 quorum 一般实现是集群中半数以上的服务器,
§ zookeeper 里还提供了带权重的 quorum 实现.
§ 都由 leader 来发起写操作.
§ 都采用心跳检测存活性
§ leader election 都采用先到先得的投票方式不同点
§ zab 用的是 epoch 和 count 的组合来唯一表示一个值, 而 raft 用的是 term 和 index
§ zab 的 follower 在投票给一个 leader 之前必须和 leader 的日志达成一致,而 raft 的 follower 则简单地说是谁的 term 高就投票给谁
raft 协议的心跳是从 leader 到 follower, 而 zab 协议则相反
§ raft 协议数据只有单向地从 leader 到 follower(成为 leader 的条件之一就是拥有最新的 log),
而 zab 协议在 discovery 阶段, 一个 prospective leader 需要将自己的 log 更新为 quorum 里面最新的 log,然后才好在 synchronization 阶段将 quorum 里的其他机器的 log 都同步到一致.
NWR
*_N_：在分布式存储系统中，有多少份备份数据
W*：代表一次成功的更新操作要求至少有w*份数据写入成功
R*： 代表一次成功的读数据操作要求至少有R*份数据成功读取
NWR值的不同组合会产生不同的一致性效果，当W+R>N的时候，整个系统对于客户端来讲能保
证强一致性。而如果 R+W<=N，则无法保证数据的强一致性。以常见的 N=3、W=2、R=2 为例：
N=3，表示，任何一个对象都必须有三个副本（Replica），W=2 表示，对数据的修改操作（Write）只需要在 3 个 Replica 中的 2 个上面完成就返回，R=2 表示，从三个对象中要读取到 2 个数据对象，才能返回。
Gossip
Gossip 算法又被称为反熵（Anti-Entropy），熵是物理学上的一个概念，代表杂乱无章，而反熵就是在杂乱无章中寻求一致，这充分说明了 Gossip 的特点：在一个有界网络中，每个节点都随机地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的状态都是一致的，当然这也是疫情传播的特点。
一致性 Hash
一致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。 Memcached client 也选择这种算法，解决将 key-value 均匀分配到众多 Memcached server 上的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删 Memcached Server 的问题 (增删 server 会导致同一个 key,在 get 操作时分配不到数据真正存储的 server，命中率会急剧下
降)。
一致性 Hash 特性
§ 平衡性(Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。
§ 单调性(Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。容易看到，上面的简单求余算法 hash(object)%N 难以满足单调性要求。
§ 平滑性(Smoothness)：平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致的。
一致性 Hash 原理
1.*建构环形hash* 空间：
- 考虑通常的 hash 算法都是将 value 映射到一个 32 为的 key 值，也即是 0~2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（ 0 ）尾（ 2^32-1 ）相接的圆环。
2.*把需要缓存的内容(*对象)*映射到hash* 空间
- 接下来考虑 4 个对象 object1~object4 ，通过 hash 函数计算出的 hash 值 key 在环上的分布
3.*把服务器(*节点)*映射到hash* 空间
- Consistent hashing 的基本思想就是将对象和 cache 都映射到同一个 hash 数值空间中，并且使用相同的 hash 算法。一般的方法可以使用 服务器(节点) 机器的 IP 地址或者机器名作为 hash 输入。
*_4._把对象映射到服务节点
- 现在服务节点和对象都已经通过同一个 hash 算法映射到 hash 数值空间中了，首先确定对象 hash 值在环上的位置，从此位置沿环顺时针“行走”，第一台遇到的服务器就是其应该定位的服务器。
考察*_cache_ 的变动
- 通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时， cache 会失效。
5.1 移除 cache：考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是那些沿 cache B 逆时针遍历直到下一个 cache （ cache C ）之间的对象。
5.2 添加 cache：再考虑添加一台新的 cache D 的情况，这时受影响的将仅是那些沿 cache D 逆时针遍历直到下一个 cache 之间的对象，将这些对象重新映射到 cache D 上即可。
虚拟节点
hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：虚拟节点（ virtual node ）是实际节点在 hash 空间的复制品（ replica ），一实际个节点对应了若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash 值排列。
仍以仅部署 cache A 和 cache C 的情况为例。现在我们引入虚拟节点，并设置“复制个数”为 2 ，这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A； cache C1, cache C2 代表了 cache C 。此时，对象到“虚拟节点”的映射关系为：
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache
C 上；平衡性有了很大提高。
引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所在 cache 时的映射关系如下图 所示。
JAVA 算法
二分查找
又叫折半查找，要求待查找的序列有序。每次取中间位置的值与待查关键字比较，如果中间位置的值比待查关键字大，则在前半部分循环这个查找的过程，如果中间位置的值比待查关键字小，则在后半部分循环这个查找的过程。直到查找到了为止，否则序列中没有待查的关键字。
public static int biSearch(int []array,int a){int lo=0;int hi=array.length-1;int mid;while(lo<=hi){mid=(lo+hi)/2;//中间位置if(array[mid]==a){return mid+1;}else if(array[mid]<a){ //向右查找lo=mid+1;}else{ //向左查找hi=mid-1;}}return -1;}
冒泡排序算法
（1）比较前后相邻的二个数据，如果前面数据大于后面的数据，就将这二个数据交换。
（2）这样对数组的第 0 个数据到 N-1 个数据进行一次遍历后，最大的一个数据就“沉”到数组第
N-1 个位置。
（3）N=N-1，如果 N 不为 0 就重复前面二步，否则排序完成。
public static void bubbleSort1(int [] a, int n){int i, j;for(i=0; i<n; i++){//表示 n 次排序过程。for(j=1; j<n-i; j++){if(a[j-1] > a[j]){//前面的数字大于后面的数字就交换//交换 a[j-1]和 a[j]int temp; temp = a[j-1]; a[j-1] = a[j]; a[j]=temp;}}}}
插入排序算法
通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应的位置并插入。插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。
如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是(n2)。
public void sort(int arr[]){for(int i =1; i<arr.length;i++){//插入的数int insertVal = arr[i];//被插入的位置(准备和前一个数比较)int index = i-1;//如果插入的数比被插入的数小while(index>=0&&insertVal<arr[index]){//将把 arr[index] 向后移动 arr[index+1]=arr[index];//让 index 向前移动index--;}//把插入的数放入合适位置arr[index+1]=insertVal;}}
快速排序算法
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。
一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
public void sort(int[] a,int low,int high){int start = low;int end = high;int key = a[low];while(end>start){//从后往前比较while(end>start&&a[end]>=key)//如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较end--;if(a[end]<=key){int temp = a[end];a[end] = a[start];a[start] = temp;}//从前往后比较while(end>start&&a[start]<=key)//如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置start++;if(a[start]>=key){int temp = a[start];a[start] = a[end];a[end] = temp;}//此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用}//递归if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1 if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1 到最后一个}}
希尔排序算法
基本思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
- 操作方法：
选择一个增量序列 t1，t2，…，tk，其中 ti>tj，tk=1；
- 按增量序列个数 k，对序列进行 k 趟排序；
- 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
private void shellSort(int[] a) {int dk = a.length/2;while( dk >= 1 ){ShellInsertSort(a, dk);dk = dk/2;}}private void ShellInsertSort(int[] a, int dk) {//类似插入排序，只是插入排序增量是 1，这里增量是 dk,把 1 换成 dk 就可以了for(int i=dk;i<a.length;i++){if(a[i]<a[i-dk]){int j;int x=a[i];//x 为待插入元素a[i]=a[i-dk];for(j=i-dk; j>=0 && x<a[j];j=j-dk){//通过循环，逐个后移一位找到要插入的位置。a[j+dk]=a[j];}a[j+dk]=x;//插入}}}
归并排序算法
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
** @param data* 数组对象* @param left* 左数组的第一个元素的索引* @param center* 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引* @param right* 右数组最后一个元素的索引*/public static void merge(int[] data, int left, int center, int right) {// 临时数组 int[] tmpArr = new int[data.length];// 右数组第一个元素索引int mid = center + 1;// third 记录临时数组的索引int third = left;// 缓存左数组第一个元素的索引int tmp = left; while (left <= center && mid <= right) {// 从两个数组中取出最小的放入临时数组if (data[left] <= data[mid]) { tmpArr[third++] = data[left++];} else {tmpArr[third++] = data[mid++];}}// 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）while (mid <= right) { tmpArr[third++] = data[mid++];public class MergeSortTest {public static void main(String[] args) {int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 }; print(data);mergeSort(data);System.out.println("排序后的数组：");print(data);}public static void mergeSort(int[] data) {sort(data, 0, data.length - 1);}public static void sort(int[] data, int left, int right) { if (left >= right)return;// 找出中间索引int center = (left + right) / 2;// 对左边数组进行递归sort(data, left, center);// 对右边数组进行递归sort(data, center + 1, right);// 合并merge(data, left, center, right);print(data);}/*** 将两个数组进行归并，归并前面 2 个数组已有序，归并后依然有序** @param data* 数组对象* @param left* 左数组的第一个元素的索引* @param center* 左数组的最后一个元素的索引，center+1 是右数组第一个元素的索引* @param right* 右数组最后一个元素的索引*/public static void merge(int[] data, int left, int center, int right) {// 临时数组 int[] tmpArr = new int[data.length];// 右数组第一个元素索引int mid = center + 1;// third 记录临时数组的索引int third = left;// 缓存左数组第一个元素的索引int tmp = left;while (left <= center && mid <= right) {// 从两个数组中取出最小的放入临时数组if (data[left] <= data[mid]) { tmpArr[third++] = data[left++];} else {tmpArr[third++] = data[mid++];}}// 剩余部分依次放入临时数组（实际上两个 while 只会执行其中一个）while (mid <= right) {tmpArr[third++] = data[mid++];}while (left <= center) {tmpArr[third++] = data[left++];}// 将临时数组中的内容拷贝回原数组中// （原 left-right 范围的内容被复制回原数组）while (tmp <= right) {data[tmp] = tmpArr[tmp++];}}public static void print(int[] data) {for (int i = 0; i < data.length; i++) {System.out.print(data[i] + "\t");}System.out.println();}}
桶排序算法
桶排序的基本思想是： 把数组 arr 划分为 n 个大小相同子区间（桶），每个子区间各自排序，最后合并 。计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
1.找出待排序数组中的最大值 max、最小值 min
2.我们使用 动态数组 ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(maxmin)/arr.length+1
3.遍历数组 arr，计算每个元素 arr[i] 放的桶
4.每个桶各自排序
public static void bucketSort(int[] arr){int max = Integer.MIN_VALUE;int min = Integer.MAX_VALUE;for(int i = 0; i < arr.length; i++){max = Math.max(max, arr[i]);min = Math.min(min, arr[i]);}//创建桶int bucketNum = (max - min) / arr.length + 1;ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){bucketArr.add(new ArrayList<Integer>());}//将每个元素放入桶for(int i = 0; i < arr.length; i++){int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]);}//对每个桶进行排序for(int i = 0; i < bucketArr.size(); i++){Collections.sort(bucketArr.get(i));}}
基数排序算法
将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
public class radixSort {inta[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,101,56,17,18,23,34,15,35,25,53,51};public radixSort(){sort(a);for(inti=0;i<a.length;i++){ System.out.println(a[i]);}}public void sort(int[] array){//首先确定排序的趟数;int max=array[0];for(inti=1;i<array.length;i++){if(array[i]>max){max=array[i];}}int time=0; //判断位数; while(max>0){ max/=10; time++;}//建立 10 个队列;List<ArrayList> queue=newArrayList<ArrayList>(); for(int i=0;i<10;i++){ArrayList<Integer>queue1=new ArrayList<Integer>(); queue.add(queue1);}//进行 time 次分配和收集;for(int i=0;i<time;i++){ //分配数组元素; for(intj=0;j<array.length;j++){//得到数字的第 time+1 位数;int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10, i); ArrayList<Integer>queue2=queue.get(x); queue2.add(array[j]); queue.set(x, queue2);}int count=0;//元素计数器;//收集队列元素; for(int k=0;k<10;k++){ while(queue.get(k).size()>0){ArrayList<Integer>queue3=queue.get(k); array[count]=queue3.get(0); queue3.remove(0); count++;}}}}}
剪枝算法
在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
最短路径算法
从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra 算法，Bellman-Ford 算法，Floyd 算法和 SPFA 算法等。
最大子数组算法
最长公共子序算法
最小生成树算法
现在假设有一个很实际的问题：我们要在 n 个城市中建立一个通信网络，则连通这 n 个城市需要布置 n-1 一条通信线路，这个时候我们需要考虑如何在成本最低的情况下建立这个通信网？
于是我们就可以引入连通图来解决我们遇到的问题，n 个城市就是图上的 n 个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是我们搭建这条线路所需要的成本，所以现在我们有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST 性质（假设
N=(V,{E})是一个连通网，U 是顶点集 V 的一个非空子集，如果（u，v）是一条具有最小权值的边，其中 u 属于U，v 属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用 MST 性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。
数据结构
栈（stack）
栈（stack）是限制插入和删除只能在一个位置上进行的表，该位置是表的末端，叫做栈顶（top）。它是后进先出（LIFO）的。对栈的基本操作只有 push（进栈）和 pop（出栈）两种，前者相当于插入，后者相当于删除最后的元素。
队列（queue）
队列是一种特殊的线性表,特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。
链表（Link）
链表是一种数据结构，和数组同级。比如，Java 中我们使用的 ArrayList，其实现原理是数组。而LinkedList 的实现原理就是链表了。链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
散列表（Hash Table）
散列表（Hash table，也叫哈希表）是一种查找算法，与链表、树等算法不同的是，散列表算法在查找时不需要进行一系列和关键字（关键字是数据元素中某个数据项的值，用以标识一个数据元素）的比较操作。
散列表算法希望能尽量做到不经过任何比较，通过一次存取就能得到所查找的数据元素，因而必须要在数据元素的存储位置和它的关键字（可用key表示）之间建立一个确定的对应关系，使每个关键字和散列表中一个唯一的存储位置相对应。因此在查找时，只要根据这个对应关系找到给定关键字在散列表中的位置即可。这种对应关系被称为散列函数(可用 h(key)表示)。
用的构造散列函数的方法有：
（1）直接定址法： 取关键字或关键字的某个线性函数值为散列地址。
即：h(key) = key 或 h(key) = a * key + b，其中 a 和 b 为常数。
（2）数字分析法
（3）平方取值法： 取关键字平方后的中间几位为散列地址。
（4）折叠法：将关键字分割成位数相同的几部分，然后取这几部分的叠加和作为散列地址。
（5）除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址，即：h(key) = key MOD p p ≤ m
（6）随机数法：选择一个随机函数，取关键字的随机函数值为它的散列地址，即：h(key) = random(key)
排序二叉树
首先如果普通二叉树每个节点满足：左子树所有节点值小于它的根节点值，且右子树所有节点值大于它的根节点值，则这样的二叉树就是排序二叉树。
插入操作
首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节点，则到左子树中寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。
删除操作
删除操作主要分为三种情况，即要删除的节点无子节点，要删除的节点只有一个子节点，要删除的节点有两个子节点。
- 对于要删除的节点无子节点可以直接删除，即让其父节点将该子节点置空即可。
- 对于要删除的节点只有一个子节点，则替换要删除的节点为其子节点。
- 对于要删除的节点有两个子节点，则首先找该节点的替换节点（即右子树中最小的节点），接着替换要删除的节点为替换节点，然后删除替换节点。
查询操作
查找操作的主要流程为：先和根节点比较，如果相同就返回，如果小于根节点则到左子树中递归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。
红黑树
R-B Tree，全称是 Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。
红黑树的特性
（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
左旋
对 x 进行左旋，意味着，将“x 的右孩子”设为“x 的父亲节点”；即，将 x 变成了一个左节点(x 成了为 z 的左孩子)。 因此，左旋中的“左”，意味着“被旋转的节点将变成一个左节点”。
LEFT-ROTATE(T, x)y ← right[x]// 前提：这里假设 x 的右孩子为 y。下面开始正式操作 right[x] ← left[y]// 将 “y 的左孩子” 设为 “x 的右孩子”，即 将β设为 x 的右孩子 p[left[y]] ← x// 将 “x” 设为 “y 的左孩子的父亲”，即 将β的父亲设为 x p[y] ← p[x]// 将 “x 的父亲” 设为 “y 的父亲”if p[x] = nil[T]then root[T] ← y// 情况 1：如果 “x 的父亲” 是空节点，则将 y 设为根节点else if x = left[p[x]]then left[p[x]] ← y// 情况 2：如果 x 是它父节点的左孩子，则将 y 设为“x 的父节点的左孩子”else right[p[x]] ← y// 情况 3：(x 是它父节点的右孩子) 将 y 设为“x 的父节点的右孩子”left[y] ← x// 将 “x” 设为 “y 的左孩子” p[x] ← y// 将 “x 的父节点” 设为 “y”
右旋
对 x 进行右旋，意味着，将“x 的左孩子”设为“x 的父亲节点”；即，将 x 变成了一个右节点(x 成了为 y 的右孩子)！ 因此，右旋中的“右”，意味着“被旋转的节点将变成一个右节点”。
RIGHT-ROTATE(T, y)x ← left[y]// 前提：这里假设 y 的左孩子为 x。下面开始正式操作 left[y] ← right[x]// 将 “x 的右孩子” 设为 “y 的左孩子”，即 将β设为 y 的左孩子 p[right[x]] ← y// 将 “y” 设为 “x 的右孩子的父亲”，即 将β的父亲设为 y p[x] ← p[y]// 将 “y 的父亲” 设为 “x 的父亲”if p[y] = nil[T]then root[T] ← x// 情况 1：如果 “y 的父亲” 是空节点，则将 x 设为根节点else if y = right[p[y]]then right[p[y]] ← x// 情况 2：如果 y 是它父节点的右孩子，则将 x 设为“y 的父节点的左孩子”else left[p[y]] ← x// 情况 3：(y 是它父节点的左孩子) 将 x 设为“y 的父节点的左孩子”right[x] ← y// 将 “y” 设为 “x 的右孩子” p[y] ← x// 将 “y 的父节点” 设为 “x”
添加
第一步: 将红黑树当作一颗二叉查找树，将节点插入。
第二步：将插入的节点着色为”红色”。
根据被插入节点的父节点的情况，可以将”当节点 z 被着色为红色节点，并插入二叉树”划分为三种情况来处理。
① 情况说明：被插入的节点是根节点。
处理方法：直接把此节点涂为黑色。
② 情况说明：被插入的节点的父节点是黑色。
处理方法：什么也不需要做。节点被插入后，仍然是红黑树。
③ 情况说明：被插入的节点的父节点是红色。这种情况下，被插入节点是一定存在非空祖父节点的；进一步的讲，被插入节点也一定存在叔叔节点(即使叔叔节点为空，我们也视之为存在，空节点本身就是黑色节点)。理解这点之后，我们依据”叔叔节点的情况”，将这种情况进一步划分为 3 种情况(Case)。
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。
删除
第一步：将红黑树当作一颗二叉查找树，将节点删除。
这和”删除常规二叉查找树中删除节点的方法是一样的”。分 3 种情况：
① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就 OK 了。
② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给
“该节点的内容”；之后，删除“它的后继节点”。
第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。
因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树。
选择重着色 3 种情况。
① 情况说明：x 是“红+黑”节点。
处理方法：直接把 x 设为黑色，结束。此时红黑树性质全部恢复。
② 情况说明：x 是“黑+黑”节点，且 x 是根。
处理方法：什么都不做，结束。此时红黑树性质全部恢复。
③ 情况说明：x 是“黑+黑”节点，且 x 不是根。
处理方法：这种情况又可以划分为 4 种子情况。这 4 种子情况如下表所示：
红黑树(五)之 Java的实现之 Java的实现)
B-TREE
B-tree 又叫平衡多路查找树。一棵 m 阶的 B-tree (m 叉树)的特性如下（其中 ceil(x)是一个取上限的函数）：
- 树中每个结点至多有 m 个孩子；
- 除根结点和叶子结点外，其它每个结点至少有有 ceil(m / 2)个孩子；
- 若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；
- 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，实际上这些结点不存在，指向这些结点的指针都为 null)；
- 每个非终端结点中包含有 n 个关键字信息： (n，P0，K1，P1，K2，P2，……，Kn，Pn)。其中：
a) Ki (i=1…n)为关键字，且关键字按顺序排序 K(i-1)< Ki。
b) Pi 为指向子树根的接点，且指针 P(i-1)指向子树种所有结点的关键字均小于 Ki，但都大于 K(i-1)。
c) 关键字的个数 n 必须满足： ceil(m / 2)-1 <= n <= m-1。
一棵 m 阶的 B+tree 和 m 阶的 B-tree 的差异在于：
1.有 n 棵子树的结点中含有 n 个关键字； (B-tree 是 n 棵子树有 n-1 个关键字)
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (B-tree 的叶子节点并没有包括全部需要查找的信息)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。
(B-tree 的非终节点也包含需要查找的有效信息)
位图
位图的原理就是用一个 bit 来标识一个数字是否存在，采用一个 bit 来存储一个数据，所以这样可以大大的节省空间。 bitmap 是很常用的数据结构，比如用于 Bloom Filter 中；用于无重复整数的排序等等。bitmap 通常基于数组来实现，数组中每个元素可以看成是一系列二进制数，所有元素组成更大的二进制集合。
加密算法
AES
高级加密标准(AES,Advanced Encryption Standard)为最常见的对称加密算法(微信小程序加密传输就是用这个加密算法的)。对称加密算法也就是加密和解密用相同的密钥，具体的加密流程如下图：
RSA
RSA 加密算法是一种典型的非对称加密算法，它基于大数的因式分解数学难题，它也是应用最广泛的非对称加密算法。
非对称加密是通过两个密钥（公钥-私钥）来实现对数据的加密和解密的。公钥用于加密，私钥用于解密。
CRC
循环冗余校验(Cyclic Redundancy Check, CRC)是一种根据网络数据包或电脑文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。
它是利用除法及余数的原理来作错误侦测的。
MD5
MD5 常常作为文件的签名出现，我们在下载文件的时候，常常会看到文件页面上附带一个扩展名为.MD5 的文本或者一行字符，这行字符就是就是把整个文件当作原数据通过 MD5 计算后的值，我们下载文件后，可以用检查文件 MD5 信息的软件对下载到的文件在进行一次计算。两次结果对比就可以确保下载到文件的准确性。 另一种常见用途就是网站敏感信息加密，比如用户名密码，支付签名等等。随着 https 技术的普及，现在的网站广泛采用前台明文传输到后台，MD5 加密
（使用偏移量）的方式保护敏感数据保护站点和数据安全。
分布式缓存
缓存雪崩
缓存雪崩我们可以简单的理解为：由于原有缓存失效，新缓存未到期间所有原本应该访问缓存的请求都去查询数据库了，而对数据库 CPU 和内存造成巨大压力，严重的会造成数据库宕机。从而形成一系列连锁反应，造成整个系统崩溃。一般有三种处理办法：
\1. 一般并发量不是特别多的时候，使用最多的解决方案是加锁排队。
- 给每一个缓存数据增加相应的缓存标记，记录缓存的是否失效，如果缓存标记失效，则更新数据缓存。
- 为 key 设置不同的缓存失效时间。
缓存穿透
缓存穿透是指用户查询数据，在数据库没有，自然在缓存中也不会有。这样就导致用户查询的时候，在缓存中找不到，每次都要去数据库再查询一遍，然后返回空（相当于进行了两次无用的查询）。这样请求就绕过缓存直接查数据库，这也是经常提的缓存命中率问题。
有很多种方法可以有效地解决缓存穿透问题，最常见的则是采用布隆过滤器，将所有可能存在的数据哈希到一个足够大的 bitmap 中，一个一定不存在的数据会被这个 bitmap 拦截掉，从而避免了对底层存储系统的查询压力。另外也有一个更为简单粗暴的方法，如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟。
通过这个直接设置的默认值存放到缓存，这样第二次到缓冲中获取就有值了，而不会继续访问数据库。
缓存预热
缓存预热就是系统上线后，将相关的缓存数据直接加载到缓存系统。这样就可以避免在用户请求的时候，先查询数据库，然后再将数据缓存的问题！用户直接查询事先被预热的缓存数据！
缓存更新
缓存更新除了缓存服务器自带的缓存失效策略之外（Redis 默认的有 6 中策略可供选择），我们还可以根据具体的业务需求进行自定义的缓存淘汰，常见的策略有两种：
（1） 定时去清理过期的缓存；
（2） 当有用户请求过来时，再判断这个请求所用到的缓存是否过期，过期的话就去底层系统得到新数据并更新缓存。
缓存降级
当访问量剧增、服务出现问题（如响应时间慢或不响应）或非核心服务影响到核心流程的性能时，仍然需要保证服务还是可用的，即使是有损服务。系统可以根据一些关键数据进行自动降级，也可以配置开关实现人工降级。降级的最终目的是保证核心服务可用，即使是有损的。而且有些服务是无法降级的
（如加入购物车、结算）。
若有收获，就点个赞吧
0 人点赞
