Is there any reason why you need human-readable unique keys? Why not pack the key as a binary string using pack() while you're at it?

You haven't explained how big this DB is? I guess that it is possible although VERY unlikely that this DB is small enough to be memory resident.

If we just think about storing just the 20M SHA-1 signatures, each is 20 bytes. For the hardware, powers of 2 are magic and it goes: 2,4,8,16,32. In a practical sense, each signature will take 32 bytes: 8 32 bit(4 byte) words or 16 16 bit(2 byte) words. That is a fair amount of memory for 20M records (like 640MB) and these "keys", (they are SHA-1 signatures) aren't even unique! I don't know what your plan is to deal with that. Oh, of course besides the memory to store the SHA-1 signatures, there has to be some data that points to something (on disk or wherever). That will take some bytes too!

You need a Database. Perl DBI in its many flavors can easily handle 20M records. Forget SHA-1 or SHA-2 that makes no sense. Let the DB use its hash algorithm.

Thank everyone for the reply

Let me explain more about my project. I have 20M email listing (saved in MySQL) which we want to track in our campaigns. So instead of using original emails on the related URLs, we want to use IDs. 20-byte hexadecimal is good enough for uniqueness of 20M emails. While I am trying to find better options, i.e., if we can use shorter ID, we can significantly reduce the table size and there are more benefit from doing so...

For testing purpose, I used 3M emails and 8-byte ID and Digest::SHA1 and Convert::zBase32 to build the IDs

sub setid_1
{
    return undef if not $_[0];
    return substr( sha1_hex(_secret_code() . $_[0]), 0, 8 );
}

sub setid_2
{
    return undef if not $_[0];
    return substr( encode_zbase32(sha1_hex(_secret_code() . $_[0])), 0
+, 8 )
}
[download]

I was hoping the second one could at least give me better uniqueness. but the result is: I got 773 duplicated IDs from setid_1 and 676131 duplicated IDs from setid_2.

Any better way to handle such issue?

thanks again

lihao

Well, 32 signed bits gives about 2,000M possibilities (2GB).
If you use all 32 bits, you get 2x as much.
Obviously you can have the DB generate those numbers.

It sounds like what you want to is encode some long string into something a LOT shorter representation that doesn't have to be unique.
This is a hash function.

There are all sorts of hash functions, but since we are programming in Perl, my initial thought would be: how does Perl do this?

This is the Perl hash function written in C:

int i = klen;
unsigned int hash = 0;
char *s = key;
while (i--)
  hash = hash * 33 + *s++;
[download]

klen is the number of characters to be encoded. 
12345678901234567890123456789012345678901234567
the string above has 47 chars and would be klen
for example.
[download]

Internally Perl chops down the number of bits to get a practical index number by: index= hash & xhv_max. In your case, forget it - don't worry about what xhv_max is, use all the bits! (well maybe you should consider implications of the sign bit)

If 32 bits isn't enough, then 64 bits is gonna do it, that's 8 bytes. Don't mess with 48 bits or something like that. Powers of 2 are magic on most machines commonly in use, eg: 2,4,8,16,32,64,128.

In summary, forget about SHA-1 or SHA-2 or any other form of encryption, use an efficient hash encoding technique. I would try a 32 or 64 bit version of what Perl itself does!

Update:The Perl hash algorithm works very well based upon my subjective empirical judgment with just 120K hash key structures. Anyway, I am confident that 20 bytes aren't necessary and that 8 bytes will yield the "uniqueness" that you need. That would allow the keys to be resident in memory. But, I think that the idea of using a DB is even better as it scales gracefully to HUGE structures.

I need to setup an ID (not sequential numbers, need randomness) for each of these unique records.

Why not have the DB give you the randomness you need? If you give each record a sequential (autoincrement) record number--which guarentees uniqueness--and then have an auxillary table which maps that recno to a random 'tag' of say 6 characters: A-Z.

That would give you 300 million unique 6-char tags which should be sufficient to be going on with. And with a properly indexed table, the lookup should be very quick with any DB worth its disk space. If you ever need to expand further you can add a-z to double that; or move to seven chars which would cater for 8 billion.

The toughest part of this suggestion is generating the recno/tag mapping. Or rather, shuffling the tags once you've generated them which Perl makes easy. Shuffling a 300e6 element array is a memory intensive process even if you use an in-place shuffle. A possible solution to this is to break the problem into 2 parts.

Shuffling two small sets of 3-char stems & suffixes is trivial, and combining them at output time means you require minimal memory (~16MB), and it is very fast. It takes about a minute to produce 20e6 or roughly an hour if you wanted the full 300e6:

#! perl -slw
use strict;
use List::Util qw[ shuffle ];


our $N ||= 20e6;

my @tagStems = shuffle 'AAA' .. 'ZZZ';

my $serial = 0;
while( my $stem = pop @tagStems ) {
    for my $suffix ( shuffle 'AAA' .. 'ZZZ' ) {
        printf "%07d\t%s\n", ++$serial, $stem . $suffix;
        exit if $serial > $N;
    };
}


__END__
C:\test>786833
0000001 HBDKCE
0000002 HBDBWB
0000003 HBDRRX
0000004 HBDUJF
0000005 HBDFRH
0000006 HBDMFO
0000007 HBDAEO
0000008 HBDEYC
0000009 HBDCCZ
0000010 HBDXPK
...
0017572 HBDIWS
0017573 HBDQFL
0017574 HBDHYU
0017575 HBDUUL
0017576 HBDCGM
0017577 ZPSQVM
0017578 ZPSOUH
0017579 ZPSPJV
0017580 ZPSGAS
...
[download]

Whilst not truly random--there are some possible sequences that cannot be generated--it is sufficiently random (ie. unguessable) for many purposes.

If you needed to move to 8 billion/7-char tags, using a 4-3 or 5-2 split works equally well.

eval '(exit $?0)' && eval 'exec perl -w -S $0 ${1+"$@"}'
                  && eval 'exec perl -w -S $0 $argv:q'
                  if 0;

# The above invocation finds perl in the path, wherever it may be

use strict;
use warnings;
use Math::BigInt;

# encode/decode ID numbers

our $DECODE_OPT = q/-d/;
our $ENCODE_OPT = q/-e/;

sub usage
{
    warn "@_\n\n";
    warn "usage: $0 [$DECODE_OPT|$ENCODE_OPT] arg arg...\n\n";
    warn "\t-e\tencode an ID number into binary/octal/hex/decimal\n";
    warn "\t-d\tdecode a binary/octal/hex/decimal into the equivalent 
+text ID number\n\n";
    warn "Notes:\n";
    warn "\tvalues must be prefixed with by:\n";
    warn "\t\tbinary   0b (\"zero bee\") (or 0B)\n";
    warn "\t\toctal    0 (\"zero\")\n";
    warn "\t\thex      0x (\"zero ex\") (or 0X)\n";
    warn "\nExample: to encode N12345, use this command:\n";
    warn "\t$0 $ENCODE_OPT N12345\n";
    warn "\n";
    die;
}

usage( "Error: No arguments supplied..." ) unless (@ARGV);
usage( "Error: No encode/decode command used..." ) unless ($ARGV[0] =~
+ /^($ENCODE_OPT|$DECODE_OPT)$/i);
my $opt = $1;
shift @ARGV;
usage( "Error: Not enough arguments supplied..." ) unless (@ARGV);

# use Math::BigInt for arbitrary precision math (32bit integers too sm
+all)
our $ZERO = new Math::BigInt +0;

our %encode;
@encode{" ","A".."Z","a".."z","0".."9"} = (0,1..26,1..26,27..36);
our %decode;
@decode{0..36} = (" ","A".."Z",0..9);
our $base = $ZERO + scalar keys %decode;

sub encode
{
    my $x = shift;
    my @x = split '', $x;
    my $r = $ZERO;
    for my $c ( @x )
    {
        $r = $r * 37 + $encode{$c};
    }
    return $r;
}

sub decode
{
    my $x = shift;
    return "invalid decode" if $x =~ /[a-z]/i;
    my $r = '';
    while ( $x )
    {
        my $LSD = $x % $base; # least significant digit
        $r = $decode{$LSD} . $r; #prepend
        $x = ($x - $LSD)/$base;
    }
    return $r;
}

for (@ARGV)
{
    if ( $opt =~ /^$ENCODE_OPT$/i )
    {
        # encode
        my $e = $ZERO + encode($_);
        printf "Text:    %s\nBinary:  %s\nOctal:   %s\nHex:     %s\nDe
+cimal: %s\n\n", $_, $e->as_bin(), $e->as_oct(), $e->as_hex(), $e;
    }
    else
    {
        # decode
        printf "Input: %s\nText:  %s\n\n", $_, decode($_ + $ZERO);
    }
}

exit;
[download]