[HN Gopher] Postgres sequences can skip 32 unexpectedly
___________________________________________________________________
Postgres sequences can skip 32 unexpectedly
Author : sjwhitworth
Score : 109 points
Date : 2021-07-15 10:06 UTC (1 days ago)
(HTM) web link (incident.io)
(TXT) w3m dump (incident.io)
| combatentropy wrote:
| Thank you for uncovering this edge case. To summarize, Postgres
| reserves a batch of 32 serial numbers from its sequence objects.
| Then, in the case of a crash, or the promotion of a "follower",
| that batch is lost.
|
| I consider ID numbers somewhat opaque, like GUIDs but maybe not
| _that_ opaque. Fretting about gaps in ID numbers can cause hair
| loss. This is just one of many ways gaps can happen.
|
| It is just an artifact of "sequences", the database object in
| Postgres that autogenerates the "next" ID number for a column ---
| automatically set up if you declare a column of type "serial",
| but that's all a serial column is. Serial just means: make the
| column of type integer, and create a sequence for it, and set the
| column's default value to nextval(sequence).
|
| You can mitigate gaps somewhat, like if you're testing and
| retesting a bunch of inserts, rolling back each time. Well, after
| a few tests, the next number in the sequence is far beyond the
| last number in the table. So you can call another sequence
| function, setval, to reset it. Something like:
| select setval('sequence_name', (select max(id) from table));
|
| Further reading:
| https://www.postgresql.org/docs/current/functions-sequence.h...
| merb wrote:
| btw. it's easy to use FOR UPDATE to create custom sequences in
| a table that do not have the batch reservation feature. it's
| just slower if you can afford that. the problem with resetting
| the sequence is that it would need a full blown serilizable
| transaction which is worse thatn just using for update and read
| commited.
| combatentropy wrote:
| Right. It isn't something I recommend running in production
| before every insert. It's just something I have done
| sometimes, like as part of a big database change, and only to
| "reference" tables. Like suppose there is a table of 10 rows
| to populate a dropdown menu. Now I need to add an 11th, but
| for some reason the sequence got out of wack, and the next
| sequence value is 15. So I manually set it back to 11.
| marcosdumay wrote:
| At this point, you can just add a key to the column, set it to
| max(column) + 1 in an update, and forget about the sequence.
|
| Either way, it's better done in a column that isn't the primary
| key.
| CodesInChaos wrote:
| That's what I'd run as a one time cleanup in the OP's place, to
| minimize the customer visible impact, since it avoids the gap
| for everybody who was affected by the skip but didn't have an
| incident since then.
| agent327 wrote:
| This is why you should never expose your database IDs to the
| customer. They just complain about it, and it invites them
| wanting to assign meaning and have control over the values.
| bluenose69 wrote:
| Years ago, I bought some software. Its serial number had quite
| a few digits. I found out later that I had been the first
| customer. I guess the idea was that customers might be more
| confident to jump in the water, if they saw others there
| already.
| locao wrote:
| About 15 years ago I was part of a team of four developing a
| VoIP platform. When we were about to release we realized that
| our first customer would be upset if they knew they were
| actually the first customer. So each one of us said a number
| and our first user had an ID similar to 1003912 :)
| eyelidlessness wrote:
| This is a technique used in other ways too. For instance,
| when opening a new checking account, it's common to start
| with an arbitrary number for the first check. And often new
| businesses will start with an arbitrary invoice number.
| tyingq wrote:
| There's a fair number of ecommerce setups that default to
| numerically ascending order numbers also.
| jdofaz wrote:
| It used to be common for businesses to refuse to take a
| check if it had a low check number, the assumption was the
| account was new and had a higher chance of bouncing.
| Eventually the banks let you pick or set high numbers so
| you wouldn't have to deal with that inconvenience.
| imoverclocked wrote:
| I remember getting a large-ish IBM storage product 10-15
| years ago with a serial number of 1. They actually updated it
| once someone realized!
| peterejhamilton wrote:
| Hey, author here :)
|
| Normally I'd agree with you, but in this case we're explicitly
| dealing with external IDs that we want to be incrementing.
|
| Our internal IDs and API IDs actually follow a totally
| different approach, and hold no meaning other than as a
| reference :)
| dragontamer wrote:
| Customer IDs should have at least one or two checksum digits to
| help spotcheck for data entry errors anyway.
| t0mas88 wrote:
| Indeed, if you skip this you're going to have a weird "bug"
| some time in the next years where a customer accidentally got
| the ID wrong and the system accepted it.
|
| Google Analytics either doesn't do this or got really
| unlucky. But some day I had to troubleshoot an issue where
| the data for a totally unrelated website ended up in
| someone's GA data set. Not just the usual spam, but millions
| of visits to the wrong website which had an account ID very
| similar to the client's.
| advisedwang wrote:
| You would run into this problem even if you aren't using the
| database number as your primary key. We don't want to force the
| user to generate the incident handle (slowing down incident
| creation) so a sequence of number is useful.
|
| Generating the sequence in application logic can make it
| challenging to guarantee we don't duplicate numbers if two
| requests come in at once (you don't want locks/global
| synchronous state in the application if you can avoid it), so
| having the database generate them is a good fit.
| josep-panadero wrote:
| > Sequences felt like a good use case for this when we started,
| [...] We've since moved to a different approach which enforces
| the behaviour we want more explicitly when creating incidents,
| and we learned something along the way.
|
| The entire article shows that the author has a very good grasp as
| much of the technical side of development as of the business
| side. And the conclusion makes a lot of sense.
|
| Sequences are a technical solution for a technical problem, how
| to uniquely identify new elements in a fast and reliable manner.
| And it is optimized for such use case. But, in the real world,
| users have expectations and when their mental model conflicts
| with the inner working of an application you end creating
| confusing and lack of trust. Depending on the situation, to
| educate the user can be the path to follow, but here it seems
| reasonable to just adapt the inner workings to the mental model
| of the users. It's faster and scales easier as the number of
| customers increases.
| peterejhamilton wrote:
| Author here - thanks for the kind words. You're right, this was
| a case of pragmatic decisions revisited at a later date,
| something I'm a big fan of (although it would have been nice to
| not fall foul of the issue at all!)
|
| We were very open, and our customers in this case were really
| understanding - just one of the reasons we love working with
| them!
| CodesInChaos wrote:
| > we don't just want a monotonically increasing sequence
|
| Be careful about treating sequences as monotonic. For
| transactions in progress at the same time, the order of sequence
| values might not be consistent with the order of transaction
| commits and the logical order of serializable transactions.
|
| One example where that could cause problems is if you filter a
| change stream using the last seen id. For such an approach an
| out-of-order id would lead to missed events.
| lawrjone wrote:
| Yep, this is particularly relevant when building pagination. If
| you use the primary key, which itself is sortable and based on
| a sequence, you might be surprised when you skip over rows that
| were yet to be committed because the IDs won't respect
| transaction commit order.
| peterejhamilton wrote:
| Super interesting, and that makes a lot of sense!
|
| Luckily our _internal_ IDs don't rely on sequences at all, and
| for ordering I'd always use a field specifically for that
| purpose like `created_at` timestamps etc (vs inferring ordering
| from IDs). Best if IDs just remain references!
|
| This could have been another interesting bug though, in a way
| glad we hit this one instead and that it's now fixed so we
| don't hit this one in future!
| wongarsu wrote:
| Chances are that your created_at timestamps reflect
| transaction start, not transaction commit. That would leave
| you open to issues as described by GP as well
| CodesInChaos wrote:
| Timestamps have monotonicity issues as well:
|
| 1. If you create it in the application, clocks need to be
| synced well enough between all application servers. If you
| create it in the database, this shouldn't be an issue.
|
| 2. The transaction completes some time after the the
| timestamp was created, and that time can vary between
| concurrent transactions. This is a fundamental problem.
|
| The MAX + 1 approach should guarantee strict monotonicity,
| but might lead to scalability issues for highly contented
| counters.
| anonu wrote:
| This was raised as a bug back in 2004, but the thread shows the
| contributors didn't consider it so:
| https://www.postgresql.org/message-id/20040419231413.EE480CF...
| devit wrote:
| The initial design was quite flawed, in addition to not using
| sequences they should not use one DB object per organization, but
| rather a single object with an "organization" field.
| scarmig wrote:
| That's just a design choice: single tenancy vs multitenancy. I
| agree that multitenant databases tend to be more pleasant to
| work with as a developer of dependent services, but there are
| plenty of reasons (data isolation; resource allocation
| guarantees) one might want a single tenant db.
| wheybags wrote:
| That's a little unfair, I don't think there's enough
| information in the article to come to a conclusion either way.
| peterejhamilton wrote:
| Hey - author here! I'm not totally sure I follow on this one.
| Happy to chat more if there's any context missing from the
| article that you'd find interesting :)
| CodeWriter23 wrote:
| > but rather a single object with an "organization" field.
|
| In your opinion. There are advantages of sharding tables by
| tenant boundaries. Data isolation and query speed to name a
| couple.
| Merad wrote:
| I'm sure someone will correct me if I'm wrong, but isn't it
| simpler to manage this sort of functionality by putting a counter
| in a table and using a CTE to increment it along with the insert?
| Something like with u as ( update
| organizations set last_external_id = last_external_id + 1
| where id = 123 returning last_external_id )
| insert into incidents (organization_id, external_id, title)
| select 123, last_external_id, 'Blah blah blah' from u;
|
| The risk here of course is running into lock contention around
| the organization table there's a high volume of incident creation
| for the same organization, but considering the context (incident
| management) that seems pretty low risk.
| CapriciousCptl wrote:
| Good writeup! It's an interesting gotcha because Postgres and
| SQLite docs expressly disclaim that their sequences/AUTOINCREMENT
| are gapless but experienced and talented programmers still use
| them as such. Is the type of thing that doesn't bite you until
| production.
|
| Postgres docs-- https://www.postgresql.org/docs/13/sql-
| createsequence.html > Because nextval and setval calls are never
| rolled back, sequence objects cannot be used if "gapless"
| assignment of sequence numbers is needed. It is possible to build
| gapless assignment by using exclusive locking of a table
| containing a counter; but this solution is much more expensive
| than sequence objects, especially if many transactions need
| sequence numbers concurrently.
| [deleted]
| leftnode wrote:
| We have a similar system (multi-tenant database) where each
| tenant (account) has objects that have unique identifiers for
| that specific account (customers, locations, jobs, invoices,
| etc).
|
| Customer #C1010 may have 2 locations #L1899 and #L8443 and many
| invoices #IN1940 and #IN2399 for example.
|
| When we first built the system, I considered using native
| Postgres sequences to track these, but decided against them
| because of how they are affected during a rollback. In our
| system, each account has a record in a table that controls the
| next value of the sequence.
|
| We have an event in our ORM to automatically generate the next
| sequence value as part of the transaction so if the transaction
| is rolled back, the next sequence value is as well. Sure, it
| requires locking the sequence record but it's a very small table
| and generating a sequence is quick. We wrapped everything up in a
| stored procedure named generate_sequence() which returns the next
| value of the sequence and increments it. It's scaled to millions
| of records quite well without issue.
| garblegarble wrote:
| >We have an event in our ORM to automatically generate the next
| sequence value as part of the transaction so if the transaction
| is rolled back, the next sequence value is as well.
|
| I assume that means you also have to only allow one TX to be
| in-flight at a time adding a new record whose ID is generated
| from a given sequence?
| CodeWriter23 wrote:
| Or bounce an exception for insert duplicate on a unique
| index.
| peterejhamilton wrote:
| Nice - we're using a very similar approach now (procedure that
| runs just before creation) which I think will last us a good
| while. Glad to know it's worked out well for you :)
| leftnode wrote:
| Another added benefit is that you can build a simple
| interface to allow end users to adjust their sequences (or
| our support staff in this instance).
|
| In our system, by default, all objects start at 1000. If a
| new account is created, and they want to increase a sequence
| to some value (say they already have 5000 invoices in
| QuickBooks and they want to start all new invoices at 10000
| so they know every invoice #IN10000 and higher was created in
| our system), we have a simple interface that one of our
| support staff can go to arbitrarily increase the next value.
| bsder wrote:
| Isn't creating a sequence a bad idea in general, anyway?
|
| Aren't there a zillion ways to compromise things if you know that
| some field is a sequence?
| redis_mlc wrote:
| > Isn't creating a sequence a bad idea in general, anyway?
|
| No:
|
| - sequences are very common. I recommend using them on every
| table for mgmt. and internal efficiency reasons.
|
| For example, with Innodb, if you don't have a numeric id as a
| PK, it will assign an invisible one for internal use anyway.
|
| Most third-party tools won't allow you to manage tables without
| numeric PK's.
|
| - in most large applications, most sequence ID's are only used
| internally
|
| - for public display (your concern) uuids or random numbers are
| possible
|
| Source: DBA.
| evanelias wrote:
| I agree with your overall point, but wanted to clarify one
| topic.
|
| > with Innodb, if you don't have a numeric id as a PK, it
| will assign an invisible one for internal use anyway.
|
| There's no requirement that your PK be _numeric_ with InnoDB.
| A monotonically increasing numeric ID will have the best
| performance, yes. But even a small-ish varchar PK may perform
| better than relying on InnoDB 's internal invisible one,
| depending on the workload.
|
| InnoDB will only use an invisible numeric PK if you have no
| explicit PK defined, _and_ you either have no UNIQUE KEYs at
| all either, or all of your UNIQUE KEYs have nullable columns.
| The column type of your PK is irrelevant though.
|
| The invisible numeric PK is terrible because it uses a
| system-wide lock (or at least it did prior to 8.0, not sure
| if this has been fixed). So if you're inserting at any real
| volume to multiple tables like this, performance suffers
| badly. Worse still, the lock it uses is the dict_sys mutex,
| which other code paths (e.g. DROP TABLE) also hit.
| peterejhamilton wrote:
| Hey, author here :)
|
| I don't think they're always a bad idea, but when talking about
| external IDs many folks would agree with you, in a few ways,
| actually.
|
| Relying on exposed primary IDs being ordered, and/or exposing
| them, is often a bit of a can of worms.
|
| A common case is that you leak information about your company
| because people can see how quickly you're growing. I've seen
| this in a few products I use and it's always interesting when
| you take an action a few days apart and can see how much volume
| they're doing.
|
| TIL: German Tank Problem, thanks @teddyh! I first came across
| it with a good story about someone buying Donuts/Coffee in a
| shop and using the receipt numbers to estimate yesterday's
| sales, can't find the link, though :(
|
| In this instance it's not our primary ID field - those are
| internal, and are long and random. They holds no meaning other
| than being a reference, so aren't used for sorting or exposed
| to the customer, and even if it was, it wouldn't mean anything
| or confer any information.
|
| The IDs I refer to the in the article are more like external
| references. References we _explicitly_ want to increment by 1
| each time.
|
| For those referencing invoices as a parallel, it's a good
| equivalent. I'm not familiar with the details in the comments
| below, but if I created two invoices and they were referenced
| #1 and #33, I'd be quite confused (which is a version of what
| our customers felt/experienced here).
|
| IMO It's also often a good idea to use different external IDs
| to your internal ones in APIs too, and ideally have no meaning
| attached to them, either. That way users don't do things like
| assume "record 99" was created before "record 100", and you can
| also move data around and migrate things, so long as you honour
| those external references (i.e., you can change the type/format
| of your internal IDs at will).
| combatentropy wrote:
| Do you mean enumeration, whereby an attacker starts at some ID
| and tries several in sequence?
|
| It has never been a problem for me and my applications. Just
| because you know a record exists, doesn't mean you can see it.
| For example, if you are authorized to view
| https://www.example.com/records/100, and you decide to try
| https://www.example.com/records/101, then the code will check
| to see if you're authorized to see record 101. If not, then you
| will get Unauthorized.
|
| I suppose there are situations where it's a problem if someone
| finds out that record 101 even exists, but not in any of my
| apps.
| jacobsenscott wrote:
| I've certainly seen this be a problem - even if you and every
| future programmer who touches your code gets the
| authorization check right every time over the years the app
| is live, and over the hundreds or thousands of endpoints it
| exposes, plenty of apps don't get it right every time.
|
| Using random id's is a nice and low effort additional layer
| of security there.
| tonyarkles wrote:
| Depending, very much, on that balance between usability and
| security. For the use case in the story, I'd way rather
| talk about (and write down) incidents 122 through 124 with
| my team, rather than incidents
| 549697a9-dd6a-4a90-a5f4-b2ff1a1d9289,
| d6150929-a692-414b-ba9e-ccbcf5e48a59, and
| 2756998d-035f-42bc-a97d-4135529e85d9.
| worble wrote:
| If you're not doing your authorization properly, then no,
| basic ID obfuscation is not an extra layer of security. If
| anything, the fact that some people might gloss over the
| glaring security issues because "well its random ids so I
| never decided to check" is worse, an incremental id can at
| least be easily tested while developing to make sure, or a
| nice white hat hacker might notice and let you know.
| bsder wrote:
| > I suppose there are situations where it's a problem if
| someone finds out that record 101 even exists, but not in any
| of my apps.
|
| Well, it's things like say, an invoice number.
|
| I can buy something from you. And then 7 days later I buy
| something else from you.
|
| If the invoice numbers are in sequence, I just gained quite a
| bit of information about how fast you are selling things.
|
| That's the kind of information leak that sequences can
| create.
| teddyh wrote:
| Yes; it's often called the _German tank problem_ :
|
| https://en.wikipedia.org/wiki/German_tank_problem
| allknowingfrog wrote:
| Thanks for sharing this. I'm not saying this will
| definitely come up in my day job, but it's at least
| possible, and now I'll know what to call it. :)
| wokkel wrote:
| Nice idea, but please check your local tax office. At least
| here in the Netherlands, you are required to use a
| monotically increasing series for invoice numbers. So I
| wouldn't do this if I were you.
| silon42 wrote:
| You can't stop anyone from doing what he describes if you
| allow customers to see the invoice number. IMO, your
| sequential sequence number should be for tax audit
| purposes only.
| miken123 wrote:
| That may be your opinion, but an invoice in at least the
| Netherlands needs an monotonically increasing number. And
| it needs to be on the invoice and your customer needs to
| be able to see it.
|
| [edit] It's even EU-wide, see article 226(2) of directive
| 2006/112/EC:
|
| > a sequential number, based on one or more series, which
| uniquely identifies the invoice;
| d_k_f wrote:
| Nothing stops you from using the "...or more series" part
| to generate numbers that are specific to the day, the
| hour or, if you feel like it, the minute.
|
| Today's first invoice could be 2021-07-16-001, the second
| one 2021-07-16-002, etc.
|
| If you really don't want people to be able to guess your
| invoice volume from numbers alone, there are various ways
| to do that while still being compliant to EU laws.
| zimpenfish wrote:
| I think e.g. 2021-07-16-123 followed by 2021-07-17-001
| wouldn't fall under "sequential number" though because,
| well, they're not sequential.
|
| The Italian authorities seem to see this the same way -
| https://vatdesk.eu/en/eu-vat-news/italy-mandatory-
| mentions-o...
|
| (Annoyingly the directive doesn't give a definition for
| "a sequential number" itself.)
| wayneftw wrote:
| You asked if it was a bad idea in general. It's not.
|
| Perhaps it's a bad idea in this one specific case but not
| in general.
| mcraiha wrote:
| Most places do not care about this. e.g. our local Subway
| restaurants print purchase number of the day to every
| receipt that customer gets. So you can see how many sales
| certain Subway restaurant has done in a single day by going
| to that restaurant before it closes and buying something.
| sonotathrowaway wrote:
| If you can find a way to take a representative sample of
| their stores, you can front-run their quarterly earnings
| report and make a guaranteed profit off them.
| joshribakoff wrote:
| Even if you could approximate revenue, that hardly
| equates to profitability. Even if you could approximate
| profits, the market still behaves irrationally (in the
| short term), there are no guarantees
| jsight wrote:
| That is absolutely true, but an individual store is
| unlikely to care.
| TheCoelacanth wrote:
| Most places don't care about security very much in
| general. It is a security leak, albeit usually a minor
| one.
| bouke wrote:
| Obscurity isn't a substitute for security. You still need to
| have proper authentication and authorization in place.
| SahAssar wrote:
| It can still leak information, like if a companies customers
| have sequential id's and your id is 590 then it is reasonable
| to assume that the company has had around 500-600 customers.
|
| It is usually not something to worry about, but in some cases
| you want to avoid leaking that info.
| Symbiote wrote:
| The German Tank Problem is one example of this.
|
| The Allies estimated how many tanks Germany was producing
| based on the serial numbers, and this gave a closer result
| compared to other intelligence sources.
|
| https://en.wikipedia.org/wiki/German_tank_problem
| laurent92 wrote:
| Or Jira tickets. When you submit two support cases in a few
| days and the number increased by 20 while the company is
| still a startup, you are pretty sure to have no decent
| answer.
| CodesInChaos wrote:
| Another interesting cause of skipped sequence numbers in postgres
| is that INSERT ON CONFLICT increments the sequence number even if
| the row already exists. If the UPDATE is more common than the
| INSERT case, this will waste more values that it uses. This can
| be undesirable, even when the absence of gaps isn't strictly
| required.
| grandinj wrote:
| Oracle does this too, so do some other databases.
|
| It's quite a natural optimisation.
| dabinat wrote:
| The article was interesting but I was disappointed it didn't go
| into more detail on what the final solution was.
| adeel_siddiqui wrote:
| Nice write-up. Something does not add up here though. Primary
| writes 32 ahead to the WAL when fetched the first time, then
| keeps a counter (log_cnt) which it decreases each time nextval is
| called. So, when sequence was initialized, nextval is 1 and WAL
| has 32. The replica sees 32 as fetched offset. How does incident
| sequence switch from 7 to 39? Shouldn't it be 33 when the replica
| was made the primary? Same for incident 20 -> 52, shouldn't it be
| 33 when replica was made primary? Unless I am missing something
| here, i.e, 32 is added to the nextval and nextval is logged each
| time (20 or 7).
| rcthompson wrote:
| Maybe it "tops up" the logged values whenever the database is
| idle?
| codr7 wrote:
| Yep, already walked that path with invoice numbers.
|
| The only thing you can say for sure about a sequence is the next
| number will be greater, which is not good enough for many kinds
| of identifiers.
| gmfawcett wrote:
| You can't even say that for sure. Sequences can be exhausted,
| and can be configured to cycle (wrap around when max value is
| reached).
___________________________________________________________________
(page generated 2021-07-16 23:03 UTC)