Race condition when allocating followup sequence numbers in an issue

I don't really like my idea because I like spam to vaporize, but I thought it might add to the brainstorm.

When I get spam on one of my YouTube videos and I go moderate it, I click a spam button and the comment collapses. I often find they don't delete the spam right then and when I come back, the spam is still there, but collapsed. Maybe there's a short-term CSS solution that way?

How about D) but adding some more logic to it: When the comments are rendered some code checks for potential (rare) duplicated id's and adds something after it in that case: e.g #2a, #2b (in the case of two comments with #2).

It sounds like you want to calculate the next comment # when the form is rendered. Can't we solve the problem by calculating the next comment # right before the insert happens as part of the same query:

insert into {whatever_table} values (form_stuff, form_stuff2, (select count(1) from {commenttable} where stuff), etc)

Is this still the race condition you're talking about?

fajerstarter: I really liked your idea about #2a, #2b, #2c until I realized it has exactly the same problem we are trying to solve. If in #4 I refer to #2c and later on #2b gets deleted, the old #2c will now be #2b so my reference will be wrong.

The MySQL manual (end of section 1.9.5.3) suggests a way to fake row-level locking, which would allow option (c) to work (create a next_comment_number column in the issue table) without locking or transactions:

With MyISAM tables, you can use a flag column in the table and do something like the following:

UPDATE tbl_name SET row_flag=1 WHERE id=ID;

MySQL returns 1 for the number of affected rows if the row was found and row_flag wasn't 1 in the original row. You can think of this as though MySQL Server changed the preceding statement to:

UPDATE tbl_name SET row_flag=1 WHERE id=ID AND row_flag <> 1;

This adds two extra update queries to every followup, though.

I'm sort-of inclined to ignore the problem and allow the rare set of comments with the same sequence number. It won't happen very often and, when it does, followups can refer to "#2-bjaspan" or "#2-dww" as that designation will be right even if "#2-spammer" gets deleted. If a single user intentionally hits the race condition to create multiple followups with the same number by the same author, they are certainly all spam and no one will want to refer to them anyway.

bjaspan: So true. Although it could still be an improvement since rare (race) + rare (deletition) = rarer.

Maybe it's too costly but instead of just rendering the "2a" with some logic it could also be saved to the database, making it "sticky".

I agree that "#2-bjaspan" adoption might make this a non-issue.

Just how often would a follow up be deleted, anyway? If it happens once a week or less (I see decidedly little true spam in follow-ups), then I think that's something we can live with. If it happens daily or more, then it's probably worth the effort to close that race condition hole.

I did not think the row_flag trick depended on MyISAM, that was just given as an example because MyISAM does not have row-level locking. I assume (!!!) that all databases can tell you how many rows an UPDATE query modified. No?

@crell: The race condition doesn't depend on the number of deletions in an issue at all. If ANY two people submit a follow up to ANY issue at the same time, they're going to be fighting over the next number in the list, and could both end up with the same number.

OK, I misunderstood the problem here then. Two people replying to an issue at about the same time does happen often enough to worry about, and is likely to only happen more in the future. :-)

This sounds like a case where having a non-primary-key sequence system would help after all. ;-/

Emulate Drupal 6 and use auto_increment and update the comment once you have the id.

One could argue that this issue is not specific for the project module, or project issue module for that matter. If I have a discussion in a forum topic, I might also want to use similar comment numbers to refer to someone else comment. If there is a simple way to implement this as part of the comment module in core, I might be willing to let this slip in for Drupal 6. I'm just floating the idea, I don't have definite answers yet, and I'd like to see this discussed first.

You might want to check with the DB powers-that-be on the future of db_affected_rows(). I was using it in my SoC project and someone on IRC mentioned that it was supposed to be on the way out since it's not supported by all databases...?

http://api.drupal.org/api/function/db_affected_rows/6

db_affected_rows() is still around in D6. db_num_rows() was removed. I expect that in D7 db_affected_rows() the function will go away but the functionality will remain in some other name. It's safe to use if necessary.

If we were to do it for comments generally, it could be an easy toggle in the config whether or not to display a "local id". Probably even per-node-type. dww is right, though, that it could be tricky to do. After all, we're again trying to generate a unique sequence number without relying on an auto-increment field, so we're right back where we started, just storing the value elsewhere.

Hm, although what about something like this (properly written, anyway):

INSERT INTO comments (nid, local_id, ...) VALUES ($nid, (SELECT MAX(local_id) FROM comments WHERE nid=$nid)+1, ...)

Would that be sufficiently atomic?

(And I just realized I wrote a query that my insert-builder for D7 wouldn't be able to handle yet. Bah!)

#24: Logically, that nested query should not be atomic; there is nothing that prevents two queries from issuing the sub-query, getting the same answer, and inserting the same value into separate rows. In practice, it of course depends on the dbms implementation. In a multi-master arrangement, I'm sure it wouldn't be. I certainly wouldn't want to depend on it.

dww, i don't think that' anythings been lost by getting rid of db_next_id(). since the id would be specific to each node rather than each table you'd have been mis-using the function to a certain extent. and it locks as you said you wanted to avoid. since you're locking a table you might as well lock the project comment table and compute MAX() + 1 for the new comment number.

one thing we'll need to guard against w/ the poor man's LOCK is the (hopefully rare) situation where the db marks the row as locked, then fails for some reason to unmark it (unexpected crash, etc). in this case we're going to need a reasonable timeout for a followup trying to obtain the next comment ID.

as i understand it, the advantage of the poor man's lock is that it will be row level, as opposed to locking the whole table, which db_next_id() does.

I think we'd want to study the "poor-man's lock" suggested in the mysql manual much more extensively before using it in a Drupal-wide function that has to work 100% of the time than we would before using it in a project-only function that actually does not matter if it returns a duplicate value. Also, as others have suggested, the study would need to include performance, too.

As for timing out the lock in case of failure, we could change it from a boolean flag to a Unix timestamp:

UPDATE tbl_name SET row_flag=NOW WHERE id=ID AND row_flag < NOW-300

This updates the one row where id=ID if the flag has not been set in 5 minutes, otherwise it updates zero rows.

Of course, if for some reason a process sets row_flag, waits for 6 minutes, then continues operating assuming it has the lock, the lock has failed and we'll get erroneous results.

i don't think that will work -- it doesn't seem to provide a way for a new incoming lock request to know what's going on. i think we would need a combination of a flag and a timestamp to make this kind of thing work.

well for the d.o use case, locking all issues to get a unique number would be a serious performance problem, i think. however, at least on d.o, the number of simultaneous requests to one issue would be low, and collisions would be relatively rare. in most cases it would require two pretty inexpensive queries per followup to do the row level locking -- i see that as the most livable option we have.

Didn't the remove-sequences patch have a viable single-query sequence generator? I could have sworn some iteration of that patch had a non-locking query that worked before we decided to just drop sequences all together.

we need to move this issue forward. in the talk is cheap, code is gold spirit, here's a first stab at the poor man's row lock. after having written it, i can't say that i'm crazy about the iimplementation, but it's at least an attempt that we can work from.

tested this on postgres, and it works, including previews and the upgrade path. haven't tested a clean install, or mysql at all.

I agree that the actual implementation ends up being clunky. Anyway, my first comment is that you need some kind of delay between your tries to get the lock. I suggest that each iteration wait a random number of milliseconds between A and B (so that multiple attempting lockers do not make their second attempt at the same time, too), where A and B also increase each iteration, until some maximum amount of time passes. I'm sure there is an optimal algorithm out there somewhere for choosing the delay ranges.

@bjaspan: how's this look?

That's pretty much what I had in mind.

My late-night-math calculation is that this will wait on average 11 seconds before giving up. I have no idea if that is in the right ballpark or not.

@earnie: Good catch. Not sure how I missed that.

well, i wanted a failing lock to unlock the row. the reasoning is that if a followup can't claim a lock after 11 seconds and 20 tries, then something is wrong with the lock, ie it's stuck. my hope was to eliminate support requests of "i can't submit a followup to issue X." however, given that this will be an even more rare occurance than the race condition (the database failing at exactly the right spot), i suppose it makes more sense to put the unlock where you suggest. attached patch corrects.

i've also added cleanup code for the case of a failed lock. while it probably looks a bit harsh, i see no other reasonable way to do it -- the comment has to be deleted or it will appear in the issue. i tested the code pretty thoroughly, and it works as expected -- the aborted comment is fully cleaned up, and the redirect prevents any additional bogus data from creeping in.

@earnie: i'll buy that. attached patch uses the new column name.

whoop. good catch. lost the forest for the trees... ;)

committed to HEAD. thanks everybody for the help and guidance!