I'm having a hard time understanding the theory here (it was @elcallio, not me, who wrote this code originally), but I think I got it - please let me know if I did:

DynamoDB's notion of "parent" shard (shard is the CDC stream in DynamoDB jargon) has to do only with splits: One shard is split into two (or more). If we assume that are shards are tablets (I don't know why this code does anything relevant with vnodes...) and can only split, then indeed the "parent" shard is the one with the closest start token from (inclusive) the bottom to the new shard's start token.

Anyway, I see that this code here isn't actually new code, it's @elcallio's original code which you moved around. I'll have to apply some "suspension of disbelief" and assume most of this code is correct and look only for really suspicious things.

This is rather extensively tested in alternator_unit_test, including brute force checking all possible combinations for some fixed amount of parents and children.

If i understand DynamoDB correctly, you don't have to have a split to get new shards and parent, you might get new generation just after some time.

Child relationship is to make you drain parent completely before starting to process child. To do this you've a guarantee that if children exists, no more entries will be added to parent. We need this relationship for vnodes (here it serves the same purpose), the implementation is slightly different because vnodes token space wraps around, while tablets don't.

DynamoDB does not, as far as I know, have "generations". They don't get new shards if there isn't a split. At least as far as I know.

I'm not asking why the notion of "Child" exists in DynamoDB - what I'm doubting is why what we did in Alternator - especially for vnodes - makes any sense there, where "generations" can, at least in theory, just mix up all the vnodes and there is not necessarily a single parent (whom you need to drain first) to one new "shard".

https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/Streams.html#Streams.Processing

Because shards have a lineage (parent and children), an application must always process a parent shard before it processes a child shard.

yes, generations is our concept, but it's just our implementation.

They also mention:

Shards are ephemeral: They are created and deleted automatically, as needed.

Generations can mix shards as they wish, but they have to keep lineage correct (token space wise - so for stream shard A "children" stream shards B..Z that cover the same token space must have parent-children relationship set), otherwise it's not going to work (order requirement on reading events will be broken). We're actually relaying on Streams clients using CHILD_SHARDS filtering, as parent relationship is not enough.

This comment (which I know, was preexisting, so it's not your fault) looks self-constricting - if "by doing unsigned compare we inadvertently ...", then why do it? Maybe the comment meant to say "signed compare"?

My english isn't that good, to me this feels not precise, but decently correct. Updated comment.

Did you deliberately decide to use assert() instead of SCYLLA_ASSERT() to make this compile out in release mode?
I don't love this, but it's indeed safer than SCYLLA_ASSERT(). The throwing_assert() I'm now proposing would be better than both.

By the way, I'm curious why you decided to assert end1 <= lo2, and not other possible assertions like lo1 <= end1 and lo2 <= end2. Or is it because wrap-around is possible?

This is developing leftover - i'm used to use assert and it breaks, when running under gdb. The algorithm is messy (even my implementation, which is like 4th version and the best i could come up so far), the assert here checks, that after wrap around two ranges don't overlap (the upper layer should merge them together then).

These two notes are very strange. Why make different assumptions on the two lists?
If you call this function several times, it re-sorts the already sorted current list? Why does this make sense?

That's why the comment is there.

This is the original behaviour (where we sorted parents by signed comparison to be able to find a parent for our shard and we sorted children by unsigned, because that's how we want them to be returned). It is just moved to a function.

You could mess around with comparison function and remove sorting i think. Not sure it's worth it.

I don't know what this comment explains. Better to explain what the test that you did write does.

Added some explanation.

You didn't explain... This "NOTE" explains what was hard to do and what you didn't test yet. But what is this test even about?

Here is what I would have used:

# This test is the most basic check of DescribeStream with ShardFilter set to CHILD_SHARDS. Since there is no cluster changes in this single-node test, there are no shards being closed and child shards being born, so we expect the list of child shards is expected to be empty.

All the other apologetics - why this test isn't more sophisticated - can come afterwards (if at all).

Updated.

Done. Rewrote the comment on test_stream_shard_filtering_simple_no_children to explain: this tests the CHILD_SHARDS filter in a simple case where there's only one generation, so asking for child shards returns nothing. Commit 0020137.

I thought you didn't like to get the ARN from ListStreams, and prefered to use DescribeTable to do it :-)

I copied from the test above. I tried slightly to find out property name to get arn from table (which should be there), but failed, so copied.

You have here multiple tests which create a table and a stream and then just run a silly do-nothing (even failing) command against it. Would have been less wasteful to create a module-scope fixture with this test table, and then the individual tests just use it.

Unfortunately this test file doesn't have such a fixture yet so you'll need to add it.

You need to explain to me what exactly module-scope fixture does? It is created once per module (rather than once per test)?

Yes. "module" is just a test file, and a module-scoped fixture is created when the first test needs it, and destroyed when the test file ends. So if 5 tests use the same fixture, it is only created once.
Here is some untested example code:

# Note: See comments above why DynamoDB has a bug (?) in LATEST making it difficult to use the
# same test-table fixture for multiple tests that do actual CDC data checks. But it should be fine on
# both Alternator and DynamoDB for checking error handling and such
@pytest.fixture(scope="module")
def table1(dynamodb, dynamodbstreams):
     with create_stream_test_table(dynamodb, StreamViewType='KEYS_ONLY') as table:
           yield table

Updated.