短链生成系统设计——Counter+ZooKeeper+Base62

我们最后设计出的系统架构如图所示，如果想了解最后的结论可以跳到最后一小节。这个系统理论上可以支持大流量的生成请求，分布式部署便于扩展。当然在使用的存储方案性能上没有过多的讨论，因为这次的重点是解决“唯一”、“分布式”的ID问题。

准备设计

设计一个系统之前，我们应该对系统的需求有所了解。对于短链系统，首先应该有以下思考：

• 我们需要什么样的短链接，具体是多短？
• 短链系统的请求量有多大？
• 这是个单实例还是分布式系统？

首先我们可以做一些假设，例如参考Twitter有3亿访问/月，我们假设有它的10%，也就是3千万/月，平均每日100万。

然后再来假设生成的短链，一般格式为domain/unique_id，例如s-url.com/D28CZ63，我们假设Unique ID的长度最多为7位。

下面我们根据这些假设条件来完成这个系统的设计。

数据量计算

根据上面的假设，首先每个原始URL可以按照2KB估算（2048字符），而短URL可以按照17Byte估算；我们可能还需要记录创建时间和过期时间，分别是7Byte。因此可以大致估算每行记录的大小应该为2.031KB。

我们一共有30M月访问，30M * 2.031KB = 60.7GB，每月约60GB数据，因此一年内估算为0.7TB，5年3.6TB数据量。

唯一ID算法

我们需要的是一个短的（7位）唯一ID生成方案。考虑Base62和MD5，Base62即使用0-9A-Za-z一共62个字符，MD5使用0-9a-z，一般输出长度为32的字符串。

使用MD5的话，因为输出长度固定，我们可能需要截取其前7位来作为唯一ID，这种情况下，首先不同的输入可能会输出相同的MD5，其次，不同的MD5的前7位也可能是相同的。这样的话会产生不少的Collision，需要业务上进行保障。而使用MD5的好处，也恰恰是如果不同用户提交相同输入，那么可以得到相同的ID而不需要重复生成新的短链ID，但是同样需要业务进行处理和保证。

对于Base62，每一位有62个可能字符串，7位则是62^7=3521614606208种组合，每秒产生1000个ID的话也足够使用110年。同时在短URL的要求上，Base62接受输入，产生的输出长度会根据输入变化，因此不需要进行截取，而只需要想办法将7位ID的所有情况消耗完毕就可以满足大部分场景的要求。Base62伪代码如下：

f base62_encode(deci):
    s = '0-9A-Za-z'
    hash_str = ''
    while deci > 0:
        hash_str = s[deci % 62] + hash_str
        deci /= 62
    return hash_str

存储选择

一般我们会考虑使用RDBMS比如MySQl，或者NoSQL比如Redis。在关系型数据库中，横向扩展会比较麻烦，例如MySQL进行分表和分库，我们可能需要多个实例，而扩展需要一开始就设想好，但是这一点在NoSQL中会相对比较容易，例如使用一个Redis的Cluster，或许向里面添加节点会相对容易一点。而使用NoSQL我们可能需要考虑数据的最终一致性，还有数据的持久化等问题。

同时根据业务场景，从性能上考虑如果在高峰期有大量短链生成请求需要写入到MySQL或许表现会比Redis差一些。

对于将“长URL-短URL”的映射关系写入数据库的步骤，重点是确保这个短URL没有被其他长URL使用过。如果使用过，那么你需要想办法使用新的字符串生成这个短URL。

先来想一下，这是一个两步操作，首先查询是否存在，然后写入。如果这是个串行，那么是可行的。如果这是一个并行操作，很显然，你可能查询的时候发现没有存在这个短URL，而其他Session也查到了同样的结果，最后大家都认为可以写入，然后写入过程中晚写的一方就会出问题。

在RDBMS中我们可能可以通过一些提供的方法来解决这个问题，例如INSERT_IF_NOT_EXISTS，但是在NoSQL中是没有这些方法的，因为它的设计是要实现最终一致性，所以不会提供这种支持。

基于以上分析和假设的方案

我们需要确定的内容主要是：

• 生成算法
• 存储选择

目前罗列出来的方案主要包括：MD5，Base62，以及MySQL和Redis。

如果使用MD5的话，需要使用能够解决哈希冲突的RDBMS，因为这个步骤在NoSQL上处理比较麻烦，所以会有MD5+MySQL的组合。这套组合实际上性能并不太满足需求，并且在扩展上会相对另外一组组合难度大些。

那么另外一种就是我们打算使用的方案：Base62+Redis。如何将7位Base62的所有情况都用尽，我们可以采用一个计数器，从0-62^7的数字转为Base62，作为短链ID使用。这个方案在单实例上是很容易的，并且可以保证冲突问题。那么如何实现它的可扩展性呢？

在接入大流量的情况下，我们必然需要部署多点的ID生成服务，那么根据思路，我们需要对应的计数来转换成Base62的唯一ID，如果不同的服务拿到了同样的计数，那么就会生成相同的ID，造成冲突，且因为分布式的部署，仍然能够正常写入。

因此现在问题转化为如何让不同的服务拿到正确的计数。因为总的数字段是已知的（0-62^7），一个很简单的方法就是我们提前将这些数字进行分段，每个ID生成服务都拿到不同段的数字本地使用。例如：

0-100000
100001-200000
200001-300000
300001-400000
400001-500000
500001-600000
...

当服务的计数消耗完毕后，继续向计数分配的服务请求下一段可用的数字。例如目前有3个ID生成服务A、B、C，在最初的分配中A拿到了0-100000号码段，B拿到了100001-200000，C拿到了200001-300000。当A使用完之后，询问分配服务，拿到下一段300001-400000。如此即可解决计数器分布式部署的问题。

在数字段分配的业务场景，很容易想到使用ZooKeeper实现，因为ZooKeeper是分布式架构，保障单点故障时仍然可以正确地分配计数号码，这样我们不用重复造轮子实现自己的高可用的分发服务。

2020-03-03：号段生成与获取

补充这一段主要因为很想尝试一下，ZK对于自己来说还是太过陌生，于是就花了点时间测试。

初始化

import json
from kazoo.client import KazooClient

zk = KazooClient(hosts='127.0.0.1:2181')
zk.start()
exist = zk.exists("/url-shortener")
if exist:
    quit()

# Node not exist. Initializing with counter range
zk.create("/url-shortener")

uid_length = 7
start = 62 ** uid_length
end = start + 100000
data = json.dumps({
    "start": start,
    "end": end
}).encode("utf-8")
zk.create("/url-shortener/range-", value=data, sequence=True)

children = zk.get_children("/url-shortener")
int(children)

连接上本地的ZK，如果目录已经存在，说明已经完成过初始化了，直接结束。

初始化过程也就是根据配置参数初始化对应的起始数值，因为我需要一个7位长度的ID，对应base62的数值起始位置是62 ** 7。号段长度可以分配，号段太长的话，如果有应用的节点挂掉，则有可能浪费掉一段；号段太短，则应用节点需要频繁向ZK询问取号。这里设置为100000。

拿到号段始末后，初始化一个顺序的znode，顺序是因为我可以提前生成一堆znode保存数据，Client直接取即可。不过这里测试过62^7-62^8的范围实在是太大了，按照区间长度为100000来分配的话需要预先初始化(62^8 - 62^7) / 100000 = 2148184909个节点，完全没有必要。先初始化1个节点，然后让Client取的时候自动生成下一段即可。

取号

import json
import os
import time
import random

from kazoo.client import KazooClient
zk = KazooClient(hosts='127.0.0.1:2181')
zk.start()
lock = zk.Lock("/url-shortener-lock", "get_range")

def get_range():
    with lock:
        exist = zk.exists("/url-shortener")
        if not exist:
            print("ZK path not exist!")

        children = zk.get_children("/url-shortener/")
        if children and len(children) == 1:
            node_path = "/url-shortener/%s" % children[0]
            data, stat = zk.get(node_path)
            seq_range = json.loads(data.decode("utf-8"))
            start = seq_range["start"]
            end = seq_range["end"]
            print("Process %d gets range: %d-%d" % (os.getpid(), start, end))
            # generating next range
            start = end + 1
            end = start + 100000
            data = json.dumps({
                "start": start,
                "end": end
            }).encode("utf-8")
            zk.create("/url-shortener/range-", value=data, sequence=True)
            zk.delete(node_path)
            children = zk.get_children("/url-shortener")
        else:
            print("Running out of range!")
    return

if __name__ == '__main__':
    get_range()

取号逻辑也很简单，暂时还没有完善异常处理。检查指定的Path下是否有znode可用，如果没有的话可能是异常或号段用完，对应处理一下即可。然后获取znode的值，作为自己目前的号段范围。

生成下一个号段，那么就用上一段的末尾加上固定长度就行，同样创建一个znode，删除旧的节点。

原来确实是这么考虑的，不过发现，如果有多个Client同时尝试获取range，因为读znode和写znode和删除znode并不是原子操作，多个节点读到znode信息后，用作自己的range（已重复），创建新znode（创建了多个顺序的，内容相同的znode），删除znode（只有1个会操作成功，其余出错），所以数据都是错的。

既然用到了ZK，那么顺便来用一下ZK的分布式锁，原理就是创建对应的用作锁的顺序znode，序号靠后的client需要注册对应的watcher等待前一把锁释放（删除），当前面的锁释放（或挂掉，临时znode自动删除）触发watcher后，后面的client获得锁。kazoo已经为我们实现好了对应的逻辑，在执行过程中，可以看到/url-shortener-lock路径下的znode：

[zk: localhost:2181(CONNECTED) 121] ls /url-shortener-lock
[1f5cda205022418c8b7db432a667dfd5__lock__0000000342, 9dffb44d40a74bbc969c4c64616b77d2__lock__0000000344, a829fbf9835c46bbaa4af4dda02aa9c1__lock__0000000343]

我们运行了3个并行的进程，因此有3个znode被创建，只有其中1个能执行临界区的代码。执行结果就是各自获取到了不同的range，符合期望：

(zk) duck@duck-MS-7A34:~/src/apache-zookeeper-3.5.7-bin/script$ ./run_consume.sh 
Process 14188 gets range: 3521648606548-3521648706548
Process 14186 gets range: 3521648706549-3521648806549
Process 14187 gets range: 3521648806550-3521648906550
All done