What assertion would you have used in this case? For every comment you'd have to iterate through all it's parents to check if there is a cycle, which seems pretty inefficient to do for something that should never happen (there are other ways that you could check for this problem as you go, but the only other ways that I can think of require holding extra state just in order to perform the assertion).

I'm for assertions when they are simple and don't cost much (especially during development), but it's not feasible to check every condition that should not happen.

You could assert a limit on depth, perhaps. Then the cycle would still exist but after X number of comments, the rendering ends.

This is a reasonable solution. While it will (almost) never provide the correct result (it might print out a cycle of comments until X is reached, or it might cut off a very long but legitimate comment thread), it would provide a reasonable guarantee on this sort of problem not generating infinite pages.

At the risk of being accused of flame-baiting, I'd say it's the engineering solution rather than the mathematical one.. ;-)

For some reason I tend to be a fan of the "stick it in a secure box" rather than "get it right in the first place" approach..

typically, if you're operating upon a particular comment, you've gotten there by traversing to it from the parent. Ensuring that traversals don't encounter cycles is easy, keep hold of a hashtable (or a set) of comment ids as you traverse. As the traversal encounters a comment, its id is added to the hash, and as you complete traversal of each comment, the id is removed. If you encounter an id that's already in the set, assertion failed - or better yet, log the condition and then cease the traversal. That way everything keeps running and the error is visible in the logs.

If the code is organized (as it should be) such that all functions which require traversal of hierarchical comments pull this from a single function, then the hash check only need be applied in that one place in the code, where it need not be visible anywhere else.

>iterate through all it's parents to check if there is a cycle,which seems pretty inefficient to do for something that should never happen

The number of parents is almost always under 3 or 4 and never over 100. Writes occur a few times a second at peak. You are prematurely optimizing.

The kind of assertion he needed though, could only be ensured by the database, not application code (my impression).

Agreed, infinite loops are a little hard to protect using asserts.

When I hit the first infinite loop bug on a code path, I frequently add code to assert that the number of calls is less than $A_LARGE_NUMBER to catch future occurrences of the same root cause.

I dimly remember a language that just hard-limited loops. I thought it was John Pane's HANDS system, but I can't seem to find a reference in the thesis...can anybody refresh my memory?

http://www.cs.cmu.edu/~pane/research.html

http://www.cs.cmu.edu/~pane/thesis/

Pretty cool work regardless, I really like the way it deals with aggregates, for example.

This is similar to the "while with timeout" that is common in embedded code (of course, watchdogs are better...)

> Agreed, infinite loops are a little hard to protect using asserts.

    assert(is_tree(comment_graph))

Typically, a composite entity (like an "item" on HN which has many "comments") will define invariants to ensure data integrity. In this case, the invariant is that an "item"'s comments form a tree.

The database layer often contains this logic, but it depends on how you're building your application; NoSQL backends for example typically must put validation in the application layer. Since HN just uses files, a well-developed application layer should be riddled with invariants like this.

The kind of assertion he needed could not be ensured by the database. The kind of assertion he needed was there are no cycles in the graph. How would you ensure that in a database?

Also, HN uses flat files, not database.

A constraint on the parent-child link table "Child creation time stamp > Parent creation timestamp" would do it.

Might not be a bad idea, if the site were to have the two requirements "maintenance must be done on the live site from a repl" and "5 nines availability".

How are you modelling your data? I think this should be a self reference.

    create table post (id int primary_key, parent_id int references post(id), child_id int references post(id), created_at timestamp)

How will you place the check constraint? You only have parent_id and child_id, not parent and child entities. You will have to write a trigger.

I am not saying this can't or shouldn't be done. I am saying a db won't directly solve it.

However, you example will work perfectly for enforcing constraints in the code via the mutator which can compare child and parent timestamps, provided pg was doing it via a mutator, and not directly changing the ids.

Following http://stackoverflow.com/questions/3438066/check-constraint-..., and assuming that ID's get doled out in increasing order:

    create table post (
      id int primary_key,
      parent_id int references post(id),
      CONSTRAINT foo CHECK (id > parent_id)
    );

I was thinking something like (supposing the comments were stored as "closure tables" like Karwin suggests):

  CREATE TABLE comment_tree (
   ascestor_id REFERENCES comments(id) NOT NULL,
   descendant_id REFERENCES comments(id) NOT NULL,
   CHECK ( ascestor_id <> descendant_id )
  )

but I'm probably overlooking something. (I'm aware that HN uses flat files, I was just making a counter-point to the "simple assert" solution...)

That will prevent a child being its own parent. It won't work for more than one level i.e a post being its own grandchild. Assume (post_id, parent_id) sequence: (1, 3) -> (2, 1) -> (3, 2).

you can assert that "post_id > parent_id", assuming comments are always created subsequent to the creation of their parents (as is the case here) and that integer identifiers are always increasing (otherwise use timestamps). (1, 3) above would indicate an invalid case (not necessarily a cycle, but a precondition for one).

Please note that the "Closure Table solution involves storing all paths through the tree, not just those with a direct parent-child relationship."

My bad. I was speed reading, and didn't read the "Closure Table" part.