hge网站做微端,软文有哪几种类型,网站域名维护,3g 手机网站建设键值存储 ( key-value store )#xff0c;也称为 K/V 存储或键值数据库#xff0c;这是一种非关系型数据库。每个值都有一个唯一的 key 关联#xff0c;也就是我们常说的 键值对。常见的键值存储有 Redis, Amazon DynamoDB#xff0c;Microsoft Azure Cosmos DB#xff0c… 键值存储 ( key-value store )也称为 K/V 存储或键值数据库这是一种非关系型数据库。每个值都有一个唯一的 key 关联也就是我们常说的 键值对。常见的键值存储有 Redis, Amazon DynamoDBMicrosoft Azure Cosmos DBMemcachedetcd 等。你可以在 DB-Engines 网站上看到键值存储的排行。 设计要求 在这个面试的系统设计环节中我们需要设计一个键值存储 要满足下面的几个要求• 每个键值的数据小于 10kB。• 有存储大数据的能力。• 高可用高扩展性低延迟。 单机版 - 键值存储 对于单个服务器来说开发一个键值存储相对来说会比较简单一种简单的做法是把键值都存储在内存中的哈希表中这样查询速度非常快。但是由于内存的限制把所有的数据放到内存中明显是行不通的。所以对于热点数据经常访问的数据可以加载到内存中而其他的数据可以存储在磁盘。但是当数据量比较大时单个服务器仍然会很快达到容量瓶颈。 分布式 - 键值存储 分布式键值存储也叫分布式哈希表把键值分布在多台服务器上。在设计分布式系统时理解 CAP一致性可用性分区容错性 定理很重要。 CAP 定理 CAP 定理指出在分布式系统中不可能同时满足一致性、可用性和分区容错性。让我们认识一下这三个定义• 一致性无论连接到哪一个节点所有的客户端在同一时间都会看到相同的数据。• 可用性可用性意味着任何请求数据的客户端都会得到响应即使某些节点因故障下线。• 分区容错性分区表示两个节点之间的网络通信中断。分区容错性意味着当存在网络分区时系统仍然可以继续运行。通常可以用 CAP 的两个特性对键值存储进行分类CP一致性和分区容错性系统牺牲可用性的同时支持一致性和分区容错。AP可用性和分区容错性系统牺牲一致性的同时支持可用性和分区容错。CA一致性和可用性系统牺牲分区容错性的同时支持一致性和可用性。由于网络故障是不可避免的所以在分布式系统中必须容忍网络分区。让我们看一些具体的例子在分布式系统中为了保证高可用数据通常会在多个系统中进行复制。假设数据在三个节点 n1, n2, n3 进行复制如下理想情况在理想的情况下网络分区永远不会发生。写入 n1 的数据会自动复制到 n2 和 n3实现了一致性和可用性。现实世界的分布式系统在分布式系统中网络分区是无法避免的当发生分区时我们必须在一致性和可用性之间做出选择。在下图中n3 出现了故障无法和 n1 和 n2 通信如果客户端把数据写入 n1 或 n2就没办法复制到 n3就会出现数据不一致的情况。如果我们选择一致性优先CP系统当 n3 故障时 就必须阻止所有对 n1 和 n2 的写操作避免三个节点之间的数据不一致。涉及到钱的系统通常有极高的一致性要求。如果我们选择可用性优先AP系统当 n3 故障时系统仍然可以正常的写入读取但是可能会返回旧的数据当网络分区恢复后数据再同步到 n3 节点。选择合适的 CAP 是构建分布式键值存储的重要一环。 核心组件和技术 接下来我们会讨论构建键值存储的核心组件和技术• 数据分区• 数据复制• 一致性• 不一致时的解决方案• 故障处理• 系统架构图• 数据写入和读取流程 数据分区 在数据量比较大场景中把数据都存放在单个服务器明显是不可行的我们可以进行数据分区然后保存到多个服务器中。需要考虑到的是多个服务器之间的数据应该是均匀分布的在添加或者删除节点时需要移动的数据应该尽量少。一致性哈希非常适合在这个场景中使用下面的例子中8台服务器被映射到哈希环上然后我们把键值的 key 也通过哈希算法映射到环上然后找到顺时针方向遇到的第一个服务器并进行数据存储。使用一致性哈希在添加和删除节点时只需要移动很少的一部分数据。 数据复制 为了实现高可用性和可靠性一条数据在某个节点写入后会复制到其他的节点也就是我们常说的多副本。那么问题来了如果我们有 8 个节点一条数据需要在每个节点上都存储吗并不是副本数和节点数没有直接关系。副本数应该是一个可配置的参数假如副本数为 3同样可以借助一致性哈希环按照顺时针找到 3 个节点并进行存储如下 一致性 因为键值数据在多个节点上复制所以我们必须要考虑到数据一致性问题。Quorum 共识算法可以保证读写操作的一致性我们先看一下 Quorum 算法中 NWR 的定义。N 副本数, 也叫复制因子在分布式系统中表示同一条数据有多少个副本。W 写一致性级别表示一个写入操作需要等待几个节点的写入后才算成功。R 读一致性级别表示读取一个数据时需要同时读取几个副本数然后取最新的数据。如下图N 3注意W 1 并不意味着数据只写到一个节点控制写入几个节点的是 N 副本数。N 3 表示一条数据会写入到 3 个节点W 1 表示只要收到任何节点的第一个写入成功确认消息ACK后就直接返回写入成功。这里的重点是对 N、W、R的值进行不同的组合时会产生不同的一致性效果。• 当 W R N 的时候通常是 N 3, W R 2对于客户端来讲整个系统能保证强一致性一定能返回更新后的那份数据。• 当 W R N 的时候对于客户端来讲整个系统只能保证最终一致性所以可能会返回旧数据。通过 Quorum NWR可以调节系统一致性的程度。 一致性模型 一致性模型是设计键值存储要考虑的另外一个重要因素一致性模型定义了数据一致性的程度。• 强一致性 任何一个读取操作都会返回一个最新的数据。• 弱一致性 数据更新之后读操作可能会返回最新的值也有可能会返回更新前的值。• 最终一致性 这是弱一致性的另外一种形式。可能当前节点的值是不一致的但是等待一段时间的数据同步之后所有节点的值最终会保持一致。强一致性的通常做法是当有副本节点因为故障下线时其他的副本会强制中止写入操作。一致性程度比较高但是牺牲了系统的高可用。而 Dynamo 和 Cassandra 都采用了最终一致性这也是键值存储推荐使用的一致性模型当数据不一致时客户端读取多个副本的数据进行协调并返回数据。 不一致的解决方案版本控制 多副本数据复制提供了高可用性但是多副本可能会存在数据不一致的问题。版本控制和向量时钟vector clock 是一个很好的解决方案。向量时钟是一组 [serverversion] 数据它通过版本来检查数据是否发生冲突。假设向量时钟由 D([S1, v1], [S2, v2], ..., [Sn, vn]) 表示其中 D 是数据项v1 是版本计数器下面是一个例子1. 客户端把数据 D1 写入系统写入操作由 Sx 处理服务器 Sx 现在有向量时钟 D1[(Sx, 1)]。2. 客户端把 D2 写入系统假如这次还是由 Sx 处理则版本号累加现在的向量时钟是 D2([Sx, 2])。3. 客户端读取 D2 并更新成 D3假如这次的写入由 Sy 处理 现在的向量时钟是D3([Sx, 2], [Sy, 1]))。4. 客户端读取 D2 并更新成 D4假如这次的写入由 Sz 处理现在的向量时钟是 D4([Sx, 2], [Sz, 1]))。5. 客户端读取到 D3 和 D4检查向量时钟后发现冲突因为不能判断出两个向量时钟的顺序关系客户端自己处理解决冲突然后再次写入。假如写入是 Sx 处理现在的向量时钟是 D5([Sx, 3], [Sy, 1], [Sz, 1])。注意向量时钟只能检测到冲突如何解决那就需要客户端读取多个副本值自己处理了。 故障处理 在分布式大型系统中发生故障是很常见的接下来我会介绍常见的故障处理方案。 故障检测 一种很常见的方案是使用 Gossip 协议我们看一下它的工作原理• 每个节点维护一个节点成员列表其中包含成员 ID 和心跳计数器。• 每个节点周期性地增加它的心跳计数器。• 每个节点周期性地向一组随机节点发送心跳这些节点依次传播到另一组节点。• 一旦节点收到心跳成员列表就会更新为最新信息。• 如果在定义的周期内发现心跳计数器的值比较小则认为该成员离线。 处理临时故障 通过 gossip 协议检测到故障后为了保证数据一致性严格的 Quorum 算法会阻止写入操作。而 sloppy quorum 可以在临时故障的情况下保证系统的可用性。当网络或者服务器故障导致服务不可用时会找一个临时的节点进行数据写入当宕机的节点再次启动后写入操作会更新到这个节点上保持数据一致性。如下图所示当 s2 不可用时写入操作暂时由 s3 处理 在一致性哈希环上顺时针查找到下一个节点就是s3当 s2 重新上线时s3 会把数据还给 s2。 处理长时间故障 数据会在多个节点进行数据复制假如节点发生故障下线并且在一段时间后恢复那么节点之间的数据如何同步? 全量对比明显是低效的。我们需要一种高效的方法进行数据对比和验证。使用 Merkle 树是一个很好的解决方案Merkle 树也叫做哈希树这是一种树结构最下面的叶节点包含数据或哈希值每个中间节点是它的子节点内容的哈希值根节点也是由它的子节点内容的哈希值组成。下面的过程展示了 Merkle 树是如何构建的。第 1 步把键值的存储空间划分为多个桶一个桶可以存放一定数量的键值。第 2 步创建桶之后使用哈希算法计算每个键的哈希值。第 3 步根据桶里面的键的哈希值计算桶的哈希值。第 4 步计算子节点的哈希值并向上构建树直到根节点结束。如果要比较两个 Merkle 树首先要比较根哈希如果根哈希一致表示两个节点有相同的数据。如果根哈希不一致就遍历匹配子节点这样可以快速找到不一致的数据并进行数据同步。 系统架构图 我们已经讨论了设计键值存储要考虑到的技术问题现在让我们关注一下整体的架构图如下这个架构主要有下面几个特点• 客户端通过简单的 API 和键值存储进行通信get (key) 和 put (key, value)。• coordinator 协调器充当了客户端和键值存储之间的代理节点。• 所有节点映射到了一致性哈希环上。• 数据在多个节点上进行复制。 写入流程 下图展示了数据写入到存储节点的过程主要基于 Cassandra 的架构设计。1. 写入请求首先被持久化在提交日志文件中。2. 然后数据保存在内存缓存中。3. 当内存已满或者达到阈值时数据移动到本地磁盘的 SSTable这是一种高阶数据结构感兴趣的读者自行查阅资料了解。 读取流程 在进行数据读取时它首先检查数据是否在内存缓存中如果是就把数据返回给客户端如下图所示如果数据不在内存中就会从磁盘中检索。我们需要一种高效的方法找到数据在哪个 SSSTable 中通常可以使用布隆过滤器来解决这个问题。1. 系统首先检查数据是否在内存缓存中。2. 如果内存中没有数据系统会检查布隆过滤器。3. 布隆过滤器可以快速找出哪些 SSTables 可能包含密钥。4. SSTables 返回数据集的结果。5. 结果返回给客户端。 Reference [0] System Design Interview Volume 2:https://www.amazon.com/System-Design-Interview-Insiders-Guide/dp/1736049119[1] Amazon DynamoDB: https://aws.amazon.com/dynamodb/[2] memcached: https://memcached.org/[3] Redis: https://redis.io/[4] Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf[5] Cassandra: https://cassandra.apache.org/[6] Bigtable: A Distributed Storage System for Structured Data: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf[7] Merkle tree: https://en.wikipedia.org/wiki/Merkle_tree[8] Cassandra architecture: https://cassandra.apache.org/doc/latest/architecture/[9] SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/[10] Bloom filter https://en.wikipedia.org/wiki/Bloom_filterEND做了一个 .NET 的学习网站内容涵盖了分布式系统数据结构与算法设计模式操作系统计算机网络等以及工作推荐和面试经验分享欢迎来撩。回复 dotnet 获取网站地址。回复 面试题 获取 .NET 面试题。回复 程序员副业 获取适合程序员的副业指南。
