V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
cdffh
V2EX  ›  PHP

php 如何实现尽可能短的唯一 id

  •  1
     
  •   cdffh · 2014-10-10 10:45:45 +08:00 · 15033 次点击
    这是一个创建于 3698 天前的主题,其中的信息可能已经有所发展或是发生改变。
    目前的实现方法为
    md5(uniqid ( time (), true )) 生成出来有32位.因为要做到二维码里面,所以希望尽可能短,系统的数据量不会超过10亿(9位). 问下大家有没有什么比较好的方法.
    第 1 条附言  ·  2014-10-10 14:42:48 +08:00
    感谢各位的指点
    鄙人受益匪浅
    如果我用md5对数据的内容做hash然后选出其中11位数字 不足补0 作为唯一id
    二维码里面使用base62 压缩
    那么新的问题来了.
    这样的id会不会碰撞
    40 条回复    2015-12-20 09:00:09 +08:00
    tabris17
        1
    tabris17  
       2014-10-10 10:54:38 +08:00
    一个32位整数自增字段,如果要对自增数据保密,可以用skip32算法加密
    tabris17
        2
    tabris17  
       2014-10-10 10:56:25 +08:00
    整数再用base64编码
    cdffh
        3
    cdffh  
    OP
       2014-10-10 10:56:52 +08:00
    @tabris17 自增不合适.因为有多个数据库需要合并的需求 .
    cdffh
        4
    cdffh  
    OP
       2014-10-10 10:58:44 +08:00
    @tabris17 而且我希望唯一id尽可能短.最好12位能够解决.
    tabris17
        5
    tabris17  
       2014-10-10 10:58:45 +08:00
    自增跟数据库没有必然,你不一定要用数据库的自增字段哪
    tabris17
        6
    tabris17  
       2014-10-10 11:00:52 +08:00
    我的意思是把32位整数的二进制数据用base64编码,也就是用64进制表示一个整数,6个字符就够了
    cdffh
        7
    cdffh  
    OP
       2014-10-10 11:01:18 +08:00
    @tabris17 有道理.如果我有两张表存储数据(一个是服务器上的mysql,一个是嵌入式终端里面的sqllite),现在需要合并了. 如何才能保证两边生成的自增id不重复呢? 而且以后可能是多个服务器 多个嵌入式终端 随时都会有同步数据的需求.
    qiayue
        8
    qiayue  
       2014-10-10 11:01:53 +08:00
    http://www.zhihu.com/question/19798317/answer/13604187
    “它的字符集包括所有128个字符,可容纳多达1850个字符或2710个数字或1108个字节,或500多个汉字”

    所以没必要尽可能短吧
    cdffh
        9
    cdffh  
    OP
       2014-10-10 11:04:25 +08:00
    @qiayue 抱歉 题目没说清楚,因为我们想把二维码做的比较小,所以当数据量大了的时候二维码就会变的比较大,而且经过测试,二维码数据量越小扫描和纠错就相对容易.
    qiayue
        10
    qiayue  
       2014-10-10 11:06:21 +08:00
    32 位降到 12 位,也就是省 20 而已啊,省不了多少
    换句话说,32 位不长
    icyflash
        11
    icyflash  
       2014-10-10 11:08:53 +08:00
    1楼 +1

    不算特殊符号,26个字母大小写再加10个数字,总共62个字符。按你的数据量,最短5位,可以参照短网址生成的算法,取6位,再做个KEY-VALUE表。

    说话做到二维码里面跟尽量短有什么联系么。。
    icyflash
        12
    icyflash  
       2014-10-10 11:10:29 +08:00
    好吧,回复后忘了点回复,回过头来回复后发现LZ已经解释了
    tabris17
        13
    tabris17  
       2014-10-10 11:13:00 +08:00
    @cdffh 我不知道你这两套数据库的系统是否是独立的,如果不是独立的,可以使用共享的全局自增整数生成器服务。如果是相互独立的两套系统,可以让一个系统的ID由低往高自增,一个系统的ID由高往低自减。如果是多套独立系统,可以把自增的步进设为系统数目,比如三个系统,系统1是:1、4、7、10……;系统2是:2、5、8、11……;系统3是:3、6、9、12……
    tabris17
        14
    tabris17  
       2014-10-10 11:16:11 +08:00   ❤️ 1
    @cdffh 如果系统数目一开始不确定,可以把每个系统32位整型的自增ID的最高几位设置成系统编号(反正你说9亿数据就够了,32位整数的最高几位也用不到)
    cdffh
        15
    cdffh  
    OP
       2014-10-10 11:19:56 +08:00
    @qiayue
    @icyflash
    统一回复下吧 因为需要把id做到二维码里面进行打印 .如果是32位的长度为了保证能够扫描,打印的二维码大小最佳尺寸为180mm*180mm 如果是12位 就可以做的比较小.可以做到100mm*100mm. 因为考虑到打印出来的二维码的应用环境是需要保存5年,而且尺寸不宜过大.,所以我希望在二维码的信息尽可能少.这也就是需要把唯一id尽可能做短的原因.
    feiyuanqiu
        16
    feiyuanqiu  
       2014-10-10 11:21:32 +08:00   ❤️ 1
    用大小写字母 (52) + 数字 (10) = 62

    >>> 62*62*62*62*62
    916132832

    只需要5位就能获取到9亿的排列
    kisshere
        17
    kisshere  
       2014-10-10 11:26:08 +08:00 via Android
    很久以前在一个博客上看到过,uniqid后面加一个random,random取四位吧,如果还撞上了,别去开发二维码,买彩票吧
    cdffh
        18
    cdffh  
    OP
       2014-10-10 11:26:54 +08:00
    @feiyuanqiu 这是理论值 有没有一个方法能保证生成的id不碰撞呢?
    cdffh
        19
    cdffh  
    OP
       2014-10-10 11:27:54 +08:00
    @kisshere 这个方案考虑过 被否了 因为公司有撞上过的前辈.
    royzheng
        20
    royzheng  
       2014-10-10 11:28:06 +08:00
    如果你考虑多套系统数据库无法共享用到统一的中央ID数据库的话,那么你就只能应用尽可能多的字符来生成随机减少重复率
    理论上说吧 52个字母(大小写区分)+10个数字 = 62个
    62^12=3.2262668e+21
    很长一段时间够用了 等真不够用很多东西要改了。。。不用想着一步到位一下子能容纳上亿什么的
    feiyuanqiu
        21
    feiyuanqiu  
       2014-10-10 11:31:10 +08:00
    @cdffh
    你想太多了,你可以把原数据保存在数据表里面,获取到每个数据的自增主键。
    然后把这个自增主键转换成62进制,也就是这种大小写字母的格式就ok了。完全不需要hash什么的
    akfish
        22
    akfish  
       2014-10-10 11:37:03 +08:00
    碰撞问题并不难解决,用不重复的伪随机序列就行了,只要seed一样,生成随机id的顺序就是一样的。

    分布式也没问题,把id地址空间分割成不重合的区间,分配给各个节点,每个节点在各自的区间里顺序取出id。
    duzhe0
        23
    duzhe0  
       2014-10-10 11:38:18 +08:00
    如果用纯随机数来做id, 一般认为uuid(128位)是安全的。
    如果希望id短,可以牺牲一点扩展时的便利性,用机器id+自增id组合成id。
    jarlyyn
        24
    jarlyyn  
       2014-10-10 11:41:53 +08:00   ❤️ 1
    看了半天感觉就是实现个uuid
    按uuid的思路,可以采用自增啊。
    被个设备有独立编号就可以了。
    比如14位数字,前4位是设备号,后10位是自增数值。
    然后base64压一下
    ysjdx
        25
    ysjdx  
       2014-10-10 11:45:21 +08:00
    整数遍历群模算法(貌似不是这么翻译的)

    https://www.usenix.org/system/files/conference/woot14/woot14-adrian.pdf
    看看随机生成ip的那个群模算法

    可以随机不重复遍历某个整数区间。用这个随机不重复的id序列,应该可以解决问题?
    feiyuanqiu
        26
    feiyuanqiu  
       2014-10-10 12:09:34 +08:00   ❤️ 1
    又想了下,真是不觉得有必要上那么高大上的算法,如果数据在单表,直接下面这个代码就行了,如果是多表,给每个表一个单独标识加最前面就行

    <?php
    $i = 1000;
    while ($i--) {
    var_dump(_uniqId());
    }
    exit;
    function _uniqId()
    {
    static $now = 100000000;
    return _10262($now++);
    }

    function _10262($n)
    {
    $b = array(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, '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');
    $cn = $b[$n % 62];
    if (($nn = floor($n / 62)) > 0) {
    $cn .= _10262($nn);
    }
    return strrev($cn);
    }
    alex321
        27
    alex321  
       2014-10-10 12:14:41 +08:00
    请参考短网址生成原理
    cevincheung
        28
    cevincheung  
       2014-10-10 12:26:44 +08:00   ❤️ 1
    二维码需要打印出来,所以必然是预先生成好的一堆数据然后才能打印。那就不怕重复了,任何一种方案在生成过程中不断的检测是否已经存在重复的ID就好啊。

    比如最简单的随机数字, rand(100000000,999999999)。while(true) redis->has。难道你每天都生成一大堆?- -# 考虑一下实际应用场景。还有就是mysql的uuid [ select uuid() ]和[ select uuid_short() ]保证不重复 ....
    wingoo
        29
    wingoo  
       2014-10-10 12:53:02 +08:00
    内部依旧int,外部用base62,把62个字符随机打乱下
    keefo
        30
    keefo  
       2014-10-10 14:08:18 +08:00   ❤️ 1
    首先,我觉得这个问题工程解法应重于理论解法。

    推荐一个简单方法
    unix_timestamp 10位 加上2位随机的字符[0-9a-z][0-9a-z]

    大概意味着一秒钟内系统要生成超过1296条数据才肯定会有重复。如果你们系统负载量有这么大,可以在timestamp后面加上3位系统毫秒时间。

    如果多套系统数据需要合并,最好在合并前给id加上一个domain prefix
    例如 server1 server2
    s1_timestamp_[0-9a-z][0-9a-z]
    s2_timestamp_[0-9a-z][0-9a-z]

    这样可以区分,也不会冲突,需要调用数据时候代码remove掉prefix。

    无论多好的uuid算法,鲁莽的合并2个数据都不是正确做法。
    keefo
        31
    keefo  
       2014-10-10 14:11:47 +08:00
    没用[0-9a-zA-Z][0-9a-zA-Z]是因为我记得mysql默认是大小写不敏感的。如果你们数据库设置的是大小写敏感用[0-9a-zA-Z][0-9a-zA-Z]就更好了。组合数变成了3844
    msg7086
        32
    msg7086  
       2014-10-10 14:59:21 +08:00
    合并两个数据库的话,id越长越不容易撞,越短越容易撞呗。

    最简单的做法,id后面加一位来表示数据库编号。
    0x142857
        33
    0x142857  
       2014-10-10 15:00:51 +08:00
    rtrim(base64_encode(md5(microtime())),"=")
    jerray
        34
    jerray  
       2014-10-10 16:03:56 +08:00   ❤️ 2
    Zuckonit
        35
    Zuckonit  
       2014-10-10 18:49:09 +08:00
    uuid4
    c742435
        36
    c742435  
       2014-10-10 21:52:25 +08:00   ❤️ 1
    自增,n个库每个分配一个唯一id 1-n
    然后每次自增增量为n
    nigelvon
        37
    nigelvon  
       2014-10-10 22:33:45 +08:00 via Android   ❤️ 1
    自增能保证唯一且短,否则碰撞只是概率问题。至于自增涉及到不同的库,这有很多办法解决。
    Actrace
        38
    Actrace  
       2014-10-11 09:08:00 +08:00   ❤️ 1
    把自增ID进行进制转换,这是以前的惯用手段.
    在数据量不高的情况下,这个ID会短得让你非常满意.
    如果是发邀请码这种应用就更适合这种场景了.
    NCE
        39
    NCE  
       2014-10-11 17:34:55 +08:00
    base64(guid)
    qhxin
        40
    qhxin  
       2015-12-20 09:00:09 +08:00   ❤️ 1
    你说的很有道理。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1004 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 19:03 · PVG 03:03 · LAX 11:03 · JFK 14:03
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.