分布式数据库DynamoDB

水深无声 2022-04-15 06:46 284阅读 0赞

# DynamoDB #

DynamoDB是分布式数据库，设计成用来解决数据库管理、性能、可扩展性和可靠性等核心问题。开发人员可以创建一个数据库表，该表可以存储和检索任何数量的数据。  
DynamoDB改进了Memcached的一致性hash算法  
采用了虚拟节点的机制改进了一致性hash算法，有Q个虚拟节点，S个物理节点，那么为每一个物理节点分配Q/S个虚拟节点，其中Q>>S，虚拟节点的好处是能够分布不均匀的问题，最大限度减少服务器增减时的缓存重新分布![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]  
Memcached虚拟节点不固定，虚拟节点位置随机性，如果有新节点加入，则需要扫描所有节点上的所有数据对象，判断是否需要迁移，这种全局扫描会造成很大开销。  
DynamoDB固定虚拟节点，只改变虚拟节点和节点的对应关系。

1.  当加入节点的时候，从现有节点中拿出等量虚拟节点分配给新节点
2.  当节点离开的时候，将此节点的所有虚拟节点平均分配给余下的节点

### Quarum机制： ###

R + W > N的机制能够保证数据的正确性，但是不能保证一致性，如果R=W=N可以保证一致性，但是无疑牺牲了很多可用性

### 多副本机制 ###

DynamoDB有多副本机制，但是为了达到高的可用性，牺牲了一致性，满足AP，牺牲了C，通常如果有N个副本，那么顺时针找N个节点存放。

### preference list ###

N个副本存放构成一个preference list，但是客户端的请求交给一个节点处理，在其中选择一个节点作为coodinator

### 写数据流程 ###

1.  coodinator生成新的数据副本以及vector clock分量
2.  向preference list中所有节点发出写请求
3.  收到W-1个回复写成功

### 读数据流程 ###

1.  coodinator向preference list中所有的节点请求数据版本
2.  等到R-1个答复，答复中包括vector clock
3.  通过处理vector clock处理有因果关系的副本
4.  将不相容的所有数据版本返回给用户

### vector clock ###

DynamoDB通过向量时钟算法来确定时间发生的先后顺序

### vector clock无限增长 ###

向量时钟随着时间的推移会无限增长，有两种方案解决问题：

1.  采用服务器向量的形式
2.  时钟向量减枝  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]

采用服务器向量会丢失数据，向量减枝的方法更优采用服务器向量会丢失数据，向量减枝的方法更优

### 暗示接力技术（hinted handoff） ###

DynamoDB针对临时节点失效处理采用了hinted handoff技术，往后找一个节点暂时替代失效的节点，该节点定期的检查故障节点是否恢复。

### 使用gossip协议进行数据传播 ###

虽然写了W个节点，但是通过gossip节点加上vector clock，能够维持成员的最终一致性。  
每个几点每间隔一秒随机选择另外一个节点进行通信，两个节点协调他们保存的成员变动历史  
另外采用种子节点来避免逻辑分裂，每一个节点都要与种子节点通信。

### 副本同步校验merkle tree ###

当故障发生或者有新节点加入的时候，都涉及到分片的靠背和传输，希望能够快速检查分片中的内容是否相同。  
DynamoDB DB采用了merkle tree技术，merkle tree在区块链中也有非常典型的应用，比如想要寻找是否存在某一个交易，那么构造一个认证路径最后比较根节点即可。

*  叶子节点对应每一个数据项，并记录hash值
 *  非叶子节点记录所有子节点的hash值

如果根的hash相等，叶子的hash相等，那么节点不需要同步，这样可以解决hash list文件太大的问题。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70]: /images/20220415/e2a53e3677d44c6d956d89805abff5e2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjM3Mjg3OQ_size_16_color_FFFFFF_t_70 1]: /images/20220415/5ca9fdc286de46919881c6555e5c4f2f.png