likes
comments
collection
share

由一道简单的手写题引出的方案设计——短链雪花算法

作者站长头像
站长
· 阅读数 9

前言

本文是一次学习分享,主要是我从一个面试题引发的思考,然后结合实际业务解决问题的案例。从这篇文章中,大家可以思考怎么样才能够举一反三,怎么样结合自己的实际情况去突破技术瓶颈,?

由于公司扩展了新的业务,我们有了一个运营活动需要同时运行在多个App的需求,但是,比如某个活动前端只开发一次,但是需要部署在两个域名下(有一些法务上的限制),对于运营来说,如果每个活动都要让他们配置两次的话,无疑是增加了他们的工作负担,而且还可能出现错配的问题。因此,就引入了一个短链的需求(实际上就是用一个地址根据App的UserAgent来做分发,但是为了照顾到别的业务线的运营,我们就直接把它当做一个短链需求来完成),我们直接把跳转的内容关联到某个短链上,直接把短链给运营进行投放。

面试题之数字转Excel单元格序号

这道面试题,我相信很多同学都做过,比如下面这个图: 由一道简单的手写题引出的方案设计——短链雪花算法 横轴上面的序号是由A-Z,第27列就是AA,其实就相当于是26进制,A代表1,27就是26*10^1+26*10^0得来的。

现在,请编写一个算法,给你一个合法的整数得到转换成Excel横轴上面的字母标识法(即26进制)的内容。

这个题的解决办法,在初等数学就已经讲过叫除K取余法,不过对于很久已经没有再看过数学教材的我们来说,似乎已经忘了这个解法的过程了。我们就不管用什么办法,反正尽量写出这道题吧。

我的思路是,假设从最左边开始取,有多少个26,假设几百上千个,怎么去确定最高位的数字?那好像就完全没办法做。

那从右边开始算呢?因为我们总能求得个位上的数的,所以拿这个整数对26取余,这样就得到了个位上的字母了,因为把个位上的字母已经得到了,那么用这个数减去这个个位上的数字之后,剩下的数就是26的整26倍了。

如果我们现在把这个剩下是整26倍的数除以26,原来的从右边数的第二位不就变成了第一位了吗?似乎已经把刚才的那个数字的规模减小了,而且又回到了重复的问题,就这样一直往从右往左递推,那这样就能把问题解决了。

function transform(num) {
  let result = '';
  const charMap = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
    'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
    'U', 'V', 'W', 'X', 'Y', 'Z'
  ];
  while (num >= 26) {
    const digit = (num - 1) % 26;
    const alphabet = charMap[digit];
    result = alphabet + result;
    num = Math.floor((num - 1) / 26);
  }
  // 处理最后一位数
  result = charMap[num - 1] + result;
  return result;
}

168. Excel表列名称 - 力扣(LeetCode)

短链雪花算法

什么是短链?

短链,一般就是一个很简洁的域名,然后后面跟上一个有意义的参数(比如,v.dy.cn/w1Uirh2,我随便写的,不一定打的开哦),但是我们作为用户不知道它的意义,这个短链服务一般会作为公司的全栈架构入口,一般可以作为BFF中的一个功能,也可以单独开发部署。服务端可以根据用户的UserAgent的不同,把用户的请求导向到对应的业务服务。

对于用户来说,短链比较好记忆,他实际上仅仅只需要记住短链码即可;对于开发者来说,短链服务是一个很好的导流入口,因为开发者可以很容易的拿到用户的UserAgent,就可以根据用户的信息吞吐用户当前设备感兴趣的内容。

比如,在我曾经就职过的一家公司,对于运营来说,有一个叫做超级二维码的功能。这个二维码如果用App扫开,打开的是一个内嵌H5页面;如果是用小程序扫,可以直接打开公司的小程序,这个地址就是根据小程序的标识,返回了一个对应的scheme;而内嵌H5直接以302方式的重定向到了一个网页,其它应用类型以此类推。

生成短链码

短链服务的响应必须要快,在明白了短链服务的意义之后,对我们的雪花算法效率就有一定的要求,所以问题的关键就是在于如何生成短链码,怎么快速的解析短链码。

我们需要用一张表来存这些短链的跳转内容,整数作为主键和UUID作为主键都有各自的优势和考虑因素,以下是使用整数主键相比使用UUID主键的一些优势:

  1. 效率和性能:整数主键通常比UUID主键更高效,因为它们在存储和比较时占用更少的空间。这可以减小磁盘和内存消耗,提高查询性能,特别是在大型数据集上;整数主键通常更容易进行索引,因此查询操作通常更快速。

  2. 数据库大小:整数主键通常需要更少的存储空间,这在大型数据库中可以节省大量的磁盘空间。

  3. 连接操作:在连接不同表时,使用整数主键通常更高效,因为比较整数比较UUID更快。

  4. 数据一致性:整数主键通常更容易确保数据的一致性,因为它们不容易受到UUID生成算法的影响。

然而,使用UUID作为主键也有其优势,特别是在分布式系统和分布式数据库中:

  1. 全局唯一性:UUID保证了全球范围内的唯一性,即使在分布式环境中也可以安全使用。这对于分布式系统和多个数据库实例之间的数据同步非常有用。

  2. 安全性:UUID不容易被猜测或计算出来,因此可以提高数据的安全性。

  3. 独立性:UUID主键不依赖于特定数据库或生成顺序,因此更容易在不同数据库之间迁移和复制数据。

  4. 随机性:UUID主键具有随机性,这可以帮助减轻锁定和热点问题,特别是在高并发环境下。

比较容易想到的就是,用UUID生成一个指定长度的内容,然后取指定的长度。既然是短链,要方便用户记忆,那肯定不可能太长,如果UUID的长度取的太短,我们不禁心里面会有个问号,真的不会出现重复吗?

假设我们在数据库中用自增ID,然后采用哈希算法,然后再取多少位,仍然跟前面的算法存在一样的问题。

所以,在这个时候,我就想到了我在上节提到的面试题。我以26个大写字母+26个小写字母+10个数字对数据库的自增ID做进制转换,那么短链肯定是不会太长了,并且两个ID生成出来的内容一定是不会重复的。

此刻,我又进一步思考了一个问题,如果我的短链服务就这样被别人发现了规律,那岂不是我的所有内容都可以被别人爬取完了吗?哈哈哈,😈,可以玩儿一个阴招,我干嘛那么老实啊,谁告诉你0就真的是代表0啊,哈哈哈。

于是我将这62个字符乱序,得到一个排列,然后将这个序列保存下来,这个就是以后短链的秘钥,加密解密都可以用它来做。

好了,这样就能保证短链码跟数据库表记录有唯一的关联,并且短链码能够转出数据记录的ID,数据记录的ID也能转出短链码。

这个代码简单的令人发指,哈哈哈:

function getShortLinkCode(num) {
  let result = '';
  // 我的字符映射码没有乱序,实际项目中一定要乱序,并且一定要存下来
  const charMap = [
    'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
    'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
    'U', 'V', 'W', 'X', 'Y', 'Z', 
    'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
    'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
    'u', 'v', 'w', 'x', 'y', 'z',
    '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'
  ];
  // 仅仅只需要将原来的26进制转化为62进制即可
  while (num >= 62) {
    const digit = (num - 1) % 62;
    const alphabet = charMap[digit];
    result = alphabet + result;
    num = Math.floor((num - 1) / 62);
  }
  // 处理最后一位数
  result = charMap[num - 1] + result;
  return result;
}

另外,还需要一个根据短链码求解表记录ID的函数,这个函数相对来说要简单一些,但是一定要跟生成短链过程中所用到字符顺序是一致的

function parsePkFromShortLinkCode(code) {
  // 我的字符映射码没有乱序,实际项目中一定要乱序,并且一定要存下来
  const charMap = {
    'A': 1,
    'B': 2,
    'C': 3,
    'D': 4, 
    'E': 5,
    'F': 6,
    'G': 7,
    'H': 8,
    'I': 9,
    'J': 10,
    'K': 11,
    'L': 12,
    'M': 13,
    'N': 14,
    'O': 15,
    'P': 16,
    'Q': 17,
    'R': 18,
    'S': 19,
    'T': 20,
    'U': 21,
    'V': 22,
    'W': 23,
    'X': 24,
    'Y': 25,
    'Z': 26, 
    'a': 27,
    'b': 28,
    'c': 29,
    'd': 30,
    'e': 31,
    'f': 32,
    'g': 33,
    'h': 34,
    'i': 35,
    'j': 36,
    'k': 37,
    'l': 38,
    'm': 39,
    'n': 40,
    'o': 41,
    'p': 42,
    'q': 43,
    'r': 44,
    's': 45,
    't': 46,
    'u': 47,
    'v': 48, 
    'w': 49,
    'x': 50,
    'y': 51,
    'z': 52,
    '0': 53,
    '1': 54,
    '2': 55,
    '3': 56,
    '4': 57,
    '5': 58,
    '6': 59,
    '7': 60,
    '8': 61,
    '9': 62
  };
  // 从个位一直求和到最高位,所以需要reverse一下
  return code.split('').reverse().reduce((total, char, idx) => {
      return (total += charMap[char] * 62 ** idx)
  }, 0)
}

试一下,看看转换是否正确:

由一道简单的手写题引出的方案设计——短链雪花算法

为了让短链不至于太短,我们可以初试数据库的自增ID从1E开始。

这个雪花算法能够在保证性能的前提下,内容不至于被爬虫爬取。

结语

虽然很多同学比较反感刷题,不过从我的经历来说的话,刷题是成为高手的一个必经之路,是突破自己技术瓶颈至关重要的一个阶段。在刷题的过程中,往往我们能够见识到很多不常见的编程手段,俗话说好记性不如烂笔头,自己亲自写一遍,知识就容易转化成我们自己的,形成永久记忆。

在我的这个场景中,也是通过刷题积累到的,然后在合适的时机用对了合适的工具就能迅速的解决问题。对于刷题也没必要怼着一类题型不停的刷刷刷,如果当你已经完全掌握到了一类问题的解决方案之后,就可以跳过了,如果过一段时间你觉得可能忘了,然后再回过头来尝试做几道这个类型的题加深记忆,多重复几次,就形成了永久记忆(至少我是这样的,遇到问题的时候,脑子里下意识的反应就是,这个问题我曾经解决过,哈哈哈)

对于本文阐述的内容有任何疑问的同学可以在评论区留言或私信我。

如果大家喜欢我的文章,可以多多点赞收藏加关注,你们的认可是我最好的更新动力,😁。

转载自:https://juejin.cn/post/7331980540208545801
评论
请登录