Java知识图谱
2023-02-15 11:12:25 1 举报AI智能生成
登录查看完整内容
Java知识图谱
作者其他创作
大纲/内容
分布式协调
加锁 生成个key释放锁 删除key
RedLock算法
redis
zk、redis分布式锁的优缺点
阻塞锁、非阻塞锁
分布式锁
kafka之类的，存储元数据
元数据或者配置信息管理
hdfs、yarn
HA高可用性
应用场景
zookeeper
大数据
高性能
高并发
为什么要用缓存
数据治理、数据关联
数据分发
规则下发
缓存数据
缓存是怎么用的
先修改数据库再删除缓存，结果缓存删除失败，数据库却更新了，造成数据不一致
（高并发情况下，对某个数据大量读写）先删除了缓存，去更新数据库，但还没更新完成的时候，又来了个请求，把旧的值又加载进了缓存，这个时候数据不一致
不一致的情况
读的时候先读缓存，缓存没有再读数据库，然后取出数据后放入缓存，同时返回响应
而且这个缓存使用不一定频繁
更新的时候，先删除缓存，然后再更新数据库
因为更新缓存开销大
所以等他需要的时候再去加载即可
为什么是删除缓存而不是更新缓存
读请求长时间阻塞
吞吐量下降
读多写少就还好
存在的问题
维护内存队列按照数据标识hase入队用一个单线程去操作保证同一个队列里的数据有序
让删缓存-写数据库-读数据库-更新缓存有序化即可
数据库与缓存更新进行异步串行化
方法
缓存与数据库双写一致怎么保证
缓存失效时的雪崩效应对底层系统的冲击非常可怕！大多数系统设计者考虑用加锁或者队列的方式保证来保证不会有大量的线程对数据库一次性进行读写，从而避免失效时大量的并发请求落到底层存储系统上
还有一个简单方案就时讲缓存失效时间分散开，比如我们可以在原有的失效时间基础上增加一个随机值，比如1-5分钟随机，这样每一个缓存的过期时间的重复率就会降低，就很难引发集体失效的事件
核心在于控制访问底层数据的最大并发数，将其控制在db能接受的范围内
事前：redis高可用
ehcache jvm本地级缓存
限流值可控
通过自定义降级的方式进行降级，比如返回NULL，或者某种提示
过多的请求会被降级
请求经过hystrix限流再去查询数据库
事中：本地ehcache缓存+hystrix限流&降级
事后：redis持久化，快速恢复缓存数据
石杉的方法
当缓存服务器重启或者大量缓存集中在某一个时间段失效，这样在失效的时候，也会给后端系统(比如DB)带来很大压力
缓存死了，大量的请求打过来，把数据库等都搞死了
只要缓存起不来，数据库也会一直被干死，恶性循环
缓存雪崩
最常见的则是采用布隆过滤器
也有一个更为简单粗暴的方法，如果一个查询返回的数据为空（不管是数据不存在，还是系统故障），我们仍然把这个空结果进行缓存，但它的过期时间会很短，最长不超过五分钟
key对应的数据在数据源并不存在，每次针对此key的请求从缓存获取不到，请求都会到数据源，从而可能压垮数据源。比如用一个不存在的用户id获取用户信息，不论缓存还是数据库都没有，若黑客利用此漏洞进行攻击可能压垮数据库
缓存穿透
业界比较常用的做法，是使用mutex（互斥锁）
key对应的数据存在，但在redis中过期，此时若有大量并发请求过来，这些请求发现缓存过期一般都会从后端DB加载数据并回设到缓存，这个时候大并发的请求可能会瞬间把后端DB压垮
缓存击穿
zk上分布式锁
读数据这条记录的值和时间
写入缓存
每次要写缓存前判断写时间是否大于缓存里的时间
如果小于就不用操作了
redis有CAS可以解决这个问题
多客户端同时并发写一个key，顺序不一致，比如后写的数据先到，被先写的覆盖了，数据就不对了
缓存并发竞争
用了有啥不良效果
技术选型
redis支持服务端的数据操作memcached需要查出来本地处理好再set回去增加了网络IO的次数数据体积
redis支持更多的操作和数据结构
redis只使用单核，memcached多核平均到一个核上redis在存储小数据时比memcached性能更高当数据超过100K时，memcached性能更高
memcached没有原生的集群模式，需要依靠客户端来实现往集群分片中写入数据redis是有原生的集群模式的
和memcached有什么区别
单线程异步IO模型
多个socket
后续了解怎么实现的
基于epoll机制实现
IO多路复用程序
文件事件分派器
连接应答处理器
命令请求处理器
命令回复处理器等
事件处理器
文件事件处理器（单线程的）file event handler
redis的网络IO和键值对读写是由一个线程来完成的这也是redis对外提供键值存储服务的主要流程
其他功能比如持久化、异步删除、集群数据同步等其实是由额外的线程执行的
全部都是内存运算，非常快
核心是非阻塞的IO多路复用机制
c写的代码，距离操作系统更近，速度相对更快
没有用多线程，节省了上下文切换的时间，也避免了共享资源同步的问题
支持高并发的原因
单线程模型剖析
redis6.0后开始使用多线程模型
为甚么redis是单线程还可以支持高并发
string
hash
list
set
按照指定的分数进行排序
sorted set
数据类型
可以指定过期时间
默认每隔100ms随机抽取一批设置了过期时间的key进行检查，看是否过期，过期就删除
定期删除
后面在获取某个key的时候，如果该key设置了过期时间，那么会检查一下，如果过期了，那么删除掉并且不返回
惰性删除
如何批量删除过期的值
如果上面两种情况外，比如大量key过期了，然后没有被随机抽取到，你也没有去查，没有触发惰性删除的情况下怎么解决？
没人用
noevication:当内存不足以容纳新数据写入时，新写入操作会报错
最常用
allkeys-lru:当内存不足以容纳新数据写入时，在键空间中，移除最近最少使用的key
一般没人用
allkeys-random:当内存不足以容纳新数据写入时，在键空间中随机移除某个key
一般不合适
volatile-lru:当内存不足以容纳新数据写入时，在设置了过期时间的键空间中，移除最近最少使用的key
volatile-random：当内存不足以容纳新数据写入时，在设置了过期时间的键空间中随机移除某个key
volatile-ttl:当内存不足以容纳新数据写入时，在设置了过期时间的键空间中，有更早过期时间的key优先移除
redis内存占用过多时，会按照策略进行淘汰
继承LinkedHashMap来实现
true表示让linkedHashMap按照访问顺序来进行排序，最近访问的放在头部，最老的放在尾部
CACHE_SIZE= cacheSize，CACHE_SIZE为内部定义变量
当map中数量大于指定的缓存个数时，就自动删除最老的数据
return size() > CACHE_SIZE
重载removeEldestEntry
初始化方法，设置大小cacheSize（最多能缓存的数据量）
如何手写一个LRU算法
内存淘汰
过期策略
对缓存来说一般是读高并发写一般较少
主节点(master)只写并把数据同步到从节点(slave)，从节点只负责读
可以水平扩容，增加redis从节点的数量即可
读写分离
每个实例都容纳了完整的数据，
如果redis需要缓存的数量超过了一台机器的内存，那么就需要redis集群
主从架构，一主多从
概要
一个slave挂了，不会影响可用性因为其他slave节点可用提供一样的数据供查询
不可用
如果master死掉了，就无法写数据了
可能就几分钟、几秒钟不可用
高可用架构下，在master挂掉后，会把一个slave升级为master，这个过程叫主备切换这样保证了高可用性
sentinel节点（哨兵节点）负责监控master是否活着
如果全年99.99%时间处于可用，那么就称具有高可用性
主从架构+哨兵模式
高可用
怎么保证redis高并发高可用
在于故障恢复
持久化的意义
代表了某一时刻redis中的数据，适合做冷备
因为redis只要fork一个子进程，由子进程进行磁盘IO操作进行RDB持久化即可
对redis对外提供的读写服务影响非常小，可以让redis保持高性能
相比AOF，RDB基于数据文件恢复和重启会更快速
优点
想让redis故障时尽可能少丢数据，RDB没AOF好，因为RDB都是之前时刻的数据
fork子进程来执行RDB快照数据文件生成的时候，如果文件特别大，可能会导致对客户端提供的服务暂停数毫秒甚至数秒
缺点
对redis中的数据执行周期化的持久化
RDB
随着数据不断的进来，AOF文件会不断的膨胀变大
当大到一定程度的时候，会触发AOF rewirte操作，会基于当前redis内存中的数据，重新构造一个更小的AOF文件，然后把旧的膨胀的很大了的文件删掉
对每条写入命令作为日志，以append-only的模式写入一个日志文件中，在redis重启的时候，可以通过回放AOF日志中的写入指令来重新构建整个数据集
如果同时使用RDB和AOF两种持久化机制，那么redis在重启到时候，会使用AOF来重新构建数据，因为AOF中的数据更加完整
更好的保证数据不丢，一般AOF每隔1秒，就会在后台执行一次fsync操作（落盘），最多丢一秒数据
以append_only的模式写入，没有任何磁盘寻址的开销，写入性能非常高，而且文件不容易破损，即使文件尾部破损，也很容易修复
AOF即使文件很大，触发rewrite的时候，也不会影响客户端的读写
AOF日志命令以非常可读的方式进行记录，这个特性非常适合做灾难性的误删除的紧急恢复
对于同一份数据来说AOF通常比RDB文件更大
因为1秒fsync一次（可配置）
AOF开启后，支持的写QPS会比RDB支持的写QPS低
相比RDB更加脆弱，容易出bug
AOF
持久化的方案
海量数据、高并发、高可用
综合两者使用
不要仅仅只用AOF或者RDB
企业级的持久化方案
如果redis仅仅作为纯内存的缓存使用，那么可以禁止RDB和AOF的持久化机制
必须要开启master的持久化
不建议使用slave做数据热备，因为那样如果master没有持久化，在宕机后重启时数据是空的，经过一复制，slave的数据也丢了
即使采用了后续的高可用机制，slave可以自动接管master，但是semtimel可能还没检测到master挂了，master节点就重启好了，这样还是会出现上面说的问题，导致slave数据情况
说明
采用异步方式从主节点复制数据到从节点从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
完整流程
redis replication主从复制
当启动一个slave节点时，会向master发送PSYNC命令
master启动一个后台进程，开始生成一份RDB快照文件(bgsave)
同时将从客户端收到的所有写命令缓存在内存中
如果rdb复制的时间超过60s（repl-timeout），那么slave就会认为复制失败，可以适当调大这个参数
对于1000M网卡的机器，一般1s传输100MB，6G的文件很容易超过60s
RDB文件生成完后，master会将这个RDB发送给slave
slave会把这个RDB文件先写入本地磁盘，然后从磁盘加载到内存中
client-output-buffer-limit slave 256MB 64MB 60如果在复制期间，内存缓冲区持续消耗超过64M或者一次性超过256M，那么停止复制，复制失败
如果在复制的过程中缓存的数量增长过快怎么办？
然后master会将内存里面缓存的写命令发送给slave，slave也会同步这份数据
触发full synchronization时
如果这个slave是重新连接master，则master仅仅只会复制部分缺少的数据给slave，如果slave是第一次连接，则会触发一次full resynchronization，
如果slave和master有网络故障，断开了连接，会自动重连，master如果发现多个slave都重新连接，仅仅会启动一个RDB save操作，用一份数据服务所有slave节点
2.8后支持主从复制的断点续传
master和slave都会维护一个的offset，并且自身不断做累加slave每秒都会上报自己的offset给master同时msater也会保存每个slave的offset
master的backlog默认大小1MB
master给slave复制数据时，也会将数据在backlog中同步写一份
master节点会在内存中常驻一个backlog，master和slave都会保存一个replica offset和一个master idoffset就是保存在backlog中的，如果master和slave网络中断了，slave会让master从上次的replica offset开始继续复制
但是如果没有找到对应的offset，那么就会执行一次full resynchronization
如果主从复制的过程中，网络连接断掉了，那么可以接着上次复制的地方，继续复制下去，而不是从头开始复制一份（从backlog复制）
info server 可以看到master run id
比如主节点数据有问题，回滚到了20h前的RDB冷备数据数据重新载入，runid会发生变化此时slave就需要进行一次全量同步
根据host+ip定位master节点是不靠谱的，如果master重启或者数据出现了变化runid都会变化有时候slave需要根据run id的不同选择全量加载数据
如果需要不更改run id重启redis，可以使用redis-cli debug reload命令
master runid
主从复制的断点续传
默认值no，是否开启无磁盘化复制
repl-diskless-sync
等待一定时长再开始复制，因为要等待更多slave重新连接过来
repl-diskless-sync-delay
master在内存中直接创建RDB，然后发送给slave，不会在自己本地落盘了
无磁盘化复制
slave不会过期key，只会等master过期key，如果master过期了一个key，或者LRU淘汰了一个key，那么会模拟一条del命令发送给slave，slave再剔除key
过期key处理
master每次接收写命令后，先在内存中写入数据，然后异步发送给slave
异步复制
master默认10s发送一次
心跳同步，主从之间会互相发送心跳同步
heartbeat
原理
主从架构
负责监控master和slave是否正常工作
集群监控
当某个redis实例有故障时，哨兵负责发送消息作为报警通知给管理员
消息通知
如果master挂了，会自动转移到slave上
故障转移
如果故障发生转移了，通知client客户端新的master地址
配置中心
功能
本身也是分布式的，作为一个哨兵集群在运行
故障转移时，判断一个master是否挂了，需要大部分哨兵都同意才行，涉及到了分布式的问题
slave默认1s发送一次
即使部分哨兵挂了，哨兵集群也还能正常工作，如果作为一个高可用机制故障转移系统本身是单点的，那就太坑了
只要有一个哨兵认为要故障转移就会发生故障转移
configuration:quorum=1
就是大部分哨兵是运行的
2个哨兵的majority是2
3个哨兵的majority是2
4个哨兵的majority是2
5个哨兵的majority是3
要求majority
如果是两个哨兵，如果其中一个哨兵和master在同一台机器上机器挂了后，由于达不到majority的数量，所以哨兵不会执行故障转移操作，所以无法保证高可用，所以至少得有三个哨兵实例组成哨兵集群
同时会选举一个哨兵来进行故障转移
为什么两个节点无法工作？
quorum=2
majority=2
所以可以允许挂一台哨兵机器
经典模式是3节点哨兵集群
至少需要3个实例，来保证自己的健壮性
哨兵+redis主从的部署架构，是不会保证数据零丢失的，只能保证redis集群高可用
对于哨兵+redis主从这种复杂的部署架构，尽量在测试环境和生产环境都进行充足的测试和演练
核心知识
数据写master成功，但是因为是异步复制，还没有复制到slave此时master挂了，发生了主备切换，那么没同步的数据就丢了
master出现了异常性的，有相同数据，相同工作的两个节点
一般由网络分区造成
当网络恢复后，此时有旧的master会被降为slave那么之前往这个节点上写的数据会丢失（因为他会从另一个master上同步数据）
集群脑裂
要求至少有1个slave
min-slaves-to-write 1
数据复制和同步的延迟不能超过10s
min-slaves-max-lag 10
一般会在client做降级，写到本地磁盘
在client对外接收请求
再做降级，做限流，减慢请求涌入的速度
1
client将数据临时写入kafka
每隔10分钟去队列里面消费一次，尝试重新发挥master
2
client采取的措施
异步复制如果时间超过10s，master就会拒绝写操作，把异步丢失的数据控制在一个范围内（client使用本地缓存或者尝试停顿一段时间再写）
脑裂的时候，由于slave都联系不到了，所以超过10s后，旧的master就会拒绝写入请求了所有最多丢10s的数据
一旦所有的slave数据复制和同步延迟都超过了10s，那么master就不会接收任何请求了
解决方法
哨兵主备切换的数据丢失问题
sdown和odown是两种失败状态
就是一个哨兵，他觉得master宕机了，那么就是主观宕机
sdown达成的条件很简单，如果一个哨兵ping一个master，超过了is-master-down-after-milliseconds指定的毫秒数后，就主观认为master宕机了
sdown到odown的转换条件很简单，如果一个哨兵在指定的时间内，收到了quorum指定数量的其他哨兵也认为那个master是sdown了，那么就认为是odown，客观的认为master宕机了
sdown是主观宕机
如果quorum数量的哨兵都认为master宕机了，那么就是客观宕机
odown是客观宕机
sdown和odown转换机制
哨兵互相之间的发现是通过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如果要成为潜在的master候选人，哨兵会确保slave在复制现有master的数据
如果slave连接到了一个错误的master上，比如故障转移之后，那么哨兵会确保它们连接到正确的master上
slave配置的自动纠正
需要quorum数量的哨兵认为sdown，从而转换成odown
然后选举一个哨兵来做切换，这个哨兵还得得到majority个哨兵的授权，才能正常执行切换
如果quorum<majority，比如5个哨兵，majority就是3，quorum设置成2，那么就得三个哨兵授权才可以执行切换
但是如果quorum>=majority，那么必须quorum数量的哨兵都授权，比如5个哨兵，quorum=5，那么需要5个哨兵都授权才能执行切换
如果一个master被认为odown了，而且majority（绝大多数）哨兵都允许了准备切换，那么某个哨兵就会执行准备切换操作
(down-after-milliseconds * 10) + milliseconds_since_master_is_ins_SDOWN_state
如果一个slave和master断开连接已经超过了down-after-milliseconds的10倍外加master宕机的时长，那么slave就被认为不适合选举为master
跟master断开连接是时长
slave优先级
复制offset
run id
此时首先要选举出一个slave来会考虑的slave的信息
slave-priority越低，优先级就越高
如果slave-priority相同，那么看replica offset， 哪个slave复制了越多的数据，offset越靠后，优先级就越高
如果上面两个条件都相同，那么选择一个run id比较小的slave
执行切换的那个哨兵，会从要切换到的新master那里得到一个configuration epoch，就是一个version号，每次切换的version号都必须是唯一的
如果第一个哨兵切换失败了，那么其他哨兵会等待failover-timeout时间，然后接替继续进行切换，此时会重新获取一个新的configurationepoch，作为新的version号
configuration epoch
哨兵完成切换后，会在自己本地生成最新的master配置，然后同步给其他的哨兵，就是通过之前说的pub/sub机制
同步master配置给其他哨兵的时候，会携带之前的version号，其他哨兵会根据version号的大小来更新自己的master配置
configuration 传播
slave->master选举算法
核心原理
哨兵模式
key是如何寻址的
分布式寻址有哪些算法
了解一致性hash算法吗
如何动态增加和删除一个节点
疑问
我们只要基于redis cluster去搭建redis集群即可，不需要手动去单件主从架构+读写分离+哨兵集群
主要用于海量数据，如果数据量少，用主从架构+哨兵模式即可
自动将数据进行分片，每个master上放一部分数据
提供内置的高可用支持，部分master不可用时，还是可以继续工作的
需要开放两个端口，1个6379，一个10000以上，比如16379，用于节点间通信
集群模式
主要技术
缓存
不支持事务
不支持外键
这样可以在内存中缓存更多的索引
单纯做查询的话，性能更好
数据和索引是分开存储的
非聚簇索引
支持全文检索
表锁
表定义
.frm
数据文件
.myd
索引文件
.myi
会生成三种文件
MyISAM现在用的很少了
支持事务
支持外键
数据和索引存在同一个文件上
聚簇索引
不支持全文检索
行锁
表定义文件
数据+索引文件
.idb
会生成两种文件
InnoDB现在比较常用
存储引擎
B+树
使用的数据结构
如果最左的索引没有被使用到，则其他索引不会生效，因为是无序的
最佳左前缀法则
联合索引
!=
or 前后不是同一个所以
is null 或者 is not null
like
联合索引不符合最左前缀法则的时候
对列用了函数
索引失效的情况
索引
共享锁就是读锁
写锁拥有比读锁更高的优先级写锁可以插队到读锁前面但是读锁无法插队到写锁前面（排队的队列）
独占锁就是写锁
间隙锁
开销最小
并发最低
写锁时，独占，其他人不能操作
读锁不会阻塞
锁定整张表
表锁是最基本的锁策略
开销最大
并发最高
在存储引擎层面实现，服务器层没有实现
锁策略
读写锁
多个事务在同一资源上相互占用，并请求对方占有的资源而造成的额性循环现象
多个事务同时锁定同一个资源也会产生死锁
检测到死锁后立即返回false
InnoDB目前的做法是，将持有最少行级排他锁的事务进行回滚
产生死锁后只有部分或者全部回滚事务才能打破死锁
死锁是不可避免的
因此应用程序在设计的时候要考虑怎么处理死锁
只要将因死锁而回滚的事务重新提交即可
为了解决死锁，数据库实现了各种死锁检测机制和死锁超时机制
死锁
事务是一组原子性的SQL是一个独立的工作单元
一个事务是逻辑上不可分割的最小单元，一个事务的所有操作要么全部成功，要么全部失败
原子性
A
比如A和B一共5000员，那么不管他们之间怎么转账，他们的总金额都必须是5000
从一个一致性转移到另外一个一致性
一致性
C
读未提交
读已提交
可重复读
串行化
隔离级别
多个事务之间互不影响
隔离性
I
事务一旦提交，那么他的修改就会永久保存在数据库中
持久性
D
特性
事务id，全局唯一递增的
事务
多版本并发控制
每个事务会对操作的那条数据会生成一个这个版本（用事务id标识）的快照
如果另一个事务也操作同一条数据，那么也会存在一个另一个事务版本的快照，也就是会有两个
当前事务只能查到版本小于自己版本的快照记录
在大多数情况下避免加锁，大家都实现了非阻塞的读操作
写操作也只锁要操作的行
MVCC
explain：看执行计划
调优
MySQL
数据库
O(n²)
平均时间复杂度
最坏时间复杂度
从排序序列向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换位置，使值较大的元素逐渐从前移向后部，最终大的值在后面，小的值在前，像水泡一样，所以称为冒泡排序
从0到n-1找到最大的，把最大的值放到n-1的位置
从0到n-2找到次大的，把次大的放到n-2的位置
以此类推（如果要逆序的话，那么就是找最小的）
如果在某次排序中一次交换都没发生，那么意味着序列已经有序了，可以结束排序了
示例
冒泡排序
第一次从0到n-1中找到最小的，与0位置的值进行交换，注意并不是立即交换，而是整个比较结束了再交换
第二次从1到n-1中找次小的，然后与1位置的值进行交换
以此类推（如果要逆序的话，就是找最大的）
选择排序
以我们这个待排序数组为无序数组
先取无序数组中第2个元素与第1个元素比较，并保证他们的顺序（如果顺序不符合就调整位置）
然后对无序数组里面的第3个元素与第2个和第1个进行比较，然后把它放到合适的位置
以此类推
跟打扑克整理牌的意思是一致的
如果最小的值在数组后面，那么整个数组的值都要进行移动，效率过低
插入排序
交换排序
O(nlogn)
O(n^s) 1<=s<=2
也是一种插入排序，但是进行了优化，也叫缩小增量排序
对数组按照下标的一定增量（步长，比如0和5的步长是5）进行分组（即0、5放一组，1、6放一组，这种）（以数组长度为10举例）
两个数字一组，那么需要分10/2=5组，步长定义为5
各个分组进行插入排序
缩短增量（步长），再进行插入排序，5/2=2（取整），数据被分成两组
直至增量为1，排序结束
经过这种处理，小的值一般都会被放到了前面，用插入排序的时候，移动量大大减少
性能相比插入排序更差，以为时间都花在交换上了，插入排序不是交换的是移动的
进行插入时采用交换法
交换式
性能相比插入排序提升很多
进行插入时采用移动法
移动式
希尔排序
对冒泡排序的改进
找到标志位，把数据分成左右两部分，保证左边的数据都比它小，右边的数据都比它大
然后对两边的数据分别再进行快速排序
快速排序
先把数组进行拆分，拆分到最低层级后，将数据进行合并，合并成有序序列
然后逐级递归的进行合并，最终形成有序
归并排序
速度最快，内存占用最多，海量数据时容易oom异常
构建10个桶
先把数组里面元素按照个位数的大小放置到对应的桶里面
然后按桶下标的顺序把数据取出来放到数组里
第二次把数组里面元素按照十位数的大小放置到对应的桶里面
基数排序
排序
二分查找
插值查找
斐波那契查找
查找
单链表翻转
埃筛法
双指针法
算法
JUC
before
after
实例场景1：单引擎解耦前
实例场景2：视图库的订阅
解耦
结构化
入myBase
入myFace
入Mongo
实例场景1：单引擎入库同步高延时的场景
异步
实例场景1：单引擎实时接入路人数据没有mq系统高峰期挂了
削峰
有什么业务场景需要用到它
为什么使用消息队列
待补充
系统可用性降低，引入的外部依赖越多，越容易挂掉，万一mq挂掉，所举例场景都不能正常工作
系统复杂性提高，加入mq怎么保证不重复消费，怎么保证消息不丢失，怎么保证消息传递的顺序，写挂了数据积压怎么办
一致性问题，比如异步解耦后A处理成功，B、C处理失败怎么处理？这样数据的一致性就有问题了
消息队列的优缺点
各个队列优缺点比较
当一个节点挂了后，会丢失1/n的数据（n为节点数量）
引入了副本机制后，才有了高可用
kafka 0.8版本前没有高可用机制
一个topic由多个partition组成
每个partition都有自己的副本
partition的leader和副本不在同一台机器上
数据的读写在partition的leader上进行
partition的leader的选举算法
机器宕机后，可以从副本中选举新的leader，数据不会丢
分布式模式保证高可用
怎么保证高可用
重复消费的场景：一般是offset提交失败造成的重复消费
怎么保证不重复消费
消费者自动提交offset，具体查看rabbit
消费者弄丢数据
leader收到数据，还没同步给follow，然后leader挂了
此时会重新选举一个follow作为leader
但是在新leader里面就没有那个数据了
kafka弄丢了数据
服务端：replication.factor 副本数量，必须大于1
服务端：min.insync.replicas 这个值必须大于1表示至少有1个副本和主节点保持同步，数据没有掉队
生产端：acks=all 每条数据都入到副本后，才认为写成功了
生产端：retries=Integer.Max， 发送失败无限重试
怎么保证消息不丢
给同一批数据指定相同的key值
数据就会进入同一个partition
kafka的特性一个partition只能被一个消费者消费这样就可以保证消息的顺序
怎么保证消息的顺序性
每当新的controller产生的时候就会在zk中生成一个全新的、数值更大的controller epoch的标识，并同步给其他的broker进行保存，这样当第二个controller发送指令时，其他的broker就会自动忽略。
通过controller epoch解决
kafka脑裂
消息积压怎么处理
kafka
入门演练用的，没什么讲的必要
单机模式
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所在那台机器挂掉了，数据就丢失了，无法消费了
3、消费者向Q1写入数据时，假设向A机器写入，那么A机器上的Queue会把数据同步到B、C机器
4、消费者消费消息时，无论连哪台机器都能拿到完整的数据
每个节点都有这个Queue的一个完整镜像包含这个Queue的全部数据，所以这个模式叫镜像集群模式
与集群模式的不同点
任何节点宕机都没问题，其他节点都有数据
他不是分布式的，如果Queue数据大到机器无法容纳时，怎么办？
镜像集群
rabbit不是分布式的，它有三种模式
启用rabbit的事务机制，事务机制是同步的会导致消费者的吞吐量急剧下降
使用confirm机制，把channal调整在confirm模式，提交消息后就不用管了，走消息的回调机制
网络传输过程中丢失了
数据传输到mq，但是mq内部出错，没保存下来
生产者端数据丢失
Queue创建时将它设置为持久化这样会持久化queue的元数据但是不会持久化queue里面的数据
发送消息的时候将消息的deliveryModel设置为2，将消息持久化，这样mq就会将消息持久化到磁盘中
将数据持久化到磁盘
mq收到消息暂存在内存中，结果消费者还没消费，mq挂了缓存在内存的数据就丢失了
消息写到了mq，但还没来得及持久化，mq就挂了
即便开启了持久化，也会丢数据
mq服务端数据丢失
只有一种情况下会发生，打开了消费者的autoAck机制
关闭autoAck，手动进行ack，确保消息正确被消费后再进行ack
消费者收到消息，还没开始处理，消费者挂了，mq以为消费完了
消费者端数据丢失
存在的数据丢失的问题
rabbit
主要使用队列
消息队列
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
1s后刷入os cache中
buffer快满的时候也会刷到os cahce
数据在buffer中时，暂时无法被查出来
写入buffer
当segment file数量足够多时，会触发merge操作，合并成一个大segment file
触发merge的时候，会对.del文件也进行merge操作，把删除的记录剔除掉（物理删除）
os cache再刷到磁盘中，形成segment file（生成segment file的时候就已经建立好了倒排索引库）数据从buffer刷到os cache的过程叫做refresh当buffer为空的时候，不会触发refresh且触发refresh后数据才能被搜索到每次refresh都会生成一个新的segment file
先存入os cache中
5s 后刷入磁盘文件
buffer、os cache 里面的数据强制刷出到磁盘并清空缓存（触发refresh）
将commit point写入磁盘，记录所有对应的segment file
旧的translog文件清除，把数据存储到磁盘中，并生成新的translog文件
当translog足够大，或者经过30分钟时会触发commit操作
写入translog
所以会有丢数据的风险，大概会丢5s。也可以配置不写入os cache，直接落盘，这样数据不会丢，但是写入性能会指数下降
5、数据写入primary shard的时候，同时写入es的内存buffer和translog
写入
将请求发送到一台es机器，这个节点被称为协调节点
协调节点对document进行路由，将请求转发到对应的node，此时会使用随机轮询算法，在primary shard 和replica shard中随机选择一个，让读取请求负载均衡
接收请求的node返回document给协调节点
协调节点，返回document给到客户端
get
客户端发送请求到协调节点
协调节点将请求发送到所有的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更多的内存尽量让内存容纳所有的index segment file索引数据文件那么搜素的时候基本都是走内存，性能会非常高
数据量1T的情况下，起码要保证fileSystem cache的内存加起来有512G，这样有一半的数据可以走内存搜索
生产环境中，尽量在es中存储少量的数据，只存储你要搜索的字段，内存留给fileSystem cache这样所有的搜索几乎都可以走内存，性能就很高了（单条数据量越大，能缓存的数据量就越少了）
hbase的特点是对海量数据做在线存储，不对他做复杂的搜索，只做很简单的根据id进行查询
相当于es先搜索出id，然后去hbase里捞详细数据
所以一般推荐es+hbase的架构
但是如果索引数据有1个T，但是实际内存只有100G的情况下怎么保证高性能呢
fileSystem cache
把经常有人访问的数据，专门做一个缓存预热子系统，对热数据定时访问一下，让数据进入fileSystem cache里面去，这样其他人来访问的时候性能就会好很多（例如：微博提前将大V数据预热下，淘宝提前将热门商品预热下）
如果按照上述方案去做，es中每台机器写入的数据量还是超过了fileSystem cache的一倍以上
缓存预热
最好冷数据一个索引，热数据一个索引，这样确保热数据在预热后尽量留在fileSystem cache中，不会被冷数据冲刷掉
冷热分离
数据模型尽量设计好，兼容以后的各种运算情况
尽量不要用es里面的各种关联查询、复杂查询语法，一旦用了性能一般都不好
document模型设计
第100页，那么对于就第1000条左右数据
每个shard查1000条数据，返回给协调节点
假设有5个shard，那么协调节点拿到了5000条数据
对5000条数据进行合并、处理，返回第100页的10条给客户端
那如果shard数更多一些呢？翻的页更深写呢？比如10000页，那是不是每个shard返回的数量都越来越多，协调节点汇总要处理的数据也越多
es分页性能很差，比如每页10条数据，现在你要查第100页的数据
scroll原理是保存一个数据快照
然后在一定时间内，如果不断的滑动往后翻页
scroll不断的通过游标获取下一页数据，这个性能是很高的比es实际分页要好得多
可以用scroll来进行处理或者after search（scroll只适合一页一页往下翻的，不进行跳页，不从第1页跳到10页，再跳到5页这种）
分页性能优化
es的搜索引擎严重依赖底层的fileSystem cache（操作系统缓存）
在几十亿数据量级下如何优化查询性能
5-7台机器
每台机器64核512G内存
集群总内存3.5T
es的部署架构是什么
es集群日增数据量大概是2亿条
每天日增数据量大约是300G
每月增量90亿左右，大小9T，目前有60T，数据存留半年
每个索引的数据量大概有多少
每天自动建索引，分为人、车、其他等
每个索引的数量大约是：7-8千万条
建了12个shard
每个索引大概有多少个分片
生产环境的分布式搜索引擎是怎么部署的
elastic search
主要使用
搜索引擎
大平台拆成各个子系统
易于维护
减少冲突
减少工作量，避免重复测试
轻量发布，易于部署
为什么要进行服务拆分
需要进行多轮拆分
后续业务发展，可能需要再进行拆分
最理想状态下，1个人负责1-3个服务
怎么进行拆分
当然可以，纯http接口访问也行
但是要考虑很多问题，请求超时怎么办，负载均衡怎么处理，请求的服务方异常了怎么办
拆分后不用dubbo可以吗
dubbo和thrift有什么区别
provider和consumer
接口层
config层
proxy层
dubborpc框架
服务调用
spring cloud
分布式服务框架
一个系统走本地事务
多个系统怎么进行分布式事务
分布式事务
分布式会话
比如不能重复扣款
比如网络原因，重复提交
一个订单重复提交两次，被扣两次款，这种要怎么避免
问题
每个请求得有一个唯一标识id
处理完得有一个记录标识，标识这个标识id的数据已经处理过
每次接受请求前要判断之前是否已经处理过
单引擎图片md5做id，插入前判断记录是否有存在
举例：
分布式系统中接口的幂等性如何保证
一般很多接口是不需要保证的
搞一个网关，每个请求都携带一个id，同一批请求携带相同的id网关根据id求hash，然后把同样id的请求发到同一台服务器上
比如1/2/3，一共三个请求，现在系统是分布式的，不同请求可能会被分发到不同服务器上去，怎么保证他们的执行顺序
分布式锁，太重了，不建议
分布式系统中的接口调用如何保证顺序
微服务化
分布式业务系统
分布式存储
分布式
一站式解决方案
用数据库来存储路由路径，从而实现动态路由
对zuul二次开发
动态路由
灰度发布
授权认证
性能监控
系统日志
数据缓存
限流熔断
作用
配置一下不同请求路径和服务的对应关系
请求到了网关，他查找匹配的服务
把请求用Http协议进行封装
然后就把请求转发给某台机器
配合ribbon
zuul
nginx里面的一个基于lua写的模块，实现了网关的功能
Kong
Nginx+Lua（OpenResty）
基于Netty自研
自研网关
api网关
维护所有注册服务的一个信息
服务注册表
readOnly其他服务从只读缓存获取服务信息拉不到信息时，会向上级将数据同步过来
用这种方式，可以避免并发冲突避免上锁，可以解决并发问题
readWrite
二级缓存
子主题
其他配置参数
Eureka
ZooKeeper
集群中机器地位一样
任意一台机器的数据都会同步给其他机器
peer-to-peer
AP
牺牲了一致性，但是可以保证最终一致性
因为其他的服务经过心跳就能达到新的一致了
感知是几十秒级的，甚至分钟级
eureka
leader可以写
leader、follow可以读
leader、follow两种角色
leader选举过程中不可用
CP
感知是秒级的
C：一致性
A：可用性
P：分区容错性
CAP
比较
服务注册与发现
Hystrix
熔断机制
对接口打个注解
针对注解生成动态代理
然后用动态代理去调其他方法时
在底层生成http协议格式的请求
会先用ribbon获取机器列表，然后进行负载均衡，选出一条机器来
然后把请求发送到这台机器上
Feign
服务接口调用
定时拉取eureka的注册表信息
进行负载均衡
Ribbon
负载均衡
Spring Cloud NetFlix
半自动，需要整合别人的
自己实现
Dubbo
Zookeeper
借助Hystrix
熔断
Apach Dubbo Zookeeper
Spring Cloud Alibaba
解决方案
微服务
应用层
表示层
会话层
传输控制层
网络层
数据链路层
物理层
七层架构
http/ftp协议
建立连接
目的
1、客户端发送syn给服务端
2、服务端发送sync+ack给客户端
3、客户端发送ack给服务端
为什么需要三次握手
1、两次连接后对客户端来说，它是可发送可读取的，没有问题
2、对服务端来说，它能接受，发送，但是发送的数据客户端能不能收到，还是未知的
3、所以需要客户端再回个ack，这样服务端才能确定，请求可达
两次握手后连接就已经建立了，为什么还需要第三次？
发送队列
接收队列
握手完开辟资源
三次握手
表示客户端想要断开
1、客户端发送一个FIN报文到服务端
服务端收到消息，表示收到请求了
2、服务端回一个FIN+ACK
服务端发送报文，表示服务端也想断开
3、服务端再发送一个FIN报文
客户端回一个ack表示收到，同意断开
4、客户端回一个ACK
释放资源
四次分手
什么是连接
即A向B发送数据包
B需要向A回复，表示有收到
可靠的，所以有发送就有回复（每个数据包的发送都是这样）
怎么保证可靠
面向连接的可靠的传输协议
TCP协议
UDP协议
路由的下一个点。如果路由器没有直接连接到目的网络，它会有一个提供下一跳路由的邻居路由器，用来传递数据到目的地
存储下一跳的信息地址
route -u 命令查看
诸如目标网络号、网关、掩码等信息
如果我们要发包给220.12.10.11这个ip
首先会和genmask（掩码）做二进制与运算，得到的值作为网络号和destination（目标）进行比较
如果值相等表示可以联通，然后查看gateway（网关），如果gateway为0.0.0.0表示可以直达，无需转发，直接发送即可
如果gateway值为某个ip，则把数据包发给这个ip
然后通过这个ip进行下一跳逐步转发，知道发送给220.12.10.11为止
比如：如图
路由表
数据怎么发到指定ip
IP
比如当前家里局域网是192.168.150.11，想要访问220.12.10.11这个ip
那么我们数据包里面的ip填的是哪个ip呢，是按照网络层里面说的网关地址，还是220.12.10.11这个ip地址
如果填网关ip，那么网关收到这个数据后就处理了，并不会发送给目标ip了
如果填写目标端ip，在这个网络内直接就不可达了
内网是怎么访问公网的
1、根据mac，直接将包发给网关
2、网关收到数据包后，一看ip，是要发给220.12.10.11不是给自己的
3、广播获取所有ip与其对应的mac地址，并判断能否直达
4、如果能直达，则直接将数据包发给220.12.10.11
5、如果不能直达，则对数据包进行处理，mac改成下一跳的mac地址，将数据包发给下一跳的网关
6、重复执行5，直到4为止
采取的措施是，ip填目标端（220.12.10.11）的ip，mac地址填网关的地址
如图
arp -a 命令广播获取可达的ip及mac地址
链路层
TCP/IP协议
能建立唯一的连接
端口号0-65535
客户端 ip+port 服务端 ip+port
Socket
网络通信
JVM
线程安全
方便
不能按需创建即便不需要也会被加载
如果单例过于复杂可能存在内存问题
存在序列化和反序列化的问题
直接静态变量实现
饿汉模式
能按需创建
线程不安全
懒加载的实现方式
懒汉模式
能按需
懒汉模式的扩充需要加上volatile关键字
双端检锁机制
一个类加载时，其子类不会马上加载，当且仅当其静态成员（变量、方法等）被调用时，才会被加载
实现简单
静态内部类实现
具备以上所有的优点，同时可以规避序列化和反序列化的问题
枚举类实现
实现方式
单例模式
设计模式
因为位运算的效率很高，比直接取模要快个10倍左右
与任意值做&，值都只有0和16两种
而15的二进制为 0000 0000 0000 1111
15与任意值做&，可能的值有0-15，共16种
以16为例，对应的二进制为 0000 0000 0001 0000
为什么要length -1
hash值一样时，叫hash碰撞，然后会去遍历链表看该记录是否有存在，没存在就插入，使用头插法
map初始化大小是16，后续会以2的幂进行扩充，之所以是2的幂，主要是因为根据hashcode求索引值时，使用的是位运算
所以map初始化的时候即使你指定了大小，他也会转换成对应的大于你的初始值的最小的2次幂的值
hashmap不是线程安全的主要就是指扩容的时候
hashmap扩容的时候有死锁的风险
数组+链表
jdk1.7
数组-》链表使用尾插法
链表长度超过8是（并且数组大小小于64时），转红黑树，当红黑树长度小于6时又会从红黑树转回链表
让高位参与运算，降低发生hash碰撞的几率
扰动函数
HashMap在jdk1.7中采用头插入法，在扩容时会改变链表中元素原本的顺序，以至于在并发场景下导致链表成环的问题。而在jdk1.8中采用尾插入法，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了
用尾插法为什么不用头插法了？
数组+链表+红黑树
jdk1.8
执行构造方法的时候并不会初始化，而是在插入第一个元素的时候才开始初始化
HashMap
无序，查找性能差
二叉树
左节点的值都比根节点小，右节点的值都比根节点大
当插入的数据都是有序的时候，就退化成链表了
二分查找法就没用了
二叉有序树
保持最长子树和最短子树的层数差不超过1
牺牲插入性能保证查询性能
二分查找法可以使用
二叉平衡树
最长子树不超过最短子树的两倍即可
尽量保持插入、查询性能的平衡
红黑树
从而提高查询效率
因此可以减少数的高度
一个节点可以存在多个值
索引和数据一起存储
进行范围查找时会存在回旋查找的问题
B数
相当于B树+单向链表
索引存在非叶子节点，数据存在叶子节点
并且数的所有叶节点形成一个有序链表，所以范围查找时不存在回旋查找的问题
Tree（这个网站包含了很多tree的数据结构）
进行范围查找，均存在回旋查找的问题
数据结构
在BeanPostProcessor接口的beforeInitial阶段就执行了，所以最早
1、@PostConstruct
2、实现InitializingBean接口
3、xml配置的init-method
类初始化后执行方法的顺序
先调用initializingBean的afterPropertiesSet方法
再调用init-method
如果afterPropertiesSet报错了，init-method不会被调用
在invokeInitialBean()方法中被调用执行
Spring
Java知识图谱
0 条评论
回复 删除
下一页
