generating 9 digit ids without database sequence

Question

I'd like to create 9-digit numeric ids that are unique across machines. I'm currently using a database sequence for this, but am wondering if it could be done without one. The sequences will be used for X12 EDI transactions, so they don't have to be unique forever. Maybe even only unique for 24 hours.

My only idea:

1. Each server has a 2 digit server identifier.
2. Each server maintains a file that essentially keeps track of a local sequence.
3. id = + <7 digit sequence which wraps>

My biggest problem with this is what to do if the hard-drive fails. I wouldn't know where it left off.

All of my other ideas essentially end up re-creating a centralized database sequence.

Any thoughts?

Answer 1

If HD fails you can just set new and unused 2 digit server identifier and be sure that the number is unique (for 24 hours at least)

Answer 2

The Following

{XX}{dd}{HHmm}{N}

Where {XX} is the machine number {dd} is the day of the month {HHmm} current time (24hr) and {N} a sequential number.

A hd crash will take more than a minute so starting at 0 again is not a problem.

You can also replace {dd} with {ss} for seconds, depending on requirements. Uniqueness period vs. requests per minute.

Answer 3

How about generating GUIDs (ensures uniqueness) and then using some sort of hash function to turn the GUID into a 9-digit number?
Just off the top of my head...

Answer 4

Use a variation on:

md5(uniqid(rand(), true));

Just a thought.

Answer 5

In my recent project I also come across this requirement, to generate N digit long sequence number without any database.

This is actually a good Interview question, because there are consideration on performance and software crash recovery. Further Reading if interested.

The following code has these features:

1. Prefix each sequence with a prefix.

2. Sequence cache like Oracle Sequence.

3. Most importantly, there is recovery logic to resume sequence from software crash.

Complete implementation attached:

import java.util.concurrent.atomic.AtomicLong;
import org.apache.commons.lang.StringUtils;

/**
 * This is a customized Sequence Generator which simulates Oracle DB Sequence Generator. However the master sequence
 * is stored locally in the file as there is no access to Oracle database. The output format is "prefix" + number.
 * <p>
 * <u><b>Sample output:</u></b><br>
 * 1. FixLengthIDSequence(null,null,15,0,99,0) will generate 15, 16, ... 99, 00<br>
 * 2. FixLengthIDSequence(null,"K",1,1,99,0) will generate K01, K02, ... K99, K01<br>
 * 3. FixLengthIDSequence(null,"SG",100,2,9999,100) will generate SG0100, SG0101, ... SG8057, (in case server crashes, the new init value will start from last cache value+1) SG8101, ... SG9999, SG0002<br>
 */
public final class FixLengthIDSequence {

    private static String FNAME;
    private static String PREFIX;
    private static AtomicLong SEQ_ID;
    private static long MINVALUE;
    private static long MAXVALUE;
    private static long CACHEVALUE;

    // some internal working values.
    private int iMaxLength; // max numeric length excluding prefix, for left padding zeros.
    private long lNextSnapshot; // to keep track of when to update sequence value to file. 
    private static boolean bInit = false; // to enable ShutdownHook routine after program has properly initialized

    static {
        // Inspiration from http://stackoverflow.com/questions/22416826/sequence-generator-in-java-for-unique-id#35697336.
        Runtime.getRuntime().addShutdownHook(new Thread(() -> {
            if (bInit) { // Without this, saveToLocal may hit NullPointerException.
                saveToLocal(SEQ_ID.longValue());
            }
        }));
    }

    /**
     * This POJO style constructor should be initialized via Spring Singleton. Otherwise, rewrite this constructor into Singleton design pattern.
     * 
     * @param sFilename This is the absolute file path to store the sequence number. To reset the sequence, this file needs to be removed manually.
     * @param prefix The hard-coded identifier.
     * @param initvalue
     * @param minvalue
     * @param maxvalue
     * @param cache
     * @throws Exception
     */
    public FixLengthIDSequence(String sFilename, String prefix, long initvalue, long minvalue, long maxvalue, int cache) throws Exception {
        bInit = false;
        FNAME = (sFilename==null)?"C:\\Temp\\sequence.txt":sFilename;
        PREFIX = (prefix==null)?"":prefix;
        SEQ_ID = new AtomicLong(initvalue);
        MINVALUE = minvalue;
        MAXVALUE = maxvalue; iMaxLength = Long.toString(MAXVALUE).length();
        CACHEVALUE = (cache <= 0)?1:cache; lNextSnapshot = roundUpNumberByMultipleValue(initvalue, cache); // Internal cache is always 1, equals no cache.

        // If sequence file exists and valid, restore the saved sequence.
        java.io.File f = new java.io.File(FNAME);
        if (f.exists()) {
            String[] saSavedSequence = loadToString().split(",");
            if (saSavedSequence.length != 6) {
                throw new Exception("Local Sequence file is not valid");
            }

            PREFIX = saSavedSequence[0];
            //SEQ_ID = new AtomicLong(Long.parseLong(saSavedSequence[1])); // savedInitValue
            MINVALUE = Long.parseLong(saSavedSequence[2]);
            MAXVALUE = Long.parseLong(saSavedSequence[3]); iMaxLength = Long.toString(MAXVALUE).length();
            CACHEVALUE = Long.parseLong(saSavedSequence[4]);
            lNextSnapshot = Long.parseLong(saSavedSequence[5]);

            // For sequence number recovery
            // The rule to determine to continue using SEQ_ID or lNextSnapshot as subsequent sequence number:
            // If savedInitValue = savedSnapshot, it was saved by ShutdownHook -> use SEQ_ID.
            // Else if saveInitValue < savedSnapshot, it was saved by periodic Snapshot -> use lNextSnapshot+1.
            if (saSavedSequence[1].equals(saSavedSequence[5])) {
                long previousSEQ = Long.parseLong(saSavedSequence[1]);
                SEQ_ID = new AtomicLong(previousSEQ);
                lNextSnapshot = roundUpNumberByMultipleValue(previousSEQ,CACHEVALUE);
            } else {
                SEQ_ID = new AtomicLong(lNextSnapshot+1); // SEQ_ID starts fresh from lNextSnapshot+!.
                lNextSnapshot = roundUpNumberByMultipleValue(SEQ_ID.longValue(),CACHEVALUE);
            }
        }

        // Catch invalid values.
        if (minvalue < 0) {
            throw new Exception("MINVALUE cannot be less than 0");
        }
        if (maxvalue < 0) {
            throw new Exception("MAXVALUE cannot be less than 0");
        }
        if (minvalue >= maxvalue) {
            throw new Exception("MINVALUE cannot be greater than MAXVALUE");
        }
        if (cache >= maxvalue) {
            throw new Exception("CACHE value cannot be greater than MAXVALUE");
        }

        // Save the next Snapshot.
        saveToLocal(lNextSnapshot);
        bInit = true;
    }

    /**
     * Equivalent to Oracle Sequence nextval.
     * @return String because Next Value is usually left padded with zeros, e.g. "00001".
     */
    public String nextVal() {
        if (SEQ_ID.longValue() > MAXVALUE) {
            SEQ_ID.set(MINVALUE);
            lNextSnapshot = roundUpNumberByMultipleValue(MINVALUE,CACHEVALUE);
        }

        if (SEQ_ID.longValue() > lNextSnapshot) {
            lNextSnapshot = roundUpNumberByMultipleValue(lNextSnapshot,CACHEVALUE);
            saveToLocal(lNextSnapshot);
        }

        return PREFIX.concat(StringUtils.leftPad(Long.toString(SEQ_ID.getAndIncrement()),iMaxLength,"0"));
    }

    /**
     * Store sequence value into the local file. This routine is called either by Snapshot or ShutdownHook routines.<br>
     * If called by Snapshot, currentCount == Snapshot.<br>
     * If called by ShutdownHook, currentCount == current SEQ_ID.
     * @param currentCount - This value is inserted by either Snapshot or ShutdownHook routines.
     */
    private static void saveToLocal (long currentCount) {
        try (java.io.Writer w = new java.io.BufferedWriter(new java.io.OutputStreamWriter(new java.io.FileOutputStream(FNAME), "utf-8"))) {
            w.write(PREFIX + "," + SEQ_ID.longValue() + "," + MINVALUE + "," + MAXVALUE + "," + CACHEVALUE + "," + currentCount);
            w.flush();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    /**
     * Load the sequence file content into String.
     * @return
     */
    private String loadToString() {
        try {
            return new String(java.nio.file.Files.readAllBytes(java.nio.file.Paths.get(FNAME)));
        } catch (Exception e) {
            e.printStackTrace();
        }
        return "";
    }

    /**
     * Utility method to round up num to next multiple value. This method is used to calculate the next cache value.
     * <p>
     * (Reference: http://stackoverflow.com/questions/18407634/rounding-up-to-the-nearest-hundred)
     * <p>
     * <u><b>Sample output:</b></u>
     * <pre>
     * System.out.println(roundUpNumberByMultipleValue(9,10)); = 10
     * System.out.println(roundUpNumberByMultipleValue(10,10)); = 20
     * System.out.println(roundUpNumberByMultipleValue(19,10)); = 20
     * System.out.println(roundUpNumberByMultipleValue(100,10)); = 110
     * System.out.println(roundUpNumberByMultipleValue(109,10)); = 110
     * System.out.println(roundUpNumberByMultipleValue(110,10)); = 120
     * System.out.println(roundUpNumberByMultipleValue(119,10)); = 120
     * </pre>
     * 
     * @param num Value must be greater and equals to positive integer 1.
     * @param multiple Value must be greater and equals to positive integer 1.
     * @return
     */
    private long roundUpNumberByMultipleValue(long num, long multiple) {
        if (num<=0) num=1;
        if (multiple<=0) multiple=1;
        if (num % multiple != 0) {
            long division = (long) ((num / multiple) + 1);
            return division * multiple;
        } else {
            return num + multiple;
        }
    }

    /**
     * Main method for testing purpose.
     * @param args
     */
    public static void main(String[] args) throws Exception {
        //FixLengthIDSequence(Filename, prefix, initvalue, minvalue, maxvalue, cache)
        FixLengthIDSequence seq = new FixLengthIDSequence(null,"H",50,1,999,10);
        for (int i=0; i<12; i++) {
            System.out.println(seq.nextVal());
            Thread.sleep(1000);
            //if (i==8) { System.exit(0); }
        }
    }

}

To test the code, let the sequence run normally. You can press Ctrl+C to simulate the server crash. The next sequence number will continue from NextSnapshot+1.

Answer 6

Cold you use the first 9 digits of some other source of unique data like:

1. a random number
2. System Time
3. Uptime

Having thaught about it for two seconds, none of those are unique on there own but you could use them as seed values for hash functions as was suggested in another answer.