Key-Value Store 键值资料储存解说– 系统设计11

system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech

序言

还记得我们在 资料库基础介绍– 系统设计08 讲解过了关联式资料库,这一篇会更深入讲解键值资料储存(Key-Value Store)的原理,当然我下面也另外提供NoSQL 以及键值资料库(Key-value database)的简介。

什么是NoSQL?

NoSQL 的意思是Not Only SQL,是一种非关联式资料库,也就是说它不使用传统的关联式资料库模型来储存资料。 NoSQL 资料库通常使用更灵活、更可扩展的资料模型,例如:键值对、文件、图形或宽表。这一篇就来好好讲解键值资料库(Key-value database)。

什么是键值资料库(Key-value database)?

键值资料库使用杂凑表(Hash Table)等键值方法以键值对的形式储存资料。键充当主键(Primary Key),值(Value)可以是从简单标量值到复杂物件的任何值。常见的键值资料库,包含:Amazon DynamoDB、Redis 。

键值资料储存(Key-Value Store)

键值资料储存(Key-Value Store)是一种分散式杂凑表(Distributed Hash Table),其中DHT是一种去中心化储存方式,提供类似杂凑表的查找、储存。杂凑表(Hash Table) 也是一个Abstract Data Type (ADT),它的优点是通常可以用比较快的时间完成Search operation 的动作。这边先来讲讲杂凑(Hash)的原理,由杂凑函式(Hash Function)产生一组密钥,并且是唯一的密钥。键值储存(Key-Value Store)则是将钥匙绑入特定的值中,而值可以是Map、Image之类的储存类型。

通常我们会将值限制在相对较小的档案大小,约略MB 至KB 的内容大小。键值资料储存可以用在满多不同的情境的,例如:建立一个Messenger,并且将使用者对话去做储存,这样的情境就很适合使用此NoSQL 的方式处理。

如何设计键值资料储存?

如果要设计一个系统元件,首先就需要回归到最原本的问题,此系统元件有哪些需求?如果忘了需求的读者,建议可以观看 软体设计非功能性特性– 系统设计03

功能需求(Functional Requirement)

通常,键值储存与一般资料库相同,都有一些常见的功能,例如: get 和put 之类的功能。不过键值储存系统与一般储存系统,在功能需求上还是有一些不同的。

  1. 可配置服务:某些系统可能会牺牲强一致性(Consistency)来换取更高的可用性(Availability)。键值储存会需要提供可配置的服务,以便不同的系统中也可以使用一致性模型。
  2. 始终写入的能力:系统需要具有写入键值储存的功能。如果使用者想要强一致性(Consistency),由于CAP 定理的影响,势必会舍弃可用性(Availability)。换句话说,在CAP中,更倾向C。

非功能需求(Non-Functional Requirement)

可扩展性(Scalability):键值储存要可以在全球的数万台伺服器上运行。并且根据需求去新增或删除伺服器,同时减少对服务可用性的影响,甚至不造成影响。另外,系统应该能够处理键值储存的大量使用者。

容错(Fault Tolerance):如果系统伺服器或系统元件发生故障,键值储存应该要持续的运作而不间断。

设计键值资料储存

在开始设计系统前,首先设计简单(Design Simple)的原则,需要先假设以下:

  1. 资料中心是可信任的。
  2. 资料储存中的身份验证都已完成。
  3. 使用者请求和回应是透过HTTPS。

API设计

首先是API 的设计,我们需要从功能面的角度来去思考需要哪些API,其中键值储存与杂凑表(Hash Table)一样,提供两个主要功能:get 和put。

Get 函式

				
					get(key)
				
			

我们根据参数的键(Key)传回对应的值。这里也另外提一下 Data Replication 如何优化资料库? - 系统设计09 有提到的资料复制问题,当键值资料库在进行复制资料时,它会找到与金钥关联的物件副本。如果储存配置了较弱的资料一致性模型,则由系统完成。

Put 函式

				
					put(key, value)
				
			

此函式用来储存与键关联的值,键值资料储存会自动决定资料应放置的位置。另外系统通常保留有关储存物件的元资料(Metadata)。未来也会再好好的介绍什么是元资料(Metadata)。

增加可扩展性

对系统设计来说,可扩展性(Scalability)是非常重要的,因此在设计键值资料储存(Key-Value Store)时,我们会将键值资料储存在储存节点中。随着需求的变化,我们可能需要新增或删除储存节点。这代表我们需要在系统中的节点上对资料进行分区(Partition),以将负载分布到所有节点上。如果尚未熟悉分区的读者,可以参考 Data Partitioning 资料分区是什么? – 系统设计10

回到键值资料储存中的分区,这边提供一个范例:假设我们有四个节点,我们希望40% 的请求发送到每个节点以平衡负载,解决这个问题的传统方法是透过模运算子(Modulus Operator)来去做计算。每个到达的请求都有一个与之关联的金钥。当请求到来时,我们计算密钥的杂凑值。然后,我们透过将杂凑值与节点数m 来求余数。

一致性杂凑(Consistent Hashing)

曾经我们在 DNS 是什么?网域名称系统介绍– 系统设计06 有介绍过各种不同类型的演算法来去处理流量问题,那么如果讨论到杂凑时,就不得不讨论一致性杂凑(Consistent Hashing)演算法了。这个演算法是一个非常适合平衡节点负载的方法。

在一致性杂凑演算法中,我们需要先假定,有一个杂凑环(Hash Ring)从0 到n−1,其中n 是可用杂凑值的数量。我们使用每个节点的ID,计算其杂凑值,并将其杂凑值透过映射(Mapping)到杂凑环(Hash Ring)。每个请求都由它在环中顺时针方向移动找到的下一个节点完成。

每当一个新节点加入环中时,紧邻的下一个节点都会受到影响。它必须与新添加的节点共享其资料,而其他节点不受影响。这样的演算法很容易进行扩展,能够将对节点的变更保持在最低限度。杂凑值是随机分布的,因此我们期望请求的负载是随机的并且平均分布在环上。

一致性杂凑的主要好处是,当节点加入或离开时,我们需要确保移动的键(Key)数量最少。不过在实务上,请求负载并不是平均分配的。任何处理大量资料的伺服器都可能成为分散式系统中的瓶颈。该节点会收到不成比例的大量资料储存和搜寻请求,从而降低整体系统效能。这边提供我觉得写得很详细的文章,提供读者做参考,并且附上一致性杂凑的图解。

system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech01
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech02
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech03
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech04
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech05
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech06
system-design-系统设计11-键值资料储存-key-value-store-introductoin-to-database-fundamentals-hogantech07

使用虚拟节点(Virtual Nodes)

除了使用一致性杂凑演算法以外,我们也可以使用虚拟节点来确保节点之间的负载分布更均匀。此方法是在同一个键上使用多个杂凑函式,而不是应用单一杂凑函式。

这边快速举例,假如我们有四个杂凑函数。对于每个节点,我们计算四个杂凑值并将它们放入环中。对于该请求,我们仅使用一个杂凑函数。无论请求到达环上的哪个位置,都会由沿着顺时针方向移动时找到的下一个节点进行处理。每个伺服器有四个位置,因此请求的负载更加均匀。此外,如果一个节点比其他节点具有更多的硬体容量,我们可以透过使用额外的杂凑函数来添加更多的虚拟节点。这样,它将在环中占据更多位置并满足更多请求。

资料复制(Data Replication)

这一篇 Data Replication 如何优化资料库? - 系统设计09 写了关于资料库复制的内容,到了键值资料库,我们也会有多种不同的方法来处理资料复制。常见的资料复制包含:主从关系以及点对点关系。

主从复制(Primary-secondary)

在主从方法中,其中一个储存区域是主要储存区域,其他储存区域是辅助储存区域。辅助副本从主副本复制其资料。主要储存区域用来处理写入请求,而辅助服务则服务于读取请求。另外如果主资料库发生故障,我们将无法写入存储,并且它将成为单点故障。

点对点复制(Peer-to-peer)

在点对点方法中,所有储存区域都是主要储存区域,也会复制资料以保持更新。所有节点也都允许读取和写入。通常,在所有n 个节点中进行复制效率低且成本高。相反,三个或五个是要复制的储存节点数量的常见选择。

结论

刚好接下来会有将近两周的时间在国外旅行,不过依然会持续更新系统设计的技术文章,未来也会持续撰写系统设计的内容。如果喜欢这类型的文章,也不妨留言给予鼓励!

相关文章

Data Partitioning 资料分区是什么? – 系统设计10

Data Replication 如何优化资料库? - 系统设计09

资料库基础介绍– 系统设计08

负载平衡器解说– 系统设计07

DNS 是什么?网域名称系统介绍– 系统设计06

系统设计元件介绍Building Block – 系统设计05

Back-of-the-envelope 封底计算– 系统设计04

软体设计非功能性特性– 系统设计03

抽象在系统设计中的应用– 系统设计02

现代系统设计介绍– 系统设计01

引用

A Guide to Consistent Hashing

What Is a Key-Value Database?

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

zh_CN简体中文