Automatically pulling into a committer's Git repository
Posted Friday Nov 26th, 2010 06:08am
by Alvaro Herrera | Permalink

I was a bit unhappy because I couldn't keep my "bare" Git repository up-to-date unattended — I needed to be at my workstation to be able to do a git fetch, because it needs my SSH passphrase.

I didn't have this problem with CVS because I kept an rsync copy of the anonymous CVS repository, from which my regular trees where checked out. (My committer's checkouts were separate, which was annoying, but I considered that problem solved with the jump to Git.)

Yesterday I had an epiphany that this could be solved very easily: just add a new remote to the anonymous clone, which doesn't require any SSH key to be involved, and so can run unattended. This sounds quite trivial, but I couldn't make it work at first for reasons that appeared quite obscure; and indeed they were :-)

The full solution looks like this:

git remote add anon-origin git://git.postgresql.org/git/postgresql.git

This adds the new remote, from which you can "git fetch anon-origin"; but while it will pick up the objects when you do, it won't update the branches. To make it update the branches, you have to fetch into each branch explicitely:

git fetch anon-origin \
    master:master REL9_0_STABLE:REL9_0_STABLE \
    REL8_4_STABLE:REL8_4_STABLE REL8_3_STABLE:REL8_3_STABLE \
    REL8_2_STABLE:REL8_2_STABLE

Now I can have this in my crontab and be confident that the repository will be always reasonably up to date.

Why this doesn't work without this trick is beyond me, but I don't really care all that much. I'm not into Git internals enough, it seems (and I don't think I want to be anyway).

Of course, non-committers don't have this problem, because they can always run "git fetch" or "git pull" without worrying about being asked for a passphrase.

---

blog comments powered by Disqus

Fixing foreign key deadlocks, part 2 revisited
Posted Thursday Nov 25th, 2010 12:02pm
by Alvaro Herrera | Permalink

While trying to implement SELECT FOR KEY LOCK at the lock manager level, I stumbled across the problem that I need to represent the lock faithfully in the lock manager's terms. And since I previously mentioned that FOR KEY LOCK would conflict with FOR SHARE, I get in trouble — it's not easy to see which lock mode to use (if there is one, which I doubt).

So I revisited that decision: a FOR KEY LOCK does not conflict with FOR SHARE, and this allows them to use the same ShareLock mode.

This has two consequences:

1. After the tuple is locked by two transactions or more in the two different modes, there's no way to figure out which one has which lock.
2. The HEAP_XMAX_SHARED_LOCK infomask bit needs to be carried forward in an UPDATE, just like HEAP_XMAX_KEY_LOCK bit was going to be.

None of these is a problem, as far as I can see. Just a little bit different. But the basic fact that FOR SHARE and FOR KEY LOCK do not conflict could take someone by surprise.

---

blog comments powered by Disqus

Fixing foreign key deadlocks, part 2
Posted Thursday Nov 18th, 2010 04:34pm
by Alvaro Herrera | Permalink

In the previous article, I explained the problem with foreign key checks checks obtaining too strong of a lock, and promised that we would be attempting to fix it.

Here is my proposal:

1. Create a new SELECT locking clause. For now, we're calling it SELECT FOR KEY LOCK
2. This will acquire a new type of lock in the tuple, dubbed a "keylock".
3. This lock will conflict with DELETE, SELECT FOR UPDATE, and SELECT FOR SHARE.
4. It also conflicts with UPDATE if the UPDATE modifies an indexed attribute.

That's the gist of it. The end effect is that you are allowed to UPDATE a tuple that's being used in a foreign key check, as long as you don't change any indexed columns.

This idea was suggested by Simon Riggs in the pgsql-hackers thread referenced in my previous article, and further debugged and improved by the developers in the ensuing discussion to a reasonably workable level — though it remains ticklish.

The interesting implementation details are:

1. We need to use a new bit in t_infomask. 0x0010 is currently unused so we will grab that.
2. Key-locking a tuple means setting the XMAX_KEY_LOCK bit, and setting the Xmax to the locker. If the tuple is already key-locked, a MultiXactId needs to be created from the original locker(s) and the new transaction.
3. The original tuple needs to be marked with the Cmax of the locking command, to prevent it from being seen in the same transaction.
4. A non-conflicting update to the tuple must carry forward some fields from the original tuple into the updated copy. Those include Xmax, XMAX_IS_MULTI, XMAX_KEY_LOCK, and the CommandId and COMBO_CID flag.

If you're curious about also carrying forward COMBO_CID: at first I thought this wasn't necessary, because the only transaction that might care about those bits is the one creating the tuple, thus no transaction can do the necessary UPDATE. However, if a transaction creates the tuple, then modifies it in a subtransaction, then aborts the subtransaction, then key-locks the tuple, and finally updates it again, the last version of the tuple needs to have the correct CommandId information. This is fairly corner case and I would be surprised to see it happen in reality. But this is no excuse for not supporting the case.

(Offhand, I don't see any other fields that need to be carried forward, but I'm open to the possibility that I'm missing some.)

Note that the lock would be even more granular if instead of checking for an attribute of any index, we were to check for the particular UNIQUE index that implements the foreign key being verified. We choose not to do that for now, because it brings excessive modularisation breakage and possibly extra locking considerations.

---

blog comments powered by Disqus

Fixing foreign key deadlocks
Posted Thursday Nov 11th, 2010 01:58pm
by Alvaro Herrera | Permalink

I've been commissioned to work on foreign keys. More specifically, on the problem that when foreign keys are verified, they sometimes obtain locks that are stronger than really needed. This causes some operations to block unnecessarily and, perhaps more aggravating, some other operations to deadlock.

This problem has been known for a very long time, and it affects many users to varying degrees. The most recent detailed discussion about this problem took place on August 2010 on pgsql-hackers.

To recapitulate on this problem a bit: in the aboriginal code, foreign key checks obtained FOR UPDATE locks on referenced tuples, meaning that they were exclusively locked for the duration of the transaction doing the check. This was so strong a lock that it had a severe impact to the performance of applications that expected to concurrently access and modify tables with foreign key relationships. Consequently, many people used to drop their foreign keys just to get a reasonable concurrency level.

We partly fixed this by introducing SELECT FOR SHARE in 8.1, which allowed checks to be run concurrently. This had an enormous positive impact to concurrency, so people then began to use foreign keys more extensively.

But when you start raising the load level, at some point another problem becomes apparent: the locks taken are a stronger than strictly necessary, causing pauses and sometimes deadlocks.

Joel Jacobson of Glue Finance illustrated it with an example in the post referenced above, which can be seen in action in this screencast. His test case was this:

DROP TABLE B;
DROP TABLE A;

CREATE TABLE A (
AID integer not null,
Col1 integer,
PRIMARY KEY (AID)
);


CREATE TABLE B (
BID integer not null,
AID integer not null,
Col2 integer,
PRIMARY KEY (BID),
FOREIGN KEY (AID) REFERENCES A(AID)
);

INSERT INTO A (AID) VALUES (1);
INSERT INTO B (BID,AID) VALUES (2,1);

Process 1:                             Process 2:
BEGIN;
                                       BEGIN;
UPDATE A SET Col1 = 1 WHERE AID = 1;
                                       UPDATE B SET Col2 = 1 WHERE BID = 2;
UPDATE B SET Col2 = 1 WHERE BID = 2;
                                       UPDATE B SET Col2 = 1 WHERE BID = 2;

In Joel's example, he was getting an unexpected deadlock when session 2 updated the row the second time. Why, he asked, wasn't the process getting blocked the first time around? His initial explanation was incorrect, but the underlying reason for his problem was that that transaction was getting a shared lock on the referenced row (the one on table A), which it really didn't need except to ensure that the row didn't go away — that is, to make sure the foreign key constraint remained satisfied until it could commit.

Put simply, certain operations are blocked when there is no need for it. Consider this simple example:
Session 1:

CREATE TABLE foo (a int PRIMARY KEY, b text);
CREATE TABLE bar (a int NOT NULL REFERENCES foo);
INSERT INTO foo VALUES (42);

BEGIN;
INSERT INTO bar VALUES (42);

Session 2:

UPDATE foo SET b = 'Hello World' ;

Note that session 2 is now blocked. And the reason it's blocked is pretty simple: session 1 is holding a shared lock on the row in table foo, and the UPDATE in session 2 wants to acquire an exclusive lock to be able to modify it.

The pgsql-hackers discussion contained some very useful ideas on how to attack this problem, which is what I intend to do. If you've been affected by this problem and would like to discuss a solution, please let me know in a comment below. I'll be explaining my proposal in a forthcoming article.

---

blog comments powered by Disqus

The old Berkeley Postgres code
Posted Tuesday Nov 9th, 2010 11:17am
by Alvaro Herrera | Permalink

Some days ago, I was reading some patch from the in-progress commitfest, and happened to notice this comment in src/include/tcopprot.h:

 *    This file was created so that other c files could get the two
 *    function prototypes without having to include tcop.h which single
 *    handedly includes the whole f*cking tree -- mer 5 Nov. 1991

The weird thing about this was that there's no tcop.h file on the tree. I thought that it must have been removed somewhere along the long history of code cleanups and rearrangements. I was curious to see what this file looked like, so I went to the very first commit in our CVS, which turns out to be this one in Git. However, it turns out that it's not there either!

So I turned to a quick web search, and found out that Berkeley (or rather the University of California) still has the old tarballs for anyone to grab.

I eventually found the file in the postgres-v4r0 tarball; and as foretold in the old comment above, it clearly includes the whole source tree. Now that that file is long gone, I think it's time to remove that comment.

---

blog comments powered by Disqus