Alternator: support TTL

[nyh]

This issue is about supporting DynamoDB's TTL feature, which is very different from the Scylla feature of the same name:

While Scylla's TTL allows individual column values to be expired, DynamoDB's TTL is different - it specifies expiration times for entire items.
DynamoDB’s TTL works by specifying with UpdateTimeToLive, for each table you want TTL for, the name of an attribute which will hold an item’s expiration time - in seconds since the Unix epoch. An item with this attribute set to a time older than the current time will eventually be deleted. The DescribeTimeToLive operation can be used to inquire about a table’s TTL setting.
The TTL documentation explains that “a background job checks the TTL attribute of items to see if they are expired.”. We could do this too, and maybe have to do it - although it is inefficient.

Considering Scylla already has compaction and processes in place to expire data, it would be nice if we could reuse those. We can perhaps do something like this: add to the table a TTL column (in addition to the map we always have). When an UpdateItem or PutItem operation changes an item’s chosen TTL attribute (we know its name), also put this value into the TTL column with the same time also as timestamp. During compaction, if the Unix time specified in the TTL column has passed, we add a row tombstone (i.e., a range tombstone) with the column’s timestamp. However, there’s a big difficulty to correctly support the changing of an item's TTL. The problem is that a non-major compaction may not see all the data, so see an old TTL value and decide to delete data based on this old TTL value. We may need to do this TTLing only if we're sure the compaction includes all the sstables with item (as we do today in tombstone GC). Also since this node may have missed a TTL update, we need to be sure a repair happened, so we need to wait for GC grace period (exactly as we do in tombstone GC). Another option is to have a new additional primary-key bloom filter. I’m worried that this last option is an overkill for just the TTL feature, and will also be inefficient (and have high false positives) when there are many small sstables (e.g., LCS).

[nyh]

By the way, as noted by @amoskong and @fastio, the Redis API also has a per-item (not per-cell) TTL, which will need a similar feature:

• https://redis.io/commands/expire (set ttl of one key)

• https://redis.io/commands/ttl (read ttl of one key)

The above documentation says that expiration may be delayed by only 1ms after the specified expiration time. Because we obviously can't find and delete expired data with such accuracy, we will need to check for the possibility of expiration in every read - so that even if expired data is not expunged from disk yet, it's at least not returned.

Note that this read-time check is not necessary in Alternator - the DynamoDB documentation https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html explains that an item may be deleted an unspecified long time ("typically" up to 48 hours) after it was requested to be expired - and until the final deletion the expired items can still be read and modified (and it's even possible to change their expiration time, to cancel their would-be deletion).

[nyh]

An idea on how to implement the TTL feature quickly but somewhat inefficiently:

Now that Alternator uses LWT for every write and writes are substantially slower, one way we can implement the TTL feature over the existing Scylla TTL is by making every write a read-modify-write operation, as detailed below. Note that an LWT write which needs to read is a bit slower than an LWT write that doesn't read, but probably not much slower.

1. When an UpdateItem modifies the TTL attribute (and possibly other attributes as well), we read the entire item and write it again with a different TTL on all its attributes.
2. When an UpdateItem modifies other attributes but not the TTL, we read the TTL column first to know which TTL to put on the new mutation.
3. When PutItem is used, we know the entire item is replaced so we don't need to read at all.

[nyh]

We just had an interesting discussion on the mailing list - see https://groups.google.com/g/scylladb-dev/c/Ddv31GGB9pI - on the the compaction-based implementation, some implementation details and possible pitfalls, and how it would work for the Alternator and Redis APIs.

[slivne]

The implementation needs to take into account more aspects:

https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/howitworks-ttl.html

"
As items are deleted from the table, two background operations happen simultaneously:

Items are removed from any local secondary index and global secondary index in the same way as a DeleteItem operation.

A delete operation for each item enters the DynamoDB Stream, but is tagged as a system delete and not a regular delete. For more information about how to use this system delete, see DynamoDB Streams and Time to Live.
"

1. DynamoDB TTL also remove GSI and LSI and its not clear if the TTL column is projected into the MV.

2. DynamoDB TTL has an effect on whats recorded in the DynamoDB Streams

3. DynamoDB allows updating the column that is used for TTL and allows to enable / disable this feature.
   (https://docs.aws.amazon.com/amazondynamodb/latest/developerguide/time-to-live-ttl-before-you-start.html#time-to-live-ttl-before-you-start-notes)

This has implications on how we can add support for this feature (e.g. entering future tombstones can't be done).

[avikivity]

Right. Since our views/indexes are coordinator-managed, this is hard to do.

[psarna]

@avikivity as for secondary indexing, isn't it enough to always include the special TTL attribute in the underlying materialized view as well? It will receive all updates via existing mechanisms, and the garbage collection process could then just treat materialized views just as normal tables, removing the rows once they expire.

[psarna]

DynamoDB TTL docs also mention that:

You cannot reconfigure TTL to look for a different attribute. You must disable TTL, and then reenable TTL with the new attribute going forward.

, which would mean that when reenabling TTL, we'd have to add a column to existing views (which is not legal via CQL, but sounds possible by just upgrading the view schemas). In any case, we could start with one-shot TTLs that cannot be disabled and reenabled to another column, for simplicity's sake.

[avikivity]

@avikivity as for secondary indexing, isn't it enough to always include the special TTL attribute in the underlying materialized view as well? It will receive all updates via existing mechanisms, and the garbage collection process could then just treat materialized views just as normal tables, removing the rows once they expire.

I think it should work. Auto-project the TTL attribute to the index.

Requires a read-before-write, but we're heading in that direction anyway (and indexes already do that).

[avikivity]

DynamoDB TTL docs also mention that:

You cannot reconfigure TTL to look for a different attribute. You must disable TTL, and then reenable TTL with the new attribute going forward.

, which would mean that when reenabling TTL, we'd have to add a column to existing views (which is not legal via CQL, but sounds possible by just upgrading the view schemas). In any case, we could start with one-shot TTLs that cannot be disabled and reenabled to another column, for simplicity's sake.

We could launch an index rebuild job (similar to the existing job, but just copies the TTL attribute).

[slivne]

On Sun, Dec 6, 2020 at 5:52 PM Avi Kivity ***@***.***> wrote: @avikivity <https://github.com/avikivity> as for secondary indexing, isn't it enough to always include the special TTL attribute in the underlying materialized view as well? It will receive all updates via existing mechanisms, and the garbage collection process could then just treat materialized views just as normal tables, removing the rows once they expire. I think it should work. Auto-project the TTL attribute to the index. Requires a read-before-write, but we're heading in that direction anyway (and indexes already do that).

Projection is needed for correct result computation not for deletion. Deletion should be done via the base table updates (like any other operation in MV/SI) - if the base table row is deleted the MV/SI will be deleted as well. —

…

You are receiving this because you commented. Reply to this email directly, view it on GitHub <#5060 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA2OCCFR5HA63HTWF3LO2J3STOSE3ANCNFSM4IYEE5JQ> .

[slivne]

On Sun, Dec 6, 2020 at 5:53 PM Avi Kivity ***@***.***> wrote: DynamoDB TTL docs also mention that: You cannot reconfigure TTL to look for a different attribute. You must disable TTL, and then reenable TTL with the new attribute going forward. , which would mean that when reenabling TTL, we'd have to add a column to existing views (which is not legal via CQL, but sounds possible by just upgrading the view schemas). In any case, we could start with one-shot TTLs that cannot be disabled and reenabled to another column, for simplicity's sake. We could launch an index rebuild job (similar to the existing job, but just copies the TTL attribute).

We should test out how TTL update works in DynamoDB and see how it operates when switching the TTL column to better understand what approach we should take. We should check the edge cases what happens in MV/SI if the column is not used as part of the projection and the TTL expires does the MV/SI work or not. What happens when the column is changed does the MV/SI work under a changed column or not. I am not sure the rebuild approach suggested will work - during rebuild the index is not avail We need to be able to have two indexes - current one and new one and switch between them once rebuild is done. We do not have that capability today. An alternate approach is for DynamoDB is to always include in the SI/MV an additional TTL column (even if the column is projected in the MV/SI). That column will hold the copy of the column used for TTL - if the column is changed and is not part of the MV/SI projected columns its not an issue we have a place to store the value. If the TTL column is updated to be empty / another column a full scan will be done updating the TTL column data in the View/SI (this will be a background process - similar to rebuild). As the rebuild/update will be long - we can use something like a truncation record for point in time recording from which point TTL info should be considered correct - to help detect records that have TTL value that was not updated and should be considered as non existing. The benefit of this approach is that the MV/SI exists all the time - there is no need to hold duplicate indexing /switch indexing Again, checking what DynamoDB dopes under the edge cases (MV/SI doesn't contain TTL column, MV/SI doesn't contain TTL column - when its first set) - will help understand what they used in their implementation and direct us to a compatible solution aligned with how they support TTL column changes.

…

— You are receiving this because you commented. Reply to this email directly, view it on GitHub <#5060 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA2OCCCODRPJZRGFPZSSFELSTOSIBANCNFSM4IYEE5JQ> .

[nyh]

Started to work on this feature. A draft pull request - currently including just tests - is in #8564.

[nyh]

At this point, we already have support for TTL in Alternator, although it is still marked "experimental".
I think it's time to close this issue, and instead open issues for specific things that need to be fixed or improved in this feature, of course with the goal of graduating it from "experimental" to GA.