4 ms·

Seems like they fall into the same pit as many does: using primary keys with autoincrement as offset. This leads to skipping messages because there is no guaran

Seems like they fall into the same pit as many does: using primary keys with autoincrement as offset. This leads to skipping messages because there is no guarantees that primary keys will be available in monotonic order. Because, you know, transactions.

Fire-Dragon-DoL 7y ago
Can you expand a bit on this? From my understanding, autoincrement keys ca mn have gaps, but are always increasing. Sometimes a message might arrive "late", so you get a 3,then a 2. This problem cannot really be solved without giant locks that are not ideal. As far as I'm aware, all messaging systems are subject to this problem. Messages will never arrive, arrive out of order and I don't remember the third one right now (messages will arrive late?)
- rmrfchik 7y ago
  Yes, you described the problem exactly as it is. The problem is not in arrive order to subscriber, the problem is "selecting next messages with offset > last_offset". And in this case you simply miss late messages.
  - Fire-Dragon-DoL 7y ago
    Oh ok. Well, I don't believe is permanently solvable, but there can be mitigation techniques where instead the software reads messages way back every now and then, to recover some messages. Some messages might still be too late and get missed, but most of them should get through, which is what every messaging service is currently doing
    - rmrfchik 7y ago
      It is solvable, but not with SQL. I mean, one have to have side logic to keep all transactions, messages and such and use as simple storage (i.e. do not use database transaction/locking mechanisms for main business logic).
      - Fire-Dragon-DoL 7y ago
        Yeah my point is, it's not solvable by the transport mechanism. The application logic can indeed solve it, "eventually consistent systems" are a thing. My main goal was figuring out if this was impossible in SQL for some reason, but my understanding is just that the implementations are usually weak and do the "read-back" they need to, to recover late messages.
- nicois 7y ago
  Databases such as postgresql will effectively issue a buffer of keys to each connection, meaning in some circumstances the sequences will not be monotonic with respect to time. Also that usually long running transactions will use the timestamp the transaction was opened, regardless of how many seconds have passed between then and when the statement is executed.
  - Fire-Dragon-DoL 7y ago
    Very interesting details, thanks. So the alternative is have inconsistency, or "giant locks". One is not performant, the other is inconsistent. Tough choice, interesting nevertheless
abhishekjha 7y ago
Off topic but does this not effect the Pagination functionality of databases as well? Using primary keys to skip first N pages and then limit the count of results seems to be the suggested way for getting items for the Nth page. If primary key is not monotonic then this is going to give jumbled results thus messing up results in the Nth page. EDIT: More context for the above process[1] [1]https://www.eversql.com/faster-pagination-in-mysql-why-order-by-with-limit-and-offset-is-slow/ https://www.eversql.com/faster-pagination-in-mysql-why-order...
- siscia 7y ago
  Hummm, not sure I follow but most likely no. What parent mean is that there may be holes in the sequence of primary keys. What you do with pagination is that you first sort the sequence, then thrown away the first N results, and finally select only the next M results. It will work just fine.
  - abhishekjha 7y ago
    I have linked the article for the above process.
  - felixyz 7y ago
    That is one way, not necessarily the most efficient. And having gaps in the id sequence can complicate pagination. Recommended reading: https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/ https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin...
  - quietbritishjim 7y ago
    > What parent mean is that there may be holes in the sequence of primary keys. Are you sure that's what they mean? It's not what they said. "Monotonic" means "strictly increasing" (or decreasing) e.g. 1, 2, 5, 7 is monotonic even though it has gaps. "Contiguous" means "without gaps".
deleted 7y ago
[deleted]

Fire-Dragon-DoL 7y ago

Can you expand a bit on this? From my understanding, autoincrement keys ca mn have gaps, but are always increasing. Sometimes a message might arrive "late", so you get a 3,then a 2. This problem cannot really be solved without giant locks that are not ideal. As far as I'm aware, all messaging systems are subject to this problem. Messages will never arrive, arrive out of order and I don't remember the third one right now (messages will arrive late?)

rmrfchik 7y ago
Yes, you described the problem exactly as it is. The problem is not in arrive order to subscriber, the problem is "selecting next messages with offset > last_offset". And in this case you simply miss late messages.
- Fire-Dragon-DoL 7y ago
  Oh ok. Well, I don't believe is permanently solvable, but there can be mitigation techniques where instead the software reads messages way back every now and then, to recover some messages. Some messages might still be too late and get missed, but most of them should get through, which is what every messaging service is currently doing
  - rmrfchik 7y ago
    It is solvable, but not with SQL. I mean, one have to have side logic to keep all transactions, messages and such and use as simple storage (i.e. do not use database transaction/locking mechanisms for main business logic).
    - Fire-Dragon-DoL 7y ago
      Yeah my point is, it's not solvable by the transport mechanism. The application logic can indeed solve it, "eventually consistent systems" are a thing. My main goal was figuring out if this was impossible in SQL for some reason, but my understanding is just that the implementations are usually weak and do the "read-back" they need to, to recover late messages.
nicois 7y ago
Databases such as postgresql will effectively issue a buffer of keys to each connection, meaning in some circumstances the sequences will not be monotonic with respect to time. Also that usually long running transactions will use the timestamp the transaction was opened, regardless of how many seconds have passed between then and when the statement is executed.
- Fire-Dragon-DoL 7y ago
  Very interesting details, thanks. So the alternative is have inconsistency, or "giant locks". One is not performant, the other is inconsistent. Tough choice, interesting nevertheless

abhishekjha 7y ago

Off topic but does this not effect the Pagination functionality of databases as well? Using primary keys to skip first N pages and then limit the count of results seems to be the suggested way for getting items for the Nth page. If primary key is not monotonic then this is going to give jumbled results thus messing up results in the Nth page. EDIT: More context for the above process[1] [1]https://www.eversql.com/faster-pagination-in-mysql-why-order-by-with-limit-and-offset-is-slow/ https://www.eversql.com/faster-pagination-in-mysql-why-order...

siscia 7y ago
Hummm, not sure I follow but most likely no. What parent mean is that there may be holes in the sequence of primary keys. What you do with pagination is that you first sort the sequence, then thrown away the first N results, and finally select only the next M results. It will work just fine.
- abhishekjha 7y ago
  I have linked the article for the above process.
- felixyz 7y ago
  That is one way, not necessarily the most efficient. And having gaps in the id sequence can complicate pagination. Recommended reading: https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/ https://www.citusdata.com/blog/2016/03/30/five-ways-to-pagin...
- quietbritishjim 7y ago
  > What parent mean is that there may be holes in the sequence of primary keys. Are you sure that's what they mean? It's not what they said. "Monotonic" means "strictly increasing" (or decreasing) e.g. 1, 2, 5, 7 is monotonic even though it has gaps. "Contiguous" means "without gaps".

deleted 7y ago

[deleted]