Skip to content

Explain

Jump to bottom
songang edited this page Jan 21, 2022 · 5 revisions

项目详细解释

一个短链系统，我们应该做什么呢？

  1. 将长链接变为短链；
  2. 用户访问短链接，会跳转到正确的长链接上去。

短链系统有哪些需要注意的地方

  1. 短链key的生成逻辑
  2. 如何提高短链key生成效率

如何生成短链key

生成短链方法有很多,如: md5长链、 自增序列算法、 摘要算法、哈希法、 普通随机数。

最终本项目借鉴了 美团leaf分布式ID生成系统 整理出来了适合本项目的生成短链key逻辑 <号码段模式>

在针对生成短链key生成效率优化: 使用简化版的 Leaf-segment 数据库方案 及 双buffer优化

数据库方案

首先先看下 短链key生成表结构

CREATE TABLE `durl_short_num` (
    `id` tinyint(1) unsigned NOT NULL AUTO_INCREMENT,
    `max_num` int(11) unsigned NOT NULL DEFAULT '1' COMMENT '号码段开始值',
    `step` int(11) unsigned NOT NULL DEFAULT '1' COMMENT '步长',
    `version` int(11) unsigned NOT NULL DEFAULT '1' COMMENT '版本号',
    `update_time` int(10) unsigned NOT NULL DEFAULT '0' COMMENT '数据修改时间',
    PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=1 DEFAULT CHARSET=utf8mb4 COMMENT='短链号码段';

短链key为号码段short_num进行62进制转换后的值.

项目初始化及使用期间,每次获取一个step号段。如:200-300, 用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。

重要字段说明： max_num表示目前所被分配的短链key的最大值。 step表示每次分配的号段长度。version是一个乐观锁，每次都更新version，保证并发时数据的正确性

在多台机器,考虑获取号码段重复获取数据时使用乐观锁查询方式.

在实际线上环境,只需要把step设置得足够大，比如1000。 那么只有当1000个号被消耗完了之后才会去重新读写一次数据库。 读写数据库的频率从1减小到了1/step，大致架构如下图所示：

双buffer

如果取号段的时机是在号段消耗完的时候进行的，也就意味着号段临界点的ID下发时间取决于下一次从DB取回号段的时间， 并且在这期间进来的请求也会因为DB号段没有取回来，导致线程阻塞。 如果请求DB的网络和DB的性能稳定，这种情况对系统的影响是不大的，但是假如取DB的时候网络发生抖动，或者DB发生慢查询就会导致整个系统的响应时间变慢。

为此，我们希望DB取号段的过程能够做到无阻塞，不需要在DB取号段的时候阻塞请求线程， 即当号段消费到某个点时就异步的把下一个号段加载到内存中。 而不需要等到号段用尽的时候才去更新号段。

采用双buffer的方式，服务内部有两个号段缓存区segment。 当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。 当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。

黑名单模块 ipTireBenchMark

序言

在短链业务转换请求中，亦或者短链跳转时要考虑恶意的短链生成请求以及本不存在的短链跳转请求，大量的恶意请求将穿透内存缓存并直接将请求压力转移至数据库， 为避免情况发生，我们开发了黑名单管理模块，可将恶意请求ip地址进行屏蔽。

测试思路

这里衍出一些思考针对一个恶意的IP地址怎么存放和查询效率是最高的，是当成字符串直接存入数据表中还是以点分割分别存储。 我们目前的做法是将一个IP地址以点分割成四块，然后使用内存存入[]byte 字节数组，使用前缀树的检索逻辑来增加检索效率。 但是我们同时考虑如果针对一个IP地址省去分割的工作直接以map[string]结构进行存储是否会占用更小的内存，或者检索速度上会更好。(注:这里IP地址仅指ipv4格式) 我们希望通过durl项目中 app/share/tool/ipTire_test.go 中一些go基准测试方法去进行两种对比。

测试目标

使用 go test 的基准测试进行测试，体现两种实现方式的调用耗时、内存分配情况

测试方法

以 go test -bench=BenchmarkAddAndSearch -benchmem 测试前缀树实现下的基准测试结果

以 go test -bench=BenchmarkAddAndSearchMap -benchmem 测试map实现下的基准测试结果

以上两类基准测试方法均使用相同数据量下，随机的ip生成及检索的结果。

开始测试

环境

性能测试使用的机器配置为:

  • 单机1: 2021MacPro Apple M1pro 8 核中央处理器 14 核图形处理器 16GB 内存 macOS12.0.1

配置

使用go test 默认基础配置，GOMAXPROCS:8

结果

前缀树下

  • go test -bench=BenchmarkAddAndSearch -benchmem
    goos: darwin
    goarch: arm64
    pkg: durl/app/share/tool
方法 调用次数 平均耗时 每次内存分配字节 内存分配次数 解释
BenchmarkAddAndSearch1-8 8308 140554 ns/op 72000 B/op 2000 allocs/op 添加100ip，检索1000次
BenchmarkAddAndSearch2-8 830 1425830 ns/op 720004 B/op 20000 allocs/op 添加1000ip，检索1万次
BenchmarkAddAndSearch3-8 81 14595697 ns/op 7200025 B/op 200000 allocs/op 添加1万，检索10万次
BenchmarkAddAndSearch4-8 8 140793474 ns/op 72000268 B/op 2000000 allocs/op 添加10万，检索100万次
BenchmarkAddAndSearch5-8 1 1389990292 ns/op 720000032 B/op 20000000 allocs/op 添加100万，检索1000万次

map下

  • go test -bench=BenchmarkAddAndSearchMap -benchmem
    goos: darwin
    goarch: arm64
    pkg: durl/app/share/tool
方法 调用次数 平均耗时 每次内存分配字节 内存分配次数 解释
BenchmarkAddAndSearchMap1-8 85 14125581 ns/op 16005 B/op 1000 allocs/op 添加100ip，检索1000次
BenchmarkAddAndSearchMap2-8 8 141022245 ns/op 160030 B/op 10000 allocs/op 添加1000ip，检索1万次
BenchmarkAddAndSearchMap3-8 1 1410140500 ns/op 1600000 B/op 100000 allocs/op 添加1万，检索10万次
BenchmarkAddAndSearchMap4-8 1 14098579667 ns/op 16009984 B/op 1000059 allocs/op 添加10万，检索100万次
BenchmarkAddAndSearchMap5-8 1 140832991125 ns/op 160004848 B/op 10000017 allocs/op 添加100万，检索1000万次

结论

通过基础测试结果得出：

  • 不管从小量数据到大量数据的基准测试结果上来看，从调用次数和平均耗时上都是前缀树占优势
  • 从内存分配占用上来说，map在测试时由于知道待添加的ip数据量可以直接开辟对应的内存进行使用，所以内存分配字节、内存分配次数上是占据优势的，而前缀树的初始大小为256，所以根据所需存储量的大小，内存需要一次次的重新分配。
Clone this wiki locally