GSI Sharding in DynamoDB

Keywords: AWS, Amazon, DynamoDB

在传统数据库中, 经常会有按照某一个列的区间进行查询的需求. 例如仅按照时间来筛选数据. 在 DynamoDB 中由于查询必须要带 Hash Key, 你无法仅仅对时间列进行查询. 很直接的你就会想到创建一个 attribute 叫做 gsi_pk, 它的值是一个定值. 然后创建了一个以 gsi_pk 为 PK, 时间为 SK 的 GSI 索引不就可以对时间进行查询了? 由于 GSI 本质上也是一个特殊的, 和主表自动同步的 DynamoDB table, 它同样也会按照 PK 来将数据分散到不同的 node 上. 而你的 gsi_pk 是一个定值, 也就是所有的数据都落在了一个 Node 上, 这样 GSI index 很快就会不堪重负.

为了解决这一问题, Amazon 推荐使用 GSI Sharding 的技术 (和以前 S3 中的这个技术很像, 后来 S3 做了优化, 你不需要做这件事了). 这个技术本质上是将 gsi_pk 的那个常量变成一个随机数. 例如 1-100. 那么这样流量就会被打散了.

不过你的代价就是:

1. 查询的时候要发起 100 个查询, 然后将查询结果汇总.

2. 对时间的排序需要在结果汇总之后在内存中汇总, 因为每个 shard 返回的数据的时间是分散的.

这种技巧还有一些变种. 例如你的一个表有很多 job, 每个 job 有一个 id, 以及一个 status (pending, in_progress, failed, succeeded, ignored) 来表示这个 job 的进度, 还有 job 的 create_time 和 update_time. 很自然的, 你会想要查询 status 处于某个状态的所有 job, 并且按照 create_time 或是 update_time 来进行筛选. 这时 status 的问题是它虽然不是一个常量, 但是 cardinality 太低了, 只有 5 个值. 这时候你不应该无脑的给每个 status 加上 1-100 的后缀. 因为这样做某些非常热的 status 例如 succeeded, ignored 的 item 还是会很多, 最后数据还是不均匀. 这时候你应该按照不同的 status 的比例来分配. 例如 succeeded, ignored 的数据多, 那么你将它们分为 35 份. 而给 pending, in_progress, failed 一人 10 份, 总计还是 100 份, 但是数据最终就会比较平均.

Reference:

• Using Global Secondary Index write sharding for selective table queries

Diagram

下面我们用 Diagram 来详细介绍一下这个技术.

如何决定 Shard 的数量

我们在决定 Shard 的数量时遵循两个原则:

1. Shard 的数量应该尽量少, 这样查询的时候就简单些. 不过计算 Shard 多问题不大, 最终就是 request 数量多一点而已. 你完全可以用多线程同时查询然后最后汇总. 并且 DynamoDB 只按照返回的数据量收费而不管 request 的数量的多少, 费用上并没有增加.

2. 按照概率流量能比较平均的分布在每个 Node 上.

这里我们详细来讨论一下 #2. 我们假设 Node 的数量为 N. Shard 的数量为 K. 如果流量是完全分散的, 那么一个 Node 上收到的流量就应该是 1/N. 我们定义如果某一个 Node 上的流量超过了 1/N 的 20%, 就是流量不平均了, 而超过 50%, 那么一般就视为处于系统超载的边缘了. 这在 N 等于 2 的时候就意味着有一个 Node 处理了 75% 的流量. N 等于 3 的时候有一个 Node 处理了 50% 的流量. N 等于 4 的时候有一个 Node 处理了 37.5% 的流量.

之所以这个数是 50% 也很好理解. 一般分布式系统的扩容机制是当最热节点的负载超过了 70% 就要将节点数加倍, 使得每个节点的流量降低到 35%. 而由于流量不平均, 这个最热节点实际负担了 70% * 1.5 = 105% 的流量, 这也就意味着在流量平均时无需扩容, 而就是因为流量不平均, 你需要扩容一倍. 换言之你的机器是 2 台当 1 台用.

这里我们不推导具体的发生系统超载的概率公式. 根据测量经验, K 的数量一般是 N 的十倍以上, 才能保证发生系统超载的概率要低于 5%.

import uuid
import random
from datetime import datetime, timezone, timedelta

import pynamodb_mate as pm
from boto_session_manager import BotoSesManager

bsm = BotoSesManager(profile_name="bmt_app_dev_us_east_1")
with bsm.awscli():
    pm.Connection()

def get_utc_now() -> datetime:
    return datetime.utcnow().replace(tzinfo=timezone.utc)

class TimeIndex(pm.GlobalSecondaryIndex):
    class Meta:
        index = "time-index"
        projection = pm.KeysOnlyProjection()

    shard = pm.NumberAttribute(hash_key=True)
    time = pm.UTCDateTimeAttribute(range_key=True)


class Event(pm.Model):
    class Meta:
        table_name = "gsi_sharding_test_1"
        region = "us-east-1"
        billing_mode = pm.PAY_PER_REQUEST_BILLING_MODE

    event_id = pm.UnicodeAttribute(hash_key=True)
    time = pm.UTCDateTimeAttribute()
    shard = pm.NumberAttribute()

    index = TimeIndex()

Event.create_table(wait=True)

n_shard = 5

with Event.batch_write() as batch:
    start = datetime(2020, 1, 1, tzinfo=timezone.utc)

    for i in range(100):
        event = Event(
            event_id=str(uuid.uuid4()),
            time=start + timedelta(minutes=15) * i,
            shard=random.randint(1, n_shard),
        )
        batch.save(event)

If you don’t care the order

def query_between_time_range(
    start: datetime,
    end: datetime,
):
    items = list()
    for i in range(1, 1+n_shard):
        res = Event.index.query(
            hash_key=i,
            range_key_condition=TimeIndex.time.between(start, end),
        )
        for item in res:
            items.append(item)
    return items

for i in query_between_time_range(
    start=datetime(2020, 1, 1, tzinfo=timezone.utc),
    end=datetime(2020, 1, 1, 11, 59, 59, tzinfo=timezone.utc),
):
    print(i.attribute_values)

{'event_id': '990be593-cc9c-43e1-97eb-898ca20290b2', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 1, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'dc49a5e4-6d81-41e1-86d5-ae55f4d5b2ce', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 3, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'cd9b36d7-3128-42bf-a6c5-57df5cedbede', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 4, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '83bab38d-3340-4f4d-b35b-29821034a8cf', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 4, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'edec7a07-194b-4387-9433-8d896ef5c5e5', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 5, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '3116920d-c49b-4c9c-8472-0488a4d22a80', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 7, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'a60d7b0a-5f2f-42d3-bfb9-41e12c8f5b3b', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 8, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '6df0ce08-8311-40a2-9cf7-4199318b683d', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 8, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '2a1ea437-1a08-4e70-9ff5-ebfd4908b34d', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 11, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '5d63b0aa-fd6a-4e4d-a2b0-d7f6337069ed', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 0, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '26740dfd-0c4d-4cd1-bdb0-e5f1f37e8629', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 2, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '3692a7fb-0196-43d1-88b6-71151b117a63', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 2, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3716063-8ba9-4bba-8fcf-e7d1ecf9d273', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 3, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '7fb72b7b-4c2e-485d-ae7a-ed33c80e3af9', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 9, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '49b17218-b2ba-434b-8efd-3ef9475dcac3', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 10, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '7ad2bf73-285e-45e8-8a52-5bbc73b3076b', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 11, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'e6fd52be-8214-4dad-8726-cec3bf5f616a', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 0, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'e6ac98fa-2790-44ae-8346-fdcd59995f14', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 1, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '864b3b92-0103-42a7-a82b-68b67978655c', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 3, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'd178642e-fcb2-4a66-bd22-a1ef432d8aca', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 5, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '197b9afe-7d0f-46d7-b840-417b3a236f79', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 6, 45, tzinfo=datetime.timezone.utc)}
{'event_id': 'f7bec3f9-e379-4a42-b11c-9a2d7a1f9d3e', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 7, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '2eed8f56-b377-4d01-8407-4205939dabf6', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 8, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '5bb69fdf-a4d2-4f8a-9856-c9bbdadb0cca', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 9, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '3c7cf8ce-6cff-4cb6-b2a1-96e413ed7bd1', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 11, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '3e606ffa-d42f-4e47-8f4d-0a71c2b943eb', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 0, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3a7d180-593b-4158-a552-6ecfc116ddb5', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 2, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'e29b403a-b987-4b57-bee8-7be63cebd8cf', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 3, 45, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3df8c0b-728c-4b92-8276-9c46439c0462', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 6, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'b16321a1-bd2d-4b89-9e41-68d396494e01', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 7, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '3288c254-fcf7-4e96-8c35-1a08fc866c58', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 9, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '95853eee-0459-4110-be8a-cd6d68fc7d06', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 0, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'adab2405-84a9-481d-9831-f4a5af872acf', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 4, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'd3f780f2-23d9-48ae-956f-8a6d9c630753', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 6, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'faee22b1-7014-4200-a209-7a7f5dd8d351', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 8, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'fd3e1051-1d78-45da-9708-23fed9ff9755', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 10, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '605703e6-1651-421a-87de-4ccf6d5fc2df', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 11, 15, tzinfo=datetime.timezone.utc)}

If you care the order

def query_between_time_range(
    start: datetime,
    end: datetime,
):
    items = list()
    for i in range(1, 1+n_shard):
        res = Event.index.query(
            hash_key=i,
            range_key_condition=TimeIndex.time.between(start, end),
        )
        for item in res:
            items.append(item)
    return list(sorted(
        items,
        key=lambda item: item.time,
    ))

for i in query_between_time_range(
    start=datetime(2020, 1, 1, tzinfo=timezone.utc),
    end=datetime(2020, 1, 1, 11, 59, 59, tzinfo=timezone.utc),
):
    print(i.attribute_values)

{'event_id': 'e6fd52be-8214-4dad-8726-cec3bf5f616a', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 0, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '3e606ffa-d42f-4e47-8f4d-0a71c2b943eb', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 0, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '95853eee-0459-4110-be8a-cd6d68fc7d06', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 0, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '5d63b0aa-fd6a-4e4d-a2b0-d7f6337069ed', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 0, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '990be593-cc9c-43e1-97eb-898ca20290b2', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 1, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'e6ac98fa-2790-44ae-8346-fdcd59995f14', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 1, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '26740dfd-0c4d-4cd1-bdb0-e5f1f37e8629', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 2, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '3692a7fb-0196-43d1-88b6-71151b117a63', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 2, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3a7d180-593b-4158-a552-6ecfc116ddb5', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 2, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3716063-8ba9-4bba-8fcf-e7d1ecf9d273', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 3, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'dc49a5e4-6d81-41e1-86d5-ae55f4d5b2ce', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 3, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '864b3b92-0103-42a7-a82b-68b67978655c', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 3, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'e29b403a-b987-4b57-bee8-7be63cebd8cf', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 3, 45, tzinfo=datetime.timezone.utc)}
{'event_id': 'cd9b36d7-3128-42bf-a6c5-57df5cedbede', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 4, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'adab2405-84a9-481d-9831-f4a5af872acf', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 4, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '83bab38d-3340-4f4d-b35b-29821034a8cf', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 4, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'd178642e-fcb2-4a66-bd22-a1ef432d8aca', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 5, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'edec7a07-194b-4387-9433-8d896ef5c5e5', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 5, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'a3df8c0b-728c-4b92-8276-9c46439c0462', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 6, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'd3f780f2-23d9-48ae-956f-8a6d9c630753', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 6, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '197b9afe-7d0f-46d7-b840-417b3a236f79', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 6, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '3116920d-c49b-4c9c-8472-0488a4d22a80', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 7, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'f7bec3f9-e379-4a42-b11c-9a2d7a1f9d3e', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 7, 30, tzinfo=datetime.timezone.utc)}
{'event_id': 'b16321a1-bd2d-4b89-9e41-68d396494e01', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 7, 45, tzinfo=datetime.timezone.utc)}
{'event_id': 'a60d7b0a-5f2f-42d3-bfb9-41e12c8f5b3b', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 8, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '2eed8f56-b377-4d01-8407-4205939dabf6', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 8, 15, tzinfo=datetime.timezone.utc)}
{'event_id': 'faee22b1-7014-4200-a209-7a7f5dd8d351', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 8, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '6df0ce08-8311-40a2-9cf7-4199318b683d', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 8, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '5bb69fdf-a4d2-4f8a-9856-c9bbdadb0cca', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 9, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '3288c254-fcf7-4e96-8c35-1a08fc866c58', 'shard': 4, 'time': datetime.datetime(2020, 1, 1, 9, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '7fb72b7b-4c2e-485d-ae7a-ed33c80e3af9', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 9, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '49b17218-b2ba-434b-8efd-3ef9475dcac3', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 10, 0, tzinfo=datetime.timezone.utc)}
{'event_id': 'fd3e1051-1d78-45da-9708-23fed9ff9755', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 10, 45, tzinfo=datetime.timezone.utc)}
{'event_id': '7ad2bf73-285e-45e8-8a52-5bbc73b3076b', 'shard': 2, 'time': datetime.datetime(2020, 1, 1, 11, 0, tzinfo=datetime.timezone.utc)}
{'event_id': '605703e6-1651-421a-87de-4ccf6d5fc2df', 'shard': 5, 'time': datetime.datetime(2020, 1, 1, 11, 15, tzinfo=datetime.timezone.utc)}
{'event_id': '2a1ea437-1a08-4e70-9ff5-ebfd4908b34d', 'shard': 1, 'time': datetime.datetime(2020, 1, 1, 11, 30, tzinfo=datetime.timezone.utc)}
{'event_id': '3c7cf8ce-6cff-4cb6-b2a1-96e413ed7bd1', 'shard': 3, 'time': datetime.datetime(2020, 1, 1, 11, 45, tzinfo=datetime.timezone.utc)}