EricJJ' Blog

写代码

关于短链接生成系统

2019-09-03

最近有用到短链接服务,参考了目前已有的算法,62 进制转换。如果短链接长度为6的话, 能产生 5680,023,5584 个不重复短链接,
主要是要维护一个当前已有短链接数量,用来实现 int to str62的转换,其他部分都可以改成 db 存储。

我这里用 index_cache 来表示原始链接转换后的 index,对应数据库的自增 id。
cache 来表述原始链接与短链接的对应关系。
低配单机生成 100,000 条需要 0.2s
不过业务量大还是需要分布式生成算法, 譬如Snowflake MongoID等。

class SortLinker(object):

  def __init__(self, base_url='https://google.com/', url_len=6, cap=0):
    self.digits62 = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
    self.max_len = pow(len(self.digits62), url_len)
    self.base_url = base_url
    self.url_len = url_len
    self.cache = {}
    self.index_cache = {}
    self.cap = cap

  def _int_to_str62(self, x):
    s = ''
    if x == 0:
        s = str(x)
    else:
      while x >= 62:
          s = self.digits62[x % 62] + s
          x = x // 62
      if x >= 0:
        s = self.digits62[x] + s
    return s

  # 生成短链接
  # 获取 index 可换成 db 操作
  def create(self, origin_url):
    index = 0
    if origin_url in self.index_cache:
      index = self.index_cache[origin_url]
    else:
      self.cap += 1
      index = self.cap
      if index >= self.max_len:
        print(f'index exceed the limit {index} > {self.max_len}')
        return ''

    key = self._int_to_str62(index)
    prefix = '0' * (self.url_len - len(key))
    url = f'{self.base_url}{prefix}{key}'
    self.cache[url] = origin_url
    self.index_cache[origin_url] = index
    return url

  # 获取原始长链接
  # decode url
  def find(self, sort_url):
    return self.cache.get(sort_url, '')


linker = SortLinker()
sort_urls = []
for i in range(10000):
  origin_url = f'https://repl.it/{i}'
  sort_url = linker.create(origin_url)
  print(origin_url, sort_url, linker.find(sort_url), i, len(linker.cache.keys()))