这是一个创建于 4470 天前的主题，其中的信息可能已经有所发展或是发生改变。
正在做一个优惠券相关的系统：
要求：生成的优惠券验证码为6位，并且唯一。
因为系统中有N个优惠券同时提供，所以这个6位不好生成唯一。
大家有什么好的想法或算法。
系统的服务并发不大，预计每天请求20W次左右。
要求：生成的优惠券验证码为6位，并且唯一。
因为系统中有N个优惠券同时提供，所以这个6位不好生成唯一。
大家有什么好的想法或算法。
系统的服务并发不大，预计每天请求20W次左右。
 |
1
stackpop 2012-08-27 18:16:30 +08:00
生成的时候做个哈希表查一下？
|
 |
2
acalarolo 2012-08-27 18:18:35 +08:00
加上MAC地址戳？
|
 |
5
dingstyle 2012-08-27 18:32:21 +08:00
uuid
|
 |
9
macdino OP @acalarolo 提供的是一个服务，应该是服务器对服务器的，而且允许通过各种手段获取，手机，短信，APP，WEB，MAIL。=====
|
|
10
acalarolo 2012-08-27 19:14:44 +08:00
@macdino 额，我不是互联网行业的，请容我钻下牛角尖哈……就多种获取手段而言，只要走TCP/IP的应该都有MAC地址吧，短信有号码，MAIL有MAIL地址，任何请求都应有唯一标示参数的吧……
……当然6位比较少，加MAC之类的不现实。可以这样操作：6^10=60466176，进程1由零开始步进分发，进程2由六百万开始步进分发，共分10个线程每个六百万，剩余466176备用……如果可以用拉丁字母的话…… |
 |
11
ming 2012-08-27 19:15:27 +08:00
加个时间相关就可以了
|
|
12
ming 2012-08-27 19:16:30 +08:00
前3位是时间相关生成的 后3位你自己看着办
|
 |
13
luin 2012-08-27 19:17:52 +08:00
|
 |
14
yuelang85 2012-08-27 19:24:02 +08:00
可以预先准备出来吗？如果这样的话，自增数字＋字母组合，先做出来，然后一个一个的发。。。。
|
|
15
acalarolo 2012-08-27 19:24:29 +08:00
额，应该是10^6=1000000个……反正我的意思是每个线程有唯一的一个池子……
|
|
16
yuelang85 2012-08-27 19:29:23 +08:00
我想起来这里一哥们出的牛逼招数，每位都随机一下。。。。
|
 |
17
reorx 2012-08-27 20:01:59 +08:00
既然要求唯一，就最好不要用“随机”的算法来生成了，那么其实只是看起来像随机数吧？
|
 |
18
gockxml 2012-08-27 20:37:32 +08:00
要想通过随机生成是不可能的，因为会有概率重复。因此正确的方法应该是映射。
所以要想办法把一个数通过各种操作变换到另一个数，而且这个过程是可逆的。这个过程可以通过各种运算变得看似随机。 举个例子，二进制a=[1,1,1]， b初始化为a[0]，即b=[1],接下来拿a[1:]的每一个元素与b的最后一个元素做异或运算，并且添加到b中，b最终为[0,1,0]，而且完全可以通过b倒推a！这里只是提供个思路，还可以通过更复杂的方法增加随机度。 附一份自己写的代码https://gist.github.com/3488007 ， 希望有所帮助。 |
 |
19
litten 2012-08-27 21:50:27 +08:00
|
 |
20
013231 2012-08-28 01:01:01 +08:00  1
很簡單的.
全部的6位正整數不過1M個, 按一個數8字節算總共不過8M字節, 完全可以全部裝入内存. 所以先生成一個長度1M的整數數組, 包含每一個6位數, 然後對這個數組洗牌. 需要數字的時候從這個數組中依次取數就行了, 用完前肯定不會有重復. http://gist.github.com/3490375 |
 |
21
ljbha007 2012-08-28 01:30:48 +08:00
可以参考mongodb的ObjectID生成方式
http://www.mongodb.org/display/DOCS/Object+IDs 比如你的例子可以前两位为服务器的ID 中间两位为服务进程的ID 最后两位为该进程的计数器的ID 每一位是36进制的（0~9A~Z） |
|
22
ljbha007 2012-08-28 01:32:41 +08:00
如果只有一个服务器或者只有一个进程的话还可以把其中一个改为当前时间戳
|
 |
23
no2x 2012-08-28 01:42:04 +08:00
6 位验证码假设用 10 个数字 + 26 个大写字母，那么就是 36 ^ 6 的容量
可以用（自动增长的 id 序 + 带微秒的UNIX时间戳）来得到这个 21E 以内的 10 位有效数字，然后转成验证码。 id 序 和 时间戳 都在变化，不会产生重复问题，而且无规律可循。 |
 |
24
qiuai 2012-08-28 08:49:19 +08:00
我记得MD5不是有16位的么?把UUID加密称16位的MD5好了.
|
 |
25
ipconfiger 2012-08-28 09:26:54 +08:00
最简单的办法就是预先生成 000000 ～ 999999 的全部组合，不过100W条而已，内存里随便存。然后只需要随机索引去取就好了，取完就remove掉，只要保证取-remove这个过程的原子性，那么取是随机的，然后不重复。
|
|
26
macdino OP @013231 @ipconfiger 这样子是最好的方法，一个队列去处理。但是我的优惠券很多很多，如果说一个优惠券占用1M，哪么N张的话，这个量也不少。。。如果用库的话，就得考虑锁的事。如果用队列，就得考虑维护队列的成本。
|
|
27
ipconfiger 2012-08-28 09:48:04 +08:00
@macdino 可以分段生成、分批发放，比如一批次生成10W个，用得差不多的时候再生成5W个放进池里待用，差不多了再来5W个，这样内存消耗的最大值不会持续递增，总体来说仍然是随机的，而且也绝不会重复
|
|
28
macdino OP |
 |
29
Numbcoder 2012-08-28 10:02:08 +08:00
自增id序列 + 时间戳 ，然后转化为36进制
|
|
31
ljbha007 2012-08-28 11:22:56 +08:00
@ipconfiger remove不但要原子性 还要保证不能和读取产生竟态条件
|
 |
36
soulhacker 2012-08-28 15:26:30 +08:00
几次想回这个但是都不知道咋回。。。楼主有些约束没有说清楚，比如：
1. 生成号码的N个「东西」到底是啥？是进程？线程？还是分布式的节点？ 2. 生成的频率和响应时间要求如何？最重要的是，需要实时生成吗？为什么？ 3. 6位只能是数字还是可以是字母？ |
|
37
macdino OP @soulhacker 可能是我有些没有说清楚；
1、我是针对不同的优惠券发放不同的优惠券码，系统中可能同时有很多优惠券在发放，最后是认码的，所以这些码是唯一的。 2、不一定实时生成。生成的频率系统设计，每秒请求5个码，响应时间小于150ms(期望值 ) 3、6位string型的，但是每一位都是数字。因为会出现012345这种码。 |
|
40
soulhacker 2012-08-29 10:11:51 +08:00
@macdino 如果没有很强的实时性、分布式考虑，最简单有效的办法是把所有号码生成好，然后使用一个乱序算法打乱次序（就是一个数据表嘛，撑死100万条记录），然后使用一个号码生成服务来把所有请求串行化（这个逻辑非常简单，可以做到单机每秒上千次请求处理没什么压力），申请一个给一个。
|
|
41
soulhacker 2012-08-29 11:18:38 +08:00
@macdino 另外关于乱序算法，准确的说叫“生成一个有限集合的随机序列”的算法，经典的是 Knuth / Fisher–Yates Shuffle，复杂度是 O(n)，具体请 Google。
如果对效率要求不高，有更简单的的算法，就是先给每个码一个 0 到 1 之间的随机实数，然后按照这个数排序，大致复杂度 O(nlogn)。 |
Select Language