通知设置 新通知
怎么设计一个抢红包系统?
zkbhj 发表了文章 • 0 个评论 • 2522 次浏览 • 2022-07-03 11:46
活动规模
公司在年底,为员工准备了 25 万元的抢红包活动,在年三十晚 8 点准时开始。
技术方案
首先要理解到抢红包特殊的业务场景,红包抢到了并不等于把钱拿到手了。抢红包其实主要有 3 个核心流程:红包金额拆分->抢红包->打款。
红包金额拆分是指将指定金额拆分为指定数目红包的过程,用来确定每个红包的金额数;抢红包是用户抢红包的这个操作,典型的高并发场景,需要系统扛流量且避免红包超发的情况;打款就是将抢到的红包通过微信/银行打款到用户钱包的过程(真正把红包的钱拿到手了),因为要对接三方支付系统是整个系统比较耗时的操作,一般通过异步任务来实现;
红包金额拆分
可选的方案
拆分方式
1、实时拆分
实时拆分,指的是在抢红包时实时计算每个红包的金额,以实现红包的拆分过程,对系统性能和拆分算法要求较高,例如拆分过程要一直保证后续待拆分红包的金额不能为空,不容易做到拆分的红包金额服从正态分布规律。
2、预先生成
预先生成,指的是在红包开抢之前已经完成了红包的金额拆分,抢红包时只是依次取出拆分好的红包金额,对拆分算法要求较低,可以拆分出随机性很好的红包金额,通常需要结合队列使用。
拆分算法
红包拆分算法拆分的金额要看起来随机,最好能够服从正态分布,可以参考 微信 和 @lcode 提供的红包拆分算法。
微信拆分算法的优点是算法较简单,拆分效率高,同时由于该算法天然的特性,可以保证后续红包金额一定不为空,特别适合实时拆分场景,但缺点是会导致大额红包较大概率地在拆分的最后出现。 @lcode 拆分算法的优点是拆分金额基本符合正态分布,适合随机性要求较高的拆分场景。
我们的方案
我们这次的场景对红包金额的随机性要求不高,但是对系统可靠性要求较高,所以我们选用了预先生成方式,使用 二倍均值法 的算法拆分红包金额。
拆分算法可以描述为:假设剩余拆分金额为 M,剩余待拆分红包个数为 N,红包最小金额为 1 元,那么定义当前红包的金额为:
m=rand(1,floor(M/N∗2))
其中,floor 表示向下取整,rand(min, max) 表示从 [min, max] 区间随机一个值。M/N*2 表示剩余待拆分金额平均金额的 2 倍,因为 N >= 2,所以 M/N*2 <= M,表示一定能保证后续红包能拆分到金额。
代码实现为:for ($i = 0; $i < $N - 1; $i++) {
$max = (int)floor($M / ($N - $i)) * 2;
$m[$i] = $max ? mt_rand(1, $max) : 0;
$M -= $m[$i];
}
$m = $M;值得一提的是,为了保证红包金额差异尽量小,先将总金额平均拆分成 N+1 份,将第 N+1 份红包按照上述的红包拆分算法拆分成 N 份,这 N 份红包加上之前的平均金额才作为最终的红包金额。
抢红包
可选的方案
限流
1、前端限流
前端限制用户在 n 秒之内只能提交一次请求,虽然这种方式只能挡住小白(99% 的用户),所以也必须得做。
2、后端限流
常用的后端限流方法有 漏桶算法 和 令牌桶算法。漏桶算法 主要目的是控制请求数据注入的速率,如果此时漏桶溢出,后续的请求数据会被丢弃。而 令牌桶算法 是以一个恒定的速度往桶里放入令牌,而如果请求数据需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌时,这些请求才被丢弃,令牌桶算法的一个好处是可以方便地改变应用接受请求的速率。
防并发超发红包
1、库存加锁
可以通过加锁的方式解决,但是加锁会增加系统开销,大流量下更容易拖垮系统,也可以尝试一下基于版本号的乐观锁。
2、队列串行化请求
之所会出现超发问题,是因为并发时会出现多个进程同时操作同一资源的现象,如果使用高速队列将并行请求串行化,那么问题就不存在了。高速队列可以使用 Redis 来实现,但是还要必须保证整个流程调用链要短、要快,否则队列会积压严重,甚至会拖垮整个系统。
我们的方案
我们选用队列串行化的方案,抢红包整个过程只会操作 Redis,且都是简单高效的 Pop 和 Push 命令操作。
抢红包流程:先从红包队列中 Pop 占有红包,然后 Push 红包到任务队列(待异步打款处理),并同步告知用户抢到红包的结果,抢红包流程就结束了。
当然,在实际应用中,占有红包过程中还会有一些前置规则校验,比如用户是否已经领取过,领取次数是否已经达到上限等?红包占有流程图如下:
其中,red::list为 List 结构,存放预先拆分好金额的红包;red::task 也为 List 结构,异步打款处理任务队列;red::draw为 Hash 结构,存放红包领取记录,field为用户的 openid,value为序列化的红包信息;red::draw_count:u:openid为 k-v 结构,用户领取红包计数器。
1、怎么保证不超发
从红包占有流程图可看出,这个过程是会操作很多 Key,那怎么保证原子性?我们选用了 Lua 方案,一方面是因为首先要保证性能,没有多次请求的网络开销,另一方面 Lua 脚本执行时本身就是原子性的,满足需求。
红包占有的 Lua 脚本实现如下:-- 领取人的openid为xxxxxxxxxxx
local openid = 'xxxxxxxxxxx'
local isDraw = redis.call('HEXISTS', 'red::draw', openid)
-- 已经领取
if isDraw ~= 0 then
return true
end
-- 领取太多次了
local times = redis.call('INCR', 'red::draw_count:u:'..openid)
if times and tonumber(times) > 9 then
return 0
end
local number = redis.call('RPOP', 'red::list')
-- 没有红包
if not number then
return {}
end
-- 领取人昵称为Fhb,头像为https://xxxxxxx
local red = {money=number,name='Fhb',pic='https://xxxxxxx'}
-- 领取记录
redis.call('HSET', 'red::draw', openid, cjson.encode(red))
-- 处理队列
red['openid'] = openid
redis.call('RPUSH', 'red::task', cjson.encode(red))
return true
需要注意 Lua 脚本执行过程并不是事务的,脚本中的操作命令在执行时是有先后顺序的,当某个操作执行失败时不会回滚已经执行成功的操作。
2、怎么提高系统响应
由于抢红包和打款流程分开,抢红包过程只需操作 Redis,整个操作短且快,故不存在性能问题。
打款
我们的方案
采用 Worker 任务去消费任务队列,调用红包支付 API,以及数据持久化操作(后续对账)。尽管红包发放调用链又长又慢,但是这些 Worker 是 无状态 的,所以可以通过增加 Worker 数量,提高系统的消费处理能力。
1、怎么保证数据一致性
若红包打款失败了,前面已经告知用户抢到红包,但是却木有发,那用户肯定会很愤怒。但是根据 CAP 原理,我们通常只需做到数据最终一致性。
我们在打款流程里面做了重试机制,生成一个全局唯一的外部订单号,当某红包打款失败,就会放回任务队列重试,当然重试时要处理好幂等。
2、怎么保证Worker不异常结束
Worker 的实现如下:$maxTask = 1000;
$sleepTime = 1000;
while (true) {
while ($red = RedLogic::getTask()) {
RedLogic::doTask($red);
//处理多少个任务主动退出
$maxTask--;
if ($maxTask < 0) {
return EXIT_CODE_NORMAL;
}
}
//等待任务
usleep($sleepTime);
}
这里使用 LPOP 命令获取任务,所以使用了 while 结构,并且无任务时需要等待,可以用阻塞命令 BLPOP 来改进。
由于 Worker 需要常驻内存运行,难免会出现异常结束的情况(也有主动 Exit), 所以需要保持 Worker 一直处于运行状态。我们使用进程管理工具 Supervisor 来监控和管理 Worker 任务,当任务队列出现堆积时,增加 Worker 数量即可。Supervisor 的监控后台如下:
保障方案
资源CDN缓存
由于本次活动力度较大,静态页面占流量的很大一部分,所以静态页面在发布时都会放置一份在 CDN 上,这样回源的流量就很小了。
降级措施
尽管做了很多准备,还是无法确保万无一失,我们在每个关键节点都增加了开关,一但出现异常,可以通过配置中心人工介入做降级处理。
原文来自微信公众号:后端搬运工。
原文地址:https://mp.weixin.qq.com/s/VG_Wcxte8avnXzn4bPXiGA
欢迎大家多关注! 查看全部
活动规模
公司在年底,为员工准备了 25 万元的抢红包活动,在年三十晚 8 点准时开始。
技术方案
首先要理解到抢红包特殊的业务场景,红包抢到了并不等于把钱拿到手了。抢红包其实主要有 3 个核心流程:红包金额拆分->抢红包->打款。
- 红包金额拆分是指将指定金额拆分为指定数目红包的过程,用来确定每个红包的金额数;
- 抢红包是用户抢红包的这个操作,典型的高并发场景,需要系统扛流量且避免红包超发的情况;
- 打款就是将抢到的红包通过微信/银行打款到用户钱包的过程(真正把红包的钱拿到手了),因为要对接三方支付系统是整个系统比较耗时的操作,一般通过异步任务来实现;
红包金额拆分
可选的方案
拆分方式
1、实时拆分
实时拆分,指的是在抢红包时实时计算每个红包的金额,以实现红包的拆分过程,对系统性能和拆分算法要求较高,例如拆分过程要一直保证后续待拆分红包的金额不能为空,不容易做到拆分的红包金额服从正态分布规律。
2、预先生成
预先生成,指的是在红包开抢之前已经完成了红包的金额拆分,抢红包时只是依次取出拆分好的红包金额,对拆分算法要求较低,可以拆分出随机性很好的红包金额,通常需要结合队列使用。
拆分算法
红包拆分算法拆分的金额要看起来随机,最好能够服从正态分布,可以参考 微信 和 @lcode 提供的红包拆分算法。
微信拆分算法的优点是算法较简单,拆分效率高,同时由于该算法天然的特性,可以保证后续红包金额一定不为空,特别适合实时拆分场景,但缺点是会导致大额红包较大概率地在拆分的最后出现。 @lcode 拆分算法的优点是拆分金额基本符合正态分布,适合随机性要求较高的拆分场景。
我们的方案
我们这次的场景对红包金额的随机性要求不高,但是对系统可靠性要求较高,所以我们选用了预先生成方式,使用 二倍均值法 的算法拆分红包金额。
拆分算法可以描述为:假设剩余拆分金额为 M,剩余待拆分红包个数为 N,红包最小金额为 1 元,那么定义当前红包的金额为:
m=rand(1,floor(M/N∗2))
其中,floor 表示向下取整,rand(min, max) 表示从 [min, max] 区间随机一个值。M/N*2 表示剩余待拆分金额平均金额的 2 倍,因为 N >= 2,所以 M/N*2 <= M,表示一定能保证后续红包能拆分到金额。
代码实现为:
for ($i = 0; $i < $N - 1; $i++) {值得一提的是,为了保证红包金额差异尽量小,先将总金额平均拆分成 N+1 份,将第 N+1 份红包按照上述的红包拆分算法拆分成 N 份,这 N 份红包加上之前的平均金额才作为最终的红包金额。
$max = (int)floor($M / ($N - $i)) * 2;
$m[$i] = $max ? mt_rand(1, $max) : 0;
$M -= $m[$i];
}
$m = $M;
抢红包
可选的方案
限流
1、前端限流
前端限制用户在 n 秒之内只能提交一次请求,虽然这种方式只能挡住小白(99% 的用户),所以也必须得做。
2、后端限流
常用的后端限流方法有 漏桶算法 和 令牌桶算法。漏桶算法 主要目的是控制请求数据注入的速率,如果此时漏桶溢出,后续的请求数据会被丢弃。而 令牌桶算法 是以一个恒定的速度往桶里放入令牌,而如果请求数据需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌时,这些请求才被丢弃,令牌桶算法的一个好处是可以方便地改变应用接受请求的速率。
防并发超发红包
1、库存加锁
可以通过加锁的方式解决,但是加锁会增加系统开销,大流量下更容易拖垮系统,也可以尝试一下基于版本号的乐观锁。
2、队列串行化请求
之所会出现超发问题,是因为并发时会出现多个进程同时操作同一资源的现象,如果使用高速队列将并行请求串行化,那么问题就不存在了。高速队列可以使用 Redis 来实现,但是还要必须保证整个流程调用链要短、要快,否则队列会积压严重,甚至会拖垮整个系统。
我们的方案
我们选用队列串行化的方案,抢红包整个过程只会操作 Redis,且都是简单高效的 Pop 和 Push 命令操作。
抢红包流程:先从红包队列中 Pop 占有红包,然后 Push 红包到任务队列(待异步打款处理),并同步告知用户抢到红包的结果,抢红包流程就结束了。
当然,在实际应用中,占有红包过程中还会有一些前置规则校验,比如用户是否已经领取过,领取次数是否已经达到上限等?红包占有流程图如下:
其中,red::list为 List 结构,存放预先拆分好金额的红包;red::task 也为 List 结构,异步打款处理任务队列;red::draw为 Hash 结构,存放红包领取记录,field为用户的 openid,value为序列化的红包信息;red::draw_count:u:openid为 k-v 结构,用户领取红包计数器。
1、怎么保证不超发
从红包占有流程图可看出,这个过程是会操作很多 Key,那怎么保证原子性?我们选用了 Lua 方案,一方面是因为首先要保证性能,没有多次请求的网络开销,另一方面 Lua 脚本执行时本身就是原子性的,满足需求。
红包占有的 Lua 脚本实现如下:
-- 领取人的openid为xxxxxxxxxxx
local openid = 'xxxxxxxxxxx'
local isDraw = redis.call('HEXISTS', 'red::draw', openid)
-- 已经领取
if isDraw ~= 0 then
return true
end
-- 领取太多次了
local times = redis.call('INCR', 'red::draw_count:u:'..openid)
if times and tonumber(times) > 9 then
return 0
end
local number = redis.call('RPOP', 'red::list')
-- 没有红包
if not number then
return {}
end
-- 领取人昵称为Fhb,头像为https://xxxxxxx
local red = {money=number,name='Fhb',pic='https://xxxxxxx'}
-- 领取记录
redis.call('HSET', 'red::draw', openid, cjson.encode(red))
-- 处理队列
red['openid'] = openid
redis.call('RPUSH', 'red::task', cjson.encode(red))
return true
需要注意 Lua 脚本执行过程并不是事务的,脚本中的操作命令在执行时是有先后顺序的,当某个操作执行失败时不会回滚已经执行成功的操作。
2、怎么提高系统响应
由于抢红包和打款流程分开,抢红包过程只需操作 Redis,整个操作短且快,故不存在性能问题。
打款
我们的方案
采用 Worker 任务去消费任务队列,调用红包支付 API,以及数据持久化操作(后续对账)。尽管红包发放调用链又长又慢,但是这些 Worker 是 无状态 的,所以可以通过增加 Worker 数量,提高系统的消费处理能力。
1、怎么保证数据一致性
若红包打款失败了,前面已经告知用户抢到红包,但是却木有发,那用户肯定会很愤怒。但是根据 CAP 原理,我们通常只需做到数据最终一致性。
我们在打款流程里面做了重试机制,生成一个全局唯一的外部订单号,当某红包打款失败,就会放回任务队列重试,当然重试时要处理好幂等。
2、怎么保证Worker不异常结束
Worker 的实现如下:
$maxTask = 1000;
$sleepTime = 1000;
while (true) {
while ($red = RedLogic::getTask()) {
RedLogic::doTask($red);
//处理多少个任务主动退出
$maxTask--;
if ($maxTask < 0) {
return EXIT_CODE_NORMAL;
}
}
//等待任务
usleep($sleepTime);
}
这里使用 LPOP 命令获取任务,所以使用了 while 结构,并且无任务时需要等待,可以用阻塞命令 BLPOP 来改进。
由于 Worker 需要常驻内存运行,难免会出现异常结束的情况(也有主动 Exit), 所以需要保持 Worker 一直处于运行状态。我们使用进程管理工具 Supervisor 来监控和管理 Worker 任务,当任务队列出现堆积时,增加 Worker 数量即可。Supervisor 的监控后台如下:
保障方案
资源CDN缓存
由于本次活动力度较大,静态页面占流量的很大一部分,所以静态页面在发布时都会放置一份在 CDN 上,这样回源的流量就很小了。
降级措施
尽管做了很多准备,还是无法确保万无一失,我们在每个关键节点都增加了开关,一但出现异常,可以通过配置中心人工介入做降级处理。
原文来自微信公众号:后端搬运工。
原文地址:https://mp.weixin.qq.com/s/VG_Wcxte8avnXzn4bPXiGA
欢迎大家多关注!
算法之旅:理解透彻冒泡算法及它的几个优化版本
zkbhj 发表了文章 • 0 个评论 • 1557 次浏览 • 2020-05-11 15:29
冒泡排序的英文Bubble Sort,是一种最基础的交换排序。
大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。
而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。
增强版1
对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
鸡尾酒排序增强版
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
地精排序
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;
if(array == NULL) {
return FALSE;
}
while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}
return TRUE;
}
参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
查看全部
冒泡排序的英文Bubble Sort,是一种最基础的交换排序。
大家一定都喝过汽水,汽水中常常有许多小小的气泡,哗啦哗啦飘到上面来。这是因为组成小气泡的二氧化碳比水要轻,所以小气泡可以一点一点向上浮动。
而我们的冒泡排序之所以叫做冒泡排序,正是因为这种排序算法的每一个元素都可以像小气泡一样,根据自身大小,一点一点向着数组的一侧移动。
原始的冒泡排序是稳定排序。由于该排序算法的每一轮要遍历所有元素,轮转的次数和元素数量相当,所以时间复杂度是O(N^2) 。
增强版1
对于后面已经有序的部分,不需要在进行比较了。增加isSorted标记,默认true,如果本轮存在交换,就变为false,说明下一轮可能还有排序。否则break跳出循环
这一版代码做了小小的改动,利用布尔变量isSorted作为标记。如果在本轮排序中,元素有交换,则说明数列无序;如果没有元素交换,说明数列已然有序,直接跳出大循环。
增强版2
提前预知已排好序的边界,减少排序比较次数。最后交换元素的下标记住。
这一版代码中,sortBorder就是无序数列的边界。每一轮排序过程中,sortBorder之后的元素就完全不需要比较了,肯定是有序的。
鸡尾酒排序
告别冒泡排序的单项比较移动,鸡尾酒排序是左右比较移动轮换着来的。内层循环有2个循环,一个向左,一个向右。
下面这段代码是鸡尾酒排序的原始实现。代码外层的大循环控制着所有排序回合,大循环内包含两个小循环,第一个循环从左向右比较并交换元素,第二个循环从右向左比较并交换元素。
鸡尾酒排序增强版
代码中使用了左右两个边界值,rightSortBorder 代表右边界,leftSortBorder代表左边界。
在比较和交换元素时,奇数轮从 leftSortBorder 遍历到 rightSortBorder 位置,偶数轮从 rightSortBorder 遍历到 leftSortBorder 位置。
地精排序
它也像冒泡排序一样,相邻元素之间两两进行比较,如果这两个元素逆序,则交换。与冒泡排序不同的是,它如果遇到交换操作时,变为向前冒泡,直至不发生交换操作位置。相当于做了一个插入操作,将比较小的数插入到前面的有序序列中合适的位置。所以,地精排序可以说是冒泡排序和直接插入排序的综合。
BOOL GnomeSort(datatype *array, int size)
{
int i = 0;
if(array == NULL) {
return FALSE;
}
while(i < size) {
//如果i=0或者i-1与i正序时,i++
if(i == 0 || array[i-1] <= array[i]) {
i++;
} else {
//如果i-1与i逆序时,i--
Swap(array + i-1, array + i);
i--;
}
}
return TRUE;
}
参考文档:
https://mp.weixin.qq.com/s/wO11PDZSM5pQ0DfbQjKRQA
https://mp.weixin.qq.com/s/tXqjWWyjQ1ILfvnFv3_f7Q
https://blog.csdn.net/u010647471/article/details/49976345
算法之旅:如何评价算法好坏的神器之时间复杂度
zkbhj 发表了文章 • 0 个评论 • 1302 次浏览 • 2020-05-07 14:22
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。
O(1)< O(logn)< O(n)< O(n^2)
参考文档:
https://mp.weixin.qq.com/s?src=11×tamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
查看全部
在计算机科学中,时间复杂性,又称时间复杂度,算法的时间复杂度是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。
若存在函数 f(n),使得当n趋近于无穷大时,T(n)/ f(n)的极限值为不等于零的常数,则称 f(n)是T(n)的同数量级函数。
记作 T(n)= O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
渐进时间复杂度用大写O来表示,所以也被称为大O表示法。
O(1)< O(logn)< O(n)< O(n^2)
参考文档:
https://mp.weixin.qq.com/s?src=11×tamp=1588832012&ver=2323&signature=37Md0F80eUGKg9BeRAXTAeHawoHpJxHPzwvPguG0Ow0y5e7oK1IQ5C*36ApecKiCEkT98Vi6hPH2KoVqeHQ6ZSVvuFWp0MEzvDb*Wg657Fcvg9ToEOTDltnC39r*5*I9&new=1
https://mp.weixin.qq.com/s?__biz=MzU1MDE4MzUxNA==&mid=2247483867&idx=1&sn=6270b56b79cb74334eb4faf80de05f0a&chksm=fba536eeccd2bff8e38566b3c12b439666fca9ec7ffa2a6c0d2271550702a3dc0851bd99d0cf&scene=21#wechat_redirect
搜索相似度算法探究之MMR
zkbhj 发表了文章 • 0 个评论 • 5298 次浏览 • 2020-02-21 18:06
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。
MMR的主要思路是:
• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it
在MMR的公式是这样的:
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1Diversified Ranking
d1计算剩余文档与 {d1} 的相似度和对应的多样性分数
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档Diversified Ranking
d1
d5
d3
d6
d2Repeat until all documents in the initial ranking are added to the diversified ranking
所以就有了最后的排名 {d1, d5, d3, d6, d2}
MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158 查看全部
今天同事分享了相似度算法中最简单的算法:MMR。接下来就仔细研究学习下。
MMR的全称为Maximal Marginal Relevance ,中文名字为最大边界相关法或者最大边缘相关。算法目的是减少排序结果的冗余,同时保证结果的相关性。最早应用于文本摘要提取和信息检索等领域。在推荐场景下体现在,给用户推荐相关商品的同时,保证推荐结果的多样性,即排序结果存在着相关性与多样性的权衡。
MMR的主要思路是:
• Use the query to retrieve a ranking R of documents
• Use MMR to rerank the top N documents (build a new ranking S)
– Select the 1st document based on how well it satisfies the query
– Select subsequent documents based on two criteria
» How well it satisfies the query
» How different it is from documents ranked above it
在MMR的公式是这样的:
R: The initial ranking
S: Documents already selected for the diverse ranking
– Documents ranked above this position
Sim(di, dj): Similarity metric
– E.g., vector space model or Jensen-Shannon Divergence
λ : 权重系数,调节推荐结果相关性与多样性。λ越大,推荐结果越相关; λ越小,推荐结果多样性越高。
举个例子,假设λ=0.6λ=0.6,初始排名及其相关性分数如下:
Initial Ranking
d1, 0.80
d2, 0.78
d3, 0.76
d4, 0.74
d5, 0.72
d6, 0.70
第一步,选择与 query 最相关的文档 d1,并从 R 中移除 d1
Diversified Ranking计算剩余文档与 {d1} 的相似度和对应的多样性分数
d1
选择分数最高的文档作为多样性排名的第 2 篇文档,并从 R 中移除该文档
Diversified Ranking分别计算剩余文档与已排序文档 {d1, d5} 的相似度,选相似度最大的值,计算 MMR 分数
d1
d5
选择分数最高的文档作为多样性排名的第 3 篇文档,并从 R 中移除该文档
Diversified Ranking分别计算剩余文档与已排序文档 {d1, d5, d3} 的相似度,选相似度最大的值,计算 MMR 分数
d1
d5
d3
选择分数最高的文档作为多样性排名的第 4 篇文档,并从 R 中移除该文档
Diversified Ranking分别计算剩余文档与已排序文档 d1, d5, d3, d6 的相似度,选相似度最大的值,计算 MMR 分数
d1
d5
d3
d6
选择分数最高的文档作为多样性排名的第 5 篇文档,并从 R 中移除该文档
Diversified RankingRepeat until all documents in the initial ranking are added to the diversified ranking
d1
d5
d3
d6
d2
所以就有了最后的排名 {d1, d5, d3, d6, d2}
MMR 也会用于其它的任务如文本摘要,因为它是符合摘要的基本要求的,即相关性和多样性的权衡。摘要结果与原文的相关性越高,摘要就接近全文中心意思,而多样性则使摘要内容更加的全面。直观和简单是这种方法最大的优点。
参考文档:
http://www.shuang0420.com/2016/12/07/Search%20Engines%E7%AC%94%E8%AE%B0%20-%20Diversity/
文档相似性分数计算:
https://blog.csdn.net/yixianfe ... 17158
设计模式之策略者模式(组合模式)
zkbhj 发表了文章 • 0 个评论 • 2362 次浏览 • 2019-08-29 11:20
前期设计及思路
根据情景的设计,首先我们想到这是一些列的鸭子,便会想到利用继承的手段,进行解决。其UML图型为:
后续设计:需要让有的鸭子飞,有的鸭子不能飞。
后续设计
问题:
1、在调用中是通过抽象类进行操作的,所以新功能在超类有所体现,
但是下载超类中实现,就所有的鸭子会飞。
2、在超类中是飞的行为是抽象函数,这样每个子类都要实现,代码重写太复杂。
3、用接口,只让飞的鸭子继承实现飞的行为接口,这样在超类中进行初始化接口。
4、但是用接口后,让飞的行为进行修改,那个每个子类中飞的行为也要修改,这样改动也是很大。
经过分析,利用组合的原则,将变化部分进行提取,封装一个新类,所以我们见fly这个行为提取出来,行为上肯定是接口,同时这个接口由行为类实现,而不是具体鸭子类实现,这样就实现策略模式。
这里的接口就是所谓的概念,针对“利用接口编程”,关键在于多态。利用多态,程序可以对超类进行操作,根据实际情况执行到真正行为,将行为和对象进行解耦。
在程序运行时就是针对超类编程,超类编程就是接口和抽象类。
图为:
所以这样针对新行为,我们重新定义个接口,然后实现这个接口,在调用时初始化接口。
其中主要的代码为:
//关键这是超类,必定是抽象类
public abstract class Duck
{
protected IFlyBehavior flyBehavior;
protected QuackBehavior quackBehavior;
public virtual void Quack()
{
throw new System.NotImplementedException();
}
//当然这些行为也可通过接口,但是这游泳鸭子都会,所以超类直接实现
public virtual void Swim()
{
throw new System.NotImplementedException();
}
//抽象函数,子类必须实现,意味子类这个行为不同
public abstract void DisPlay();
public virtual void performFly()
{
//通过接口执行fly行为,要寻找接口在那初始化
flyBehavior.fly();
}
}
//duck的子类,其中初始化了接口
public class BlueDuck : Duck
{
public BlueDuck()
{
//初始化接口,在用BlueDuck初始化Duck时,接口也被初始化了。
flyBehavior = new FlyWithWings();
}
public override void DisPlay()
{
throw new System.NotImplementedException();
}
}当你将两个类结合起来使用时,如同本例,这就是组合。这种做法的不同是在于行为不是继承而来,单独通过行为类和接口进行实现。
策略模式定义了算法族,分别封装起来,让他们之间可以相互替换,使算法的变化独立于使用算法的客户。
原文地址:https://www.cnblogs.com/polly333/p/4705682.html 查看全部
前期设计及思路
根据情景的设计,首先我们想到这是一些列的鸭子,便会想到利用继承的手段,进行解决。其UML图型为:
后续设计:需要让有的鸭子飞,有的鸭子不能飞。
后续设计
问题:
1、在调用中是通过抽象类进行操作的,所以新功能在超类有所体现,
但是下载超类中实现,就所有的鸭子会飞。
2、在超类中是飞的行为是抽象函数,这样每个子类都要实现,代码重写太复杂。
3、用接口,只让飞的鸭子继承实现飞的行为接口,这样在超类中进行初始化接口。
4、但是用接口后,让飞的行为进行修改,那个每个子类中飞的行为也要修改,这样改动也是很大。
经过分析,利用组合的原则,将变化部分进行提取,封装一个新类,所以我们见fly这个行为提取出来,行为上肯定是接口,同时这个接口由行为类实现,而不是具体鸭子类实现,这样就实现策略模式。
这里的接口就是所谓的概念,针对“利用接口编程”,关键在于多态。利用多态,程序可以对超类进行操作,根据实际情况执行到真正行为,将行为和对象进行解耦。
在程序运行时就是针对超类编程,超类编程就是接口和抽象类。
图为:
所以这样针对新行为,我们重新定义个接口,然后实现这个接口,在调用时初始化接口。
其中主要的代码为:
//关键这是超类,必定是抽象类当你将两个类结合起来使用时,如同本例,这就是组合。这种做法的不同是在于行为不是继承而来,单独通过行为类和接口进行实现。
public abstract class Duck
{
protected IFlyBehavior flyBehavior;
protected QuackBehavior quackBehavior;
public virtual void Quack()
{
throw new System.NotImplementedException();
}
//当然这些行为也可通过接口,但是这游泳鸭子都会,所以超类直接实现
public virtual void Swim()
{
throw new System.NotImplementedException();
}
//抽象函数,子类必须实现,意味子类这个行为不同
public abstract void DisPlay();
public virtual void performFly()
{
//通过接口执行fly行为,要寻找接口在那初始化
flyBehavior.fly();
}
}
//duck的子类,其中初始化了接口
public class BlueDuck : Duck
{
public BlueDuck()
{
//初始化接口,在用BlueDuck初始化Duck时,接口也被初始化了。
flyBehavior = new FlyWithWings();
}
public override void DisPlay()
{
throw new System.NotImplementedException();
}
}
策略模式定义了算法族,分别封装起来,让他们之间可以相互替换,使算法的变化独立于使用算法的客户。
原文地址:https://www.cnblogs.com/polly333/p/4705682.html
服务保障经验谈之服务熔断
zkbhj 发表了文章 • 0 个评论 • 1680 次浏览 • 2018-12-18 10:56
熔断这一概念来源于电子工程中的断路器(Circuit Breaker)。在互联网系统中,当下游服务因访问压力过大而响应变慢或失败,上游服务为了保护系统整体的可用性,可以暂时切断对下游服务的调用。
这种牺牲局部,保全整体的措施就叫做熔断。
如果不采取熔断措施,我们的系统会怎样呢?我们来看一个栗子。
当前系统中有A,B,C三个服务,服务A是上游,服务B是中游,服务C是下游。它们的调用链如下:
一旦下游服务C因某些原因变得不可用,积压了大量请求,服务B的请求线程也随之阻塞。线程资源逐渐耗尽,使得服务B也变得不可用。紧接着,服务A也变为不可用,整个调用链路被拖垮。
像这种调用链路的连锁故障,叫做雪崩。
正所谓刮骨疗毒,壮士断腕。在这种时候,就需要我们的熔断机制来挽救整个系统。熔断机制的大体流程和刚才所讲的考试策略如出一辙:
这里需要解释两点:
1.开启熔断
在固定时间窗口内,接口调用超时比率达到一个阈值,会开启熔断。进入熔断状态后,后续对该服务接口的调用不再经过网络,直接执行本地的默认方法,达到服务降级的效果。
2.熔断回复
熔断不可能是永久的。当经过了规定时间之后,服务将从熔断状态回复过来,再次接受调用方的远程调用。
更多服务降级熔断限流,参考:https://www.cnblogs.com/raosha ... .html 查看全部
熔断这一概念来源于电子工程中的断路器(Circuit Breaker)。在互联网系统中,当下游服务因访问压力过大而响应变慢或失败,上游服务为了保护系统整体的可用性,可以暂时切断对下游服务的调用。
这种牺牲局部,保全整体的措施就叫做熔断。
如果不采取熔断措施,我们的系统会怎样呢?我们来看一个栗子。
当前系统中有A,B,C三个服务,服务A是上游,服务B是中游,服务C是下游。它们的调用链如下:
一旦下游服务C因某些原因变得不可用,积压了大量请求,服务B的请求线程也随之阻塞。线程资源逐渐耗尽,使得服务B也变得不可用。紧接着,服务A也变为不可用,整个调用链路被拖垮。
像这种调用链路的连锁故障,叫做雪崩。
正所谓刮骨疗毒,壮士断腕。在这种时候,就需要我们的熔断机制来挽救整个系统。熔断机制的大体流程和刚才所讲的考试策略如出一辙:
这里需要解释两点:
1.开启熔断
在固定时间窗口内,接口调用超时比率达到一个阈值,会开启熔断。进入熔断状态后,后续对该服务接口的调用不再经过网络,直接执行本地的默认方法,达到服务降级的效果。
2.熔断回复
熔断不可能是永久的。当经过了规定时间之后,服务将从熔断状态回复过来,再次接受调用方的远程调用。
更多服务降级熔断限流,参考:https://www.cnblogs.com/raosha ... .html
类设计的六大基本原则
zkbhj 发表了文章 • 0 个评论 • 1748 次浏览 • 2018-11-12 20:12
Single Responsibility Principle, 简称SRP。
定义:There should never be more than one reason for a class to change.
应该有且仅有一个原因引起类的变更。
二.里氏替换原则
Liskov Substitution Principle, 简称LSP。
定义:Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.
(所有引用基类的地方必须能透明地使用其子类的对象)
三.依赖倒置原则
Dependence Inversion Principle, 简称DIP
定义:High level modules should not depend upon low level modules.Both should depend upon abstractions.Abstractions should not depend upon details.Details should depend upon abstractions.
翻译过来,包含三层含义:
1.高层模块不应该依赖低层模块,两者都应该依赖其抽象。2.抽象不应该依赖细节。3.细节应该依赖抽象。
精简的定义: 面向接口编程。
四.接口隔离原则:
接口--这里指用interface关键字定义的接口。
定义:
1.Clients should not be forced to depend upon interfaces that they don't use.(客户端不应该依赖它不需要的接口)
2.The dependency of one class to anther one should depend on the smallest possible interface.(类间的依赖关系应该建立在最小的接口上)
概括:建立单一接口,不要建立臃肿庞大的接口。通俗来讲:接口尽量细化,同时接口中的方法尽量少。
五.迪米特法则
Law of Demeter, LOD。又称最少知识原则(Least Knowledge Principle, LKP)。
通俗来讲:一个类应该对自己需要耦合或调用的类知道得最少,你(被耦合或调用的类)的内部是如何复杂都和我没有关系,那是你的事情,我就调用你提供的public方法,其他一概不关心。
六.开闭原则
Software entities like classes, modules and functions should be open for extension but closed for modifications.(一个软件实体如类、模块和函数应该对扩展开放,对修改关闭) 查看全部
Single Responsibility Principle, 简称SRP。
定义:There should never be more than one reason for a class to change.
应该有且仅有一个原因引起类的变更。
二.里氏替换原则
Liskov Substitution Principle, 简称LSP。
定义:Functions that use pointers or references to base classes must be able to use objects of derived classes without knowing it.
(所有引用基类的地方必须能透明地使用其子类的对象)
三.依赖倒置原则
Dependence Inversion Principle, 简称DIP
定义:High level modules should not depend upon low level modules.Both should depend upon abstractions.Abstractions should not depend upon details.Details should depend upon abstractions.
翻译过来,包含三层含义:
1.高层模块不应该依赖低层模块,两者都应该依赖其抽象。2.抽象不应该依赖细节。3.细节应该依赖抽象。
精简的定义: 面向接口编程。
四.接口隔离原则:
接口--这里指用interface关键字定义的接口。
定义:
1.Clients should not be forced to depend upon interfaces that they don't use.(客户端不应该依赖它不需要的接口)
2.The dependency of one class to anther one should depend on the smallest possible interface.(类间的依赖关系应该建立在最小的接口上)
概括:建立单一接口,不要建立臃肿庞大的接口。通俗来讲:接口尽量细化,同时接口中的方法尽量少。
五.迪米特法则
Law of Demeter, LOD。又称最少知识原则(Least Knowledge Principle, LKP)。
通俗来讲:一个类应该对自己需要耦合或调用的类知道得最少,你(被耦合或调用的类)的内部是如何复杂都和我没有关系,那是你的事情,我就调用你提供的public方法,其他一概不关心。
六.开闭原则
Software entities like classes, modules and functions should be open for extension but closed for modifications.(一个软件实体如类、模块和函数应该对扩展开放,对修改关闭)
#原创#API接口设计要考虑的几个重要原则和方法总结
zkbhj 发表了文章 • 0 个评论 • 8305 次浏览 • 2018-11-12 11:04
【规范和最佳实践】
1.合理的接口命名;
接口的命名必须规范优雅,在未看到接口文档时,就可以根据接口的URL明白接口的功能是什么?
如下面的例子://好的接口命名示例
/customer/cert/search.json
//不好的接口命名示例
/customer/info/get.json
2.入参和出参的规范化定义,有统一的风格;
一个项目内的所有接口,必须有统一的风格,统一返回格式,约定业务层错误编码,每个编码可以携带明确的错误信息。出入参字段含义明确,采用统一的命名规范,如驼峰命名等。返回格式统一采用json格式。举一个例子:{
"status": "failure",
"error_code": 100003,
"error_message": "未获取到用户信息",
"data":
}status标识接口是否逻辑处理成功;error_code为不同类型错误信息对应的唯一错误码,error_message为错误信息的简要描述信息(注意某些数据或者信息是否可直接展示给用户),data则为需要返回给调用方的数据信息。
另外,每个参数一定要有明确且固定的数据格式,int就是int,string就是string,array就是array,object就是object,因为对于一些对数据类型要求比较严格的使用方,不明确的数据格式返回,可能会造成不可预知的错误。
下面给大家列一下Json里的六种基本数据格式:
Number:整数或浮点数
String:字符串
Boolean:true 或 false
Array:数组包含在方括号中
Object:对象包含在大括号{}中
Null:空类型
3.接口的功能定义要具备单一性;
单一性是指接口要做的事情应该是一个比较单一的事情,比如登陆接口,登陆完成应该只是返回登陆成功以后一些用户信息如uid即可,但很多人为了减少接口交互,返回一大堆额外的数据。
但有时候对于一些内部系统接口来讲,为了实现通用性,可能会提供一些通用的查询接口,即在同一个接口内返回尽可能多的信息,但也不建议这么做,至少不是一个好的实践;
4.明确接口支持的协议;
接口要明确所支持的协议,是POST/GET/PUT/DELETE等的哪一个。一般来讲,同一个接口而言,尽量只支持一种协议,并且在接口被调用时,如果参数传递非接口定义协议,要明确提示返回错误信息,这样可以减少很多类似于“为啥我调接口参数都对还调不通”的问题的沟通成本。同时,严格的协议规范也可以避免一些意料之外的问题出现。例如:您请求的资源不支持 http 方法“POST
5.是否支持幂等;
这是作为一个接口而言,很需要明确的一点,尤其是在一些特殊的应用场景下,是否支持幂等是需要首先明确的。比如下面这个例子:
发放卡券的接口:/coupon/card/handOut.json POST
这是一个卡券系统里发放租金卡的接口,支持POST协议传参。由于很多种原因,同一类卡券被某个人领取时,都可能会产生接口被调用不支持一次的情形,比如网络抖动、用户快速点击、甚至是恶意刷接口等,我们希望,对于“同一个调用”,我们给用户返回的结果应该是一致的,这就是幂等。实现幂等的方式有几种,比如卡券系统就是通过生成订单号的形式完成的接口幂等;
6、充分考虑接口的可扩展性,避免做大而全的接口;
要根据实际业务场景定义接口,充分考虑接口的可扩展性。比如自如的APP首页数据接口,我们可以设计成整个首页就一个大接口,但是假如这样,未来再次改版APP,我们可能就需要完全重新写这个接口,但假如我们按模块区分接口,可能我们仅需要开发新增加的模块的接口,对于以前有的,在数据结构不调整只做样式改变的需求里,就可以减少工作量的开发。
另外这么做还有一个优点,尤其对移动端作用尤为突出,由于移动端对带宽有限,所以,接口中尽量不要返回无用的信息,只返回真正需要的数据,进而减少由于过多的数据量影响处理速度,最重要的是影响传输效率。
7、接口里尽量不做客户端可以处理的逻辑,减少服务端压力;
接口主要是提供给客户端数据的,对于能够在客端完成的逻辑处理,尽量由客端来处理(当然APP比较特殊,如果改动这部分逻辑需要发版,还是需要放在后端),进而减轻后端服务器的压力,让后端接口更加“专心”做好数据服务;
8、清晰的日志分类、记录以及归档规范;
接口日志很重要,无论对于追溯问题还是解决bug,都有着举足轻重的作用。所以,好的日志规范,是一个很好的习惯。日志主要有info和error两种(warning一般不做记录,或者很少用到),info日志一般用于记录现场,用来追溯问题;error日志一般用于协作我们查找bug,定位代码问题。
另外日志也需要定期做归档处理,防止机器磁盘被日志文件大量占用。
更高级的,可以接入一些日志搜集和分析工具,如ELK等,将日志信息持久化存储以及可视化展示,更加方便的对日志信息进行使用。
9、版本控制:
这一点,对于接口来讲,非常重要。在实际的场景中,维护多个版本是非常常见的事情,在系统的迭代升级过程中,无可避免的会增减返回参数及入参,修改返回数据的结构,甚至会废弃原有接口改为新的数据接口。所以,为了不影响老版本应用的正常使用,大部分应用后台都会针对性的维护多个接口版本。
一般来讲,有2中常用的方式:
1.每个接口有各自的版本,一般为接口添加个version的参数。
2.整个接口系统有统一的版本,一般在URL中添加版本号,比如 http://api.zkbhj.com/v2。
【性能和高可用】
1、接口的平均响应时长、支持的并发数、TPS;
这个很重要,无论是我们自己设计的接口,还是我们在使用第三方提供的接口时,我们都需要明确接口的平均响应时长,因为这直接关系到你系统的安全性问题!如果在接口调用时,没有设置合理的超时时间甚至都没有设置超时时间,那么一旦所以依赖的接口出现问题甚至服务不可用时,对你调用方系统来讲,将是致命的,雪崩式的系统崩溃,很大一部分就是由于这个原因造成的。所以为了不害人害己,设计以及最终提供的接口,一定要提供一个明确的接口平均响应时长,而且要在接口文档中写明并强烈建议接口调用方设置合理的超时时间,防止由于接口超时而造成雪崩式的连锁反应。
2、数据库和缓存的选择;
为了提高接口性能,合理的选择数据库和缓存很是总要。一般情况下,关系型存储我们一般都会选择MySQL数据库,缓存一般都选择Redis。当然,MySQL数据库的分库分表,加索引用事务、读写分离等,redis作为缓存使用时的缓存时长、缓存数据类型等,都有他们的使用原则和最佳实践,这里不做赘述。我们这里只讨论在何种场景下要使用缓存。比如查询类型的接口,如果要查询的数据并不是实时性要求很高的接口,那我们可以进行缓存处理,比如APP首页接口,一般都是CMS里面配置的一些图文信息,我们有必要做缓存处理。当然可能里面有一部分数据是需要实时的,比如自如寓的管家信息,那我们可以把这一部分内容做实时的处理。
3、限流、熔断和降级;
对于一些特殊的应用场景,比如抢红包、秒杀等,要对接口进行限流处理,方式短时间内的高并发请求将接口搞死;
接口熔断和降级,是为了解决系统不被拖死,不影响核心业务流程而采取的措施,比如获取用户信息列表,实时获取用户头像和昵称的接口暂时不可用(比如根据设置,10个请求里6个以上都超时,则判定为服务不可用,触发熔断机制),我们可以主动放弃调用(熔断),只返回核心数据uid等,昵称和头像暂时返回默认数据(降级);
4、消除单点,负载均衡;
对于任何一个接口服务,我们至少要有2台机器对外提供服务,禁止单点服务,单点一旦出问题,会直接造成服务不可用;
对于访问量很大的API服务,为了提供更加快速的接口响应,我们往往不是单台机器提供服务,而是有多台机器组成一个分布式集群对外提供服务。这个时候就会涉及到负载均衡,比如我们就会由nginx来做负载均衡,根据一定的策略机制,将接口请求平均的分发到不同的应用机器上进行处理和响应。进而提高接口的性能。
5、是否有第三方服务接口?
如果接口依赖了第三方服务接口,能用缓存就用缓存。这样可以进一步降低由于第三方接口不稳定给我们自己系统造成的波动。当然,也有一些第三方接口无法做缓存,比如就是要实时进行身份验证等,这个时候,超时时间的设置就尤为重要!
6、能异步处理的异步处理:
其实有很多场景下,一个接口里面的很多逻辑是可以异步处理的。举个例子:
比如用户注册场景,用户注册成功之后会给客户的邮箱发送一封激活邮件。常规的逻辑流程应该是,前段提交用户信息到注册接口,注册接口做各种校验,校验通过后,发送邮件,发送成功后,返回给前端告诉用户注册成功,请进入邮箱激活账号。其实,这个流程里的“发送邮件”就是可以拿出来异步处理的部分,当校验通过而且注册完成之后,我们把发送邮件这件事抛出去,交给另外一个就负责发邮件的任务进行处理(如我们现在有的补偿队列,或者是发一个MQ消息),然后直接返回给用户注册成功。这样,注册接口的平均响应时间一定会比第一种方案提高很多。
7、更高要求的高可用,可以采用异地机房部署;
在物理地域上就分开部署,两地同时崩溃的概率还是比较低的;
8、监控和报警;
在对接口建立高效的监控和报警机制,能够及时发现问题并通知到相应的人员进行第一时间的处理和跟进。
【稳定和安全】
1、身份验证;
在一些接口场景中,是要依赖于用户身份的,比如通过token还实现用户身份的验证;
2、接口防抓取和串改数据;
防止数据被轻易抓取到,我们可以采用https作为接口的网络传输协议,进而保证数据包不被轻易的就抓取和分析。即使这种情况下,依然被抓取到,我们还可以对传输的数据进行我们自己的加密处理,比如用对称加密算法AES或者非对称加密算法RSA,亦或是我们系统内部自己商定好的加密算法,对数据进行加密处理,这样,即使抓取到数据包,也很难分析出数据的原始信息。
对于防止数据被串改,可以使用sign验签,进一步防止接口参数被串改的可能性。
3、防刷;
接口防刷会有一些策略,根据实际的应用场景进行选择,比如增加图形验证码、接入智能验证码、时间戳限制单位时间内的调用次数、ip限制等;
另外监控很重要,及时发现异常的调用,进行封禁处理;
【其他】
1、是否需要支持跨域;
这一点是针对于H5提供接口时需要考虑的,因为一般情况下,实际的应用和接口所在的域并不是同一个域,基于浏览器的安全策略,对于XHR请求来讲,是不允许进行跨域请求的,所以,一般提供给H5的接口要支持跨域请求。当然解决跨域的方法也不在本次讨论的范围之内,目前主流的方式就是在服务器配置的header头信息中增加两项参数。
2、基于H5提供接口的一些安全性问题;
比如常见的CSRF攻击,我们可以在接口里验证 HTTP Referer字段、x-requested-with字段、header中增加token等,从一定程度上提高被CSRF攻击的门槛。
3、在代码结构层面,尽量和其他部分分开;
API集中由同一个系统“模块”提供,尽量不要和页面等其他功能混合开发。例如下面的项目分层模式就是一个较好的实践方案:
即所有API接口均分布在api内部,不与pc(PC站页面)、mobile(M站页面)等混合在一起。
4、文档:
好的接口,还有一项优点,就是会有为之配套的接口文档。如果希望降低接口文档的维护成本等,也可以使用开源的第三方自动化接口文档工具,比如swagger等。 查看全部
【规范和最佳实践】
1.合理的接口命名;
接口的命名必须规范优雅,在未看到接口文档时,就可以根据接口的URL明白接口的功能是什么?
如下面的例子:
//好的接口命名示例
/customer/cert/search.json
//不好的接口命名示例
/customer/info/get.json
2.入参和出参的规范化定义,有统一的风格;
一个项目内的所有接口,必须有统一的风格,统一返回格式,约定业务层错误编码,每个编码可以携带明确的错误信息。出入参字段含义明确,采用统一的命名规范,如驼峰命名等。返回格式统一采用json格式。举一个例子:
{status标识接口是否逻辑处理成功;error_code为不同类型错误信息对应的唯一错误码,error_message为错误信息的简要描述信息(注意某些数据或者信息是否可直接展示给用户),data则为需要返回给调用方的数据信息。
"status": "failure",
"error_code": 100003,
"error_message": "未获取到用户信息",
"data":
}
另外,每个参数一定要有明确且固定的数据格式,int就是int,string就是string,array就是array,object就是object,因为对于一些对数据类型要求比较严格的使用方,不明确的数据格式返回,可能会造成不可预知的错误。
下面给大家列一下Json里的六种基本数据格式:
Number:整数或浮点数
String:字符串
Boolean:true 或 false
Array:数组包含在方括号中
Object:对象包含在大括号{}中
Null:空类型
3.接口的功能定义要具备单一性;
单一性是指接口要做的事情应该是一个比较单一的事情,比如登陆接口,登陆完成应该只是返回登陆成功以后一些用户信息如uid即可,但很多人为了减少接口交互,返回一大堆额外的数据。
但有时候对于一些内部系统接口来讲,为了实现通用性,可能会提供一些通用的查询接口,即在同一个接口内返回尽可能多的信息,但也不建议这么做,至少不是一个好的实践;
4.明确接口支持的协议;
接口要明确所支持的协议,是POST/GET/PUT/DELETE等的哪一个。一般来讲,同一个接口而言,尽量只支持一种协议,并且在接口被调用时,如果参数传递非接口定义协议,要明确提示返回错误信息,这样可以减少很多类似于“为啥我调接口参数都对还调不通”的问题的沟通成本。同时,严格的协议规范也可以避免一些意料之外的问题出现。例如:
您请求的资源不支持 http 方法“POST
5.是否支持幂等;
这是作为一个接口而言,很需要明确的一点,尤其是在一些特殊的应用场景下,是否支持幂等是需要首先明确的。比如下面这个例子:
发放卡券的接口:/coupon/card/handOut.json POST
这是一个卡券系统里发放租金卡的接口,支持POST协议传参。由于很多种原因,同一类卡券被某个人领取时,都可能会产生接口被调用不支持一次的情形,比如网络抖动、用户快速点击、甚至是恶意刷接口等,我们希望,对于“同一个调用”,我们给用户返回的结果应该是一致的,这就是幂等。实现幂等的方式有几种,比如卡券系统就是通过生成订单号的形式完成的接口幂等;
6、充分考虑接口的可扩展性,避免做大而全的接口;
要根据实际业务场景定义接口,充分考虑接口的可扩展性。比如自如的APP首页数据接口,我们可以设计成整个首页就一个大接口,但是假如这样,未来再次改版APP,我们可能就需要完全重新写这个接口,但假如我们按模块区分接口,可能我们仅需要开发新增加的模块的接口,对于以前有的,在数据结构不调整只做样式改变的需求里,就可以减少工作量的开发。
另外这么做还有一个优点,尤其对移动端作用尤为突出,由于移动端对带宽有限,所以,接口中尽量不要返回无用的信息,只返回真正需要的数据,进而减少由于过多的数据量影响处理速度,最重要的是影响传输效率。
7、接口里尽量不做客户端可以处理的逻辑,减少服务端压力;
接口主要是提供给客户端数据的,对于能够在客端完成的逻辑处理,尽量由客端来处理(当然APP比较特殊,如果改动这部分逻辑需要发版,还是需要放在后端),进而减轻后端服务器的压力,让后端接口更加“专心”做好数据服务;
8、清晰的日志分类、记录以及归档规范;
接口日志很重要,无论对于追溯问题还是解决bug,都有着举足轻重的作用。所以,好的日志规范,是一个很好的习惯。日志主要有info和error两种(warning一般不做记录,或者很少用到),info日志一般用于记录现场,用来追溯问题;error日志一般用于协作我们查找bug,定位代码问题。
另外日志也需要定期做归档处理,防止机器磁盘被日志文件大量占用。
更高级的,可以接入一些日志搜集和分析工具,如ELK等,将日志信息持久化存储以及可视化展示,更加方便的对日志信息进行使用。
9、版本控制:
这一点,对于接口来讲,非常重要。在实际的场景中,维护多个版本是非常常见的事情,在系统的迭代升级过程中,无可避免的会增减返回参数及入参,修改返回数据的结构,甚至会废弃原有接口改为新的数据接口。所以,为了不影响老版本应用的正常使用,大部分应用后台都会针对性的维护多个接口版本。
一般来讲,有2中常用的方式:
1.每个接口有各自的版本,一般为接口添加个version的参数。
2.整个接口系统有统一的版本,一般在URL中添加版本号,比如 http://api.zkbhj.com/v2。
【性能和高可用】
1、接口的平均响应时长、支持的并发数、TPS;
这个很重要,无论是我们自己设计的接口,还是我们在使用第三方提供的接口时,我们都需要明确接口的平均响应时长,因为这直接关系到你系统的安全性问题!如果在接口调用时,没有设置合理的超时时间甚至都没有设置超时时间,那么一旦所以依赖的接口出现问题甚至服务不可用时,对你调用方系统来讲,将是致命的,雪崩式的系统崩溃,很大一部分就是由于这个原因造成的。所以为了不害人害己,设计以及最终提供的接口,一定要提供一个明确的接口平均响应时长,而且要在接口文档中写明并强烈建议接口调用方设置合理的超时时间,防止由于接口超时而造成雪崩式的连锁反应。
2、数据库和缓存的选择;
为了提高接口性能,合理的选择数据库和缓存很是总要。一般情况下,关系型存储我们一般都会选择MySQL数据库,缓存一般都选择Redis。当然,MySQL数据库的分库分表,加索引用事务、读写分离等,redis作为缓存使用时的缓存时长、缓存数据类型等,都有他们的使用原则和最佳实践,这里不做赘述。我们这里只讨论在何种场景下要使用缓存。比如查询类型的接口,如果要查询的数据并不是实时性要求很高的接口,那我们可以进行缓存处理,比如APP首页接口,一般都是CMS里面配置的一些图文信息,我们有必要做缓存处理。当然可能里面有一部分数据是需要实时的,比如自如寓的管家信息,那我们可以把这一部分内容做实时的处理。
3、限流、熔断和降级;
对于一些特殊的应用场景,比如抢红包、秒杀等,要对接口进行限流处理,方式短时间内的高并发请求将接口搞死;
接口熔断和降级,是为了解决系统不被拖死,不影响核心业务流程而采取的措施,比如获取用户信息列表,实时获取用户头像和昵称的接口暂时不可用(比如根据设置,10个请求里6个以上都超时,则判定为服务不可用,触发熔断机制),我们可以主动放弃调用(熔断),只返回核心数据uid等,昵称和头像暂时返回默认数据(降级);
4、消除单点,负载均衡;
对于任何一个接口服务,我们至少要有2台机器对外提供服务,禁止单点服务,单点一旦出问题,会直接造成服务不可用;
对于访问量很大的API服务,为了提供更加快速的接口响应,我们往往不是单台机器提供服务,而是有多台机器组成一个分布式集群对外提供服务。这个时候就会涉及到负载均衡,比如我们就会由nginx来做负载均衡,根据一定的策略机制,将接口请求平均的分发到不同的应用机器上进行处理和响应。进而提高接口的性能。
5、是否有第三方服务接口?
如果接口依赖了第三方服务接口,能用缓存就用缓存。这样可以进一步降低由于第三方接口不稳定给我们自己系统造成的波动。当然,也有一些第三方接口无法做缓存,比如就是要实时进行身份验证等,这个时候,超时时间的设置就尤为重要!
6、能异步处理的异步处理:
其实有很多场景下,一个接口里面的很多逻辑是可以异步处理的。举个例子:
比如用户注册场景,用户注册成功之后会给客户的邮箱发送一封激活邮件。常规的逻辑流程应该是,前段提交用户信息到注册接口,注册接口做各种校验,校验通过后,发送邮件,发送成功后,返回给前端告诉用户注册成功,请进入邮箱激活账号。其实,这个流程里的“发送邮件”就是可以拿出来异步处理的部分,当校验通过而且注册完成之后,我们把发送邮件这件事抛出去,交给另外一个就负责发邮件的任务进行处理(如我们现在有的补偿队列,或者是发一个MQ消息),然后直接返回给用户注册成功。这样,注册接口的平均响应时间一定会比第一种方案提高很多。
7、更高要求的高可用,可以采用异地机房部署;
在物理地域上就分开部署,两地同时崩溃的概率还是比较低的;
8、监控和报警;
在对接口建立高效的监控和报警机制,能够及时发现问题并通知到相应的人员进行第一时间的处理和跟进。
【稳定和安全】
1、身份验证;
在一些接口场景中,是要依赖于用户身份的,比如通过token还实现用户身份的验证;
2、接口防抓取和串改数据;
防止数据被轻易抓取到,我们可以采用https作为接口的网络传输协议,进而保证数据包不被轻易的就抓取和分析。即使这种情况下,依然被抓取到,我们还可以对传输的数据进行我们自己的加密处理,比如用对称加密算法AES或者非对称加密算法RSA,亦或是我们系统内部自己商定好的加密算法,对数据进行加密处理,这样,即使抓取到数据包,也很难分析出数据的原始信息。
对于防止数据被串改,可以使用sign验签,进一步防止接口参数被串改的可能性。
3、防刷;
接口防刷会有一些策略,根据实际的应用场景进行选择,比如增加图形验证码、接入智能验证码、时间戳限制单位时间内的调用次数、ip限制等;
另外监控很重要,及时发现异常的调用,进行封禁处理;
【其他】
1、是否需要支持跨域;
这一点是针对于H5提供接口时需要考虑的,因为一般情况下,实际的应用和接口所在的域并不是同一个域,基于浏览器的安全策略,对于XHR请求来讲,是不允许进行跨域请求的,所以,一般提供给H5的接口要支持跨域请求。当然解决跨域的方法也不在本次讨论的范围之内,目前主流的方式就是在服务器配置的header头信息中增加两项参数。
2、基于H5提供接口的一些安全性问题;
比如常见的CSRF攻击,我们可以在接口里验证 HTTP Referer字段、x-requested-with字段、header中增加token等,从一定程度上提高被CSRF攻击的门槛。
3、在代码结构层面,尽量和其他部分分开;
API集中由同一个系统“模块”提供,尽量不要和页面等其他功能混合开发。例如下面的项目分层模式就是一个较好的实践方案:
即所有API接口均分布在api内部,不与pc(PC站页面)、mobile(M站页面)等混合在一起。
4、文档:
好的接口,还有一项优点,就是会有为之配套的接口文档。如果希望降低接口文档的维护成本等,也可以使用开源的第三方自动化接口文档工具,比如swagger等。
海量数据相似度计算算法:simhash和海明距离
zkbhj 发表了文章 • 0 个评论 • 1691 次浏览 • 2018-09-12 16:04
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;
long t1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}
long t2 = System.currentTimeMillis();
System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");耗费时间: 4266 ms
大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。
为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。
2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。
3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。
4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。
5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。
整个过程图为:
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。
通过simhash计算结果为:
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过 hashcode计算为:
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101
大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。
现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。
为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。
未完待续:
1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?
2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?
查看全部
String s1 = "你妈妈喊你回家吃饭哦,回家罗回家罗" ;耗费时间: 4266 ms
String s2 = "你妈妈叫你回家吃饭啦,回家罗回家罗" ;
long t1 = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
int dis = StringUtils .getLevenshteinDistance(s1, s2);
}
long t2 = System.currentTimeMillis();
System. out .println(" 耗费时间: " + (t2 - t1) + " ms ");
大跌眼镜,居然计算耗费4秒。假设我们一天需要比较100w次,光是比较100w次的数据是否重复就需要4s,就算4s一个文档,单线程一分钟才处理15个文档,一个小时才900个,一天也才21600个文档,这个数字和一天100w相差甚远,需要多少机器和资源才能解决。
为此我们需要一种应对于海量数据场景的去重方案,经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西,据说这玩意可以把文档降维到hash数字,数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash,他们每天需要处理的文档在亿级别,大大超过了我们现在文档的水平。既然老大哥也有类似的应用,我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的,参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理,为了便于理解尽量不使用数学公式,分为这几步:
1、分词,把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重,我们假设权重分为5个级别(1~5)。比如:“ 美国“51区”雇员称内部有9架飞碟,曾看见灰色外星人 ” ==> 分词后为 “ 美国(4) 51区(5) 雇员(3) 称(1) 内部(2) 有(1) 9架(3) 飞碟(5) 曾(1) 看见(3) 灰色(4) 外星人(5)”,括号里是代表单词在整个句子里重要程度,数字越大越重要。
2、hash,通过hash算法把每个词变成hash值,比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字,还记得文章开头说过的吗,要把文章变为数字计算才能提高相似度计算性能,现在是降维过程进行时。
3、加权,通过 2步骤的hash生成结果,需要按照单词的权重形成加权数字串,比如“美国”的hash值为“100101”,通过加权计算为“4 -4 -4 4 -4 4”;“51区”的hash值为“101011”,通过加权计算为 “ 5 -5 5 -5 5 5”。
4、合并,把上面各个单词算出来的序列值累加,变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”,“51区”的 “ 5 -5 5 -5 5 5”, 把每一位进行累加, “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的,真实计算需要把所有单词的序列串累加。
5、降维,把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。最后算出结果为:“1 0 1 0 1 1”。
整个过程图为:
大家可能会有疑问,经过这么多步骤搞这么麻烦,不就是为了得到个 0 1 字符串吗?我直接把这个文本作为字符串输入,用hash函数生成 0 1 值更简单。其实不是这样的,传统hash函数解决的是生成唯一值,比如 md5、hashmap等。md5是用于生成唯一签名串,只要稍微多加一个字符md5的两个数字看起来相差甚远;hashmap也是用于键值对查找,便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算,要比较的是两个文章是否相识,当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了,我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的,而传统的hashcode却不行。我们可以来做个测试,两个相差只有一个字符的文本串,“你妈妈喊你回家吃饭哦,回家罗回家罗” 和 “你妈妈叫你回家吃饭啦,回家罗回家罗”。
通过simhash计算结果为:
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过 hashcode计算为:
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101
大家可以看得出来,相似的文本只有部分 01 串变化了,而普通的hashcode却不能做到,这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明,“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。
现在通过这样的转换,我们把库里的文本都转换为simhash 代码,并转换为long类型存储,空间大大减少。现在我们虽然解决了空间,但是如何计算两个simhash的相似度呢?难道是比较两个simhash的01有多少个不同吗?对的,其实也就是这样,我们通过海明距离(Hamming distance)就可以计算出两个simhash到底相似不相似。两个simhash对应二进制(01串)取值不同的数量称为这两个simhash的海明距离。举例如下: 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同,则海明距离为3。对于二进制字符串的a和b,海明距离为等于在a XOR b运算结果中1的个数(普遍算法)。
为了高效比较,我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code,然后和内存里的simhash code 进行比较,测试100w次计算在100ms。速度大大提升。
未完待续:
1、目前速度提升了但是数据是不断增量的,如果未来数据发展到一个小时100w,按现在一次100ms,一个线程处理一秒钟 10次,一分钟 60 * 10 次,一个小时 60*10 *60 次 = 36000次,一天 60*10*60*24 = 864000次。 我们目标是一天100w次,通过增加两个线程就可以完成。但是如果要一个小时100w次呢?则需要增加30个线程和相应的硬件资源保证速度能够达到,这样成本也上去了。能否有更好的办法,提高我们比较的效率?
2、通过大量测试,simhash用于比较大文本,比如500字以上效果都还蛮好,距离小于3的基本都是相似,误判率也比较低。但是如果我们处理的是微博信息,最多也就140个字,使用simhash的效果并不那么理想。看如下图,在距离为3时是一个比较折中的点,在距离为10时效果已经很差了,不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3,短文本大量重复信息不会被过滤,如果使用距离为10,长文本的错误率也非常高,如何解决?
Grpc应用场景分析
zkbhj 发表了文章 • 0 个评论 • 12278 次浏览 • 2018-03-27 10:57
gRPC 基于 HTTP/2 标准设计,带来诸如双向流、流控、头部压缩、单 TCP 连接上的多复用请求等特性。这些特性使得其在移动设备上表现更好,更省电和节省空间占用(相比当前传统的http1.1+json)。
gRPC是由Google主导开发的RPC框架,使用HTTP/2协议并用ProtoBuf作为序列化工具。其客户端提供Objective-C、Java接口,服务器侧则有Java、Golang、C++等接口,从而为移动端(iOS/Androi)到服务器端通讯提供了一种解决方案。 当然在当下的环境下,这种解决方案更热门的方式是RESTFull API接口。该方式需要自己去选择编码方式、服务器架构、自己搭建框架(JSON-RPC)。gRPC官方对REST的声音是:和REST一样遵循HTTP协议(明确的说是HTTP/2),但是gRPC提供了全双工流和传统的REST不同的是gRPC使用了静态路径,从而提高性能用一些格式化的错误码代替了HTTP的状态码更好的标示错误。
至于是否要选择用gRPC。对于已经有一套方案的团队,可以参考下。如果是从头来做,可以考虑下gRPC提供的从客户端到服务器的整套解决方案,这样不用客户端去实现http的请求会话,JSON等的解析,服务器端也有现成的框架用。
grpc主要使用场景:
低延时、高可用的分布式系统;移动端与云服务端的通讯;使用protobuf,独立于语言的协议,支持多语言之间的通讯;可以分层扩展,如:身份验证,负载均衡,日志记录,监控等。
在微服务场景中使用究竟是否要使用grpc呢?开源社区较为成熟的微服务框架有dubbo、spring cloud。dubbo虽然在服务治理上做的比较完善,但是不支持跨语言。个人觉得,如果不考虑跨语言问题,选用dubbo。考虑跨语言,可以选用grpc、Thrift,但是grpc、Thrift没有服务发现和负载均衡机制,一般使用代理转发负载均衡控制策略。
在移动端app应用场景中,grpc以其优异的性能,因pb和http2的特性,为移动端用户节省流量、电量。对比传统的http1.1+json方式,建议可以先尝试小范围使用grpc,待系统稳定后,再扩大grpc使用范围。
查看全部
gRPC 基于 HTTP/2 标准设计,带来诸如双向流、流控、头部压缩、单 TCP 连接上的多复用请求等特性。这些特性使得其在移动设备上表现更好,更省电和节省空间占用(相比当前传统的http1.1+json)。
gRPC是由Google主导开发的RPC框架,使用HTTP/2协议并用ProtoBuf作为序列化工具。其客户端提供Objective-C、Java接口,服务器侧则有Java、Golang、C++等接口,从而为移动端(iOS/Androi)到服务器端通讯提供了一种解决方案。 当然在当下的环境下,这种解决方案更热门的方式是RESTFull API接口。该方式需要自己去选择编码方式、服务器架构、自己搭建框架(JSON-RPC)。gRPC官方对REST的声音是:和REST一样遵循HTTP协议(明确的说是HTTP/2),但是gRPC提供了全双工流和传统的REST不同的是gRPC使用了静态路径,从而提高性能用一些格式化的错误码代替了HTTP的状态码更好的标示错误。
至于是否要选择用gRPC。对于已经有一套方案的团队,可以参考下。如果是从头来做,可以考虑下gRPC提供的从客户端到服务器的整套解决方案,这样不用客户端去实现http的请求会话,JSON等的解析,服务器端也有现成的框架用。
grpc主要使用场景:
- 低延时、高可用的分布式系统;
- 移动端与云服务端的通讯;
- 使用protobuf,独立于语言的协议,支持多语言之间的通讯;
- 可以分层扩展,如:身份验证,负载均衡,日志记录,监控等。
在微服务场景中使用究竟是否要使用grpc呢?开源社区较为成熟的微服务框架有dubbo、spring cloud。dubbo虽然在服务治理上做的比较完善,但是不支持跨语言。个人觉得,如果不考虑跨语言问题,选用dubbo。考虑跨语言,可以选用grpc、Thrift,但是grpc、Thrift没有服务发现和负载均衡机制,一般使用代理转发负载均衡控制策略。
在移动端app应用场景中,grpc以其优异的性能,因pb和http2的特性,为移动端用户节省流量、电量。对比传统的http1.1+json方式,建议可以先尝试小范围使用grpc,待系统稳定后,再扩大grpc使用范围。