Re: [HACKERS] Serializable Isolation without blocking
Robert Haas robertmh...@gmail.com wrote: Nope, you're on target. Although - if I were you - I would post the ACCESS EXCLUSIVE lock version of the patch for feedback. I can't speak for anyone else, but I'll read it. Here you go! :-) This is the milestone of having full serializable behavior, albeit with horrible performance, using the simplest implementation possible. I didn't use ACCESS EXCLUSIVE locks, because on review it seemed to me that a SHARE lock would be strong enough. It compiles and passes the regression tests, and I've been testing some of the scenarios previously used to show the snapshot anomalies; I now get correct behavior through blocking. I identified the points to insert predicate locking by looking for places where ExecStoreTuple was called with a valid heap buffer; if there is anywhere that obtains tuples from the heap without going through that method, I have more work to do. If anyone knows of such locations, I'd be grateful for a heads up. If I've done anything horribly wrong in organizing the code, that'd be nice to hear about before I go too much farther, too. I'm definitely not looking for this to be committed, but should I add it to the CF page just for a feedback review? (I'm OK with keeping it more ad hoc, especially if it's going to hold up the beta at all.) -Kevin *** a/src/backend/catalog/index.c --- b/src/backend/catalog/index.c *** *** 2133,2139 IndexCheckExclusion(Relation heapRelation, * * After completing validate_index(), we wait until all transactions that * were alive at the time of the reference snapshot are gone; this is ! * necessary to be sure there are none left with a serializable snapshot * older than the reference (and hence possibly able to see tuples we did * not index).Then we mark the index indisvalid and commit. Subsequent * transactions will be able to use it for queries. --- 2133,2139 * * After completing validate_index(), we wait until all transactions that * were alive at the time of the reference snapshot are gone; this is ! * necessary to be sure there are none left with a transaction-based snapshot * older than the reference (and hence possibly able to see tuples we did * not index).Then we mark the index indisvalid and commit. Subsequent * transactions will be able to use it for queries. *** a/src/backend/commands/trigger.c --- b/src/backend/commands/trigger.c *** *** 2319,2325 ltrmark:; case HeapTupleUpdated: ReleaseBuffer(buffer); ! if (IsXactIsoLevelSerializable) ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), errmsg(could not serialize access due to concurrent update))); --- 2319,2325 case HeapTupleUpdated: ReleaseBuffer(buffer); ! if (IsXactIsoLevelXactSnapshotBased) ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), errmsg(could not serialize access due to concurrent update))); *** a/src/backend/executor/execMain.c --- b/src/backend/executor/execMain.c *** *** 1538,1544 EvalPlanQualFetch(EState *estate, Relation relation, int lockmode, case HeapTupleUpdated: ReleaseBuffer(buffer); ! if (IsXactIsoLevelSerializable) ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), errmsg(could not serialize access due to concurrent update))); --- 1538,1544 case HeapTupleUpdated: ReleaseBuffer(buffer); ! if (IsXactIsoLevelXactSnapshotBased) ereport(ERROR, (errcode(ERRCODE_T_R_SERIALIZATION_FAILURE), errmsg(could not serialize access due to concurrent update))); *** a/src/backend/executor/nodeBitmapHeapscan.c --- b/src/backend/executor/nodeBitmapHeapscan.c *** *** 42,47 --- 42,48 #include executor/nodeBitmapHeapscan.h #include pgstat.h #include storage/bufmgr.h + #include storage/predicate.h #include utils/memutils.h #include utils/snapmgr.h #include utils/tqual.h *** *** 114,119
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner kevin.gritt...@wicourts.gov wrote: Here you go! :-) Hmmm... I just got a write skew example to show a snapshot isolation anomaly, so I've got something wrong still. :-( Will continue to work on it. Sorry. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner kevin.gritt...@wicourts.gov wrote: This is the milestone of having full serializable behavior, albeit with horrible performance, using the simplest implementation possible. A tad too simple, as it turns out. It did it's main job of providing a simple milestone to identify code organization and lock points, but I'd have to jigger some things to make S2PL work with snapshot isolation which aren't needed for SSI. So, for those keeping score, I'm moving on down the checklist to get to the SSI implementation, rather than futzing with code which would just be thrown away. No need for anyone to test for full serializable behavior. Comments on technique welcome. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: Nicolas Barbier nicolas.barb...@gmail.com wrote: AFAICS, detecting a rw dependency where the read executes after the write is rather easy: the writer has created a row version that is not visible to the reader's snapshot. Therefore, any time a reader reads a non-last version of a row, there is a rw dependency between it and the creators of any newer versions. Sure. As you have written below, we still need the SIREAD lock on the tuple read to be able to detect rw dependencies (where the read executes before the write). I was trying to point out the difference between rw dependencies on existing tuples (where the write is an update/delete) vs those on newly created tuples (inserts) that *would* have been read. The later clearly needs predicate locking. For the former, basing on table- as well as row-level locking have been discussed so far. What I'm thinking about is if it would make sense to use the very same locking infrastructure for both, which needs to be some kind of predicate locking. Maybe that was intended by Kevin and already clear to others. It wasn't for me. As we don't yet have predicate locking or tagging, let's check what SSI needs from that building block. AFAICT we currently have the following (long term) requirements: A) reference rows that don't exist, yet B) keep the lock (tag) until after the session that created it has expired (yes, session, not only transaction). C) fit in (shared) memory, no matter how many rows get tagged (thus maybe use dynamical adjustment of granularity) AFAICT using the existing locking structure will get complicated mainly because of B), because we sometimes lack a PGPROC for the transaction holding the lock. It's specific to SSI (not generally usable for predicate locking). A) and C) might be usable for a general purpose predicate locking mechanism as well, but those requirements make it hard to map the object to be locked to a LOCKTAG. Unlike a general purpose predicate locking implementation, we don't need to block on SIREAD locks, so we don't need waiting queues nor deadlock detection for SSI. Basically, I have to confirm that the read will see *all* new versions of a row without jumping out early on any code path. Well, a heap scan immediately returns the currently visible version of a row to the caller, for example. That one may or may not continue the scan. So I fear yes, current code paths jump out early very often (as that's an optimization for the LIMIT case as well). I assume here that PG's non-SI-compatible behavior of not always rollbacking any transaction that writes to a non-last version will be disabled in serializable mode. Can that currently happen in PostgreSQL's snapshot isolation?!? I thought that was a READ COMMITTED issue. If I've missed something there, I need to understand what. Anybody? A write to a non-last (or non-head) version would lead to having multiple last (or rather multiple head) versions, which is not something that's ever supposed to happen in Postgres, IIRC. Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
2010/1/8 Kevin Grittner kevin.gritt...@wicourts.gov: Nicolas Barbier nicolas.barb...@gmail.com wrote: I assume here that PG's non-SI-compatible behavior of not always rollbacking any transaction that writes to a non-last version will be disabled in serializable mode. Can that currently happen in PostgreSQL's snapshot isolation?!? I thought that was a READ COMMITTED issue. If I've missed something there, I need to understand what. Anybody? Ah woops, you are right. The manual says in [1]: 8 13.2.2. Serializable Isolation Level [..] UPDATE, DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE commands behave the same as SELECT in terms of searching for target rows: they will only find target rows that were committed as of the transaction start time. However, such a target row might have already been updated (or deleted or locked) by another concurrent transaction by the time it is found. In this case, the serializable transaction will wait for the first updating transaction to commit or roll back (if it is still in progress). If the first updater rolls back, then its effects are negated and the serializable transaction can proceed with updating the originally found row. But if the first updater commits (and actually updated or deleted the row, not just locked it) then the serializable transaction will be rolled back with the message ERROR: could not serialize access due to concurrent update because a serializable transaction cannot modify or lock rows changed by other transactions after the serializable transaction began. 8 Sorry for the noise, Nicolas [1] URL:http://www.postgresql.org/docs/8.4/static/transaction-iso.html#XACT-SERIALIZABLE -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Greg Stark wrote: I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're locks on predicates. Ie, you have to lock against values which aren't actually currently in the table at all. You need to be able to detect a conflict between a transaction which read rows WHERE i BETWEEN 1 AND 10 and one which tries to insert a row with i=1 even if the first transaction didn't see any rows with i=1 (or indeed even if the first transaction found no rows at all). I absolutely agree to that. That's about predicate locks. I've been talking about SIREAD, which is a different thing (and which I don't consider to be a lock). The SIREAD thingie certainly doesn't help implement predicate locks. And predicate locking isn't necessarily sufficient to implement truly serializable isolation. That's the hard part. How do you represent such a lock in a way that I can efficiently find it and check for the conflict when it comes time for me to do my insert. As it's not really a lock, but rather a mark or a tag, SIREAD may or may not be implemented atop existing or non-existent locking structures, IMO. I've made my points about implementing SIREAD atop table level or row level locking structures. With (non-existent) predicate locking, I'm still unsure. It might help to implement SIREAD atop such a predicate as well. Predicate tagging? Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: As I understand it, Greg's line of thinking is that we should use a technique which has never proven practical on a large scale: matching database changes against a list of predicate lock expressions. I find that approach to predicate locking pretty interesting. However, unlike others, it scales with the number of concurrently held locks. And with the current trend towards multi-multi-core platforms, that might get worse and worse (as concurrency must increase to efficiently use these cores). Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thursday, January 7, 2010, Robert Haas robertmh...@gmail.com wrote: On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark gsst...@mit.edu wrote: On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner mar...@bluegap.ch wrote: Row level locks are very fine grained, but those are spilled to disk in its current implementation. So those are an even worse fit for the needs of SIREAD. I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're not? They're just floating out in space somewhere? There are several possible ways to implement predicate locks, but every possible method I can think of involves attaching them at one of those places. well the one place you *cannot* attach them is on the tuples. because you need to new able to lock hypothetical new tuples which don't exist yet. yes the implementation could work by attach them to tables or indexes but it's representing an abstract concept which is just hanging out in space. And how do you do that without tying the implementation to specific details of how our planner, table scans, and index access methods work? You don't. You add additional methods to the index AMs to support predicate locks, just lilke we do when we want them to support anything else (bitmap index scans, index-only scans, etc.). ...Robert -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Fri, Jan 8, 2010 at 7:34 AM, Greg Stark gsst...@mit.edu wrote: On Thursday, January 7, 2010, Robert Haas robertmh...@gmail.com wrote: On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark gsst...@mit.edu wrote: On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner mar...@bluegap.ch wrote: Row level locks are very fine grained, but those are spilled to disk in its current implementation. So those are an even worse fit for the needs of SIREAD. I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're not? They're just floating out in space somewhere? There are several possible ways to implement predicate locks, but every possible method I can think of involves attaching them at one of those places. well the one place you *cannot* attach them is on the tuples. because you need to new able to lock hypothetical new tuples which don't exist yet. Well, index tuples maybe, for next-key locking... yes the implementation could work by attach them to tables or indexes but it's representing an abstract concept which is just hanging out in space. Yeah, I understand that the concept is abstract, but I'm not sure it's bad to be talking about other kinds of locks because that's how it will be implemented. I think a lot of this is going to end up falling on the index AMs - we could lock have locks on GIST pages, next-key locks on btree tuples. We'll ask each index AM if it can help with the predicate that we're trying to lock against and if they all say no then we lock the whole table... or that's what I'm thinking, anyway. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Markus Wanner mar...@bluegap.ch wrote: Greg Stark wrote: That's about predicate locks. I've been talking about SIREAD, which is a different thing (and which I don't consider to be a lock). The SIREAD thingie certainly doesn't help implement predicate locks. And predicate locking isn't necessarily sufficient to implement truly serializable isolation. SIREAD locks need to be acquired according to the exact same rules as normal read locks in predicate locking schemes. We're just using a lock level where the set of locks which conflict with it is empty. ;-) Predicate locking is clearly necessary and clearly not sufficient to implement serializable isolation. Was some part of the Cahill paper unclear on that? That's the hard part. How do you represent such a lock in a way that I can efficiently find it and check for the conflict when it comes time for me to do my insert. As it's not really a lock, but rather a mark or a tag, SIREAD may or may not be implemented atop existing or non-existent locking structures, IMO. Well, the development plan calls for it to start there. Whether a better way is found during optimization is anybody's guess at this point. I've made my points about implementing SIREAD atop table level or row level locking structures. With (non-existent) predicate locking, I'm still unsure. It might help to implement SIREAD atop such a predicate as well. Predicate tagging? It seems both respectful and less confusing to adopt the terminology of those who developed SSI techniques. I could invent new terms for vulnerable edges, dangerous structures, pivots and such which are used in the relevant literature. But I won't. It would just serve to confuse those who have spent the time to read and understand the literature. I'm not quite sure I followed what you were getting at with the (non-existent) predicate locking phrase -- was that just an acknowledgment that it is exactly what is under development and, as such, doesn't yet exist; or were you getting at something else? -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Markus Wanner mar...@bluegap.ch wrote: Kevin Grittner wrote: As I understand it, Greg's line of thinking is that we should use a technique which has never proven practical on a large scale: matching database changes against a list of predicate lock expressions. I find that approach to predicate locking pretty interesting. Sure, I find it interesting, too. Just not practical. unlike others, it scales with the number of concurrently held locks. Times the number of checks for conflicting locks. So, O(N^2). No thanks. Now if there is a breakthrough in that technology which allows it to compete favorably with techniques which model the logical predicates against database structures, I'm all ears. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark gsst...@mit.edu wrote: well the one place you *cannot* attach them is on the tuples. The predicate locking schemes I've been reading about do attach locks to tuples, as *part* of a complete strategy. you need to new able to lock hypothetical new tuples which don't exist yet. That, too. Which is where other granularities and objects come in, as you later noted. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
I had this flagged as needing a response, but it fell through the cracks yesterday. Apologies for the delayed response. Markus Wanner mar...@bluegap.ch wrote: I'm not clear if Kevin plans to go down to tuple level locking with granularity of the SIREAD thing. Eventually, where possible, subject to escalation. (I don't like calling it a lock, because it actually isn't. Let's better call it a hint or a mark). You have a point, but as I said in another email, I'm reluctant to invent my own terminology which conflicts with the literature. So I'll remain conventional on this. We certainly cannot store all of the SIREAD hint information within the tuple header, as there may be multiple transactions having marked the same tuple SIREAD, but we don't want to spend lots of bits for SSI there (rather no single bit). Absolutely. It's easy to see that the SIREAD hint information doesn't fit in shared memory for large enough tables. The only way I can imagine tuple-level SIREAD locking half-ways working is by using that for transactions reading only a few tuples and fall back to some coarser grained locking strategy after a certain limit (per transaction). Exactly. I'm not sure if I understand this correctly, but I don't think you need to lock tuples that don't exist, at least not with SIREAD. The Cahill paper covers this under Detecting Phantoms and proposes to use plain predicate locking to cover tuple level granularity AFAIUI. The proposed SIREAD hint seems to be an optimization that only works for existing tuples. I don't find it hard to believe that it performs better than a general purpose predicate locking strategy. (Especially for test cases with short transactions, i.e. only few SIREAD locks per txn). When the Cahill paper talks about predicate locking, it *is* talking about what to lock with SIREAD locks, at least as I read it. If you see something to indicate otherwise, please share. (If I'm off base on understanding any of this, I'd sure like to get straightened out as soon as possible.) (It's interesting that with database page level granularity, he states that predicate locking would not be necessary. Instead any page can be locked at any time. For this to work, according to my reasoning, you'd have to know in advance on which page potentially accessible (but not yet visible) new tuples would end up. This is close to impossible for Postgres, however, it seems to work for Berkeley DB). It was the way Sybase worked for ages, too. If you consider that you're locking both the heap and index pages read, it becomes clear that in order to add a row which conflicts with a predicate, you have to modify a page which would have been read to check the predicate. How about storing the SIREAD info in shared memory and using dynamic granularity based on the conflict rate and available memory? *duck* Don't duck. That's the plan. I really wish I was better at communicating these things. :-( See lock.c and the associated README and see if you don't think they would fit the bill. As this seems to be an optimization of predicate locking, don't we need to implement that first? Exactly. That's the plan. Implement it in the simplest form, then optimize. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Greg Stark wrote: well the one place you *cannot* attach them is on the tuples. because you need to new able to lock hypothetical new tuples which don't exist yet. Well, maybe attaching here is meant in a more general or theoretical sense. I think we all agree that adding them to the tuple header on disk is not an option. Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: SIREAD locks need to be acquired according to the exact same rules as normal read locks in predicate locking schemes. Understood. I didn't take that into account at first. Thanks for pointing it out. (Whatever normal read locks are...) We're just using a lock level where the set of locks which conflict with it is empty. ;-) Which kind of defeats the purpose of a lock. Anyway, that's a bike-shed discussion, so I might as well agree to calling it a lock. Well, the development plan calls for it to start there. Whether a better way is found during optimization is anybody's guess at this point. Okay, so you know my guess ;-) It seems both respectful and less confusing to adopt the terminology of those who developed SSI techniques. I could invent new terms for vulnerable edges, dangerous structures, pivots and such which are used in the relevant literature. But I won't. It would just serve to confuse those who have spent the time to read and understand the literature. I agree. My intention was to translate the literature terms to Postgres hacker slang. At least I had trouble to understand that SIREAD is a lock that doesn't actually block anything. I'm not quite sure I followed what you were getting at with the (non-existent) predicate locking phrase -- was that just an acknowledgment that it is exactly what is under development and, as such, doesn't yet exist; or were you getting at something else? SIREAD atop predicate locking serves detecting vulnerable edges (I hope I'm using that term correctly here) between newly inserted tuples and reads, right? I was trying to figure if it would make sense to use predicate locking (instead of table or row level locking) as well for detecting vulnerable edges between updated or deleted tuples and reads. At least you'd be free with its granularity (which cannot be said for row or table level locking, for obvious reasons). However, it certainly depends a lot on the implementation of predicate locking, which we don't have, yet, so that's all speculation... Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: I had this flagged as needing a response, but it fell through the cracks yesterday. Apologies for the delayed response. No problem. Markus Wanner mar...@bluegap.ch wrote: When the Cahill paper talks about predicate locking, it *is* talking about what to lock with SIREAD locks, at least as I read it. If you see something to indicate otherwise, please share. (If I'm off base on understanding any of this, I'd sure like to get straightened out as soon as possible.) I don't remember reading about predicate locking in the paper I read. Either he didn't cover that in his first implementation (based on page level locking), or I've simply re-used that part of my in-brain-memory. It was the way Sybase worked for ages, too. If you consider that you're locking both the heap and index pages read, it becomes clear that in order to add a row which conflicts with a predicate, you have to modify a page which would have been read to check the predicate. Hm.. interesting, thanks for this quick explanation. How about storing the SIREAD info in shared memory and using dynamic granularity based on the conflict rate and available memory? *duck* Don't duck. That's the plan. I really wish I was better at communicating these things. :-( See lock.c and the associated README and see if you don't think they would fit the bill. Cool! Exactly. That's the plan. Implement it in the simplest form, then optimize. Perfect! Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Markus Wanner mar...@bluegap.ch wrote: I don't remember reading about predicate locking in the paper I read. Either he didn't cover that in his first implementation (based on page level locking), or I've simply re-used that part of my in-brain-memory. If you read the first paper but not the second, all you would have seen was the mention that predicate locking was covered because Berkeley DB uses page level locks for everything. The second paper gets into a little more detail on the subject, with references to a good overview of the topic as well as some authoritative papers. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
2010/1/8 Markus Wanner mar...@bluegap.ch: SIREAD atop predicate locking serves detecting vulnerable edges (I hope I'm using that term correctly here) between newly inserted tuples and reads, right? I was trying to figure if it would make sense to use predicate locking (instead of table or row level locking) as well for detecting vulnerable edges between updated or deleted tuples and reads. AFAICS, detecting a rw dependency where the read executes after the write is rather easy: the writer has created a row version that is not visible to the reader's snapshot. Therefore, any time a reader reads a non-last version of a row, there is a rw dependency between it and the creators of any newer versions. Btw, rw dependencies are the only thing that needs to be checked under SI, as wr and ww dependencies never lead to problems: one can only see (or update) a certain row version using a transaction that has taken its snapshot after the writing transaction already committed. Therefore, the must be before relationship between such transactions is trivially satisfied. (I assume here that PG's non-SI-compatible behavior of not always rollbacking any transaction that writes to a non-last version will be disabled in serializable mode.) Nicolas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Nicolas Barbier nicolas.barb...@gmail.com wrote: AFAICS, detecting a rw dependency where the read executes after the write is rather easy: the writer has created a row version that is not visible to the reader's snapshot. Therefore, any time a reader reads a non-last version of a row, there is a rw dependency between it and the creators of any newer versions. That *seems* safe on the face of it, but with HOT and such I wanted to defer addressing that until I had the crude version working. I'm probably being a bit paranoid, though. [thinks...] I should probably try to satisfy myself that this is indeed safe before I start populating the new locks. Basically, I have to confirm that the read will see *all* new versions of a row without jumping out early on any code path. If that pans out, it'll save some work; it's not something which should wait until the optimization phase if we can help it. Thanks. Btw, rw dependencies are the only thing that needs to be checked under SI, as wr and ww dependencies never lead to problems Agreed; those are already covered by the underlying snapshot isolation. I assume here that PG's non-SI-compatible behavior of not always rollbacking any transaction that writes to a non-last version will be disabled in serializable mode. Can that currently happen in PostgreSQL's snapshot isolation?!? I thought that was a READ COMMITTED issue. If I've missed something there, I need to understand what. Anybody? Thanks for your posts, by the way -- you clearly have a solid grasp of the issues. I've been paying attention; I had just never felt any of your posts needed any response from me before. :-) -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Again, a somewhat tardy post from a question found in review. Markus Wanner mar...@bluegap.ch wrote: I suppose these more persistent write locks should be kept out of the DEFAULT lock method, too I fail to understand that part. What's the DEFAULT lock method? With some adjustment of line wrapping for email... From src/include/storage/lock.h: /* * Lock methods are identified by LOCKMETHODID. (Despite the * declaration as uint16, we are constrained to 256 lockmethods by * the layout of LOCKTAG.) */ typedef uint16 LOCKMETHODID; /* These identify the known lock methods */ #define DEFAULT_LOCKMETHOD 1 #define USER_LOCKMETHOD 2 From the src/backend/storage/lmgr/README: Lock Data Structures Lock methods describe the overall locking behavior. Currently there are two lock methods: DEFAULT and USER. Lock modes describe the type of the lock (read/write or shared/ exclusive). In principle, each lock method can have its own set of lock modes with different conflict rules, but currently DEFAULT and USER methods use identical lock mode sets. See src/tools/backend/index.html and src/include/storage/lock.h for more details. (Lock modes are also called lock types in some places in the code and documentation.) At least the initial implementation of the in-memory locks to support detection of rw-dependencies will use the structures defined in the lock.c file. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: We're very much on the same page. My goal was to get predicate locking that didn't miss anything, even though it was ridiculously coarse, then implement the simplest possible SSI on top of it, without worrying about optimizations, then incrementally move toward production quality. I clearly didn't communicate that as well as I'd hoped. :-( I understood it now :-) And I think it generally is a good plan. I sort of missed the predicate locking step from the wiki's Development Path. I now see it has its own section above. Is there any such plan of development for predicate locking? To me that seems to be the harder problem (due to being more general). Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
2010/1/7 Markus Wanner mar...@bluegap.ch: (It's interesting that with database page level granularity, he states that predicate locking would not be necessary. Instead any page can be locked at any time. For this to work, according to my reasoning, you'd have to know in advance on which page potentially accessible (but not yet visible) new tuples would end up. This is close to impossible for Postgres, however, it seems to work for Berkeley DB). The specifics of relation databases can be entirely ignored in case serializability is provided on the page layer level. This also implies that pages that are part of indexes and such must be treated in exactly the same way as the pages that constitute the heap. Predicate locking is only needed to provide the same semantics in a context where the page layer doesn't provide serializability, but other layers (that understand that we are talking about a relational database) are supposed to provide it. I am not suggesting that Postgres should start supporting page layer level concurrency control, but rather indicating that most literature should be interpreted this way: concurrency control can be viewed as orthogonal to relational databases, so that is the way it was originally modeled. As this seems to be an optimization of predicate locking, don't we need to implement that first? Whole-table locking is a trivial implementation of predicate locking. Nicolas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Kevin Grittner wrote: I'm probably not quite as clueless as you think on this; I realize that keeping SIREAD locks in memory will require many more slots for locks, escalation from tuple level to page or coarser when there are many on a table, or (most likely) both. ..oh, there's the dynamic adjustment idea again. Cool! What I do think is that the structures for regular locks seem usable to track the information I need without having to burden read operations with disk output, which I see as absolutely necessary for adequate performance. I certainly agree that SIREAD locks should never hit the disk. However, thinking of SIREAD more as marks or hints, I'm not so sure the current locking structures are appropriate. If we are talking about table level locks, those are not fine grained enough and have different semantics (i.e. a user can acquire these locks, which certainly doesn't make any sense for SIREAD). My gut feeling is that adjusting them for use with SIREAD is more work than implementing your own shared memory area for SIREAD marks. Row level locks are very fine grained, but those are spilled to disk in its current implementation. So those are an even worse fit for the needs of SIREAD. It also gives me somewhere to store locks related to search ranges where data doesn't currently exist, and the ability to store read locks from many transactions against the same data. Isn't a hash table in shared memory enough to store the SIREAD locks (and a lot simpler to manage)? An open question in my mind is whether I might need to keep write locks for serializable transactions in the shared memory lock hash table until commit or rollback IIUC row level locks are kept in the tuple header until the end of the transaction (and even beyond). Is this really a problem? I suppose these more persistent write locks should be kept out of the DEFAULT lock method, too I fail to understand that part. What's the DEFAULT lock method? Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Nicolas Barbier wrote: The specifics of relation databases can be entirely ignored in case serializability is provided on the page layer level. Aha, I now see very vaguely how that could work, yes. Thank you for elaborating on this. I agree that this isn't the best way forward for Postgres. As this seems to be an optimization of predicate locking, don't we need to implement that first? Whole-table locking is a trivial implementation of predicate locking. ..and whole-database locking is a trivial implementation of true serializability. In a way, both are optimizations of that trivial implementation. My point is that due to that dependency, the conceptual design of a solution for predicate locking (with acceptable performance) should at least be considered before going into details with true serializability. Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas robertmh...@gmail.com wrote: I think you should have users/kgrittner/postgres.git rather than serializable.git. serializable sounds more like the branch name. I'll wait a bit for other comments before taking any action. Robert's advice being the last (and only) offered on the topic, I'm taking the silence as agreement and have dropped the request for a serializable repository and added one for /users/kgrittn/postgres instead. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Jan 7, 2010 at 19:08, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas robertmh...@gmail.com wrote: I think you should have users/kgrittner/postgres.git rather than serializable.git. serializable sounds more like the branch name. I'll wait a bit for other comments before taking any action. Robert's advice being the last (and only) offered on the topic, I'm taking the silence as agreement and have dropped the request for a serializable repository and added one for /users/kgrittn/postgres instead. ... and i've approved it :-) -- Magnus Hagander Me: http://www.hagander.net/ Work: http://www.redpill-linpro.com/ -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner mar...@bluegap.ch wrote: Row level locks are very fine grained, but those are spilled to disk in its current implementation. So those are an even worse fit for the needs of SIREAD. I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're locks on predicates. Ie, you have to lock against values which aren't actually currently in the table at all. You need to be able to detect a conflict between a transaction which read rows WHERE i BETWEEN 1 AND 10 and one which tries to insert a row with i=1 even if the first transaction didn't see any rows with i=1 (or indeed even if the first transaction found no rows at all). That's the hard part. How do you represent such a lock in a way that I can efficiently find it and check for the conflict when it comes time for me to do my insert. And how do you do that without tying the implementation to specific details of how our planner, table scans, and index access methods work? -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Jan 7, 2010 at 2:40 PM, Greg Stark gsst...@mit.edu wrote: On Thu, Jan 7, 2010 at 11:08 AM, Markus Wanner mar...@bluegap.ch wrote: Row level locks are very fine grained, but those are spilled to disk in its current implementation. So those are an even worse fit for the needs of SIREAD. I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're not? They're just floating out in space somewhere? There are several possible ways to implement predicate locks, but every possible method I can think of involves attaching them at one of those places. And how do you do that without tying the implementation to specific details of how our planner, table scans, and index access methods work? You don't. You add additional methods to the index AMs to support predicate locks, just lilke we do when we want them to support anything else (bitmap index scans, index-only scans, etc.). ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2010-01-07 at 15:02 -0500, Robert Haas wrote: I think we're still talking past the issue. Predicate locks are not row level, nor page level, nor table level. They're not? They're just floating out in space somewhere? There are several possible ways to implement predicate locks, but every possible method I can think of involves attaching them at one of those places. Consider an exclusion constraint, which is a kind of predicate lock. You could say that the lock is in the index (now) -- but my first implementation used a shared memory structure instead, so it's clearly not required to exist in the index. You could also say that the lock is really attached to the table, because there are catalog entries connected to the table that express the constraint -- but I think that's splitting hairs. What Greg is saying (as I understand it) is that the lock conflicts with tuples that don't even exist yet. We can tack them on to any structure that's convenient, of course. But just because you want to implement them by locking a few index pages (assuming there is an index) doesn't mean we should reject Greg's line of thinking. Regards, Jeff Davis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Jeff Davis pg...@j-davis.com wrote: Consider an exclusion constraint, which is a kind of predicate lock. You could say that the lock is in the index (now) -- but my first implementation used a shared memory structure instead, so it's clearly not required to exist in the index. You could also say that the lock is really attached to the table, because there are catalog entries connected to the table that express the constraint -- but I think that's splitting hairs. Well, we're starting by locking entire tables (as a very simple way to get correctness), then reducing the granularity where we can find a way to do that. I'll not exclusion constraints as an area needing RD. Thanks for pointing it out. What Greg is saying (as I understand it) is that the lock conflicts with tuples that don't even exist yet. We can tack them on to any structure that's convenient, of course. But just because you want to implement them by locking a few index pages (assuming there is an index) doesn't mean we should reject Greg's line of thinking. As I understand it, Greg's line of thinking is that we should use a technique which has never proven practical on a large scale: matching database changes against a list of predicate lock expressions. It's not that I want to do it any particular way, it's that I want to get it working in the simplest possible way and then find things which can be shown to improve overall performance of meaningful work loads until we have something which has acceptable performance. I don't reject pure predicate tracking, per se -- I just won't put any time into it, since I don't expect it to work. I would be overjoyed if Greg or anybody else could prove that wrong with an optimization patch, say six to twelve months from now when we hit that phase. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2010-01-07 at 15:01 -0600, Kevin Grittner wrote: As I understand it, Greg's line of thinking is that we should use a technique which has never proven practical on a large scale: matching database changes against a list of predicate lock expressions. It's not that I want to do it any particular way, it's that I want to get it working in the simplest possible way and then find things which can be shown to improve overall performance of meaningful work loads until we have something which has acceptable performance. I don't reject pure predicate tracking, per se -- I just won't put any time into it, since I don't expect it to work. I would be overjoyed if Greg or anybody else could prove that wrong with an optimization patch, say six to twelve months from now when we hit that phase. I think we are in agreement. I was responding to Robert Haas's comment, because it sounded like he didn't understand Greg Stark's point. Regards, Jeff Davis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Robert Haas robertmh...@gmail.com wrote: And use git so you can keep merging up to CVS HEAD easily. Regarding this, I was thinking that it would make sense to use a repository on git.postgresql.org to coordinate my work with any other people interested in the project. I would clone from there for the repository on my own machine. Does that make sense? (I hope so, since I applied for a serializable repository there two or three days ago) I've read through some git tutorials, but there's a lot to digest and I'm not entirely sure this is a good way to proceed. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Wed, Jan 6, 2010 at 4:29 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas robertmh...@gmail.com wrote: And use git so you can keep merging up to CVS HEAD easily. Regarding this, I was thinking that it would make sense to use a repository on git.postgresql.org to coordinate my work with any other people interested in the project. I would clone from there for the repository on my own machine. Does that make sense? (I hope so, since I applied for a serializable repository there two or three days ago) I've read through some git tutorials, but there's a lot to digest and I'm not entirely sure this is a good way to proceed. I think you should have users/kgrittner/postgres.git rather than serializable.git. serializable sounds more like the branch name. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner kevin.gritt...@wicourts.gov writes: I've read through some git tutorials, but there's a lot to digest and I'm not entirely sure this is a good way to proceed. I found that the following video is really helpful at grasping the concepts of git, that it exposes pretty directly even though it's meant to promote a particular GUI for it. If you happen to use Emacs, consider using magit, it's really good at what it does. http://alexvollmer.com/index.php/2009/01/18/meet-magit/ Regards, -- dim -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Robert Haas robertmh...@gmail.com wrote: I think you should have users/kgrittner/postgres.git rather than serializable.git. serializable sounds more like the branch name. Hmmm On a multi-year project it seemed more than remotely possible that responsibility for the project could shift, either to an external contractor or some other programmer here, so a name related to the reason for the repository rather than the current lead programmer seemed to make sense. One wouldn't want the repository location shifting based on assignments, I would have thought. But if that's going to throw people, I can easily withdraw my original request and resubmit along the lines you mention. I'll wait a bit for other comments before taking any action. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Wed, Jan 6, 2010 at 5:04 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas robertmh...@gmail.com wrote: I think you should have users/kgrittner/postgres.git rather than serializable.git. serializable sounds more like the branch name. Hmmm On a multi-year project it seemed more than remotely possible that responsibility for the project could shift, either to an external contractor or some other programmer here, so a name related to the reason for the repository rather than the current lead programmer seemed to make sense. One wouldn't want the repository location shifting based on assignments, I would have thought. But if that's going to throw people, I can easily withdraw my original request and resubmit along the lines you mention. I'll wait a bit for other comments before taking any action. Well the nice thing about git is that there is no reason why you need to have a single central repository... ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Hi, Greg Stark wrote: aaah... I think I see where we've gone off track in previous discussions...you think postgres keeps row level locks in a shared memory data structure. It doesn't it stores all row level locks *in* the tuple itself. It only stores the lock in memory briefly while actually acquiring the lock. Once it acquires it the only record of the lock is the xid in the tuple itself. This is a very good point. However, I'm not clear if Kevin plans to go down to tuple level locking with granularity of the SIREAD thing. (I don't like calling it a lock, because it actually isn't. Let's better call it a hint or a mark). We certainly cannot store all of the SIREAD hint information within the tuple header, as there may be multiple transactions having marked the same tuple SIREAD, but we don't want to spend lots of bits for SSI there (rather no single bit). It's easy to see that the SIREAD hint information doesn't fit in shared memory for large enough tables. The only way I can imagine tuple-level SIREAD locking half-ways working is by using that for transactions reading only a few tuples and fall back to some coarser grained locking strategy after a certain limit (per transaction). storing the lock data in the tuples won't work for you at all because you need to lock rows that don't exist yet at all. I'm not sure if I understand this correctly, but I don't think you need to lock tuples that don't exist, at least not with SIREAD. The Cahill paper covers this under Detecting Phantoms and proposes to use plain predicate locking to cover tuple level granularity AFAIUI. The proposed SIREAD hint seems to be an optimization that only works for existing tuples. I don't find it hard to believe that it performs better than a general purpose predicate locking strategy. (Especially for test cases with short transactions, i.e. only few SIREAD locks per txn). (It's interesting that with database page level granularity, he states that predicate locking would not be necessary. Instead any page can be locked at any time. For this to work, according to my reasoning, you'd have to know in advance on which page potentially accessible (but not yet visible) new tuples would end up. This is close to impossible for Postgres, however, it seems to work for Berkeley DB). that's why where to store the lock is a critical blocking issue to figure out to know whether the plan is feasible at all. I absolutely agree to that. As I came to think of it more as a hint or mark (and because of the different lifecycle of SIREAD hints than locks), I think basing that on existing table level locks isn't a good idea. How about storing the SIREAD info in shared memory and using dynamic granularity based on the conflict rate and available memory? *duck* As this seems to be an optimization of predicate locking, don't we need to implement that first? Regards Markus Wanner -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Jeff Davis wrote: I started a wiki page here: http://wiki.postgresql.org/wiki/Serializable I've filled it in with all relevant information which came to mind. If you can spot something I missed, please feel free to correct that or let me know so that I can. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: It seems to me that the hard part of this problem is to describe the general mechanism by which conflicts will be detected, with specific references to the types of data structures that will be used to hold that information. Well, the general approach to tracking SIREAD locks I had in mind is to keep them in the existing lock data structures. [...] If I remember right, one necessity for the SIREAD lock technique was that SIREAD locks taken by a transaction have to be kept after the transaction has ended. Won't that require fundamental changes? Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz wrote: If I remember right, one necessity for the SIREAD lock technique was that SIREAD locks taken by a transaction have to be kept after the transaction has ended. Correct. An SIREAD lock must be held until completion of the last serializable transaction holding a snapshot earlier than the lock transaction's commit. Exceptions to that are: - If a serializable transaction is rolled back, all SIREAD locks can be immediately released. - If an an ACCESS EXCLUSIVE lock is acquired on the exact same object already locked by an SIREAD lock, the SIREAD lock can be released. (This is an optimization, not a requirement for correctness.) Won't that require fundamental changes? We already have two different lock methods, one of which already keeps locks past the end of a database transaction. USER locks persist until the session terminates or the lock is explicitly released. Given that, I don't think it would be fair to characterize a third lock method with a third lifespan as a fundamental change -- just another implementation detail. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
[ Reviving this old thread because a recent one referred to it. ] 2009/5/7 Albe Laurenz laurenz.a...@wien.gv.at: Kevin Grittner wrote: maybe I misunderstood something. Consider a function makehighlander(personid integer) RETURNS void defined like this: SELECT ishighlander INTO b FROM scots WHERE id=personid; IF b THEN RETURN; /* no need to do anything */ END IF; UPDATE scots SET ishighlander=TRUE WHERE id=personid; SELECT count(*) INTO n FROM scots WHERE ishighlander; IF (n 1) THEN RAISE EXCEPTION 'There can be only one'; END IF; If we assume that ishighlander is false for all records in the beginning, and there are two calls to the function with two personid's of records *in different pages*, then there cannot be any conflicts since all (write and intention) locks taken by each of these calls should only affect the one page that contains the one record that is updated and then found in the subsequent SELECT. Yet if the two execute concurrently and the two first SELECTs are executed before the two UPDATEs, then both functions have a snapshot so that the final SELECT statements will return 1 and both functions will succeed, leaving the table with two highlanders. I do think you misunderstood. If there are two concurrent executions and each reads one row, there will be an SIREAD lock for each of those rows. As an example, let's say that one of them (T0) updates its row and does its count, finds everything looks fine, and commits. In reading the row the other transaction (T1) modified it sets the T0.outConflict flag to true and the T1.inConflict flag to true. Where does T0 read the row that T1 modified? * Typically, concurrency theory doesn't care about the specifics of relational databases: it works on a (possibly countably infinite) number of data items (sometimes called variables). * If a certain concurrency control technique works for such data items (i.e., can only result in serializable executions or whatever), then it must necessarily also work for relational databases which map their data in pages, if those pages are treated the same way the data items are. Indexes and any other structures that can be used to *find out* which other pages to read/write must then also be treated this way. * To answer your specific question: T0 might not read that specific row, but the COUNT(..) definitely must read *something* that must be modified by T1 when it updates the ishighlander field: either the row itself (which I would expect if no index on ishighlander exists), or some page in an index that it used to find out that it didn't need to inspect the row itself. Otherwise, the update wasn't effective because re-executing the COUNT(..) later on would not result in any change in the result (which leads to a contradiction: changing the ishighlander field of one row must result in a change in the number of highlanders). Nicolas -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 12:45 PM, Nicolas Barbier nicolas.barb...@gmail.com wrote: * To answer your specific question: T0 might not read that specific row, but the COUNT(..) definitely must read *something* that must be modified by T1 when it updates the ishighlander field: The problem occurs when the update happens. It doesn't have any way to know currently that a SELECT has already looked at that record and that the same transaction has performed an update which this transaction has already ignored when performing the count(*). The unsolved problems that have been raised are: - How and where do we have SELECTs note all the rows they read -- and all the rows they *would* have read that don't exist already. Note that something like select count(*) where id=? needs to be able to detect new rows from being inserted with the specified value, not merely lock the existing rows. - Can we do it without requiring major code changes in every index am and destroying modularity between the transaction management and the index api. - How do we do that without causing SELECTS to perform tons of write i/o they don't have to do now. People already complain about the hint bit updates the first time you do selects, doing i/o on every select would be disastrous. - Can we do that without destroying concurrency with course locks a la MySQL ISAM tables. - Can we do it without introducing unexpected serialization failure between transactions updating unrelated rows. Ideally, can we do it in a way that serialization errors are predictable rather than depending on access paths the planner chooses so they don't just randomly start happening when plans change. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark wrote: The unsolved problems that have been raised are: [legion] Yeah, that's why this is a two to four year project. And I would point out that if there *wasn't* a performance hit in serializable mode, none of the other isolation levels would exist. These less rigorous modes exist precisely because people are often willing to give up some data integrity guarantees, or solve them with more labor-intensive techniques, to gain performance. I certainly wouldn't consider removing any of the existing transaction isolation levels or attempt to coerce anyone into using them against their will. ;-) I am keeping track of the lists you're putting out there; they should be quite useful in the optimization phase. I do intend to first get a patch which is correct in the sense of never allowing non- serializable behavior, but which contains some of the problems you list (although destroying modularity is obviously off the table even for that point), and then refine the granularity and performance to try to get within bounds which are acceptable for our use, and hopefully (eventually) the PostgreSQL community. One of the things I'm currently working on is what would make a good set of tests to run during development to track progress. I welcome any particular use-cases you want to ensure are covered. If you could provide a detailed description or (even better) a self- contained test case for something you would like to ensure is covered, that would be most welcome. Thanks, -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 3:11 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Yeah, that's why this is a two to four year project. And I would point out that if there *wasn't* a performance hit in serializable mode, none of the other isolation levels would exist. These less rigorous modes exist precisely because people are often willing to give up some data integrity guarantees, or solve them with more labor-intensive techniques, to gain performance. I certainly wouldn't consider removing any of the existing transaction isolation levels or attempt to coerce anyone into using them against their will. ;-) Hm, this raises the issue that you'll have to figure out what should happen if two different transactions are using different isolation modes. Currently our two isolation modes only control behaviour within your transaction so they co-exist perfectly fine. ISTM you would need to have transactions in read-comitted and snapshot isolation modes recording what sets of records they read in order to be able to guarantee serializable transactions to make any guarantees as well. Separately even if nobody on the system is using true serializable isolation the on-disk data structures would need space to store the additional information just in case anyone uses it. If that's a substantial amount of space it might impact performance even if you never use it. I am keeping track of the lists you're putting out there; they should be quite useful in the optimization phase. I do intend to first get a patch which is correct in the sense of never allowing non- serializable behavior, but which contains some of the problems you list (although destroying modularity is obviously off the table even for that point), and then refine the granularity and performance to try to get within bounds which are acceptable for our use, and hopefully (eventually) the PostgreSQL community. Yeah, I'm mostly concerned about the initial design question of where to store all this extra information. It seems like once you've made that decision most of the consequences will be pretty much set. The two proposals on the table -- neither of which seem acceptable to me -- are: 1) Store information in indexes used in a scans indicating what scans are in progress or have been done by the transaction. This means you need some way to store the xid and the scan keys such that you can guarantee any index maintenance will see it. You also have to be able to handle arbitrary sets of xids similar to how we handle multi-xids currently. Also you'll need some way to handle deletions which currently don't do any index maintenance. This would have to be done for every index type and would impose design constraints on the index behaviours since in many cases it's not so easy to arrange things to provide these guarantees. It also creates a big dependency on the planner behaviour such that a change in plans will create user-visible changes in the serialization failures that are possible. I fear it would have terrible false-positive rates for some types of plans possibly even being unable to ever complete some queries, notably sequential table scans which would make people try to arrange for less efficient plans because they're trying to avoid serialization failures. It would also impose space costs on every index on disk. 2) Have some kind of in-memory data structure which stores the filter conditions for different scans that are in progress or have been executed by live transactions. This would have to be consulted by updates to find conflicting filter conditions. This has the problem that there's no efficient way to search for conflicting filter conditions -- you would have to do a linear search across all filter conditions on the same table and do fairly complex theorem-proving for each one to prove there's no conflict. It would probably perform terribly. It has the advantage of working regardless of the access method and not touching index am code at all. Both of these seem unacceptable to me but perhaps there are solutions I'm not seeing. I wonder if some kind of hybrid approach is possible but it seems like it would have the worst of both worlds in that case. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark wrote: Hm, this raises the issue that you'll have to figure out what should happen if two different transactions are using different isolation modes. Currently our two isolation modes only control behaviour within your transaction so they co-exist perfectly fine. ISTM you would need to have transactions in read-comitted and snapshot isolation modes recording what sets of records they read in order to be able to guarantee serializable transactions to make any guarantees as well. No, there is no requirement that serializable transactions serialize with weaker modes. The Cahill thesis addresses this point directly. Unless you can point out some flaw in his proofs, this is not an issue. [criticisms of hypothetical implementation techniques] There are no such proposals on the table, and the hypothetical techniques you mention seem unlikely to be ones I would use. The one and only issue I have on the table at the moment is to create a new lock method for SIREAD locks. I'd welcome any comments on that. If I get to the point of feeling comfortable with that, I'll move forward to other issues. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 12:10 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark wrote: Hm, this raises the issue that you'll have to figure out what should happen if two different transactions are using different isolation modes. Currently our two isolation modes only control behaviour within your transaction so they co-exist perfectly fine. ISTM you would need to have transactions in read-comitted and snapshot isolation modes recording what sets of records they read in order to be able to guarantee serializable transactions to make any guarantees as well. No, there is no requirement that serializable transactions serialize with weaker modes. The Cahill thesis addresses this point directly. Unless you can point out some flaw in his proofs, this is not an issue. [criticisms of hypothetical implementation techniques] There are no such proposals on the table, and the hypothetical techniques you mention seem unlikely to be ones I would use. The one and only issue I have on the table at the moment is to create a new lock method for SIREAD locks. I'd welcome any comments on that. If I get to the point of feeling comfortable with that, I'll move forward to other issues. Kevin, I think I understand why you're trying to break this down into manageable pieces, but I don't think it's really possible to have this conversation in isolation. If your question is Could it ever be acceptable to add a new lock mode? then I answer yes. And I am pretty confident that this will also be the consensus view. But if your question is Does it make sense to handle SIREAD locks as a new lock mode? then I answer I don't know, because I haven't seen the whole design yet. You just can't answer a question like this in isolation. It seems to me that the hard part of this problem is to describe the general mechanism by which conflicts will be detected, with specific references to the types of data structures that will be used to hold that information. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Robert Haas wrote: It seems to me that the hard part of this problem is to describe the general mechanism by which conflicts will be detected, with specific references to the types of data structures that will be used to hold that information. Well, the general approach to tracking SIREAD locks I had in mind is to keep them in the existing lock data structures. I have in mind to use multiple granularities, with automatic escalation to coarser granularities at thresholds, to keep RAM usage reasonable. There are clearly some tough problems with the pluggable indexes, types, operators, and such that will take time to sort out an acceptable implementation at any fine-grained level, so my intent it to punt those to very coarse granularity in the first pass, with XXX SIREAD optimization opportunity comments where that's not a production- quality solution or it just seems likely that we can do better with some work. I didn't want to get too detailed before I checked that creating a new lock method for this seemed sane, since the details of the implementation depend on that choice. Lack of detail tends to draw accusations of hand-waving, so I was trying to stay away from those details until my intuition on the lock method was confirmed or shot down, so I could solidify those details before presenting them. There is a bit of a chicken and egg problem with moving this forward -- I guess I was overly conservative on what I presented. I do understand that this does mean that more RAM will need to be allocated to the lock structures to support serializable mode. I don't think that any other option is likely to provide acceptable performance. I also realize that this means that in the final form, optimized to where my shop considers it usable, there will still be coarser granularity than theoretically possible and resulting false positives causing serialization failures for which the cause is obscure. We don't care, and anyone who does will probably not want to use this isolation level. Traditional S2PL doesn't have that fault, but it blocks so badly that performance is worse; I'll take the transaction restarts over that any day. I know there are others who won't. Basically, the reasons given for having separate lock methods for DEFAULT (normal) locks and USER locks seem to apply with almost as much force to SIREAD locks (no blocking between them, different source of setting, different lifespans), so I was pretty sure this was a sane choice, but I just wanted a quick reality check before developing the level of detail that would move this past hand-waving. Other than the SIREAD locks to cover predicate locking for serializable transactions, there is no change to what locks are acquired. There is no change to blocking or deadlock detection and recovery. Other transaction isolation levels do not need to change, except perhaps to fast-path a skip over blocking and deadlock checking against SIREAD locks (one of those details I'm looking at). Let me know if you need more information to firm up an opinion on the sanity of my intuition regarding the new lock method; I'm eager to move on to the next level of detail. And thanks for the feedback. :-) -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 1:43 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas wrote: It seems to me that the hard part of this problem is to describe the general mechanism by which conflicts will be detected, with specific references to the types of data structures that will be used to hold that information. Well, the general approach to tracking SIREAD locks I had in mind is to keep them in the existing lock data structures. I have in mind to use multiple granularities, with automatic escalation to coarser granularities at thresholds, to keep RAM usage reasonable. OK. I think it will become more clear whether the existing lock data structures are adequate as you move into detailed design. It doesn't seem critical to make a final decision about that right now. One bad thing about using the existing lock structures is that they are entirely in shared memory, which limits how large they can be. If you should find out that you're going to need more work space than can be conveniently accommodated in shared memory, you will have to think about other options. But I don't know for sure whether that will be the case. The fact that the locks need to be kept around until transactions other than the owner commit is certainly going to drive the size up. There are clearly some tough problems with the pluggable indexes, types, operators, and such that will take time to sort out an acceptable implementation at any fine-grained level, so my intent it to punt those to very coarse granularity in the first pass, with XXX SIREAD optimization opportunity comments where that's not a production- quality solution or it just seems likely that we can do better with some work. It seems to me that if you lock the heap (either individual rows, or the whole thing) none of that stuff really matters. It might defeat future optimizations such as index-only scans in some cases, and it might create full-table locks in situations where a more intelligent implementation might use less than a full-table lock, but those may be (probably are) prices you are willing to pay. As an overall design comment, I sometimes find that it helps to create a working implementation of something, even if I know that the performance will suck or that the result will not be committable for other reasons. There is often value to that just in terms of getting your head around the parts of the code that need to be modified. I wonder if you couldn't start with something ridiculously poor, like maybe an S2PL implementation with only table-level granularity - just make any operation that reads or writes a table grab an ACCESS EXCLUSIVE lock until transaction commit. Convince yourself that it is CORRECT - forget performance. Then either change the locks to SIREAD, or try to weaken the locks to row-level in certain cases. Then do the other one. It'll take you a while before you have something that can seriously be considered for commit, but that's not the point. The point is you'll have working code that you can fool with. And use git so you can keep merging up to CVS HEAD easily. And thanks for the feedback. :-) Sure thing. :-) ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-12-31 at 09:11 -0600, Kevin Grittner wrote: Yeah, that's why this is a two to four year project. I started a wiki page here: http://wiki.postgresql.org/wiki/Serializable I didn't add much content yet, but can participants in this discussion please try to organize the various issues as they progress? If there was an existing wiki page I couldn't find it. Regards, Jeff Davis -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Robert Haas wrote: OK. I think it will become more clear whether the existing lock data structures are adequate as you move into detailed design. I've gotten far enough in reviewing it to be pretty convinced that they'll cover all the granularities I'm likely to want unless I get to the point of wanting to try to lock individual columns within individual rows. It probably won't come to that, so I figure I'll cross that bridge if and when I come to it. As an overall design comment, I sometimes find that it helps to create a working implementation of something, even if I know that the performance will suck or that the result will not be committable for other reasons. There is often value to that just in terms of getting your head around the parts of the code that need to be modified. That's exactly where I've been trying to go at this point. I wonder if you couldn't start with something ridiculously poor, like maybe an S2PL implementation with only table-level granularity - just make any operation that reads or writes a table grab an ACCESS EXCLUSIVE lock until transaction commit. There's an idea I hadn't thought of -- doing S2PL but with ACCESS EXCLUSIVE locks for the read locks to test the predicate locking. It would let me play around with testing that phase before I moved to the next with minimal wasted effort. Convince yourself that it is CORRECT - forget performance. Then either change the locks to SIREAD, or try to weaken the locks to row-level in certain cases. Then do the other one. It'll take you a while before you have something that can seriously be considered for commit, but that's not the point. The point is you'll have working code that you can fool with. We're very much on the same page. My goal was to get predicate locking that didn't miss anything, even though it was ridiculously coarse, then implement the simplest possible SSI on top of it, without worrying about optimizations, then incrementally move toward production quality. I clearly didn't communicate that as well as I'd hoped. :-( Anyway, I'll think about the S2PL with ACCESS EXCLUSIVE locks for reads; if I can't punch any holes in that as a valid environment to test the predicate locking logic, I'll do that first, then switch them to SIREAD locks and work on the SSI logic. And use git so you can keep merging up to CVS HEAD easily. I know. It's on my list to do soon. Thanks again, -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Jeff Davis wrote: I started a wiki page here: http://wiki.postgresql.org/wiki/Serializable I'll try to get that filled in with something useful over the weekend. I'm heading to a party soon, and may not be in shape to work on it tomorrow ;-) Happy New Year, all! -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
aaah... I think I see where we've gone off track in previous discussions...you think postgres keeps row level locks in a shared memory data structure. It doesn't it stores all row level locks *in* the tuple itself. It only stores the lock in memory briefly while actually acquiring the lock. Once it acquires it the only record of the lock is the xid in the tuple itself. This means there are no memory limits on the number of records locked by a transaction. storing the lock data in the tuples won't work for you at all because you need to lock rows that don't exist yet at all.that's why where to store the lock is a critical blocking issue to figure out to know whether the plan is feasible at all. On Thursday, December 31, 2009, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas wrote: It seems to me that the hard part of this problem is to describe the general mechanism by which conflicts will be detected, with specific references to the types of data structures that will be used to hold that information. Well, the general approach to tracking SIREAD locks I had in mind is to keep them in the existing lock data structures. I have in mind to use multiple granularities, with automatic escalation to coarser granularities at thresholds, to keep RAM usage reasonable. There are clearly some tough problems with the pluggable indexes, types, operators, and such that will take time to sort out an acceptable implementation at any fine-grained level, so my intent it to punt those to very coarse granularity in the first pass, with XXX SIREAD optimization opportunity comments where that's not a production- quality solution or it just seems likely that we can do better with some work. I didn't want to get too detailed before I checked that creating a new lock method for this seemed sane, since the details of the implementation depend on that choice. Lack of detail tends to draw accusations of hand-waving, so I was trying to stay away from those details until my intuition on the lock method was confirmed or shot down, so I could solidify those details before presenting them. There is a bit of a chicken and egg problem with moving this forward -- I guess I was overly conservative on what I presented. I do understand that this does mean that more RAM will need to be allocated to the lock structures to support serializable mode. I don't think that any other option is likely to provide acceptable performance. I also realize that this means that in the final form, optimized to where my shop considers it usable, there will still be coarser granularity than theoretically possible and resulting false positives causing serialization failures for which the cause is obscure. We don't care, and anyone who does will probably not want to use this isolation level. Traditional S2PL doesn't have that fault, but it blocks so badly that performance is worse; I'll take the transaction restarts over that any day. I know there are others who won't. Basically, the reasons given for having separate lock methods for DEFAULT (normal) locks and USER locks seem to apply with almost as much force to SIREAD locks (no blocking between them, different source of setting, different lifespans), so I was pretty sure this was a sane choice, but I just wanted a quick reality check before developing the level of detail that would move this past hand-waving. Other than the SIREAD locks to cover predicate locking for serializable transactions, there is no change to what locks are acquired. There is no change to blocking or deadlock detection and recovery. Other transaction isolation levels do not need to change, except perhaps to fast-path a skip over blocking and deadlock checking against SIREAD locks (one of those details I'm looking at). Let me know if you need more information to firm up an opinion on the sanity of my intuition regarding the new lock method; I'm eager to move on to the next level of detail. And thanks for the feedback. :-) -Kevin -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark wrote: aaah... I think I see where we've gone off track in previous discussions...you think postgres keeps row level locks in a shared memory data structure. It doesn't it stores all row level locks *in* the tuple itself. It only stores the lock in memory briefly while actually acquiring the lock. Once it acquires it the only record of the lock is the xid in the tuple itself. This means there are no memory limits on the number of records locked by a transaction. storing the lock data in the tuples won't work for you at all because you need to lock rows that don't exist yet at all.that's why where to store the lock is a critical blocking issue to figure out to know whether the plan is feasible at all. I'm probably not quite as clueless as you think on this; I realize that keeping SIREAD locks in memory will require many more slots for locks, escalation from tuple level to page or coarser when there are many on a table, or (most likely) both. Please have patience while I try to work out the details; until I get a bit farther, everyone will be spinning their wheels if we try to get too far into details -- it will all be speculation and/or hand-waving, with much mayhem to straw men. This much is fairly firm in my head, so I probably should share: What I do think is that the structures for regular locks seem usable to track the information I need without having to burden read operations with disk output, which I see as absolutely necessary for adequate performance. It also gives me somewhere to store locks related to search ranges where data doesn't currently exist, and the ability to store read locks from many transactions against the same data. An open question in my mind is whether I might need to keep write locks for serializable transactions in the shared memory lock hash table until commit or rollback; I rather suspect that I will, with similar granularity escalation policies. That's likely to raise a hue and cry, but like I've said before -- I won't try to force anybody to use this, and the structures involved are of reasonable size to allow using many of them. I suppose these more persistent write locks should be kept out of the DEFAULT lock method, too Thanks, and Happy New Year! -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 4:44 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: I wonder if you couldn't start with something ridiculously poor, like maybe an S2PL implementation with only table-level granularity - just make any operation that reads or writes a table grab an ACCESS EXCLUSIVE lock until transaction commit. There's an idea I hadn't thought of -- doing S2PL but with ACCESS EXCLUSIVE locks for the read locks to test the predicate locking. It would let me play around with testing that phase before I moved to the next with minimal wasted effort. What predicate locking? If you take ACCESS EXCLUSIVE locks on every read, that should serialize all access to every table. Predicate locking wouldn't do anything, because the table would be completely inaccessible to all competing transactions. ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Robert Haas wrote: What predicate locking? If you take ACCESS EXCLUSIVE locks on every read, that should serialize all access to every table. Predicate locking wouldn't do anything, because the table would be completely inaccessible to all competing transactions. Yeah, that's the benefit of starting with the ACCESS EXCLUSIVE locks, but once I've confirmed that I've found all the places to get the table level locks, the next step is to turn them into table level SIREAD locks, and then to implement the SSI. Locking against referenced objects is the only practical technique for implementing predicate locking for production environments that I've seen. The phase where I'm making each referenced table totally inaccessible to all competing transaction should be pretty short-lived. It just gives me an interim milestone to test that piece in isolation before going on to use it; which is great, but not a place to stop for long. Or have I totally misunderstood your suggestion? -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, Dec 31, 2009 at 7:45 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Robert Haas wrote: What predicate locking? If you take ACCESS EXCLUSIVE locks on every read, that should serialize all access to every table. Predicate locking wouldn't do anything, because the table would be completely inaccessible to all competing transactions. Yeah, that's the benefit of starting with the ACCESS EXCLUSIVE locks, but once I've confirmed that I've found all the places to get the table level locks, the next step is to turn them into table level SIREAD locks, and then to implement the SSI. Locking against referenced objects is the only practical technique for implementing predicate locking for production environments that I've seen. The phase where I'm making each referenced table totally inaccessible to all competing transaction should be pretty short-lived. It just gives me an interim milestone to test that piece in isolation before going on to use it; which is great, but not a place to stop for long. Or have I totally misunderstood your suggestion? Nope, you're on target. Although - if I were you - I would post the ACCESS EXCLUSIVE lock version of the patch for feedback. I can't speak for anyone else, but I'll read it. (Just clearly label it as what it is, of course.) ...Robert -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
I wrote: Greg Stark st...@enterprisedb.com wrote: This thread has really been one of those cases where everyone thought they were having a different kind of discussion. Apparently so. In light of discussions at PGCon, I'm going to abandon this thread in favor of a discussion of what this feature would look like from a user perspective. Only after there is consensus (if any) on the desirability of the behavior will I move on to a discussion of implementation techniques -- probably on a fresh thread. For the record, it became clear that I did a bad job of communicating on this thread, so I'll finish it with some clarifications and observations just for the record. First, the paper didn't propose any new techniques for predicate locking, other than using a lock level which doesn't block anything else. It did reference existing papers on locking techniques. Second, Robert Haas had an interesting insight: if the techniques from the paper were implemented in the absence of predicate locks, that would still reduce the frequency of serialization anomalies from current snapshot isolation techniques. Since the PostgreSQL community generally prefers incremental enhancement patches on the way to a final result, he suggested that this would be a good path -- do everything except the predicate locks, show the incremental benefits, then add the predicate locks. We could probably even add the predicate locks in stages: first implement table level predicate locks, since that has to exist and would provide a complete, if somewhat clumsy, serializable solution; then move on to more fine-grained locks. It would probably be workable, and possibly optimal, to have just table and page locks; although it seems likely that index range locks and row locks would also be worth it, eventually. But all that is just to get it on the record; I'm getting ahead of myself here. I'll be posting on the user-facing aspects of this soon. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Wed, 2009-05-27 at 13:34 -0500, Kevin Grittner wrote: For the record, it became clear that I did a bad job of communicating on this thread... You did good work, IMHO. Not everything will reach consensus and that's not your fault. first implement table level predicate locks, since that has to exist and would provide a complete, if somewhat clumsy, serializable solution; then move on to more fine-grained locks. It would probably be workable, and possibly optimal, to have just table and page locks; although it seems likely that index range locks and row locks would also be worth it, eventually. Do we need table-level predicate locks at all? What would they give us? Why not just go straight for fine-grained page-level locks? -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs si...@2ndquadrant.com wrote: Do we need table-level predicate locks at all? What would they give us? Why not just go straight for fine-grained page-level locks? I don't want to get too far into implementation discussions at this phase (see Tom's slides ;-)), but suffice it to say that a table scan can cover more pages than we'd want to track individually The coursest possible resolution allows proof of concept. Tests can be written that work at that level which should not break as finer-grained locks are implemented. (See how I'm drawing from another presentation? ;-)) -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: I still haven't actually read the paper so I should probably bow out from the conversation until I do. I was apparently already under one misapprehension as Laurenz just claimed the paper does not show how to prevent phantoms (phantom reads I assume?). Perhaps it's not as ambitious as achieving true serializability after all? It does achieve true serializability in terms of the definitions I've read, although I've discovered at least one way in which its guarantees aren't as strong as traditional blocking techniques -- it doesn't guarantee that transactions at a level less strict than serializable will see a state which would exist between some serial execution of serializable transactions which modify the data, as the blocking schemes do. I still don't buy that this implementation guarantees serializability. All the authors show with regard to predicate handling is handwaving, and while you tried to come up with ideas how that could be improved that is not what the implementation described in the paper does. So this paper shows a performant implementation of something that is closer to serializability than snapshot isolation, but did not go all the way. As I said, I think it is promising, and it can only be hoped that the authors pursue the path they have taken and share their experiences with an implementation of full serializability with their technique. Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: All the authors show with regard to predicate handling is handwaving, That is because predicate locking is a mature technology with many known implementations. The best technique for any database product will depend on that product, and their technique doesn't depend on which implementation is used. Assuming some form of predicate locking, do you have any other qualms about the the algorithm presented in the paper? -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Mon, May 11, 2009 at 2:49 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Albe Laurenz laurenz.a...@wien.gv.at wrote: All the authors show with regard to predicate handling is handwaving, That is because predicate locking is a mature technology with many known implementations. The best technique for any database product will depend on that product, and their technique doesn't depend on which implementation is used. Assuming some form of predicate locking, do you have any other qualms about the the algorithm presented in the paper? I thought the big problem with providing true serializability was the predicate locking. If it doesn't address that need then does this get us any closer? Is this like saying walls are a well understood technology so these antilock brakes work great for stopping your car as long as you combine them with a wall? :) -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: All the authors show with regard to predicate handling is handwaving, That is because predicate locking is a mature technology with many known implementations. The best technique for any database product will depend on that product, and their technique doesn't depend on which implementation is used. Assuming some form of predicate locking, do you have any other qualms about the the algorithm presented in the paper? No - given that the algorithm is correct (which the authors cite from another paper which I cannot easily access). In my first reply I wondered if the presence of concurrent read committed transactions would somehow affect the correctness of the algorithm, as the authors don't mention that. Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark st...@enterprisedb.com wrote: I thought the big problem with providing true serializability was the predicate locking. If it doesn't address that need then does this get us any closer? I thought the big problem was the perception that performance would suffer and that the level of blocking required would be unacceptable. This technique (based on available benchmarks from the prototype implementation) seems to give performance very close to snapshot isolation with no additional blocking beyond what snapshot isolation already has to support first committer wins update conflict detection. Benchmarks showed much better performance than traditional blocking techniques for achieving serializability. Since it can markedly increase serialization failure rollbacks, the software needs to be able to respond to those gracefully, but since our framework automatically re-submits transactions which are terminated with that SQLSTATE, this approach sound very useful for us. Is this like saying walls are a well understood technology so these antilock brakes work great for stopping your car as long as you combine them with a wall? :) I see it more like saying that walls are a well understood technology, and this is a proposal for a way to use them in putting up a particular useful building. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Mon, May 11, 2009 at 3:11 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark st...@enterprisedb.com wrote: I thought the big problem with providing true serializability was the predicate locking. If it doesn't address that need then does this get us any closer? I thought the big problem was the perception that performance would suffer and that the level of blocking required would be unacceptable. This thread has really been one of those cases where everyone thought they were having a different kind of discussion. If predicate locking is so well understood and if someone who understands it and understands what kind of implementation would work well in Postgres steps forward with an implementation which doesn't cause major downsides then I suspect we might revisit our prejudices against it. But as it stands I think the assumption is that having to maintain locks on hypothetical records which don't exist would be an expensive cost to impose on every query which would unduly impact performance. I, for one, certainly assumed if we did anything like that it would work like our existing locks in that it wouldn't impose any additional blocking. If there was any question of that then it sounds like this paper might be a step forward in that you're on-side at least on that question now? -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: In my first reply I wondered if the presence of concurrent read committed transactions would somehow affect the correctness of the algorithm, as the authors don't mention that. Yeah, I was concerned about that, too. In thinking it through I've convinced myself that there is a choice in implementation, which seems to have a pretty obvious winner. (1) If READ COMMITTED and SNAPSHOT isolation levels don't change at all, there would be a behavioral difference between this technique and strict two phase locking (S2PL) implementations of serializable transactions. With S2PL, even READ COMMITTED transactions can only view the database in a state which is consistent with some serial application of SERIALIZABLE transactions. Under the algorithm from this paper, without changes to other isolation levels, if you want to view the database in a coherent state relative to SERIALIZABLE transactions, you must use a SERIALIZABLE transaction. (2) Promote everything to SERIALIZABLE by having all transactions, regardless of isolation level, take out SIREAD locks and check for unsafe access patterns. This would, strictly speaking, conform to the SQL standard, because an implementation is free to promote requests for any level of isolation to a more strict level; however, it hardly seems useful. So, I think the only sane thing to do in this regard would be to document that there is a difference from blocking implementations of SERIALIZABLE in the guarantees provided for non-serializable transactions. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark st...@enterprisedb.com wrote: Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark st...@enterprisedb.com wrote: I thought the big problem with providing true serializability was the predicate locking. If it doesn't address that need then does this get us any closer? I thought the big problem was the perception that performance would suffer and that the level of blocking required would be unacceptable. This thread has really been one of those cases where everyone thought they were having a different kind of discussion. Apparently so. If predicate locking is so well understood and if someone who understands it and understands what kind of implementation would work well in Postgres steps forward with an implementation which doesn't cause major downsides then I suspect we might revisit our prejudices against it. But as it stands I think the assumption is that having to maintain locks on hypothetical records which don't exist would be an expensive cost to impose on every query which would unduly impact performance. It would only impact transactions running at the full serializable isolation level, and I'm guessing that the performance would be reasonable if an implementation similar to that in DB2, Sybase, Microsoft SQL Server, etc. is used. Some here have derided that approach as crude and implied that only something more aesthetically pleasing would be considered, but that such implementations would be prohibitively slow (which, of course, is exactly why they are not used in these other products). I, for one, certainly assumed if we did anything like that it would work like our existing locks in that it wouldn't impose any additional blocking. Until this paper, implementation of serializable transactions, even in an MVCC database required S2PL techniques which caused a lot of blocking, including readers blocking on writes and vice versa. The advance of this paper isn't any novel implementation of predicate locking, but the reduction of the locks generated by reads to a new SIREAD level lock which would not introduce any blocking; but instead would assist in the detection of unsafe patterns of reads and writes to allow rollbacks to prevent serialization anomalies. If there was any question of that then it sounds like this paper might be a step forward in that you're on-side at least on that question now? I was never on the other side of that. I know that some apparently thought that my attempts to document PostgreSQL's deviation from current standards in this regard, and to provide more real-world examples of where people might run into trouble, were really sly attempts to persuade people to implement full support for serializable transactions. That really wasn't the case. We had been slightly burned by the differences in spite of my having read the current documentation, because the example given is so far-fetched and bizarre, that I rather naively thought Well, if that's how far out you have to go to hit a problem, the risk is quite low. I was trying to find something which gave people a clearer picture of the issue, so others didn't make the same mistake. I wasn't advocating for full serializable support at that point, and probably would have been reluctant to use it if available because of the performance issues (assuming a traditional implementation). In the course of discussing the issue, this paper, published by ACM earlier in the year, was brought to my attention. I see it as the best of both worlds -- MVCC performance with the protections of serializable transactions. Back when I first read the paper, though, it looked to be a struggle to get 8.4 to beta testing, so I sat on it until now. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: What if there is an index on the ishighlander row? Then an index scan would find only one candidate to examine, and the other rows would not even be touched by the execution plan. I assume you're talking about this line of your function: SELECT count(*) INTO n FROM scots WHERE ishighlander; Right. I'm further assuming that you meant an index on the ishighlander *column*. Of course. Sorry for the sloppiness. I can think of more than one way to handle that. Off the top of my head, I think it would work to acquire an update lock on both old and new index entries for a row when it is updated, and to lock the range of an index used for a scan with the new SIREAD lock. Or perhaps, since the row must be visited to test visibility, As far as I know, only the table rows that are found in the index scan are examined for visibility. Which would be only one in my example. the update lock could be on the old and new rows, and the index scan would find the conflict in that way. Or it could keep track of the various tuples which represent different mutations of a row, and link back from the not visible to me row which has been updated to true, and find that it is a mutation of a visible row. These are important implementation details to be worked out (very carefully!). I don't claim to have worked through all such details yet, or even to be familiar enough with the PostgreSQL internals to do so in a reasonable time. :-( Of course, and that is leading us too far. Thanks for your patience. But in your attempt to sketch a way how true serializability could be implemented, you went beyond the scope of the original paper, which does not claim to tackle phantoms. I think the idea is promising, and it would be interesting to see performance results for an implementation that covers predicates. As you mentioned in your first post, there will not be a free lunch. What hurts concurrency in an implementation with blocking read locks might also hurt concurrency in an implementation where transactions are frequently aborted and have to be retried. Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark st...@enterprisedb.com wrote: On Thu, May 7, 2009 at 11:08 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: I would assume that SELECT shown above would either resolve to a table scan, in which case you would have to have an SIREAD lock at the table level That sounds like we're back to the MSSQL/Sybase way of doing things Other than not blocking, I suppose. where you have to understand the query plan to understand why you're getting spurious serialization failures. You have to know a lot more than that to solve serialization problems in PostgreSQL with current techniques. I don't think that's terribly appealing. Consider, for example, that we might not *want* to do an index scan just because there's an index. Someone more familiar than I with S2PL would be better able to respond, but I *think* you just need to track this on whatever path is actually chosen, not on all possible paths. Or there could be multiple indexes on the function, we definitely wouldn't want to have to check for range locks on every index. Agreed. And I don't think we have to. We have to think outside of the box and get away from the pre-existing implementations which have solutions which aren't really applicable. Well, this paper is well outside the box in many respects, although it still does use well-worn techniques for some portions of the processing. If PostgreSQL developers can expand on that with their own innovations, fantastic! If we were to look at doing predicate locks in any way they would probably be stored in a whole new data structure, not related to the indexes on the table. We would need some way to index them so that we can look for conflicting locks efficiently independently from the query plan and table access methods. That might burden this with much worse performance. I think that the reason most products *do* base it on the actual rows, blocks, or tables referenced is that it gives the needed behaviors with good performance. Like I said, if we want to combine the innovations in the paper with something clever and new in the predicate locking area, OK -- as long as that isn't the cause for sinking the part that can already be shown to work. I've removed the broken email address for now -- please re-add the correct email address. I'll see what I can find. When I last corresponded with him, he was still at the University of Sidney, working on his PhD by applying these techniques to InnoDB. He specified that email address for copying him when I opened the dialog. I don't think either of us expected it to take this long for PostgreSQL to get to beta so that I could do so. He said that when that was complete, he would be working full-time for Oracle, so he's probably moved on to a new location and this email address has gone stale. I'll see what I can track down. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Fri, May 8, 2009 at 3:00 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: I've removed the broken email address for now -- please re-add the correct email address. I'll see what I can find. When I last corresponded with him, he was still at the University of Sidney, working on his PhD by applying these techniques to InnoDB. He specified that email address for copying him when I opened the dialog. I don't think either of us expected it to take this long for PostgreSQL to get to beta so that I could do so. He said that when that was complete, he would be working full-time for Oracle, so he's probably moved on to a new location and this email address has gone stale. I'll see what I can track down. For what it's worth I don't think this address has gone stale, I think someone just got the email address messed up when adding it manually. The address that was in the headers before was: Michael Cahill mjc@it.usyd.edu.au Whereas I suspect the right address was: Michael Cahill m...@it.usyd.edu.au I'll add that on my followups, if others could do the same rif they're responding to a message where he isn't he should end up back on all the responses. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Fri, May 8, 2009 at 3:00 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark st...@enterprisedb.com wrote: On Thu, May 7, 2009 at 11:08 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: I would assume that SELECT shown above would either resolve to a table scan, in which case you would have to have an SIREAD lock at the table level That sounds like we're back to the MSSQL/Sybase way of doing things Other than not blocking, I suppose. where you have to understand the query plan to understand why you're getting spurious serialization failures. You have to know a lot more than that to solve serialization problems in PostgreSQL with current techniques. Well you have to understand how Postgres locks work, but that's an invariant. You don't have to know how Postgres is going to plan your specific queries -- which you can't ever be sure of since it could change as the data changes. I don't think that's terribly appealing. Consider, for example, that we might not *want* to do an index scan just because there's an index. Someone more familiar than I with S2PL would be better able to respond, but I *think* you just need to track this on whatever path is actually chosen, not on all possible paths. Well I don't understand what storing locks in an index can accomplish if other queries might use other indexes or sequential scans to access the records and never see those locks. Or does this method only require that writers discover the locks and therefore only writers can ever fail due to serialization failures they cause? I still haven't actually read the paper so I should probably bow out from the conversation until I do. I was apparently already under one misapprehension as Laurenz just claimed the paper does not show how to prevent phantoms (phantom reads I assume?). Perhaps it's not as ambitious as achieving true serializability after all? -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: As far as I know, only the table rows that are found in the index scan are examined for visibility. Which would be only one in my example. S2PL locking schemes routinely use index range locks. But in your attempt to sketch a way how true serializability could be implemented, you went beyond the scope of the original paper, which does not claim to tackle phantoms. It doesn't put forward techniques to tackle that, apparently considering the issues to be so well-known and obvious as to not require more than a brief mention. They have a section titled Phantoms: Throughout the discussion so far, we have followed typi- cal concurrency control theory and assumed that a transac- tion is a sequence of reads and writes on named data items. In general, a relational database engine must also deal with predicate operations (such as SQL *where* clauses). These mean that a concurrency control algorithm must also con- sider phantoms, where an item created or deleted in one transaction would change the result of a predicate operation in a concurrent transaction if the two transactions executed serially. The solution used in traditional two-phase locking is multigranularity locking, where a predicate operation takes intention locks on larger units, such as pages or ta- bles, to prevent insertion of records that might match the predicate. As you mentioned in your first post, there will not be a free lunch. What hurts concurrency in an implementation with blocking read locks might also hurt concurrency in an implementation where transactions are frequently aborted and have to be retried. Possibly; although the benchmarks published in the paper show much better throughput than traditional blocking techniques with long and high-conflict transactions. Eyeballing the graph (based on 20 concurrent sessions), blocking techniques got a 2% deadlock rate in this benchmark, snapshot isolation got a 2.6% update conflict rate, and the technique published in the paper got a 0.1% update conflict rate plus another 7.2% snapshot unsafe rate. Oddly, in spite of a serialization failure rate of 7.3% versus snapshot isolation's 2.6%, the performance of the new technique edged out snapshot isolation when the number of connections was 35 or higher. I assume that is because the rollbacks and restarts somehow reduced thrashing. The traditional serializable techniques started to drop below the non-blocking techniques at about 10 concurrent sessions, and performance kept dropping from that point while the non-blocking performance continued to rise all the way to 50. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark st...@enterprisedb.com wrote: Well I don't understand what storing locks in an index can accomplish if other queries might use other indexes or sequential scans to access the records and never see those locks. Or does this method only require that writers discover the locks and therefore only writers can ever fail due to serialization failures they cause? Well, readers don't need to find the SIREAD locks which readers set. Conflicts between writers are handled the same as current PostgreSQL techniques. Readers need to look for write locks, and writers need to look for SIREAD locks. Neither is blocked by the other, but finding a conflict sets both transactions with a directional edge boolean flag. (So we would need to track two booleans per transaction in addition to the new SIREAD locks.) When a transaction reaches a state where both edge booleans are set, one of the two transactions involved in setting that must be rolled back. The prototype implementation in the Berkeley DB preferred to roll back a pivot transaction (one with both edges set) where possible, so the failure would probably usually be on a transaction which modified data, but not necessarily -- if the writers involved have committed and the reader transaction might see an invalid database state, the reader would be rolled back. I still haven't actually read the paper so I should probably bow out from the conversation until I do. I was apparently already under one misapprehension as Laurenz just claimed the paper does not show how to prevent phantoms (phantom reads I assume?). Perhaps it's not as ambitious as achieving true serializability after all? It does achieve true serializability in terms of the definitions I've read, although I've discovered at least one way in which its guarantees aren't as strong as traditional blocking techniques -- it doesn't guarantee that transactions at a level less strict than serializable will see a state which would exist between some serial execution of serializable transactions which modify the data, as the blocking schemes do. As I said in an earlier post, I'm OK with that, personally. We should probably document it as a difference, to alert someone converting, but the standard doesn't seem to require the behavior that traditional blocking approaches provide on this point. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Fri, May 8, 2009 at 4:12 PM, Greg Stark st...@enterprisedb.com wrote: On Fri, May 8, 2009 at 3:49 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark st...@enterprisedb.com wrote: Well I don't understand what storing locks in an index can accomplish if other queries might use other indexes or sequential scans to access the records and never see those locks. Or does this method only require that writers discover the locks and therefore only writers can ever fail due to serialization failures they cause? Well, readers don't need to find the SIREAD locks which readers set. Conflicts between writers are handled the same as current PostgreSQL techniques. Readers need to look for write locks, and writers need to look for SIREAD locks. Well this is where I'm failing to follow. If readers need to be sure they'll find write locks then surely they can't be stored in indexes without losing any flexibility. Argh, sorry, as soon as I hit send I realized this is wrong. Writers already need to insert into every index, so that's not a problem. The problem is if readers need to see other reader locks. If that's not true then I guess I'm all wet and I will wait until I read the paper. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark st...@enterprisedb.com writes: ... Argh, sorry, as soon as I hit send I realized this is wrong. Writers already need to insert into every index, so that's not a problem. What about HOT? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Tom Lane t...@sss.pgh.pa.us wrote: Greg Stark st...@enterprisedb.com writes: ... Argh, sorry, as soon as I hit send I realized this is wrong. Writers already need to insert into every index, so that's not a problem. What about HOT? I think that a read would need to lock both the row or tuple (not sure exactly how that would work) and any index used to find the row or tuple (or detect its absence). If a table scan is used, the lock would be at the table level (keeping in mind that this is not a lock which ever blocks anything). An insert or an update which created a new conflicting tuple would hit the table or index lock. A HOT update would hit the row lock. I think -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Fri, May 8, 2009 at 3:49 PM, Kevin Grittner kevin.gritt...@wicourts.gov wrote: Greg Stark st...@enterprisedb.com wrote: Well I don't understand what storing locks in an index can accomplish if other queries might use other indexes or sequential scans to access the records and never see those locks. Or does this method only require that writers discover the locks and therefore only writers can ever fail due to serialization failures they cause? Well, readers don't need to find the SIREAD locks which readers set. Conflicts between writers are handled the same as current PostgreSQL techniques. Readers need to look for write locks, and writers need to look for SIREAD locks. Well this is where I'm failing to follow. If readers need to be sure they'll find write locks then surely they can't be stored in indexes without losing any flexibility. You would need to be sure other readers will look at the same index you put the lock in -- so you either need to put the lock in every index, have other readers look in every index, or have a very limited predictable way of ensuring everyone will use the same index for any queries where that lock matters. -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: While discussing potential changes to PostgreSQL documentation of transaction isolation levels, Emmanuel Cecchet pointed out an intriguing new paper[1] on a new algorithm to provide true serializable behavior in a MVCC based database, with no additional blocking; although, there being no such things as a free lunch, there is an increase in serialization failures under contention. I have read through the paper and will share my comments. I hope I got it right: To put it in a nutshell, the approach to true serializability presented in the paper involves intention locks which do not block writers, but cause transactions with conflict potential to be aborted. The main cost incurred is the maintenance of these intention locks, which need to be kept for a while even after a transaction has committed. Moreover, there will potentially be many of these locks (think of SELECT COUNT(*) FROM ...), so some lock escalation mechanism (to page or table locks) will be necessary. I don't know how hard that would be to implement, but I'd argue that it is only worth considering if it guarantees true serializability. The paper describes only intention locks for rows in the select list of a statement and deliberately ignores rows which are examined in the WHERE clause. The authors argue in section 3.4 that this is no problem in their implementation since Berkeley DB does all locking and versioning on page granularity. I don't buy that; maybe I misunderstood something. Consider a function makehighlander(personid integer) RETURNS void defined like this: SELECT ishighlander INTO b FROM scots WHERE id=personid; IF b THEN RETURN; /* no need to do anything */ END IF; UPDATE scots SET ishighlander=TRUE WHERE id=personid; SELECT count(*) INTO n FROM scots WHERE ishighlander; IF (n 1) THEN RAISE EXCEPTION 'There can be only one'; END IF; If we assume that ishighlander is false for all records in the beginning, and there are two calls to the function with two personid's of records *in different pages*, then there cannot be any conflicts since all (write and intention) locks taken by each of these calls should only affect the one page that contains the one record that is updated and then found in the subsequent SELECT. Yet if the two execute concurrently and the two first SELECTs are executed before the two UPDATEs, then both functions have a snapshot so that the final SELECT statements will return 1 and both functions will succeed, leaving the table with two highlanders. So I think one would have to add intention locks for rows considered in the WHERE clause to guarantee true serializability. It would be interesting to know how many lines of code would have to be added to implement that and how performance would be affected. I'm afraid that concurrency would suffer because more conflicting transactions would be aborted. Another thing I wonder is whether the authors have considered the possibility that there are serializable and cursor stability transactions at the same time, where the latter would not take intention locks. Could that affect the considerations about correctness of the algorithm? Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at writes: So I think one would have to add intention locks for rows considered in the WHERE clause to guarantee true serializability. Does the paper explain how to deal with rows considered in the WHERE clause which don't yet exist? Ie, SELECT count(*) WHERE foo needs to take out a lock which would cause any transaction which inserts a new record where foo is true to be abort. In MSSQL this requires locking the page of the index where such records would be inserted (or the entire table if there's no index). In Predicate locking schemes this requires a separate storage structure for storing such predicates which can be arbitrarily complex expressions to check any new tuple being inserted against. Are these intention locks predicate locks, in that they're not associated with actual pages or records but with potential records which might be inserted in the future? -- Gregory Stark EnterpriseDB http://www.enterprisedb.com Ask me about EnterpriseDB's PostGIS support! -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Tue, 2009-05-05 at 10:50 -0500, Kevin Grittner wrote: This paper describes a modification to the concurrency control algorithm of a database management system that automatically detects and prevents snapshot isolation anomalies at runtime for arbitrary applications, thus providing serializable isolation. The new algorithm preserves the properties that make snapshot isolation attractive, including that readers do not block writers and vice versa. An implementation and performance study of the algorithm are described, showing that the throughput approaches that of snapshot isolation in most cases. I think this is important work in database theory and a good future direction for us. It's the right thing to keep an eye on developments and to consider implementation. We would need to decide whether intention locks were indeed necessary when we have MVCC also. Other DBMS without visibility may need to be more restrictive than we would have to be to implement this. Not sure. It wouldn't be 692 lines of code and even if it were the impact of that code would be such that it would need to be optional, since it would differ in definition from an existing SQL Standard isolation mode and it would have additional performance implications. If the use is optional, I would currently prefer the existing mechanism for implementing serialization, which is to serialize access directly using either a LOCK statement or an exclusive advisory lock. It's clear that any new-theory solution will cost significantly more as the number of users increases, at least O(N^2), whereas simply waiting is only O(N), AFAICS. (Michael et al don't discuss the algorithmic complexity). So it seems its use would require some thought and care and possibly further research to uncover areas of applicability in real usage. So for me, I would say we leave this be until the SQLStandard changes to recognise the additional mode. I don't see much advantage for us in breaking the ground on this feature and it will be costly to implement, so is a good PhD project. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs wrote: It wouldn't be 692 lines of code and even if it were the impact of that code would be such that it would need to be optional, since it would differ in definition from an existing SQL Standard isolation mode and it would have additional performance implications. I thought it would be equal to the SQL standard Serializable mode, whereas what we currently call serializable is in fact not as strong as the SQL standard Serializable mode. -- Heikki Linnakangas EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-05-07 at 15:26 +0300, Heikki Linnakangas wrote: Simon Riggs wrote: It wouldn't be 692 lines of code and even if it were the impact of that code would be such that it would need to be optional, since it would differ in definition from an existing SQL Standard isolation mode and it would have additional performance implications. I thought it would be equal to the SQL standard Serializable mode, whereas what we currently call serializable is in fact not as strong as the SQL standard Serializable mode. Our serializable is the same as Oracle's implementation. I think it would be confusing and non-useful to redefine ours, when it has already been accepted that the Oracle definition implements the standard reasonably closely. If that changes, we should also, however. Perhaps the key point is the O(N^2) complexity of the new algorithm. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Greg Stark wrote: So I think one would have to add intention locks for rows considered in the WHERE clause to guarantee true serializability. Does the paper explain how to deal with rows considered in the WHERE clause which don't yet exist? Ie, SELECT count(*) WHERE foo needs to take out a lock which would cause any transaction which inserts a new record where foo is true to be abort. Quote: To prevent phantoms in a system with row-level locking and versioning, the algorithm described here would need to be extended to take SIREAD locks on larger granules analogously to multigranularity intention locks in traditional two-phase locking systems. [...] We have not pursued the details in this paper because the phantom issue does not arise in our prototype implementation, since Oracle Berkeley DB does all locking and versioning at page granularity. End quote. Are these intention locks predicate locks, in that they're not associated with actual pages or records but with potential records which might be inserted in the future? No, they are associated with the page that contains the actual record. I think that's also meant with the larger granules in the above quote: Take an intention lock on every page which might affect the condition. Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: maybe I misunderstood something. Consider a function makehighlander(personid integer) RETURNS void defined like this: SELECT ishighlander INTO b FROM scots WHERE id=personid; IF b THEN RETURN; /* no need to do anything */ END IF; UPDATE scots SET ishighlander=TRUE WHERE id=personid; SELECT count(*) INTO n FROM scots WHERE ishighlander; IF (n 1) THEN RAISE EXCEPTION 'There can be only one'; END IF; If we assume that ishighlander is false for all records in the beginning, and there are two calls to the function with two personid's of records *in different pages*, then there cannot be any conflicts since all (write and intention) locks taken by each of these calls should only affect the one page that contains the one record that is updated and then found in the subsequent SELECT. Yet if the two execute concurrently and the two first SELECTs are executed before the two UPDATEs, then both functions have a snapshot so that the final SELECT statements will return 1 and both functions will succeed, leaving the table with two highlanders. I do think you misunderstood. If there are two concurrent executions and each reads one row, there will be an SIREAD lock for each of those rows. As an example, let's say that one of them (T0) updates its row and does its count, finds everything looks fine, and commits. In reading the row the other transaction (T1) modified it sets the T0.outConflict flag to true and the T1.inConflict flag to true. No blocking occurs. Now T1 updates its row. Still no problem, because if it committed there, there would still be a sequence of transactions (T0 followed by T1) which would be consistent with the results; but it selects rows which include the one modified by T0, which causes T0.inConflict and T1.outConflict to be set to true. These would both be pivots in an unsafe pattern of updates. No mystery which one needs to be rolled back -- T0 has already committed; so T1 is rolled back with a serialization failure (probably indicating that it is an unsafe update versus an update conflict or a deadlock, which are two other forms of serialization failure). Assuming that the software recognizes the serialization failure code and retries, it now finds that there is already a highlander and fails for real. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Gregory Stark st...@enterprisedb.com wrote: Albe Laurenz laurenz.a...@wien.gv.at writes: So I think one would have to add intention locks for rows considered in the WHERE clause to guarantee true serializability. Does the paper explain how to deal with rows considered in the WHERE clause which don't yet exist? Ie, SELECT count(*) WHERE foo needs to take out a lock which would cause any transaction which inserts a new record where foo is true to be abort. The issue is mentioned, along with the note, quoted in my original post, of why they were able to dodge the issue in the Berkeley DB implementation. In MSSQL this requires locking the page of the index where such records would be inserted (or the entire table if there's no index). This is the only form of predicate locking I've seen in real-world production databases which provide true serializable behavior. In Predicate locking schemes this requires a separate storage structure for storing such predicates which can be arbitrarily complex expressions to check any new tuple being inserted against. I've never seen that done in real-world production databases, although I'm sure it's pretty in theory. Are these intention locks predicate locks, in that they're not associated with actual pages or records but with potential records which might be inserted in the future? They are predicate locks in the sense that they detect all conflicts which could occur based on the actual predicate, though they tend to indicate conflicts in some situations where a rigorous (and expensive) analisys of the actual predicates might not; but please note that such locks would be SIREAD locks, which don't block any data modification, but are only used to detect dangerous update patterns. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: maybe I misunderstood something. Consider a function makehighlander(personid integer) RETURNS void defined like this: SELECT ishighlander INTO b FROM scots WHERE id=personid; IF b THEN RETURN; /* no need to do anything */ END IF; UPDATE scots SET ishighlander=TRUE WHERE id=personid; SELECT count(*) INTO n FROM scots WHERE ishighlander; IF (n 1) THEN RAISE EXCEPTION 'There can be only one'; END IF; If we assume that ishighlander is false for all records in the beginning, and there are two calls to the function with two personid's of records *in different pages*, then there cannot be any conflicts since all (write and intention) locks taken by each of these calls should only affect the one page that contains the one record that is updated and then found in the subsequent SELECT. Yet if the two execute concurrently and the two first SELECTs are executed before the two UPDATEs, then both functions have a snapshot so that the final SELECT statements will return 1 and both functions will succeed, leaving the table with two highlanders. I do think you misunderstood. If there are two concurrent executions and each reads one row, there will be an SIREAD lock for each of those rows. As an example, let's say that one of them (T0) updates its row and does its count, finds everything looks fine, and commits. In reading the row the other transaction (T1) modified it sets the T0.outConflict flag to true and the T1.inConflict flag to true. Where does T0 read the row that T1 modified? No blocking occurs. Now T1 updates its row. Wait a minute, I am confused. I thought T1 had already modified the row before T0 committed? Or is modify not the update? Still no problem, because if it committed there, there would still be a sequence of transactions (T0 followed by T1) which would be consistent with the results; but it selects rows which include the one modified by T0, which causes T0.inConflict and T1.outConflict to be set to true. Where does T1 select rows that were modified by T0? It selects only one row, the one it modified itself, right? These would both be pivots in an unsafe pattern of updates. No mystery which one needs to be rolled back -- T0 has already committed; so T1 is rolled back with a serialization failure (probably indicating that it is an unsafe update versus an update conflict or a deadlock, which are two other forms of serialization failure). Assuming that the software recognizes the serialization failure code and retries, it now finds that there is already a highlander and fails for real. You see, there must be something fundamental I am getting wrong. Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: Kevin Grittner wrote: I do think you misunderstood. If there are two concurrent executions and each reads one row, there will be an SIREAD lock for each of those rows. As an example, let's say that one of them (T0) updates its row and does its count, finds everything looks fine, and commits. In reading the row the other transaction (T1) modified it sets the T0.outConflict flag to true and the T1.inConflict flag to true. Where does T0 read the row that T1 modified? As I said in the original post, I think we would need to track SIREAD locks in the structures which back the pg_locks view. blocking occurs. Now T1 updates its row. Wait a minute, I am confused. I thought T1 had already modified the row before T0 committed? Or is modify not the update? There are so many sequences that I didn't think it was worthwhile to step through them all, I did say As an example, let's say that one of them (T0) updates its row and does its count, finds everything looks fine, and commits. If you want to work through the case where they both UPDATE their rows before either commits, OK; it's not that different. Things are OK as far as the first select of a modified row by the other transaction; you record inConflict for one and outConflict for the other. At the point where it goes both directions, it is clear that there is a dangerous interaction and one or the other is rolled back. Where does T1 select rows that were modified by T0? It selects only one row, the one it modified itself, right? You have to select it to know whether to count it, right? You see, there must be something fundamental I am getting wrong. It is such a radical departure from traditional blocking approaches, that it can be hard to get your head around it. :) -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Heikki Linnakangas heikki.linnakan...@enterprisedb.com wrote: Simon Riggs wrote: It wouldn't be 692 lines of code and even if it were the impact of that code would be such that it would need to be optional, since it would differ in definition from an existing SQL Standard isolation mode and it would have additional performance implications. I thought it would be equal to the SQL standard Serializable mode, whereas what we currently call serializable is in fact not as strong as the SQL standard Serializable mode. Exactly. The standard probably *should* add SNAPSHOT between REPEATABLE READ and SERIALIZABLE, but so far have not. As of the 2003 version of the SQL spec, they added explicit language that makes it clear that what you get when you ask for SERIALIZABLE mode in PostgreSQL is *not* compliant (although it is more than adequate for REPEATABLE READ). By the way, the other modes are all optional, as you're allowed to escalate to a higher level whenever a lower level is requested; SERIALIZABLE is required by the standard and is specified as the default. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Kevin Grittner wrote: Where does T1 select rows that were modified by T0? It selects only one row, the one it modified itself, right? You have to select it to know whether to count it, right? We are getting closer. So an SIREAD lock is taken for every row that is examined during the execution of an execution plan? Ah. What if there is an index on the ishighlander row? Then an index scan would find only one candidate to examine, and the other rows would not even be touched by the execution plan. Then how would they contract an SIREAD lock? Yours, Laurenz Albe -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Albe Laurenz laurenz.a...@wien.gv.at wrote: What if there is an index on the ishighlander row? Then an index scan would find only one candidate to examine, and the other rows would not even be touched by the execution plan. I assume you're talking about this line of your function: SELECT count(*) INTO n FROM scots WHERE ishighlander; I'm further assuming that you meant an index on the ishighlander *column*. I can think of more than one way to handle that. Off the top of my head, I think it would work to acquire an update lock on both old and new index entries for a row when it is updated, and to lock the range of an index used for a scan with the new SIREAD lock. Or perhaps, since the row must be visited to test visibility, the update lock could be on the old and new rows, and the index scan would find the conflict in that way. Or it could keep track of the various tuples which represent different mutations of a row, and link back from the not visible to me row which has been updated to true, and find that it is a mutation of a visible row. These are important implementation details to be worked out (very carefully!). I don't claim to have worked through all such details yet, or even to be familiar enough with the PostgreSQL internals to do so in a reasonable time. :-( -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs si...@2ndquadrant.com wrote: It wouldn't be 692 lines of code Agreed. The original implementation was in an MVCC database which already supported full serializability using strict 2 phase locking and used page level locks. Both of these made the implementation simpler than it would be in PostgreSQL. (And that's not even mentioning sub-transactions and distributed transactions!) and even if it were the impact of that code would be such that it would need to be optional I was thinking perhaps a GUC to allow traditional behavior when SERIALIZABLE is requested versus using snapshot isolation for REPEATABLE READ and this new technique for SERIALIZABLE. Would that be sane? If the use is optional, I would currently prefer the existing mechanism for implementing serialization, which is to serialize access directly using either a LOCK statement or an exclusive advisory lock. I'm sure many will, particularly where the number of tables is less than 100 and the number of queries which can be run concurrently is only a thousand or two. Picking out the potential conflicts and hand-coding serialization techniques becomes more feasible on a small scale like that. That said, there's a lot less room for mistakes here, once this new technique is implemented and settled in. When I was discussing the receipting and deposit scenario while trying to clarify the documentation of current behavior, I received several suggestions from respected members of this community for how that could be handled with existing techniques which didn't, in fact, correct the problem. That just points out to me how tricky it is to solve on an ad hoc basis, as opposed to a more rigorous technique like the one described in the paper. The only suggested fix which *did* work forced actual serialization of all receipts as well as actual serialization of those with the deposit report query. The beauty of this new technique is that there would not be any blocking in the described scenario, and there would be a rollback with serialization failure if (and only if) there was an attempt to run the deposit report query while a transaction for a receipt on the old date was still pending. I suspect that the concurrency improvements of the new technique over existing safe techniques would allow it to scale well, at least in our environment. It's clear that any new-theory solution will cost significantly more as the number of users increases, at least O(N^2), whereas simply waiting is only O(N), AFAICS. I'm not following your reasoning on the O(N^2). Could you explain why you think it would follow that curve? So it seems its use would require some thought and care and possibly further research to uncover areas of applicability in real usage. Care -- of course. Real usage for serializable transactions -- well known already. (Or are you just questioning performance here?) So for me, I would say we leave this be until the SQLStandard changes to recognise the additional mode. It already recognizes this mode; it doesn't yet recognize snapshot isolation (more's the pity). I don't see much advantage for us in breaking the ground on this feature and it will be costly to implement, so is a good PhD project. Apparently it's already been done as a PhD project -- by Michael Cahill, against InnoDB. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Please keep Michael Cahill copied on this thread, per his request. I just noticed the omission on a few messages and will forward them to him. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-05-07 at 11:15 -0500, Kevin Grittner wrote: Please keep Michael Cahill copied on this thread, per his request. I just noticed the omission on a few messages and will forward them to him. Apologies Michael, I see that my mail did remove you. That was a unconscious error; I was particularly interested in your comments regarding my assessment of the algorithmic complexity of the new theory and existing serialization technique. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-05-07 at 10:56 -0500, Kevin Grittner wrote: It's clear that any new-theory solution will cost significantly more as the number of users increases, at least O(N^2), whereas simply waiting is only O(N), AFAICS. I'm not following your reasoning on the O(N^2). Could you explain why you think it would follow that curve? Each user must compare against work performed by all other users. O(N). There are N users, so O(N^2). With reasonable tuning we can make that work with 10 users each checking the other's data, but with a 100 we'll end up spending more time checking for aborts (and aborting) than we would if we had just queued up for it. If you want this, the simplest implementation is to quite literally allow only a single SERIALIZABLE txn onto the system at any time. All other SERIALIZABLEs queue. Note that simple serialization requires no special handling for aborted transactions. Implementing that will be fast, proving it works is trivial and it seems will work better in the general case. Yeh, it sucks for medium arrival rate transactions, but its great for low or high arrival rate transactions. The new model is good for medium arrival rates only and will take a lot of work to implement, correctly and sufficiently optimally to keep the applicability window wide enough to justify the effort. Optimising it would basically entail implementing the equivalent of block-level locking. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs si...@2ndquadrant.com wrote: Each user must compare against work performed by all other users. O(N). There are N users, so O(N^2). Why does that apply here and not in the update conflict detection? -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-05-07 at 12:39 -0500, Kevin Grittner wrote: Simon Riggs si...@2ndquadrant.com wrote: Each user must compare against work performed by all other users. O(N). There are N users, so O(N^2). Why does that apply here and not in the update conflict detection? I think the shoe is on the other foot. :-) Explain what you think the algorithmic complexity is, and why, if that's not correct. Can you beat O(N), with Postgres? -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs si...@2ndquadrant.com wrote: On Thu, 2009-05-07 at 12:39 -0500, Kevin Grittner wrote: Simon Riggs si...@2ndquadrant.com wrote: Each user must compare against work performed by all other users. O(N). There are N users, so O(N^2). Why does that apply here and not in the update conflict detection? I think the shoe is on the other foot. :-) That's a question, and I think a fair one. As with update conflict detection, you check whether there are any conflicting locks for what you are currently accessing. For most usage patterns you won't find conflicting access the vast majority of the time. The assertion that there is some need for each session to wade through something for every other session seems baseless to me. I'm wondering what I might be missing. If you throw a formula out there, I do think it's incumbent on you to explain why you think it fits. If I threw a formula out there, then it would be fair of you to ask me to explain how I got to it. I'm not at a point where I think I can estimate performance impact. I guess I would tend to start from the benchmarks published in the paper, some of which were confirmed by the ACM SIGMOD repeatability committee. Eyeballing that, it looks to me like the worst case they found was about a 15% performance hit, with large stretches of some of the graphs hanging within 1% of the performance of straight snapshot isolation. I think that given published benchmarks with confirmation from an independent organization like ACM, it would be incumbent on anyone who questions the benchmarks to explain why they think they're not accurate or useful. The only concern I've seen so far has been that these benchmarks lack long and complex database transactions, which seems like a fair concern. Scalability with additional concurrent sessions seems good as far as they took it, which was 50 sessions. Even on a server with 16 CPUs backing a database with 3 million to 4 million hit per day, with tens of millions of database transactions per day, we use a connection pool with fewer sessions than that. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, 2009-05-07 at 15:10 -0500, Kevin Grittner wrote: The assertion that there is some need for each session to wade through something for every other session seems baseless to me. I'm wondering what I might be missing. That's Greg's point. Do we need full locking of everything we might touch, or tracking of what we have touched? That question is still unanswered. If you need the might touch then you either need to implement locking that will effect everybody (which ain't ever gonna fly round here), or you implement a scheme that is harder work but avoids locking. That is clearly O(N^2) for non-locking design. If you track have touched only then we can do that with a hash table in shared memory. That would be O(k), if it is possible. -- Simon Riggs www.2ndQuadrant.com PostgreSQL Training, Services and Support -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
On Thu, May 7, 2009 at 6:31 PM, Simon Riggs si...@2ndquadrant.com wrote: Each user must compare against work performed by all other users. O(N). There are N users, so O(N^2). i think this logic only works if you must scan every item for every other user every time. If you have data structures like binary trees or whatever to fine any matching predicate locks or intent locks or whatever we're calling them then you can hopefully find them in faster than O(N) time. I'm not sure you can do better than a full linear search though. If I do something like SELECT count(*) FROM tab WHERE complex_function(a,b) = 5 And then you INSERT INTO tab (a,b) VALUES (1,2). How would you store any record of the fact that there's a serialization failure iff complex_function(1,2)=5 in any way that lets you look it up in any way other than evaluating complex_function for every set of values inserted? -- greg -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Serializable Isolation without blocking
Simon Riggs si...@2ndquadrant.com wrote: Do we need full locking of everything we might touch, or tracking of what we have touched? If you need the might touch then you either need to implement locking that will effect everybody (which ain't ever gonna fly round here), or you implement a scheme that is harder work but avoids locking. That is clearly O(N^2) for non-locking design. If you track have touched only then we can do that with a hash table in shared memory. That would be O(k), if it is possible. To quote what I think is a relevant section from the paper: One property of Berkeley DB that simplified our implementation was working with page level locking and versioning. In databases that version and lock at row-level granularity (or finer), additional effort would be required to avoid phantoms, analogous to standard two phase locking approaches such as multigranularity locking. Since these techniques are used in quite a few databases, I assume that implementation is fairly well understood. The big difference is that rather than traditional read locks which block updates, it would be these new non-blocking SIREAD locks. As I understand it, the point of this technique is to approximate might touch through locking have touched on both rows and index ranges. I know that is considered crude by some, but the O(N^2) cost of actual predicate lock calculation would be insane in most real-world environments. I do have to concede that the paper is silent on how transactions at other isolation levels behave in this mix. On a first think-through, it doesn't seem like they would need to obtain SILOCKs for their reads, since there is no guarantee that they see things in a state which would be consistent with some serial execution of the database transactions. I don't think transactions at less stringent transaction isolation levels need to look for SILOCKs, either. I wouldn't consider my first pass thinking it through to be particularly definitive, though. That interpretation would mean, however, that while the serializable transactions would satisfy the new, more stringent requirements of recent versions of the SQL standard, they would still not provide quite the same guarantees as traditional blocking serializable transactions. In my receipting example, traditional techniques would cause the attempt to update the control record to block until the receipts on the old date committed or rolled back, and the attempt to report the day's receipts couldn't proceed until the control record update was committed, so as long as the transactions which modify data were serializable, no select at READ COMMITTED or highter could see a state inconsistent with some serial application of the serializable transactions. With this interpretation, even a SELECT-only transaction would need to be SERIALIZABLE to ensure that that it did not see the new deposit date when there were still pending receipts for the old deposit date. I think I'm OK with that if everyone else is. -Kevin -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
