Database Sharding

http://www.25hoursaday.com/weblog/2009/01/16/BuildingScalableDatabasesProsAndConsOfVariousDatabaseShardingSchemes.aspx
Definition: the process of splitting up a database across multiple machines to improve the scalability of an application.

Why ?
Reach to a limit to original database.
Scale vertically too expensive. Limitation: RAM, CPU power, disk I/O, storage capacity. bandwidth.

Common Sharding Schemes:
主要思路: break up an application databse into multiple small dbs. Main schemas:

  1. Vertical Partitioning:
    思路: segment application databse to moves tables related to specific features to their own server. 也就是根据table的specific features来进行分割。
    举例: User table => 分割为 1. User profile table 2. friend lists table 3. user generated content table, e.g. photos, blogs. 3个table各放置在一台server上面
    Trade Off:
    Pro: approach is straightforward and low impact
    Cons: 随着site用户增长, 有些table可能需要继续拆分(further sharding a feature specific database across multiple servers), e.g. handing metadata queries for 10 billion photos by 140 million users .

  2. Range Based Partitioning
    需求场景: the entire dataset for a single feature or table still needs to be further subdivided across mutiple machines.
    思路: 1. split data based on values range that occur within each entity. e.g. sales transaction 可以根据created date 来分割; assigning users 可以根据zip code来划分
    Trade Offs:
    Pro:
    Cons: value range 选择不好,会导致unbalanced servers. sales transaction的例子可能会导致某些server的访问量巨大, user划分的例子是根据user evenly distribution划分的, 有些地区可能users跨zip的情况经常发生导致fail to account

  3. Key or Hash Based Partitioning
    需求场景: Web2.0 sites,每个user都在db中有个对应的数字 hash id, 来决定哪台server来服务这个user. e.g.10台database servers, 用户ID是个数字,每次新来一个用户,新用户分配的Id是之前用户的ID+1. 这种情况下Hash function可以选择UserID % 10 取余数, 用余数的值来决定哪台database server 来服务于这个用户.
    还有一种是对“Hash(key) mod N”的改进:假设我们要将数据分不到20台机器上,传统做法是hash(key) mod 20,而改进后,N取值要远大于20,比如是20000000,然后我们采用额外一张表记录每个节点存储的key的模值,比如:
    node1:0~1000000
    node2:1000001~2000000
    Trade Offs:
    Cons: 仅用于固定的servers数, 如果server增加也就意味着Hash Function也会变。

  4. Directory Based Partitioning
    需求场景: 根据 partitioning schema来创建个lookup service.这种松耦合结构可以有效的从原来的DB 层解耦,不用每次访问都提供db的access code。
    Trade Offs:
    Pros: 例如用GetDatabaseFor()方法来存储/返回一个从entity key-> 需求的database server的映射表. 这个映射表不会因为你partitioning scehma的改变而影响到你的app。
    例如针对之前10台db servers跟Hash function的问题,假如我们想新增5台servers, 并不想增加downtime。 我们可以保留当前的Hash function, 将这5台新增servers作为一个pool, 执行一个新的script 把根据新的hash Function数据从原来的10台servers拷贝到这5台新的servers上面(Tricky 用的用户持续update他们的信息)。 拷贝完成后, 原有的旧Hash function可以在以前的10台servers上面继续用。

    Problems Common to all Sharding schemas

    Joins and Denormalization

    Joining data from multiple shareds

    Rebalancing

Advertisements