sequence,雪花算法(将64位中的每一段根据时间,区域,机器,序列号组合生成唯一id)
10G整数文件中寻找中位数或者第K大数
- 采用基于字节的桶排序将数字分到不同的桶中,比如找到第k大数,则先找出每个桶中的第k大数,在比较。
- 整形是4byte,有32位,先按高八位建255个桶
- 如果内存只有2g,则每次读取2g的数据遍历放到255个桶中,并统计255个桶的量,2g读取完后将每个桶的数据导出到磁盘,循环读完10g数据。
- 这时根据255个桶的计数计算出中位数在哪个桶,然后开始建后续8位的桶,直到最后低8位也分完,这时候对桶内数据进行快排即可。
如何实现分布式锁
- 数据库乐观锁,利用了mysql update行锁的特点,在每次update前先select出数据然后根据数据的版本进行update,如果版本变了就不更新并把错误抛给用户重试最终达到一致。
- redis setnx,当该key不存在时就设置value,如果已经存在该key了就直接返回。
- zookeeper 不能重复创建同一个节点,创建持久结点时需要主动删除结点释放,创建临时结点时断开连接就会释放
什么是分布式系统,分布式原理是什么
将一个大的系统拆分成多个细小的子系统,子系统之间通过网络通信的构成的大系统称为分布式系统。
分布式事务怎么做
事务有四个特性acid
- a:原子性,事务中的操作不可分割,要么一起成功,要么一起失败
- c: 一致性,数据库中的数据要是完整的,也包含各资源状态的一致
- i:隔离性,事务之间要有自己的工作空间,不能相互干扰
- d:持久性,事务完成后数据要落盘
- 数据库的事务是使用undo和redo日志做的,undo会记录未提交操作的数据用来回滚,redo记录已提交操作的数据落盘。
常用的分布式事务有几种方式:
- 2pc,两阶段提交,服务a发prepare请求给协调器,协调器将请求写到本地日志,然后发送prepare给其他各服务,执行者收到请求后执行本地事务,但不会commit,然后将结果返回给协调器,协调器判断所有的返回如果都成功则让所有执行者提交commit,如果有失败的则全部回滚。
- 消息表,服务a在发起事务的时候执行本地事务的消息同时写入消息表然后发送消息给服务b,服务b在完成本地事务后回消息给服务a调度器清除消息表,如果没有清除,则事务调度器读取消息表发送消息给服务b,这就需要服务b有幂等性
- 消息事务,消息事务是通过消息中间件实现的类似2pc功能比如rocketmq,服务a提交prepare给mq,然后执行本地事务,如果失败则回滚,如果成功则确认prepare消息,mq相当于事务调度器会定期扫描prepare消息询问发送方是否要发送消息,而消费方如果失败则需要一直重试
- TCC事务补偿,先锁住资源,然后使用锁住的资源执行业务逻辑,如果失败则释放资源,如果成功则落盘。
分布式cap,base理论
分布式系统的cap理论,c一致性,a可用性,p分区容错性,因为网络和机器原因不可控所以p是一定要保障的,大家都知道cap不能同时满足,所以只能在c和a中选择,因此有base理论,ba基本可用,s软状态(在最终一致前允许存在不一样的状态),e最终一致
zookeeper
使用场景
- 配置管理,由于强一致性,可以存放集群配置
- 集群管理,有新机器加入时在指定目录创建临时znode,然后集群所有机器对目录创建watch,当有机器断连时临时znode会自动删除,集群机器收到通知
- 分布式锁,集群机器同时创建znode,创建成功的抢到锁,zonde删除释放锁
- 队列,采用编号znode,按照编号顺序依次执行
集群
集群中有三种角色,leader,follower和observer,leader负责写操作,保证集群事务的顺序性,follower参与选举,observer负责读操作。只有当集群初始化和领导者失去多数派支持时会发生领导者选举。
原理
zookeeper的核心是原子广播,采用zab协议,主要有恢复模式(选主)和广播模式(同步)
原文
https://juejin.im/post/5da147e3f265da5bab5bcb57