简介

在上一篇文章里，我们实现了DDB的基本API。上一篇文章请见《通过写代码学习AWS DynamoDB（1）》。在本文中，我们将进一步增强该DDB的模拟实现，给DDB加入Partition。

Partition是Shard的一种。关于Shard的介绍可以参看这篇文章。我们简单介绍一下Shard和Parition的概念。然后我们会在DDB的实现中加上一个简单的Parition的实现。

Shard介绍

区别于传统的基于集中式环境实现数据存储，分布式系统是将数据分散的存储在多个地方，可能是不同的host，或者是server，或者是cluster，等等。每一个这样的节点就是一个shard。使用shard带来的好处有以下几点：

• scale更加容易实现和管理：假如数据存储在一个集中的节点上，我们就要预先估计我们要使用的数据存储容量。过大会浪费很多存储，过小又会需要经常调整，非常麻烦。而且单一存储节点的容量调整本身也很麻烦，一般需要具有一定的专业知识，通过复杂的操作和指令来实现存储容量的扩容。但是有了shard这一切就变得简单和灵活很多。在需要调整数据存储容量时，我们仅仅需要增加和减少shard。
• 系统的robust会得到加强。传统的集中存储方式，一旦存储的服务器出现问题，整个系统就会瘫痪。但是基于shard的实现，如果一个shard出现问题，系统仅仅是部分数据无法访问，整体功能仍然可以部分得到保障。如果我们将shard和replica配合使用，则可以保障整体系统的robust会更好。
• 系统的响应时间会得到改善。不同于传统的集中式存储，数据可以根据需要存储在多个shard里。首先，多个存储本身就很有利于并行的处理数据操作，从而使得响应时间得到改善。其次，shard可以根据需要部署到和client更近的地方，从而改善响应时间。例如，如果数据是和城市有关的，那么我们可以将数据按照城市分别存到不同的shard里，并将每个城市的shard部署到该城市。

Shard的方法：

1. Range-based sharding：通过对某一条或者几条attribute进行区间划分来决定shard。比如对于人口的数据按照年龄的分布，0到10岁存储到一个shard，10岁到20岁存储到一个shard，等。
2. Hashed sharding：通过对key进行hash来决定该一条记录所对应的shard。
3. Directory sharding：通过某种形式的对应来决定一条记录所对应的shard。比如存储文章，我们可以将历史类的存储在一个shard，文学类的存储在一个shard，等。
4. Geo sharding：通过地理位置来决定shard。比如上面例子中通过城市来决定。

Partition介绍

数据库的Partition是将数据分成多个小组进行处理的一种技术。所以partition和shard基本一样的设计理念，但是不完全一样。Parition分为两种：

• 横向partition：将数据表的行进行分组。
• 纵向partition：将数据表的列进行分组。

事实上，两种partition都可以认为是shard在数据库中的具体实现。

在DynamoDB的模拟实现中加入Partition

首先我们先实现一个Parition类。这个Partition类可以实现CRUD的功能（也就是create，read，update，delete），同时它还提供了一个接口可以返回该partition的统计信息。具体代码如下：

class Partition:
    def __init__(self):
        self.storage = {}

    def put_item(self, key, value):
        self.storage.update({key: value})

    def get_item(self, key):
        return self.storage[key]
    
    def delete_item(self, key):
        self.storage.pop(key)

    def get_item_count(self):
        return len(self.storage.items())

我们将给DDB的table添加Parition List。在这里我们使用Hash partition。针对每一个key，我们首先计算该key的hash value，然后对partition的个数取模来确定该key应该存在在哪个partition里。并且现在Table将不再保存数据的统计信息（例如有多少条数据），因为数据已经分布到多个partition里，所以Table将通过轮询Paritition的方式来汇总Table级别的统计信息（参见Table.describe()的实现）。代码的实现如下：

import functools
from partition import Partition

# class to provide DDB public APIs
# - support partitions based on hash value of key;
class DDB:
    def __init__(self):
        self.tables = {}

    def create_table(self, table_name):
        self.tables[table_name] = self.Table(table_name)

    def list_table(self):
        for table in self.tables.values():
            table.describe()

    def delete_table(self, table_name):
        self.tables.pop(table_name)

    def get_table(self, table_name):
        return self.tables[table_name]
    
    class Table:
        def __init__(self, name, partition_count=3):
            self.name = name
            self.partitions = [Partition() for _ in range(partition_count)]
            self.partition_count = partition_count

        def put_item(self, key, value):
            print("save {} to partition {}".format(key, self.get_partition_id(key)))
            self.partitions[self.get_partition_id(key)].put_item(key, value)

        def update_item(self, key, value):
            self.partitions[self.get_partition_id(key)].put_item(key, value)

        def get_item(self, key):
            print("get {} from partition {}".format(key, self.get_partition_id(key)))
            return self.partitions[self.get_partition_id(key)].get_item(key)
        
        def delete_item(self, key):
            print("delete {} from partition {}".format(key, self.get_partition_id(key)))
            self.partitions[self.get_partition_id(key)].delete_item(key)

        def describe(self):
            item_count = functools.reduce(lambda x, y : x + y.get_item_count(), self.partitions, 0)
            print("Table name: {}, item size: {}".format(self.name, item_count))

        def get_partition_id(self, key):
            return self.my_hash(key) % self.partition_count
        
        def my_hash(self, text:str):
            hash=0
            for ch in text:
                hash = ( hash*281  ^ ord(ch)*997) & 0xFFFFFFFF
            return hash

现在我们DDB的class diagram看起来是这个样子：

显示我们修改一下我们之前的测试代码，并且看一下partition是否工作正常：

from ddb import DDB

ddb = DDB()

table_name = "test_table"
key = "test_key"
value = "test_value"

ddb.create_table(table_name)
ddb.list_table()
ddb_table = ddb.get_table(table_name)
ddb_table.put_item("1", value)
ddb_table.put_item("2", value)
ddb_table.put_item("3", value)

print(ddb_table.get_item("1"))
print(ddb_table.get_item("2"))
print(ddb_table.get_item("3"))

ddb_table.delete_item("1")

ddb_table.describe()

代码的运行结果：

Table name: test_table, item size: 0
save 1 to partition 1
save 2 to partition 2
save 3 to partition 0
get 1 from partition 1
test_value
get 2 from partition 2
test_value
get 3 from partition 0
test_value
delete 1 from partition 1
Table name: test_table, item size: 2

我们看到每条记录被正确的存储到各个partition里，并且可以正常的访问。关于整张表的统计信息，也就是表里有多少条记录也是正确的。

小结

我们的DDB已经可以将数据灵活的存储在多个partition里了。现在我们可以很容易scale out或者scale in我们的DDB。但是我们注意到如下问题：

1. 如果partition增加，根据hash value模partition的数量来确定partition的方式就不正确了，因为一条数据对应的partition会发生改变。
2. 我们仅仅是在存储上实现了partition，但是并没有真正实现并行的数据处理。
3. 我们的数据库没有replica来保障数据和服务availability。

这些问题我们将在后面的文章中继续解决。