【云计算与大数据技术】数据分片哈希算法、路由算法、复制算法的讲解（图文解释超详细）

男娘i 2023-09-30 17:47 11阅读 0赞

## 一、大数据的存储问题 ##

随着结构化数据量和非结构化数据量的不断增长，以及分析数据来源的多样化，之前的存储系统设计已经无法满足大数据应用的需求，对于大数据的存储，存在以下几个不容忽视的问题

容量 - “大容量”通常是指可达PB级的数据规模

延迟 - 大数据应用不可避免地存在实时性的问题

安全 - 催生出了一些新的、需要重新考虑的安全性问题

成本 - 只有让每一台设备都实现更高的“效率”，才能控制住成本

灵活性 - 大数据存储系统的基础设施规模都很大,为了保证存储系统的灵活性,使其能 够随时扩容及扩展

### 大数据存储技术发展 ###

可以分为以下四个阶段

人工管理

文件系统

数据库

Google File System、HDFS、HBase etc

## 二、海量存储的关键技术 ##

大数据处理面临的首要问题是如何有效地存储规模巨大的数据

通常通过数据分片和数据复制来解决这个问题

![1fad92f9b3f542bcb345f44cb15cfb23.png][]

### 数据分片与路由 ###

对于海量数据 ,将数据进行切分并分配到各个机器中的过程叫分片(shard/partition)，即将不同数据存放在不同节点

数据分片后，找到某条记录的存储位置称为数据路由 (routing)

数据分片与路由的抽象模型如下图所示

![644290e71c7542c1bbd0fb0d854122c4.png][]

### 数据分片 ###

把数据的各个部分存放在不同的服务器/节点中,每个服务器/节点负责自身数据的读取与写入操作,以此实现横向扩展,这种技术称为分片

如何存放数据 - 可以实现用户从一个逻辑节点(实际多个物理节点的方式)获取 数据,并且不用担心数据的存放位置

如何保证负载平衡 - 即如何把聚合数据均匀地分布在各个节点中,让它们需要 处理的负载量相等

#### 哈希分片 ####

采用哈希函数建立 Key-Partition映射，其只支持点查询，不支持范围查询，主要有Round Robin、虚拟桶 、一致性哈希3种算法

#### Round Robin - 其俗称哈希取模算法，若有k台机器，分片算法如下： ####

H (key ) = hash(key) mod k

优点：实现简单

缺点：缺乏灵活性，若有新机器加入，之前所有数据与机器之间的映射关系都被打乱，需要重新计算

#### 虚拟桶 - 在Round Robin 的基础上，虚拟桶算法加入一个“虚拟桶层 ”，形成两级映射 ####

所有记录首先通过哈希函数映射到对应的虚拟桶(多对一映射)。虚拟桶和物理 机之间再有一层映射(同样是多对一)

右图是 Membase 虚拟桶的运行

优点：增加了系统扩展的灵活性

缺点：实现相对麻烦

![0dca203f4f9e42e0890304a4422e2b07.png][]

### 一致性哈希 - 一致性哈希是分布式哈希表的一种实现算法，将哈希数值空间按照大小组成一个首尾相接的环状序列。 ###

对于一致性哈希可能造成的各个节点负载不均衡的情况，可以采用虚拟节点的方式来解决

在哈希空间可容纳长度为 32 的二进制数值 (m = 32 )空间里，每个机器根据 IP 地址或者端口号经过哈希函数映射到环内

![74048cee245e47a8af90eeef918d4fba.png][]

### 范围分片 ###

范围分片首先将所有记录的主键进行排序，然后在排好序的主键空间里将记录划分成数据分片，每个数据分片存储有序的主键空间片段内的所有记录

支持范围查询即给定记录主键的范围而一次读取多条记录,范围分片既支持点查询，也支持范围查询。

分片可以极大的提高读取性能，但对于频繁写的应用帮助不大，同时分片也可减少故障范围，只有访问故障节点的用户才会受影响，访问其他的节点的用户不会收到故障节点的影响

### 路由 ###

那么如何根据收到的请求找到储存的值呢，下面介绍三种方法：

#### 直接查找法 ####

如果哈希值落在自身管辖的范围内,则在此节点上查询,否则继续往后找,一直找到节点Nx ,x 是大于等于待查节点值的最小编号

#### 路由表法 ####

直接查找法缺乏效率，为了加快查找速度，可以在每个机器节点配置路由表,路由表存储每个节点到每个除自身节点的距离

#### 一致性哈希路由算法 ####

## 三、数据复制 ##

将同一份数据放置到多个节点(主从 master-slave方式、对等式per-to-per)的过程称为复制

### 主从复制 ###

master-slave模式,其中有一个 master节点，存放重要数据，通常负责数据的更新，其余节点都叫slave节点，复制操作就是让slave节点的数据与master节点的数据同步

优点：在频繁读取的情况下有助于提升数据的访问速度，还可以增加多个slave节点进行水平扩展，同时处理更多的读取请求

缺点：数据一致性，如果数据更新没有通知到全部的slave节点，则会导致数据不一致

### 对等复制 ###

对等复制是指两个节点相互为各自的副本,没有主从的概念

优点：丢失其中一个节点不影响整个数据库的访问

缺点：因为同时接收写入请求，容易出现数据不一致问题。

## 四、数据一致性 ##

有一个存储系统，其底层是一个复杂的高可用，高可靠的分布式存储系统，一致性模型的定义如下

### 1：强一致 ###

按照某一顺序串行执行存储对象的读写操作，更新存储对象之后，后续访问总是读到最新值

### 2：弱一致性 ###

更新存储对象之后，后续访问可能读不到最新值，从更新成功这一时刻算起，到所有访问者都能读到修改后的对象为止，这段时间称为不一致性窗口，在该窗口内访问存储时无法保证一致性

### 3：最终一致性 ###

最终一致性是弱一致性的特例，存储系统保证所有访问最终读到对象的最新值

**创作不易 觉得有帮助请点赞关注收藏~~~**

[1fad92f9b3f542bcb345f44cb15cfb23.png]: https://img-blog.csdnimg.cn/1fad92f9b3f542bcb345f44cb15cfb23.png
[644290e71c7542c1bbd0fb0d854122c4.png]: https://img-blog.csdnimg.cn/644290e71c7542c1bbd0fb0d854122c4.png
[0dca203f4f9e42e0890304a4422e2b07.png]: https://img-blog.csdnimg.cn/0dca203f4f9e42e0890304a4422e2b07.png
[74048cee245e47a8af90eeef918d4fba.png]: https://img-blog.csdnimg.cn/74048cee245e47a8af90eeef918d4fba.png

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关【软考】数据结构与算法基础 - 哈希表与哈希算法（Hash算法）

一、哈希算法介绍（Hash算法）哈希算法（Hash算法）是一种将任意长度的输入（通常是消息或数据）通过散列函数，变换成固定长度的输出，该输出就是哈希值。这种转换是一种数

Myth丶恋晨/ 2024年03月23日 19:04/ 0 赞/ 102 阅读

相关【大数据技术】流数据、流计算、Spark Streaming、DStream的讲解（图文解释超详细）

流数据和流计算在大数据时代，数据可以分为静态数据和流数据，静态数据是指在很长一段时间内不会变化，一般不随运行而变化的数据。流数据是一组顺序、大量、快速、连续到达的数据序

Love The Way You Lie/ 2023年09月30日 18:07/ 0 赞/ 65 阅读

相关【云计算与大数据技术】Spark的解析（图文解释超详细必看）

一、Spark RDD Spark是一个高性能的内存分布式计算框架，具备可扩展性，任务容错等特性，每个Spark应用都是由一个driver program 构成，该程序运

妖狐艹你老母/ 2023年09月30日 17:49/ 0 赞/ 59 阅读

相关【云计算与大数据技术】Hadoop MapReduce的讲解（图文解释，超详细必看）

一、Hadoop MapReduce架构 MapReduce 是一种分布式计算框架,能够处理大量数据 ,并提供容错、可靠等功能 , 运行部署在大规模计算集群中，MapR

深碍√TFBOYSˉ_/ 2023年09月30日 17:49/ 0 赞/ 51 阅读

相关【云计算与大数据技术】Bloom Filter、LSM树、Merkle哈希树、Cuckoo哈希等数据结构的讲解（图文解释超详细）

一、重要数据结构与算法分布式存储系统中存储大量的数据,同时需要支持大量的上层读/写操作，为了实现高吞吐量，设计和实现一个良好的数据结构能起到相当大的作用这是以下三个

落日映苍穹つ/ 2023年09月30日 17:47/ 0 赞/ 50 阅读

相关【云计算与大数据技术】数据分片哈希算法、路由算法、复制算法的讲解（图文解释超详细）

一、大数据的存储问题随着结构化数据量和非结构化数据量的不断增长，以及分析数据来源的多样化，之前的存储系统设计已经无法满足大数据应用的需求，对于大数据的存储，存在以下几个

男娘i/ 2023年09月30日 17:47/ 0 赞/ 12 阅读

相关【云计算与大数据技术】大数据概念和发展背景讲解（图文解释超详细）

一、什么是大数据大数据是一个不断发展的概念，可以指任何体量或负载下那个超出常规数据处理方法和处理能力的数据，数据本身可以是结构化，半结构化甚至是非结构化的，随着物联网技

╰半橙微兮°/ 2023年09月30日 17:45/ 0 赞/ 55 阅读

相关【云计算与大数据技术】虚拟化技术、开源技术Xen、KVM、OpenVZ的讲解（图文解释超详细）

一、系统虚拟化系统虚拟化的核心思想是使用虚拟化软件在一台物理机上，虚拟出一台或多台虚拟机。步骤如下利用虚拟化评估工具进行容量规划，实现同平台应用的资源整合；

朴灿烈づ我的快乐病毒、/ 2023年09月30日 17:45/ 0 赞/ 55 阅读

相关【云计算与大数据技术】虚拟化简介及虚拟化的分类讲解（图文解释超详细）

一、虚拟化简介 1：什么是虚拟化虚拟化是指计算机元件在虚拟的基础上而不是在真实的、独立的物理硬件基础上运行。这种以优化资源、简化软件的重新配置过程为目的的解决方案

深藏阁楼爱情的钟/ 2023年09月30日 17:45/ 0 赞/ 54 阅读

相关【数据结构与算法】哈希算法

一、什么是哈希算法？ 1.定义将任意长度的二进制值串映射成固定长度的二进制值串，这个映射的规则就是哈希算法，而通过原始数据映射之后得到的二进制值串就是哈希值。

红太狼/ 2022年11月29日 05:40/ 0 赞/ 212 阅读