Java知识图谱思维导图模板_ProcessOn思维导图、流程图

大数据

zookeeper

应用场景

分布式协调

分布式锁

zk、redis分布式锁的优缺点

redis

加锁生成个key
释放锁删除key

RedLock算法

阻塞锁、非阻塞锁

元数据或者配置信息管理

kafka之类的，存储元数据

HA高可用性

hdfs、yarn

缓存

技术选型

为什么要用缓存

高性能

高并发

缓存是怎么用的

数据治理、数据关联

数据分发

规则下发

缓存数据

用了有啥不良效果

缓存与数据库双写一致怎么保证

不一致的情况

先修改数据库再删除缓存，结果缓存删除失败，数据库却更新了，造成数据不一致

（高并发情况下，对某个数据大量读写）先删除了缓存，去更新数据库，但还没更新完成的时候，
又来了个请求，把旧的值又加载进了缓存，这个时候数据不一致

方法

读的时候先读缓存，缓存没有再读数据库，然后取出数据后放入缓存，同时返回响应

而且这个缓存使用不一定频繁

更新的时候，先删除缓存，然后再更新数据库

为什么是删除缓存而不是更新缓存

因为更新缓存开销大

所以等他需要的时候再去加载即可

数据库与缓存更新进行异步串行化

让删缓存-写数据库-读数据库-更新缓存有序化即可

维护内存队列
按照数据标识hase入队
用一个单线程去操作
保证同一个队列里的数据有序

存在的问题

读请求长时间阻塞

吞吐量下降

读多写少就还好

缓存雪崩

当缓存服务器重启或者大量缓存集中在某一个时间段失效，
这样在失效的时候，也会给后端系统(比如DB)带来很大压力

缓存失效时的雪崩效应对底层系统的冲击非常可怕！
大多数系统设计者考虑用加锁或者队列的方式保证来保证不会有大量的线程对数据库一次性进行读写，
从而避免失效时大量的并发请求落到底层存储系统上

还有一个简单方案就时讲缓存失效时间分散开，比如我们可以在原有的失效时间基础上增加一个随机值，
比如1-5分钟随机，这样每一个缓存的过期时间的重复率就会降低，就很难引发集体失效的事件

核心在于控制访问底层数据的最大并发数，将其控制在db能接受的范围内

石杉的方法

事前：redis高可用

事中：本地ehcache缓存+hystrix限流&降级

ehcache jvm本地级缓存

请求经过hystrix限流再去查询数据库

限流值可控

过多的请求会被降级

通过自定义降级的方式进行降级，比如返回NULL，或者某种提示

事后：redis持久化，快速恢复缓存数据

缓存死了，大量的请求打过来，把数据库等都搞死了

只要缓存起不来，数据库也会一直被干死，恶性循环

缓存穿透

key对应的数据在数据源并不存在，每次针对此key的请求从缓存获取不到，请求都会到数据源，从而可能压垮数据源。
比如用一个不存在的用户id获取用户信息，不论缓存还是数据库都没有，若黑客利用此漏洞进行攻击可能压垮数据库

最常见的则是采用布隆过滤器

也有一个更为简单粗暴的方法，如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），
我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟

缓存击穿

key对应的数据存在，但在redis中过期，此时若有大量并发请求过来，
这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，
这个时候大并发的请求可能会瞬间把后端DB压垮

业界比较常用的做法，是使用mutex（互斥锁）

缓存并发竞争

多客户端同时并发写一个key，顺序不一致，比如后写的数据先到，
被先写的覆盖了，数据就不对了

redis有CAS可以解决这个问题

zk上分布式锁

读数据这条记录的值和时间

写入缓存

每次要写缓存前判断写时间是否大于缓存里的时间

如果小于就不用操作了

主要技术

redis

和memcached有什么区别

redis支持服务端的数据操作
memcached需要查出来本地处理好再set回去
增加了网络IO的次数数据体积

redis支持更多的操作和数据结构

redis只使用单核，memcached多核
平均到一个核上redis在存储小数据时比memcached性能更高
当数据超过100K时，memcached性能更高

memcached没有原生的集群模式，需要依靠客户端来实现往集群分片中写入数据
redis是有原生的集群模式的

为甚么redis是单线程还可以支持高并发

单线程异步IO模型

单线程模型剖析

redis的网络IO和键值对读写是由一个线程来完成的
这也是redis对外提供键值存储服务的主要流程

文件事件处理器（单线程的）
file event handler

多个socket

IO多路复用程序

后续了解怎么实现的

基于epoll机制实现

文件事件分派器

事件处理器

连接应答处理器

命令请求处理器

命令回复处理器等

其他功能比如持久化、异步删除、集群数据同步等
其实是由额外的线程执行的

支持高并发的原因

全部都是内存运算，非常快

核心是非阻塞的IO多路复用机制

c写的代码，距离操作系统更近，速度相对更快

没有用多线程，节省了上下文切换的时间，也避免了共享资源同步的问题

redis6.0后开始使用多线程模型

数据类型

string

hash

list

set

sorted set

按照指定的分数进行排序

过期策略

可以指定过期时间

如何批量删除过期的值

定期删除

默认每隔100ms随机抽取一批设置了过期时间的key
进行检查，看是否过期，过期就删除

惰性删除

后面在获取某个key的时候，如果该key设置了过期时间，那么会检查一下，
如果过期了，那么删除掉并且不返回

内存淘汰

如果上面两种情况外，比如大量key过期了，然后没有被随机抽取到，
你也没有去查，没有触发惰性删除的情况下怎么解决？

redis内存占用过多时，会按照策略进行淘汰

noevication:当内存不足以容纳新数据写入时，新写入操作会报错

没人用

allkeys-lru:当内存不足以容纳新数据写入时，在键空间中，
移除最近最少使用的key

最常用

allkeys-random:当内存不足以容纳新数据写入时，
在键空间中随机移除某个key

一般没人用

volatile-lru:当内存不足以容纳新数据写入时，在设置了过期时间的键空间中，
移除最近最少使用的key

一般不合适

volatile-random：当内存不足以容纳新数据写入时，
在设置了过期时间的键空间中随机移除某个key

volatile-ttl:当内存不足以容纳新数据写入时，在设置了过期时间的键空间中，
有更早过期时间的key优先移除

如何手写一个LRU算法

继承LinkedHashMap来实现

初始化方法，设置大小cacheSize（最多能缓存的数据量）

super(Math.cell(cacheSize/0.75) + 1, 0.75f, true)

true表示让linkedHashMap按照访问顺序来进行排序，
最近访问的放在头部，最老的放在尾部

CACHE_SIZE= cacheSize，CACHE_SIZE为内部定义变量

重载removeEldestEntry

return size() > CACHE_SIZE

当map中数量大于指定的缓存个数时，就自动删除最老的数据

怎么保证redis高并发高可用

高并发

读写分离

对缓存来说一般是读高并发
写一般较少

主节点(master)只写并把数据同步到从节点(slave)，从节点只负责读

可以水平扩容，增加redis从节点的数量即可

高可用

主从架构+哨兵模式

如果全年99.99%时间处于可用，那么就称具有高可用性

一个slave挂了，不会影响可用性
因为其他slave节点可用提供一样的数据供查询

如果master死掉了，就无法写数据了

不可用

高可用架构下，在master挂掉后，
会把一个slave升级为master，
这个过程叫主备切换
这样保证了高可用性

可能就几分钟、几秒钟不可用

sentinel节点（哨兵节点）负责监控master是否活着

主从架构

说明

必须要开启master的持久化

持久化的意义

在于故障恢复

持久化的方案

RDB

对redis中的数据执行周期化的持久化

优点

代表了某一时刻redis中的数据，适合做冷备

对redis对外提供的读写服务影响非常小，可以让redis保持高性能

因为redis只要fork一个子进程，由子进程进行磁盘IO操作进行RDB持久化即可

相比AOF，RDB基于数据文件恢复和重启会更快速

缺点

想让redis故障时尽可能少丢数据，RDB没AOF好，因为RDB都是之前时刻的数据

fork子进程来执行RDB快照数据文件生成的时候，如果文件特别大，可能会导致对客户端提供的服务暂停数毫秒甚至数秒

AOF

对每条写入命令作为日志，以append-only的模式写入一个日志文件中，
在redis重启的时候，可以通过回放AOF日志中的写入指令来重新构建整个数据集

随着数据不断的进来，AOF文件会不断的膨胀变大

当大到一定程度的时候，会触发AOF rewirte操作，会基于当前redis内存中的数据，
重新构造一个更小的AOF文件，然后把旧的膨胀的很大了的文件删掉

如果同时使用RDB和AOF两种持久化机制，那么redis在重启到时候，
会使用AOF来重新构建数据，因为AOF中的数据更加完整

优点

更好的保证数据不丢，一般AOF每隔1秒，就会在后台执行一次fsync操作（落盘），最多丢一秒数据

以append_only的模式写入，没有任何磁盘寻址的开销，写入性能非常高，而且文件不容易破损，即使文件尾部破损，也很容易修复

AOF即使文件很大，触发rewrite的时候，也不会影响客户端的读写

AOF日志命令以非常可读的方式进行记录，这个特性非常适合做灾难性的误删除的紧急恢复

缺点

对于同一份数据来说AOF通常比RDB文件更大

AOF开启后，支持的写QPS会比RDB支持的写QPS低

因为1秒fsync一次（可配置）

相比RDB更加脆弱，容易出bug

企业级的持久化方案

海量数据、高并发、高可用

不要仅仅只用AOF或者RDB

综合两者使用

如果redis仅仅作为纯内存的缓存使用，那么可以禁止RDB和AOF的持久化机制

不建议使用slave做数据热备，因为那样如果master没有持久化，
在宕机后重启时数据是空的，经过一复制，slave的数据也丢了

即使采用了后续的高可用机制，slave可以自动接管master，
但是semtimel可能还没检测到master挂了，master节点就重启好了，
这样还是会出现上面说的问题，导致slave数据情况

概述

redis replication
主从复制

概述

采用异步方式从主节点复制数据到从节点
从2.8后，slave会周期性的确认自己每次复制的数据量

1个master可以配置多个slave

slave也可以连接其他slave

slave做复制的时候，是不会阻塞master节点的正常工作的

slave做复制的时候，也不会阻塞对自己的查询操作

他会用旧的数据集来提供服务

复制完成，需要删除旧的数据集，加载新的数据集

这个过程会暂停对外服务

slave主要用于横向扩容，做读写分离

完整流程

slave启动，仅仅保存master的信息，包括master的host和ip，但是复制流程还没开始

slave内部有个定时任务，每秒检查是否有新的master要连接和复制，如果发现，就和master建立socket网络连接

slave节点ping master

如果master开启了requirepass，那么slave需要发送口令给master进行认证

master第一次执行全量复制，将所有数据发给slave

master后续持续将写命令同步复制给slave

原理

当启动一个slave节点时，会向master发送PSYNC命令

如果这个slave是重新连接master，则master仅仅只会复制部分缺少的数据给slave，
如果slave是第一次连接，则会触发一次full resynchronization，

触发full synchronization时

master启动一个后台进程，开始生成一份RDB快照文件(bgsave)

同时将从客户端收到的所有写命令缓存在内存中

RDB文件生成完后，master会将这个RDB发送给slave

如果rdb复制的时间超过60s（repl-timeout），那么slave就会认为复制失败，
可以适当调大这个参数

对于1000M网卡的机器，一般1s传输100MB，6G的文件很容易超过60s

slave会把这个RDB文件先写入本地磁盘，然后从磁盘加载到内存中

然后master会将内存里面缓存的写命令发送给slave，slave也会同步这份数据

如果在复制的过程中缓存的数量增长过快怎么办？

client-output-buffer-limit slave 256MB 64MB 60
如果在复制期间，内存缓冲区持续消耗超过64M
或者一次性超过256M，那么停止复制，复制失败

如果slave和master有网络故障，断开了连接，会自动重连，master如果发现多个slave都重新连接，
仅仅会启动一个RDB save操作，用一份数据服务所有slave节点

主从复制的断点续传

2.8后支持主从复制的断点续传

如果主从复制的过程中，网络连接断掉了，那么可以接着上次复制的地方，
继续复制下去，而不是从头开始复制一份（从backlog复制）

master节点会在内存中常驻一个backlog，master和slave都会保存一个replica offset和一个master id
offset就是保存在backlog中的，如果master和slave网络中断了，
slave会让master从上次的replica offset开始继续复制

master和slave都会维护一个的offset，并且自身不断做累加
slave每秒都会上报自己的offset给master
同时msater也会保存每个slave的offset

master的backlog默认大小1MB

master给slave复制数据时，也会将数据在backlog中同步写一份

但是如果没有找到对应的offset，那么就会执行一次full resynchronization

master runid

info server 可以看到master run id

根据host+ip定位master节点是不靠谱的，如果master重启或者数据出现了变化runid都会变化
有时候slave需要根据run id的不同选择全量加载数据

比如主节点数据有问题，回滚到了20h前的RDB冷备数据
数据重新载入，runid会发生变化
此时slave就需要进行一次全量同步

如果需要不更改run id重启redis，可以使用redis-cli debug reload命令

无磁盘化复制

master在内存中直接创建RDB，然后发送给slave，不会在自己本地落盘了

repl-diskless-sync

默认值no，是否开启无磁盘化复制

repl-diskless-sync-delay

等待一定时长再开始复制，因为要等待更多slave重新连接过来

过期key处理

slave不会过期key，只会等master过期key，如果master过期了一个key，
或者LRU淘汰了一个key，那么会模拟一条del命令发送给slave，slave再剔除key

异步复制

master每次接收写命令后，先在内存中写入数据，然后异步发送给slave

heartbeat

心跳同步，主从之间会互相发送心跳同步

master默认10s发送一次

哨兵模式

功能

集群监控

负责监控master和slave是否正常工作

消息通知

当某个redis实例有故障时，哨兵负责发送消息作为报警通知给管理员

故障转移

如果master挂了，会自动转移到slave上

配置中心

如果故障发生转移了，通知client客户端新的master地址

概述

本身也是分布式的，作为一个哨兵集群在运行

故障转移时，判断一个master是否挂了，需要大部分哨兵都同意才行，涉及到了分布式的问题

即使部分哨兵挂了，哨兵集群也还能正常工作，如果作为一个高可用机制故障转移系统本身是单点的，
那就太坑了

slave默认1s发送一次

核心知识

至少需要3个实例，来保证自己的健壮性

为什么两个节点无法工作？

configuration:quorum=1

只要有一个哨兵认为要故障转移就会发生故障转移

同时会选举一个哨兵来进行故障转移

要求majority

就是大部分哨兵是运行的

2个哨兵的majority是2

3个哨兵的majority是2

4个哨兵的majority是2

5个哨兵的majority是3

如果是两个哨兵，如果其中一个哨兵和master在同一台机器上
机器挂了后，由于达不到majority的数量，所以哨兵不会执行故障转移操作，
所以无法保证高可用，所以至少得有三个哨兵实例组成哨兵集群

经典模式是3节点哨兵集群

quorum=2

majority=2

所以可以允许挂一台哨兵机器

哨兵+redis主从的部署架构，是不会保证数据零丢失的，只能保证redis集群高可用

对于哨兵+redis主从这种复杂的部署架构，尽量在测试环境和生产环境都进行充足的测试和演练

哨兵主备切换的数据丢失问题

异步复制

数据写master成功，但是因为是异步复制，还没有复制到slave
此时master挂了，发生了主备切换，那么没同步的数据就丢了

集群脑裂

master出现了异常性的，有相同数据，相同工作的两个节点

一般由网络分区造成

当网络恢复后，此时有旧的master会被降为slave
那么之前往这个节点上写的数据会丢失
（因为他会从另一个master上同步数据）

解决方法

min-slaves-to-write 1

要求至少有1个slave

min-slaves-max-lag 10

数据复制和同步的延迟不能超过10s

一旦所有的slave数据复制和同步延迟都超过了10s，
那么master就不会接收任何请求了

异步复制如果时间超过10s，master就会拒绝写操作，
把异步丢失的数据控制在一个范围内
（client使用本地缓存或者尝试停顿一段时间再写）

client采取的措施

1

一般会在client做降级，写到本地磁盘

在client对外接收请求

再做降级，做限流，减慢请求涌入的速度

2

client将数据临时写入kafka

每隔10分钟去队列里面消费一次，尝试重新发挥master

脑裂的时候，由于slave都联系不到了，
所以超过10s后，旧的master就会拒绝写入请求了
所有最多丢10s的数据

核心原理

sdown和odown转换机制

sdown和odown是两种失败状态

sdown是主观宕机

就是一个哨兵，他觉得master宕机了，那么就是主观宕机

sdown达成的条件很简单，如果一个哨兵ping一个master，
超过了is-master-down-after-milliseconds指定的毫秒数后，就主观认为master宕机了

sdown到odown的转换条件很简单，如果一个哨兵在指定的时间内，
收到了quorum指定数量的其他哨兵也认为那个master是sdown了，
那么就认为是odown，客观的认为master宕机了

odown是客观宕机

如果quorum数量的哨兵都认为master宕机了，那么就是客观宕机

哨兵集群的自动发现机制

哨兵互相之间的发现是通过redis的pub/sub系统实现的

每个哨兵都会往__sentinel__:hello这个channel里发送一个消息，
这时候所有的哨兵都可以消费到这个消息，并感知到其他哨兵的存在

每隔2秒，每个哨兵都会往自己监控的某个master+slave对应的__sentinel__:hello
channel里发送一个消息，内容是自己的host、ip和runid还有对这个master的监控配置

每个哨兵也会去监听自己监控的每个master+slave对应的__sentinel__:hello channel，
然后去感知到同样在监听这个master+slave的其他哨兵的存在

每个哨兵还会和其他哨兵交换对master的监控配置，互相进行监控配置的同步

slave配置的自动纠正

哨兵会负责自动纠正slave的一些配置，比如slave如果要成为潜在的master候选人，
哨兵会确保slave在复制现有master的数据

如果slave连接到了一个错误的master上，比如故障转移之后，
那么哨兵会确保它们连接到正确的master上

slave->master选举算法

如果一个master被认为odown了，而且majority（绝大多数）哨兵都允许了准备切换，
那么某个哨兵就会执行准备切换操作

需要quorum数量的哨兵认为sdown，从而转换成odown

然后选举一个哨兵来做切换，这个哨兵还得得到majority个哨兵的授权，才能正常执行切换

如果quorum<majority，比如5个哨兵，majority就是3，quorum设置成2，那么就得三个哨兵授权才可以执行切换

但是如果quorum>=majority，那么必须quorum数量的哨兵都授权，比如5个哨兵，quorum=5，那么需要5个哨兵都授权才能执行切换

此时首先要选举出一个slave来
会考虑的slave的信息

跟master断开连接是时长

如果一个slave和master断开连接已经超过了down-after-milliseconds的10倍
外加master宕机的时长，那么slave就被认为不适合选举为master

(down-after-milliseconds * 10) + milliseconds_since_master_is_ins_SDOWN_state

slave优先级

复制offset

run id

configuration epoch

执行切换的那个哨兵，会从要切换到的新master那里得到一个configuration epoch，
就是一个version号，每次切换的version号都必须是唯一的

如果第一个哨兵切换失败了，那么其他哨兵会等待failover-timeout时间，然后接替继续进行切换，
此时会重新获取一个新的configurationepoch，作为新的version号

configuration 传播

哨兵完成切换后，会在自己本地生成最新的master配置，然后同步给其他的哨兵，就是通过之前说的pub/sub机制

同步master配置给其他哨兵的时候，会携带之前的version号，其他哨兵会根据version号的大小来更新自己的master配置

集群模式

疑问

key是如何寻址的

分布式寻址有哪些算法

了解一致性hash算法吗

如何动态增加和删除一个节点

我们只要基于redis cluster去搭建redis集群即可，不需要手动去单件主从架构+读写分离+哨兵集群

主要用于海量数据，如果数据量少，用主从架构+哨兵模式即可

自动将数据进行分片，每个master上放一部分数据

提供内置的高可用支持，部分master不可用时，还是可以继续工作的

需要开放两个端口，1个6379，一个10000以上，比如16379，用于节点间通信

数据库

MySQL

存储引擎

MyISAM
现在用的很少了

不支持事务

不支持外键

非聚簇索引

数据和索引是分开存储的

这样可以在内存中缓存更多的索引

单纯做查询的话，性能更好

支持全文检索

表锁

会生成三种文件

.frm

表定义

.myd

数据文件

.myi

索引文件

InnoDB
现在比较常用

支持事务

支持外键

聚簇索引

数据和索引存在同一个文件上

不支持全文检索

行锁

会生成两种文件

.frm

表定义文件

.idb

数据+索引文件

索引

使用的数据结构

B+树

联合索引

举例：比如(a,b)联合索引，那么建好的索引是在a相同的情况下，b才有序，
所以如果不指定a，那么b就是无序的，索引无法生效

最佳左前缀法则

如果最左的索引没有被使用到，则其他索引不会生效，因为是无序的

索引失效的情况

!=

or 前后不是同一个所以

is null 或者 is not null

like

联合索引不符合最左前缀法则的时候

对列用了函数

读写锁

共享锁
就是读锁

独占锁
就是写锁

写锁拥有比读锁更高的优先级
写锁可以插队到读锁前面
但是读锁无法插队到写锁前面（排队的队列）

间隙锁

锁策略

表锁是最基本的锁策略

开销最小

并发最低

锁定整张表

写锁时，独占，其他人不能操作

读锁不会阻塞

行锁

开销最大

并发最高

在存储引擎层面实现，服务器层没有实现

死锁

多个事务在同一资源上相互占用，并请求对方占有的资源而造成的额性循环现象

多个事务同时锁定同一个资源也会产生死锁

为了解决死锁，数据库实现了各种死锁检测机制和死锁超时机制

检测到死锁后立即返回false

InnoDB目前的做法是，将持有最少行级排他锁的事务进行回滚

产生死锁后只有部分或者全部回滚事务才能打破死锁

死锁是不可避免的

因此应用程序在设计的时候要考虑怎么处理死锁

只要将因死锁而回滚的事务重新提交即可

事务

事务是一组原子性的SQL是一个独立的工作单元

特性

A

原子性

一个事务是逻辑上不可分割的最小单元，一个事务的所有操作要么全部成功，要么全部失败

C

一致性

从一个一致性转移到另外一个一致性

比如A和B一共5000员，那么不管他们之间怎么转账，他们的总金额都必须是5000

I

隔离性

多个事务之间互不影响

隔离级别

读未提交

读已提交

可重复读

串行化

D

持久性

事务一旦提交，那么他的修改就会永久保存在数据库中

事务id，全局唯一递增的

MVCC

多版本并发控制

每个事务会对操作的那条数据会生成一个这个版本（用事务id标识）的快照

如果另一个事务也操作同一条数据，那么也会存在一个另一个事务版本的快照，也就是会有两个

当前事务只能查到版本小于自己版本的快照记录

在大多数情况下避免加锁，大家都实现了非阻塞的读操作

写操作也只锁要操作的行

调优

explain：看执行计划

算法

排序

冒泡排序

平均时间复杂度

O(n²)

最坏时间复杂度

O(n²)

原理

从排序序列向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换位置，
使值较大的元素逐渐从前移向后部，最终大的值在后面，小的值在前，像水泡一样，所以称为冒泡排序

从0到n-1找到最大的，把最大的值放到n-1的位置

从0到n-2找到次大的，把次大的放到n-2的位置

以此类推（如果要逆序的话，那么就是找最小的）

如果在某次排序中一次交换都没发生，那么意味着序列已经有序了，可以结束排序了

示例

子主题

选择排序

平均时间复杂度

O(n²)

最坏时间复杂度

O(n²)

原理

第一次从0到n-1中找到最小的，与0位置的值进行交换，注意并不是立即交换，而是整个比较结束了再交换

第二次从1到n-1中找次小的，然后与1位置的值进行交换

以此类推（如果要逆序的话，就是找最大的）

示例

插入排序

平均时间复杂度

O(n²)

最坏时间复杂度

O(n²)

原理

以我们这个待排序数组为无序数组

先取无序数组中第2个元素与第1个元素比较，并保证他们的顺序（如果顺序不符合就调整位置）

然后对无序数组里面的第3个元素与第2个和第1个进行比较，然后把它放到合适的位置

以此类推

跟打扑克整理牌的意思是一致的

缺点

如果最小的值在数组后面，那么整个数组的值都要进行移动，效率过低

示例

交换排序

平均时间复杂度

O(n²)

最坏时间复杂度

O(n²)

希尔排序

平均时间复杂度

O(nlogn)

最坏时间复杂度

O(n^s) 1<=s<=2

原理

也是一种插入排序，但是进行了优化，也叫缩小增量排序

对数组按照下标的一定增量（步长，比如0和5的步长是5）进行分组（即0、5放一组，1、6放一组，这种）（以数组长度为10举例）

两个数字一组，那么需要分10/2=5组，步长定义为5

各个分组进行插入排序

缩短增量（步长），再进行插入排序，5/2=2（取整），数据被分成两组

直至增量为1，排序结束

经过这种处理，小的值一般都会被放到了前面，用插入排序的时候，移动量大大减少

示例

交换式

进行插入时采用交换法

性能相比插入排序更差，以为时间都花在交换上了，插入排序不是交换的是移动的

移动式

进行插入时采用移动法

性能相比插入排序提升很多

快速排序

平均时间复杂度

O(nlogn)

最坏时间复杂度

O(n²)

原理

对冒泡排序的改进

找到标志位，把数据分成左右两部分，保证左边的数据都比它小，右边的数据都比它大

然后对两边的数据分别再进行快速排序

以此类推

示例

归并排序

平均时间复杂度

O(nlogn)

最坏时间复杂度

O(nlogn)

原理

先把数组进行拆分，拆分到最低层级后，将数据进行合并，合并成有序序列

然后逐级递归的进行合并，最终形成有序

示例

基数排序

平均时间复杂度

O(nlogn)

最坏时间复杂度

O(nlogn)

速度最快，内存占用最多，海量数据时容易oom异常

原理

构建10个桶

先把数组里面元素按照个位数的大小放置到对应的桶里面

然后按桶下标的顺序把数据取出来放到数组里

第二次把数组里面元素按照十位数的大小放置到对应的桶里面

然后按桶下标的顺序把数据取出来放到数组里

以此类推

查找

二分查找

插值查找

斐波那契查找

单链表翻转

埃筛法

双指针法

JUC

消息队列

技术选型

为什么使用消息队列

有什么业务场景需要用到它

解耦

实例场景1：单引擎解耦前

before

after

实例场景2：视图库的订阅

before

after

异步

实例场景1：单引擎入库
同步高延时的场景

before

结构化

入myBase

入myFace

入Mongo

after

削峰

实例场景1：单引擎实时接入路人数据
没有mq系统高峰期挂了

before

after

消息队列的优缺点

优点

待补充

缺点

系统可用性降低，引入的外部依赖越多，越容易挂掉，万一mq挂掉，所举例场景都不能正常工作

系统复杂性提高，加入mq怎么保证不重复消费，怎么保证消息不丢失，怎么保证消息传递的顺序，写挂了数据积压怎么办

一致性问题，比如异步解耦后A处理成功，B、C处理失败怎么处理？这样数据的一致性就有问题了

各个队列优缺点比较

主要使用队列

kafka

怎么保证高可用

kafka 0.8版本前没有高可用机制

当一个节点挂了后，会丢失1/n的数据（n为节点数量）

引入了副本机制后，才有了高可用

分布式模式保证高可用

一个topic由多个partition组成

每个partition都有自己的副本

partition的leader和副本不在同一台机器上

数据的读写在partition的leader上进行

机器宕机后，可以从副本中选举新的leader，数据不会丢

partition的leader的选举算法

怎么保证不重复消费

重复消费的场景：
一般是offset提交失败造成的重复消费

怎么保证消息不丢

消费者弄丢数据

消费者自动提交offset，具体查看rabbit

kafka弄丢了数据

leader收到数据，还没同步给follow，然后leader挂了

此时会重新选举一个follow作为leader

但是在新leader里面就没有那个数据了

怎么保证消息的顺序性

给同一批数据指定相同的key值

数据就会进入同一个partition

kafka的特性一个partition只能被一个消费者消费
这样就可以保证消息的顺序

kafka脑裂

通过controller epoch解决

每当新的controller产生的时候就会在zk中生成一个全新的、数值更大的controller epoch的标识，
并同步给其他的broker进行保存，这样当第二个controller发送指令时，其他的broker就会自动忽略。

消息积压怎么处理

rabbit

怎么保证高可用

rabbit不是分布式的，它有三种模式

单机模式

入门演练用的，没什么讲的必要

集群模式

流程

1、假如有3台机器，A、B、C

2、假设有个队列Q1

3、Q1的queue存储在A上（元数据和实际数据）
其他台机器上（B/C）会有Q1的元数据信息（仅有元数据）

4、消费者连接B机器消费Q1的数据

5、由于B中Q1的元数据，所以B知道Q1队列在A机器上，于是向A请求数据

6、B向A拉数据

7、拉到数据后给消费者

缺点

rabbit内部可能产生大量数据传输

可用性几乎没有保证，一旦Queue所在那台机器挂掉了，数据就丢失了，无法消费了

镜像集群

流程

1、假如有3台机器，A、B、C

2、假设有个队列Q1

3、消费者向Q1写入数据时，假设向A机器写入，
那么A机器上的Queue会把数据同步到B、C机器

4、消费者消费消息时，无论连哪台机器都能拿到完整的数据

与集群模式的不同点

每个节点都有这个Queue的一个完整镜像
包含这个Queue的全部数据，所以这个模式
叫镜像集群模式

优点

任何节点宕机都没问题，其他节点都有数据

缺点

他不是分布式的，如果Queue数据大到机器无法容纳时，怎么办？

怎么保证不重复消费

重复消费的场景：
一般是offset提交失败造成的重复消费

怎么保证消息不丢

存在的数据丢失的问题

生产者端数据丢失

网络传输过程中丢失了

启用rabbit的事务机制，事务机制是同步的会导致消费者的吞吐量急剧下降

使用confirm机制，把channal调整在confirm模式，提交消息后就不用管了，走消息的回调机制

数据传输到mq，但是mq内部出错，没保存下来

mq服务端数据丢失

mq收到消息暂存在内存中，结果消费者还没消费，mq挂了
缓存在内存的数据就丢失了

将数据持久化到磁盘

Queue创建时将它设置为持久化
这样会持久化queue的元数据
但是不会持久化queue里面的数据

发送消息的时候将消息的deliveryModel设置为2，将消息
持久化，这样mq就会将消息持久化到磁盘中

即便开启了持久化，也会丢数据

消息写到了mq，但还没来得及持久化，mq就挂了

消费者端数据丢失

消费者收到消息，还没开始处理，消费者挂了，mq以为消费完了

只有一种情况下会发生，打开了消费者的autoAck机制

关闭autoAck，手动进行ack，确保消息正确被消费后再进行ack

怎么保证消息的顺序性

消息积压怎么处理

搜索引擎

技术选型

主要使用

elastic search

概述

es是准实时的（NRT，near real-time，准实时。）默认是每隔1秒refresh一次的，所以es是准实时的，因为写入的数据1秒之后才能被看到

架构设计

和kafka类似的分布式架构

数据写入读取流程

写入

1、向随机节点请求，该节点被称为协调节点

2、协调节点对数据的documentId做hash，根据hash值为该数据指定shard（
协调节点对docmount进行路由，将请求转发给到对应的primary shard）

3、路由到该shard的primary shard所在机器

4、数据写入primary shard的同时，同步replica shard

5、数据写入primary shard的时候，同时写入es的内存buffer和translog

写入buffer

1s后刷入os cache中

buffer快满的时候也会刷到os cahce

数据在buffer中时，暂时无法被查出来

写入translog

先存入os cache中

5s 后刷入磁盘文件

当translog足够大，或者经过30分钟时会触发commit操作

buffer、os cache 里面的数据强制刷出到磁盘并清空缓存（触发refresh）

将commit point写入磁盘，记录所有对应的segment file

旧的translog文件清除，把数据存储到磁盘中，并生成新的translog文件

读取

get

将请求发送到一台es机器，这个节点被称为协调节点

协调节点对document进行路由，将请求转发到对应的node，
此时会使用随机轮询算法，在primary shard 和replica shard中随机选择一个，
让读取请求负载均衡

接收请求的node返回document给协调节点

协调节点，返回document给到客户端

搜索

客户端发送请求到协调节点

协调节点将请求发送到所有的shard对应的primary shard或replica shard ；

每个shard将自己搜索到的结果返回给协调节点，返回的结果是documentId或者自己自定义id，
然后协调节点对数据进行合并排序操作，最终得到结果

最后协调节点根据id到个shard上拉取实际的document数据，最后返回给客户端。

删除

流程同写入，不同点在于

commit的时候会生成一个.del文件

将这个document标识为deleted状态，在搜索的搜索的时候就不会被搜索到了

更新

流程同写入，不同点在于

将原先的document标记为删除状态

插入一条新的数据

refresh、flush、merge都可以手动调api来触发

在几十亿数据量级下如何优化查询性能

几十亿级第一次搜索时很慢，5~15s
但是后面可能就快了

es的搜索引擎严重依赖底层的fileSystem cache
（操作系统缓存）

fileSystem cache

es数据是落盘的，如果搜索走文件的话，性能是秒级的
如果走fileSystem cache的话，性能是毫秒级别的

如果给fileSystem cache更多的内存
尽量让内存容纳所有的index segment file索引数据文件
那么搜素的时候基本都是走内存，性能会非常高

但是如果索引数据有1个T，但是实际内存只有100G的情况下
怎么保证高性能呢

数据量1T的情况下，起码要保证fileSystem cache的内存加起来有512G，
这样有一半的数据可以走内存搜索

生产环境中，尽量在es中存储少量的数据，只存储你要搜索的字段，内存留给fileSystem cache
这样所有的搜索几乎都可以走内存，性能就很高了（单条数据量越大，能缓存的数据量就越少了）

所以一般推荐es+hbase的架构

hbase的特点是对海量数据做在线存储，不对他做复杂的搜索，只做很简单的根据id进行查询

相当于es先搜索出id，然后去hbase里捞详细数据

缓存预热

如果按照上述方案去做，es中每台机器写入的数据量
还是超过了fileSystem cache的一倍以上

把经常有人访问的数据，专门做一个缓存预热子系统，对热数据定时访问一下，
让数据进入fileSystem cache里面去，这样其他人来访问的时候性能就会好很多
（例如：微博提前将大V数据预热下，淘宝提前将热门商品预热下）

冷热分离

最好冷数据一个索引，热数据一个索引，
这样确保热数据在预热后尽量留在fileSystem cache中，不会被冷数据冲刷掉

document模型设计

数据模型尽量设计好，兼容以后的各种运算情况

尽量不要用es里面的各种关联查询、复杂查询语法，一旦用了性能一般都不好

分页性能优化

es分页性能很差，比如每页10条数据，
现在你要查第100页的数据

第100页，那么对于就第1000条左右数据

每个shard查1000条数据，返回给协调节点

假设有5个shard，那么协调节点拿到了5000条数据

对5000条数据进行合并、处理，返回第100页的10条给客户端

那如果shard数更多一些呢？翻的页更深写呢？比如10000页，
那是不是每个shard返回的数量都越来越多，协调节点汇总要处理的数据也越多

生产环境的分布式搜索引擎是怎么部署的

es的部署架构是什么

5-7台机器

每台机器64核512G内存

集群总内存3.5T

每个索引的数据量大概有多少

es集群日增数据量大概是2亿条

每天日增数据量大约是300G

每月增量90亿左右，大小9T，目前有60T，数据存留半年

每个索引大概有多少个分片

每天自动建索引，分为人、车、其他等

每个索引的数量大约是：7-8千万条

建了12个shard

微服务

分布式

分布式业务系统

微服务化

为什么要进行服务拆分

大平台拆成各个子系统

易于维护

减少冲突

减少工作量，避免重复测试

轻量发布，易于部署

怎么进行拆分

需要进行多轮拆分

后续业务发展，可能需要再进行拆分

最理想状态下，1个人负责1-3个服务

分布式服务框架

服务调用

dubbo
rpc框架

拆分后不用dubbo可以吗

当然可以，纯http接口访问也行

但是要考虑很多问题，请求超时怎么办，负载均衡怎么处理，请求的服务方异常了怎么办

dubbo和thrift有什么区别

原理

接口层

provider和consumer

config层

proxy层

spring cloud

分布式锁

分布式事务

一个系统走本地事务

多个系统怎么进行分布式事务

分布式会话

分布式系统中接口的幂等性如何保证

问题

比如不能重复扣款

一个订单重复提交两次，被扣两次款，这种要怎么避免

比如网络原因，重复提交

原理

每个请求得有一个唯一标识id

处理完得有一个记录标识，标识这个标识id的数据已经处理过

每次接受请求前要判断之前是否已经处理过

举例：

单引擎图片md5做id，插入前判断记录是否有存在

分布式系统中的接口调用如何保证顺序

一般很多接口是不需要保证的

方法

比如1/2/3，一共三个请求，现在系统是分布式的，
不同请求可能会被分发到不同服务器上去，怎么保证他们的执行顺序

搞一个网关，每个请求都携带一个id，同一批请求携带相同的id
网关根据id求hash，然后把同样id的请求发到同一台服务器上

分布式锁，太重了，不建议

分布式存储

解决方案

Spring Cloud NetFlix

一站式解决方案

api网关

技术选型

zuul

作用

动态路由

用数据库来存储路由路径，从而实现动态路由

对zuul二次开发

灰度发布

授权认证

性能监控

系统日志

数据缓存

限流熔断

流程

配置一下不同请求路径和服务的对应关系

请求到了网关，他查找匹配的服务

把请求用Http协议进行封装

然后就把请求转发给某台机器

配合ribbon

Kong

nginx里面的一个基于lua写的模块，实现了网关的功能

Nginx+Lua（OpenResty）

自研网关

基于Netty自研

服务注册与发现

Eureka

服务注册表

维护所有注册服务
的一个信息

二级缓存

readOnly
其他服务从只读缓存获取服务信息
拉不到信息时，会向上级将数据同步过来

用这种方式，可以避免并发冲突
避免上锁，可以解决并发问题

readWrite

其他配置参数

子主题

ZooKeeper

比较

eureka

peer-to-peer

集群中机器地位一样

任意一台机器的数据都会同步给其他机器

AP

牺牲了一致性，但是可以保证最终一致性

因为其他的服务经过心跳就能达到新的一致了

感知是几十秒级的，甚至分钟级

zookeeper

leader、follow两种角色

leader可以写

leader、follow可以读

leader选举过程中不可用

CP

感知是秒级的

CAP

C：一致性

A：可用性

P：分区容错性

熔断机制

Hystrix

服务接口调用

Feign

对接口打个注解

针对注解生成动态代理

然后用动态代理去调其他方法时

在底层生成http协议格式的请求

会先用ribbon获取机器列表，然后进行负载均衡，
选出一条机器来

然后把请求发送到这台机器上

负载均衡

Ribbon

定时拉取eureka的注册表信息

进行负载均衡

Apach Dubbo Zookeeper

半自动，需要整合别人的

api网关

自己实现

服务接口调用

Dubbo

服务注册与发现

Zookeeper

熔断

借助Hystrix

Spring Cloud Alibaba

一站式解决方案

网络通信

七层架构

应用层

表示层

会话层

传输控制层

网络层

数据链路层

物理层

TCP/IP协议

应用层

http/ftp协议

传输控制层

TCP协议

面向连接的
可靠的传输协议

什么是连接

三次握手

目的

建立连接

为什么需要三次握手

1、客户端发送syn给服务端

2、服务端发送sync+ack给客户端

3、客户端发送ack给服务端

握手完开辟资源

发送队列

接收队列

四次分手

1、客户端发送一个FIN报文到服务端

表示客户端想要断开

2、服务端回一个FIN+ACK

服务端收到消息，表示收到请求了

3、服务端再发送一个FIN报文

服务端发送报文，表示服务端也想断开

4、客户端回一个ACK

客户端回一个ack表示收到，同意断开

释放资源

怎么保证可靠

可靠的，所以有发送就有回复
（每个数据包的发送都是这样）

即A向B发送数据包

B需要向A回复，表示有收到

UDP协议

网络层

IP

数据怎么发到指定ip

路由表

存储下一跳的信息地址

路由的下一个点。如果路由器没有直接连接到目的网络，
它会有一个提供下一跳路由的邻居路由器，用来传递数据到目的地

诸如目标网络号、网关、掩码等信息

route -u 命令查看

比如：如图

如果我们要发包给220.12.10.11这个ip

首先会和genmask（掩码）做二进制与运算，得到的值作为网络号和destination（目标）进行比较

如果值相等表示可以联通，然后查看gateway（网关），如果gateway为0.0.0.0表示可以直达，无需转发，直接发送即可

如果gateway值为某个ip，则把数据包发给这个ip

然后通过这个ip进行下一跳逐步转发，知道发送给220.12.10.11为止

链路层

内网是怎么访问公网的

比如当前家里局域网是192.168.150.11，想要访问220.12.10.11这个ip

那么我们数据包里面的ip填的是哪个ip呢，是按照网络层里面说的网关地址，
还是220.12.10.11这个ip地址

如果填网关ip，那么网关收到这个数据后就处理了，并不会发送给目标ip了

如果填写目标端ip，在这个网络内直接就不可达了

arp -a 命令广播获取可达的ip及mac地址

如图

物理层

Socket

客户端 ip+port
服务端 ip+port

能建立唯一的连接

端口号0-65535

JVM

设计模式

单例模式

实现方式

饿汉模式

直接静态变量实现

优点

线程安全

方便

缺点

不能按需创建
即便不需要也会被加载

如果单例过于复杂可能存在内存问题

存在序列化和反序列化的问题

懒汉模式

懒加载的实现方式

优点

能按需创建

缺点

线程不安全

存在序列化和反序列化的问题

双端检锁机制

懒汉模式的扩充
需要加上volatile关键字

优点

能按需

线程安全

缺点

存在序列化和反序列化的问题

静态内部类实现

一个类加载时，其子类不会马上加载，当且仅当其静态成员（变量、方法等）被调用时，才会被加载

优点

实现简单

线程安全

能按需创建

缺点

存在序列化和反序列化的问题

枚举类实现

具备以上所有的优点，同时可以规避序列化和反序列化的问题

数据结构

HashMap

执行构造方法的时候并不会初始化，
而是在插入第一个元素的时候才开始初始化

jdk1.7

数组+链表

map初始化大小是16，后续会以2的幂进行扩充，之所以是2的幂，
主要是因为根据hashcode求索引值时，使用的是位运算

static int indexFor(int h, int length) {
return h & (length - 1)
}

因为位运算的效率很高，比直接取模要快个10倍左右

为什么要length -1

以16为例，对应的二进制为 0000 0000 0001 0000

与任意值做&，值都只有0和16两种

而15的二进制为 0000 0000 0000 1111

15与任意值做&，可能的值有0-15，共16种

hash值一样时，叫hash碰撞，然后会去遍历链表看该记录是否有存在，没存在就插入，使用头插法

所以map初始化的时候即使你指定了大小，他也会转换成对应的大于你的初始值的最小的2次幂的值

hashmap扩容的时候有死锁的风险

hashmap不是线程安全的主要就是指扩容的时候

jdk1.8

数组+链表+红黑树

数组-》链表使用尾插法

链表长度超过8是（并且数组大小小于64时），转红黑树，当红黑树长度小于6时又会从红黑树转回链表

扰动函数

让高位参与运算，降低发生hash碰撞的几率

用尾插法
为什么不用头插法了？

HashMap在jdk1.7中采用头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了

Tree（这个网站包含了很多tree的数据结构）

二叉树

无序，查找性能差

二叉有序树

左节点的值都比根节点小，右节点的值都比根节点大

当插入的数据都是有序的时候，就退化成链表了

二分查找法就没用了

二叉平衡树

保持最长子树和最短子树的层数差不超过1

牺牲插入性能保证查询性能

二分查找法可以使用

红黑树

最长子树不超过最短子树的两倍即可

尽量保持插入、查询性能的平衡

B数

一个节点可以存在多个值

因此可以减少数的高度

从而提高查询效率

索引和数据一起存储

进行范围查找时会存在回旋查找的问题

B+树

相当于B树+单向链表

索引存在非叶子节点，数据存在叶子节点

并且数的所有叶节点形成一个有序链表，所以范围查找时不存在回旋查找的问题

Spring

类初始化后执行方法的顺序

1、@PostConstruct

在BeanPostProcessor接口的beforeInitial阶段就执行了，所以最早

2、实现InitializingBean接口

3、xml配置的init-method