没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
分布式集群架构场景化解决⽅案课程笔记(讲
师:应癫)
主要课程内容
第⼀部分:⼀致性Hash算法
第⼆部分:集群时钟同步问题
第三部分:分布式ID解决⽅案
数据表A(ID),A的数据量很⼤的情况下,我们会进⾏分表操作,A(ID)表拆分成了A1表
(ID)+A2表(ID),需要⼀种在分布式集群架构中能够产⽣全局唯⼀ID的⽅案
第四部分:分布式调度问题(定时任务的分布式)
第五部分:Session共享(⼀致性)问题
浏览器—>Nginx—>Tomcat1(Session中记录⽤户信息)
—>Tomcat2
—>Tomcat3
分布式和集群
分布式和集群是不⼀样的,分布式⼀定是集群,但是集群不⼀定是分布式(因为集群就是多个实例⼀起
⼯作,分布式将⼀个系统拆分之后那就是多个实例;集群并不⼀定是分布式,因为复制型的集群不是拆
分⽽是复制)
第⼀部分 ⼀致性Hash算法
第⼀部分 ⼀致性Hash算法
Hash算法,⽐如说在安全加密领域MD5、SHA等加密算法,在数据存储和查找⽅⾯有Hash表等, 以上
都应⽤到了Hash算法。
为什么需要使⽤Hash?
Hash算法较多的应⽤在数据存储和查找领域,最经典的就是Hash表,它的查询效率⾮常之⾼,其中的
哈希算法如果设计的⽐较ok的话,那么Hash表的数据查询时间复杂度可以接近于O(1),示例
需求:提供⼀组数据 1,5,7,6,3,4,8,对这组数据进⾏存储,然后随便给定⼀个数n,请你判断n是否存在
于刚才的数据集中?
list:List[1,5,7,6,3,4,8]
// 通过循环判断来实现
for(int element: list) {
if(element == n) {
如果相等,说明n存在于数据集中
}
}
以上这种⽅法叫做顺序查找法 :这种⽅式我们是通过循环来完成,⽐较原始,效率也不⾼
⼆分查找:排序之后折半查找,相对于顺序查找法会提⾼⼀些效率,但是效率也并不是特别好
我能否不循环!不⼆分!⽽是通过⼀次查询就把数据n从数据集中查询出来???可以!
定义⼀个数组,数组⻓度⼤于等于数据集⻓度,此处⻓度为9,数据1就存储在下标为1的位置,3就存储
在下标为3的元素位置,,,依次类推。
这个时候,我想看下5存在与否,只需要判断list.get(5) array[5] 是否为空,如果为空,代表5不存在于
数据集,如果不为空代表5在数据集当中,通过⼀次查找就达到了⽬的,时间复杂度为O(1)。
这种⽅式叫做“直接寻址法”:直接把数据和数组的下标绑定到⼀起,查找的时候,直接array[n]就取出
了数据
优点:速度快,⼀次查找得到结果
缺点:
1)浪费空间,⽐如 1,5,7,6,3,4,8,12306 ,最⼤值12306 ,按照上述⽅式需要定义⼀个⽐如⻓度为
12307的数组,但是只存储零星的⼏个数据,其他位置空间都浪费着
2)数据如:1,5,7,6,3,4,8,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2最⼤值12,⽐如开辟13个空间,存储
不了这么多内容
现在,换⼀种设计,如果数据是3,5,7,12306,⼀共4个数据,我们开辟任意个空间,⽐如5个,那
么具体数据存储到哪个位置呢,我们可以对数据进⾏求模(对空间位置数5),根据求模余数确定存储
位置的下标,⽐如3%5=3,就可以把3这个数据放到下标为3的位置上,12306%5=1,就把12306这个
数据存储到下标为1的位置上
上⾯对数据求模 (数据%空间位置数) 他就是⼀个hash算法,只不过这是⼀种⽐较普通⼜简单的hash
算法,这种构造Hash算法的⽅式叫做除留余数法
如果数据是1,6,7,8,把这4个数据存储到上⾯的数组中
在此基础上采⽤开放寻址法(了解)
开放寻址法:1放进去了,6再来的时候,向前或者向后找空闲位置存放,不好的地⽅,如果数组⻓度定
义好了⽐如10,⻓度不能扩展,来了11个数据,不管Hash冲突不冲突,肯定存不下这么多数据
拉链法:数据⻓度定义好了,怎么存储更多内容呢,算好Hash值,在数组元素存储位置放了⼀个链表
如果Hash算法设计的⽐较好的话,那么查询效率会更接近于O(1),如果Hash算法设计的⽐较low,那么
查询效率就会很低了
所以,Hash表的查询效率⾼不⾼取决于Hash算法,hash算法能够让数据平均分布,既能够节省空间⼜
能提⾼查询效率。Hash算法的研究是很深的⼀⻔学问,⽐较复杂,⻓久以来,Hash表内部的Hash算法
也⼀直在更新,很多数学家也在研究。
除留余数法 3%5
线性构造Hash算法
直接寻址法也是⼀种构造Hash的⽅式,只不过更简单,表达式:H(key)=key
⽐如H(key)=a*key + b(a,b是常量)
hashcode其实也是通过⼀个Hash算法得来的
第 1 节 Hash算法应⽤场景
Hash算法在分布式集群架构中的应⽤场景
Hash算法在很多分布式集群产品中都有应⽤,⽐如分布式集群架构Redis、Hadoop、ElasticSearch,
Mysql分库分表,Nginx负载均衡等
主要的应⽤场景归纳起来两个
请求的负载均衡(⽐如nginx的ip_hash策略)
Nginx的IP_hash策略可以在客户端ip不变的情况下,将其发出的请求始终路由到同⼀个⽬标服务
器上,实现会话粘滞,避免处理session共享问题
如果没有IP_hash策略,那么如何实现会话粘滞?
可以维护⼀张映射表,存储客户端IP或者sessionid与具体⽬标服务器的映射关系
<ip,tomcat1>
缺点
1)那么,在客户端很多的情况下,映射表⾮常⼤,浪费内存空间
2)客户端上下线,⽬标服务器上下线,都会导致重新维护映射表,映射表维护成本很⼤
如果使⽤哈希算法,事情就简单很多,我们可以对ip地址或者sessionid进⾏计算哈希值,哈希值与服务
器数量进⾏取模运算,得到的值就是当前请求应该被路由到的服务器编号,如此,同⼀个客户端ip发送
过来的请求就可以路由到同⼀个⽬标服务器,实现会话粘滞。
分布式存储
以分布式内存数据库Redis为例,集群中有redis1,redis2,redis3 三台Redis服务器
那么,在进⾏数据存储时,<key1,value1>数据存储到哪个服务器当中呢?针对key进⾏hash处理
hash(key1)%3=index, 使⽤余数index锁定存储的具体服务器节点
第 2 节 普通Hash算法存在的问题
普通Hash算法存在⼀个问题,以ip_hash为例,假定下载⽤户ip固定没有发⽣改变,现在tomcat3出现
了问题,down机了,服务器数量由3个变为了2个,之前所有的求模都需要重新计算。
剩余38页未读,继续阅读
yiyi分析亲密关系
- 粉丝: 22
- 资源: 321
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- Python 程序语言设计模式思路-结构型模式:组合模式:将对象组合成树形结构
- 毕业设计基于python矩阵分解的推荐算法研究源码+详细文档+全部数据资料 高分项目.zip
- 基于网络的入侵检测系统源码+数据集+详细文档(高分毕业设计).zip
- 微信小程序源码 旅行故事分享 - 面包旅行App界面设计与文本展示资源下载
- 微信小程序源码 创意互动游戏 - 你画我猜App下载
- 摸底考试_学生版20230305.py
- 课程设计基于FPGA数字钟课程设计源码+课设报告(95分以上).zip
- 基于Java的企业家申报系统设计源码
- Cesium案例,集成各种模型,推演,各种Cesium效果
- 基于Python的Struts2全漏洞扫描利用工具设计源码
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0