Table of Contents
左耳听风ARTS第11周
Algorithm
Leetcode 134: https://leetcode.com/problems/gas-station/
https://medium.com/@dreamume/leetcode-134-gas-station-e9cfa4a1fdfd
Review
Dynamo: Amazon’s Highly Available Key-value Store（上）
https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
Dynamo是Amazon推出的高可用key-value存储系统。
背景
该系统需要满足如下需求：
-
Query Model
数据读写操作有一个唯一标识的Key。状态以二进制方式存储，并以Key为唯一标识。操作不会夸多个数据项，因此不需要表结构记录关系。对象比较小，通常不超过1MB。
-
ACID属性
为保障高可用性，系统提供弱一致性。
-
效率
对延迟性有较高要求并且SLA达到99.9%
-
其他
Dynamo用于Amazon内部系统，无安全性相关需求
设计中的考量
由于强一致性和高可用性不能兼得，这里优先考虑高可用性。
一个重要的设计考虑是当冲突发生时，何时处理冲突。Dynamo设计目标是优先保证写操作。
另一个考量是谁来执行并处理冲突解决。数据存储模块来执行的话可选策略很优先，只能是采用最后写的优胜。应用程序来处理的话，因为它了解数据表结构，有能力合并冲突，更灵活。
其他需要考虑的有：
- 可扩展性
- 对称性
- 去中心化
- 异构。添加新节点不影响其他服务。
系统架构
Dynamo提供get和put方法操作对象，同时附带一个context包含有版本信息。
Dynamo使用特定的分区算法来保证扩展性。Dynamo动态的把数据分区到一系列的节点上，通过一致性hash分布式加载数据。
一致性hash按范围形成一个环形，每个节点被随机分配一个值代表一个环形中的位置。每个数据项有一个key，key被hash之后的值作为确定被放在环形的位置，然后放置在按顺时针方向查找比它大的第一个节点位置。
一致性hash方案的优点是分离或到达一个节点只影响其近邻的节点，对其他节点无影响。
一致性hash方案有两个问题，1是随机位置导致数据和数据分布的不统一，2是导致节点间性能不同。
因此Dynamo采用了一种变种方案，引入了虚拟节点的概念。虚拟节点看似跟普通节点相似，但每个节点可以代表多个虚拟节点。即当系统中新增一个节点时，它可以在环形中占有多个位置。
该变种方案有如下优点：
- 当一个节点异常时，该节点负载被分散到其他有效节点
- 当节点恢复或新节点新增时，该节点从其他节点中分担负载
- 可以根据节点的性能决定分配虚拟节点个数
Tips
- 考虑问题的通用性，要多使用范型。
Share
《算法》第4版 图算法部分用C++实现了一遍，原书代码用的Java。