Hacker News Reader

Comment by LoSboccacc | Hacker News Reader

how would you generate hole-free sequences for use cases like that of parents (invoicing)?

If it was a business requirement that you have perfectly sequential invoice numbers with no gaps, do it at the application level, not at the storage level.

Let the database do what it's great at doing: efficiently store and retrieve data.

A database is also exceptionally good at doing transactional stuff like atomically incrementing something. I'd even say: This is something that belongs in the database and not in some brittle application logic.

Generally, I agree. But in many RDBMSs, auto-increment features explicitly do not guarantee gap-less sequential ordering. If anything throws, it's easy to end up with discarded numbers, in which case you need to catch all errors, inspect the state of the sequence and/or the entity you're populating, and re-seed the sequence. At this point, I'd argue you've already left the pristine gardens of set theory and wandered into the thorny brambles of app dev.

ah! TIL:

MYSQL - https://stackoverflow.com/questions/449346/mysql-auto-increm...

POSTGRES - https://stackoverflow.com/questions/2095917/sequences-not-af...

thanks!

I don't think it is not possible to enforce perfectly sequential numbers at the application level.

This is the same problem as multiple threads trying to increment the same global variable. Unless there is mutual exclusion while the variable is being read/incremented there will be race conditions.

I think the only way to enforce mutual exclusion for applications would be at the database layer (or any other layer where there is 1 resource that is shared between each application peer).

I think by "application level" they are saying "using transactions at the application level". If you require a strict sequence of numbers then you BEGIN, READ, INSERT, COMMIT, that is really what you want so just do it explicitly. If the COMMIT fails because of a duplicate key then you start over.

Not the OP but perhaps if only accounting cared about it you could assign these IDs separately as some asynchronous single threaded process. This would only work if insert rates were low enough or the assignment of the gapless sequence only needed to be eventually concistent over some window of time (i.e. before next payroll we must have assigned gapless IDs to all the new user accounts)

You could do something like this.

Create a table with two columns:

1. auto-incrementing primary key

2. integer for the actual number you're generating, let's call it 'IDValue'

Seed the new table with a single row with IDValue set to one less than your minimum value (say 0), then use the following process to generate a new number:

1. Insert a new row into the table, with a known invalid value (e.g. -1) for IDValue (note this must not be the same as the IDValue from your initial row)

2. Get the primary key of the newly inserted row

3. Get all the rows from the table (in primary key order) with primary key < the new id. This will consist of one or more rows of prior valid values (or just the initial seed), followed by one or more rows that are either valid or invalid values (other clients may be running through this process concurrently and finishing at different times) - something like this:

Key / IDValue

61 / 1119

62 / 1120

64 / 1121

65 / -1

67 / 1123

70 / -1

71 / -1

(your row is the next one after this)

4. Your new IDValue == the last valid IDValue in that set of rows + the number of rows between that and your new row + 1 - update your row with this new value - in the above example, 1123 + 2 + 1 - i.e. 1126

5. Delete the first unbroken sequence of valid rows except for the latest one, to keep the table small but leave at least one valid IDValue (IDValues 1119 and 1120 in the above example) - just something like DELETE FROM table WHERE Id < 64 (in this case) should be safe.

The database takes care of atomically creating rows which is the tricky bit, and then you can generate your own number at your leisure regardless of gaps in the Key numbering sequence.

Usually, you don't. What kind of messed up requirement is that? Do you want the sky to be green at sunrise tomorrow too?

On the exceptional case where the user is on the clear and there is an unavoidable reason to create this beast, you create a separate numbering application, that uses database transactions that are independent from the ones of the main application and only cares about numbering. It will still have holes, but few enough that you can manually inspect every so often and explain why they happened.

If you look at the documentation for something like "create sequence", databases often mention that the database will reserve blocks of numbers so that they can hand out values from memory (and also without coordinating with peer databases). There's normally a way to turn that caching off.

But you may still need to check what the behavior is during a transaction, as you could have two requests trying to add a bunch of rows at the same time.

Triggers are a great option in many situations.

Reply on news.ycombinator.com