网站适合移动端,免费的企业网站建设流程,淘宝网站怎么做会话保持的,app推广方案策划目录 前言应用五#xff1a;负载均衡应用六#xff1a;数据分片应用七#xff1a;分布式存储解答开篇 内容小结 前言 本节课程思维导图 今天#xff0c;我们再来看剩余三种应用#xff1a;负载均衡、数据分片、分布式存储。你可能已经发现#xff0c;这三个应用都… 目录 前言应用五负载均衡应用六数据分片应用七分布式存储解答开篇 内容小结 前言 本节课程思维导图 今天我们再来看剩余三种应用负载均衡、数据分片、分布式存储。你可能已经发现这三个应用都跟分布式系统有关。没错今天我就带你看下哈希算法是如何解决这些分布式问题的。
应用五负载均衡
我们知道负载均衡算法有很多比如轮询、随机、加权轮询等。那如何才能实现一个会话粘滞session sticky的负载均衡算法呢也就是说我们需要在同一个客户端上在一次会话中的所有请求都路由到同一个服务器上。 我们可以通过哈希算法对客户端 IP 地址或者会话 ID 计算哈希值将取得的哈希值与服务器列表的大小进行取模运算最终得到的值就是应该被路由到的服务器编号。 这样我们就可以把同一个 IP 过来的所有请求都路由到同一个后端服务器上。
应用六数据分片
哈希算法还可以用于数据的分片。我这里有两个例子。
如何统计“搜索关键词”出现的次数假如我们有 1T 的日志文件这里面记录了用户的搜索关键词我们想要快速统计出每个关键词被搜索的次数该怎么做呢我们来分析一下。这个问题有两个难点第一个是搜索日志很大没办法放到一台机器的内存中。第二个难点是如果只用一台机器来处理这么巨大的数据处理时间会很长。 针对这两个难点我们可以先对数据进行分片然后采用多台机器处理的方法来提高处理速度。具体的思路是这样的为了提高处理的速度我们用 n 台机器并行处理。我们从搜索记录的日志文件中依次读出每个搜索关键词并且通过哈希函数计算哈希值然后再跟 n 取模最终得到的值就是应该被分配到的机器编号。这样哈希值相同的搜索关键词就被分配到了同一个机器上。也就是说同一个搜索关键词会被分配到同一个机器上。每个机器会分别计算关键词出现的次数最后合并起来就是最终的结果。实际上这里的处理过程也是 MapReduce 的基本设计思想。如何快速判断图片是否在图库中如何快速判断图片是否在图库中 当时我介绍了一种方法即给每个图片取唯一标识或者信息摘要然后构建散列表。假设现在我们的图库中有 1 亿张图片很显然在单台机器上构建散列表是行不通的。因为单台机器的内存有限而 1 亿张图片构建散列表显然远远超过了单台机器的内存上限。 我们同样可以对数据进行分片然后采用多机处理。我们准备 n 台机器让每台机器只维护某一部分图片对应的散列表。我们每次从图库中读取一个图片计算唯一标识然后与机器个数 n 求余取模得到的值就对应要分配的机器编号然后将这个图片的唯一标识和图片路径发往对应的机器构建散列表。当我们要判断一个图片是否在图库中的时候我们通过同样的哈希算法计算这个图片的唯一标识然后与机器个数 n 求余取模。假设得到的值是 k那就去编号 k 的机器构建的散列表中查找。
现在我们来估算一下给这 1 亿张图片构建散列表大约需要多少台机器。散列表中每个数据单元包含两个信息哈希值和图片文件的路径。假设我们通过 MD5 来计算哈希值那长度就是 128 比特也就是 16 字节。文件路径长度的上限是 256 字节我们可以假设平均长度是 128 字节。如果我们用链表法来解决冲突那还需要存储指针指针只占用 8 字节。所以散列表中每个数据单元就占用 152 字节。
假设一台机器的内存大小为 2GB散列表的装载因子为 0.75那一台机器可以给大约 1000 万2GB*0.75/152张图片构建散列表。所以如果要对 1 亿张图片构建索引需要大约十几台机器。在工程中这种估算还是很重要的能让我们事先对需要投入的资源、资金有个大概的了解能更好地评估解决方案的可行性。实际上针对这种海量数据的处理问题我们都可以采用多机分布式处理。借助这种分片的思路可以突破单机内存、CPU 等资源的限制。
应用七分布式存储
现在互联网面对的都是海量的数据、海量的用户。我们为了提高数据的读取、写入能力一般都采用分布式的方式来存储数据比如分布式缓存。我们有海量的数据需要缓存所以一个缓存机器肯定是不够的。于是我们就需要将数据分布在多台机器上。 该如何决定将哪个数据放到哪个机器上呢我们可以借用前面数据分片的思想即通过哈希算法对数据取哈希值然后对机器个数取模这个最终值就是应该存储的缓存机器编号。但是如果数据增多原来的 10 个机器已经无法承受了我们就需要扩容了比如扩到 11 个机器这时候麻烦就来了。因为这里并不是简单地加个机器就可以了。原来的数据是通过与 10 来取模的。比如 13 这个数据存储在编号为 3 这台机器上。但是新加了一台机器中我们对数据按照 11 取模原来 13 这个数据就被分配到 2 号这台机器上了。 因此所有的数据都要重新计算哈希值然后重新搬移到正确的机器上。这样就相当于缓存中的数据一下子就都失效了。所有的数据请求都会穿透缓存直接去请求数据库。这样就可能发生雪崩效应压垮数据库。所以我们需要一种方法使得在新加入一个机器后并不需要做大量的数据搬移。这时候一致性哈希算法就要登场了。
假设我们有 k 个机器数据的哈希值的范围是[0, MAX]。我们将整个范围划分成 m 个小区间m 远大于 k每个机器负责 m/k 个小区间。当有新机器加入的时候我们就将某几个小区间的数据从原来的机器中搬移到新的机器中。这样既不用全部重新哈希、搬移数据也保持了各个机器上数据数量的均衡。一致性哈希算法的基本思想就是这么简单。除了我们上面讲到的分布式缓存实际上一致性哈希算法的应用非常广泛在很多分布式存储系统中都可以见到一致性哈希算法的影子。
解答开篇 内容小结
这两节的内容理论不多比较贴近具体的开发。今天我讲了三种哈希算法在分布式系统中的应用它们分别是负载均衡、数据分片、分布式存储。 在负载均衡应用中利用哈希算法替代映射表可以实现一个会话粘滞的负载均衡策略。 在数据分片应用中通过哈希算法对处理的海量数据进行分片多机分布式处理可以突破单机资源的限制。 在分布式存储应用中利用一致性哈希算法可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题。
