Extending immutability: deletion without losing data
Published on , 4025 words, 15 minutes to read
Tigris has a pretty advanced replication scheme for writes. What happens when you actually need to delete things? Turns out deleting things is hard in distributed systems. Especially when you have a geo-replicated active-active database like Tigris does. We can (and do) use tombstones to mark where data once was, but how do you let people undo an accidental delete?
Tigris wants to turn storage inside out, so our implementation of soft deletion is by giving users the Recycle Bin for objects and buckets. Today we're going to dig into how this works, why it works, and what this gives you in terms of using object storage today.
Recycle bins and you
In Windows and macOS, the Recycle Bin (or Trash can) is a form of purgatory where deleted files wait for their storage to be deallocated by the user. This allows users to hit "delete" fearlessly because if they made a mistake they can just drag it back out and go on with life.
This works great in your local filesystem because there's only one writer in one region. This kinda falls apart when you have multiple regions in your database and any one of them could be writing to it. How do you name things in the recycle bin? How do you handle the conflict of an update happening in one region before the deletion was fully replicated out from another region?
This is the fun of distributed systems, which is the kind of problem space that Tigris lives in.
One way to think about how the Recycle Bin works is that the file metadata gets moved there when the user hits delete. No data bytes move around on the disk, but the file doesn't show up in My Documents anymore. In a distributed systems context you can't just move the metadata around, you have to leave a tombstone behind to record where that metadata once was. This prevents other regions from being confused when actions happen really close to each other in time.
Soft deletes in some universes
At a high level, a soft-delete is when a DELETE action doesn't actually remove the data. When data is soft-deleted, it's still there but just not visible in the main usage flow. This lets you get the data back when a delete is made by accident.
Your database becomes your API
One of the interesting side effects of designing any API is that you end up leaking the internals of how your database works to your users. Many object storage systems were designed with overwriting or deleting data as one of the primary operations, and as such have had to bolt versioning onto the side. For the most part this does work; but once you get into advanced versioning schemes everything starts to fall apart. Tigris doesn't suffer from the same problems because we built immutability into the core from day one, and in immutable systems you have to append new data on the end instead of overwriting data.
At the least, actually storing the data en masse is a boring problem. You put the data somewhere, maybe name it after the checksum of its contents, and then have a daemon make sure it's copied three places. That daemon also handles cases when drives go offline and new ones are added to make sure data is shuffled around the cluster. This is largely a solved problem with projects like Ceph, Longhorn, or other distributed storage systems.
S3 uses delete markers
Some object storage systems like S3 expose platform internals to make soft deletion work. In S3 deleting an object creates a delete marker (tombstone). A delete marker is an explicit marker that the object is deleted and should not be returned in normal operation. Here's what that looks like in practice:
┌───────────────────┐ ┌───────────────────┐ ┌───────────────────┐ ◀── DeleteObject│ v1 │ │ v2 │ │ v3 current ││ report.pdf │ │ report.pdf │ │ report.pdf ││ …198086 │ │ …198088 │ │ delete marker │└─────────┬─────────┘ └─────────┬─────────┘ └───────────────────┘│ │ no data▼ ▼┌───────────────────────────────────────────────────────────────────┐│ sea of data ││ ┌──────────┐ ┌──────────┐ ││ │ v1 bytes │ │ v2 bytes │ ││ └──────────┘ └──────────┘ │└───────────────────────────────────────────────────────────────────┘// the bytes stay. only the newest record says the object is gone.
I don't know how I feel about this flow. Based on reading between the lines in the delete marker documentation it really feels like this is a leaked internal implementation detail of how S3's eventually consistent database works instead of a full fledged feature of the storage system. If I had to choose between leaking internal database details in the API and implementing a higher level API for something complicated like soft deletion, I'd want to implement the higher level API.
Tigris' soft deletes are external references
Let's rethink what soft deletes really are. What if they were like the Recycle Bin in Windows?
Soft-deletes are external references to buckets or objects that live in a different namespace from normal buckets or objects. We implemented them as external references instead of tombstones because this is effectively moving object metadata to the recycle bin. Tombstones mark the data as not being there, but soft-delete markers are a copy of the data that was there. This makes it easy to put the object back in place if you deleted it by mistake.
Garbage collection roots
One way to think about objects and buckets is that they are garbage collection roots for points in the endless sea of data. Any data in the sea without a root anchoring it down is eligible to be deleted. Uploading multiple versions of an object with a forkable bucket creates multiple metadata entries at their different timestamped version numbers. You can then fork a bucket from any one of those timestamps to see what the bucket was like at that point:
every write appends a new version entryv1 v2 ╎ v3 v4┌────────────┐ ┌────────────┐ ╎ ┌────────────┐ ┌────────────┐│ …198086 │ │ …431907 │ ╎ │ …764522 │ │ …055310 ││ 4.1 MB │ │ 4.3 MB │ ╎ │ 4.4 MB │ │ 5.0 MB │└─────┬──────┘ └─────┬──────┘ ╎ └─────┬──────┘ └─────┬──────┘──────┴───────────────┴─────────╎─────────┴───────────────┴───────▶earlier ╎ fork point laterthe fork inherits these ╎ written later — the fork never sees them▼┌──────────────────────────────┐│ uploads/report.pdf ││ current version v2 ││ as of 1775929812004431907 │└──────────────────────────────┘// appending metadata instead of overwriting keeps any past instant addressable.
This would solve the soft-delete problem, but our existing database schema using FoundationDB requires us to enable forking and snapshots at bucket creation time. In essence, we need something that's halfway between what we have (each bucket being a globally mutable namespace) and the bucket forking land of every action being appending metadata onto the end.
To do that, we basically implemented most of that appending metadata on the end trick but to a different place: the soft deletion corner. When you enable soft-deletion and delete an object, its metadata gets moved to the trashcan so you can pluck it back into place:
main table · live keyspace soft-delete keyspace · newest first┌────────────────────────────┐ ┌──────────────────────────────────┐│ uploads/report.pdf │ │ uploads/report.pdf 3rd delete ││ live metadata record │───────▶ │ deleted …768707198086 ││ in ListObjectsV2 output │◀╌╌╌╌╌╌ └──────────────────────────────────┘┌──────────────────────────────────┐│ uploads/report.pdf 2nd delete ││ deleted …412888100731 │┌────────────────────────────┐ └──────────────────────────────────┘│ uploads/notes.md │ ┌──────────────────────────────────┐│ untouched by the delete │ │ uploads/report.pdf 1st delete │└────────────────────────────┘ │ deleted …104233715492 │└──────────────────────────────────┘───────▶ DeleteObject moves the record out — one entry per delete◀╌╌╌╌╌╌ RestoreObject moves the same metadata back// the bin entry is a copy of the metadata, not a marker. restoring is a move.
It's the same basic idea as the recycle bin on your desktop. Any buckets or
objects left in the recycle bin for long enough become eligible to be deleted,
which then makes the backend go and securely erase things. Effectively, any bits
of metadata in the soft deletion corner are still considered garbage collection
roots, they're just not shown when you do a normal ListObjectsV2 call.
Distributed systems are fun*
The real fun comes into play when you remember that Tigris has a globally replicated active-active database where any region can change any object at any time. Most of the time things work out and objects are replicated without too much strife. The annoying part comes when two events are ordered weirdly. Imagine a scenario where one agent in one datacentre deletes an object after another agent in another datacentre:
ORD (Chicago) IAD (Ashburn)┌──────────────────────────┐│ PutObject · agent A ││ uploads/report.pdf │ ──── replicates PUT ────▶│ t = …768707198086 │└──────────────────────────┘┌──────────────────────────┐│ DeleteObject · agent B │◀── replicates DELETE ── │ uploads/report.pdf ││ t = …768984210773 │└──────────────────────────┘ORD applies PUT ▸ DELETE deleted, as expectedIAD applies DELETE ▸ PUT the put looks brand new// two writers, one key. the regions disagree about whether it exists.
How would this replicate out? Well for one each change is timestamped by when it's done in terms of Unix nanoseconds, so the replication messages kinda look like this:
produced first produced 277 ms later┌──────────────────────────────────┐ ┌──────────────────────────────────┐│ uploads/report.pdf │ │ uploads/report.pdf ││ op: PUT │ │ op: DELETE ││ LastModified 1775929768707198086│ │ LastModified 1775929768984210773││ block 0x3f2ac701 · origin ORD │ │ block 0x3f2ac701 · origin IAD │└──────────────────────────────────┘ └──────────────────────────────────┘last write wins984210773 is greater than 707198086// the delete carries the newer LastModified, so the delete survives
This means that in theory, a user could DELETE an object before an update is processed by another region, and that would make the regions disagree about if the object exists or not. This is a horrible state to be in and usually requires support intervention or to recreate/re-delete the object.
The root cause boils down to deleting objects actually deleting metadata from the database doesn't scale past a single region. Updates to metadata include the entire metadata object, so if you delete it locally and a new version is pushed remotely, the object will gain the remote state.
We don't want users to have to deal with that, so we added the concept of anti-resurrection to Tigris. Any write to an object must prove it is newer than the deletion.
ORD · agent PutObject IAD · user DeleteObject┌──────────────────────────┐ ┌──────────────────────────┐│ uploads/report.pdf │ │ uploads/report.pdf ││ new version · v2 │◀─────────────│ row deleted · marker kept││ t = 15 │ delete │ tombstone t = 25 │└────────────┬─────────────┘ └────────────┬─────────────┘└────────────────────┬────────────────────┘▼┌────────────────────────────────────────────────────────────┐│ at IAD: is the write newer than the marker? ││ write t = 15 · marker t = 25 · is 15 > 25 ? ││ no — not strictly newer, so the write is dropped ││ equal timestamps lose too · the guard runs for every bucket│└────────────────────────────────────────────────────────────┘// without the marker, an empty slot looks exactly like a key that never existed.
In this circumstance, a user sent a DeleteObject request to the IAD datacentre at time 25, but an agent sent a new version of the object with PutObject to the ORD datacentre at time 15. The user's delete is newer than the agent's put, so the new version is rejected and the delete gets sent back to ORD.
Using soft deletes
Tigris extends the S3 API by having users add headers to their requests. For example, to create a bucket with soft deletion enabled:
import (
"context"
"github.com/aws/aws-sdk-go-v2/aws"
"github.com/aws/aws-sdk-go-v2/service/s3"
"github.com/tigrisdata/storage-go"
)
client, err := storage.New(ctx,
storage.WithGlobalEndpoint(),
storage.WithAccessKeypair(
os.Getenv("TIGRIS_STORAGE_ACCESS_KEY_ID"),
os.Getenv("TIGRIS_STORAGE_SECRET_ACCESS_KEY"),
),
)
_, err := client.CreateBucketWithSoftDelete(ctx, &storage.CreateBucketWithSoftDeleteInput{
CreateBucketInput: &s3.CreateBucketInput{Bucket: aws.String("my-bucket")},
RetentionDays: 30, // 0 uses the 7-day default
})
Or to list soft-deleted objects:
out, err := client.ListSoftDeletedObjects(ctx, &storage.ListSoftDeletedObjectsInput{
Bucket: "my-bucket",
Prefix: "uploads/",
})
if err != nil {
return err
}
for _, o := range out.Objects {
log.Printf("%s v=%s %d bytes deleted=%s", o.Key, o.VersionID, o.Size, o.LastModified)
}
Or to permanently delete one soft-deleted version:
_, err := client.PermanentlyDeleteObject(ctx,
"my-bucket", "uploads/report.pdf", "1775929768707198086")
When you have a soft-delete enabled bucket, you can also forcibly delete an entire bucket:
_, err := client.ForceDeleteBucket(ctx, &s3.DeleteBucketInput{
Bucket: aws.String("my-bucket"),
})
Warning
If you use this call on a bucket that doesn't have soft deletion enabled, you have permanently deleted your bucket. Please call this with care. Support cannot help you if you use this call wrongly.
And then bring it back from the dead:
trash, err := client.ListSoftDeletedBuckets(ctx, nil)
if err != nil {
return err
}
for _, b := range trash.Buckets {
log.Printf("%s (%d day retention)", b.Name, b.RetentionDays)
if _, err := client.RestoreBucket(ctx, &storage.RestoreBucketInput{Bucket: b.Name}); err != nil {
return err
}
}
Now what?
Object storage entered our stacks as an unlimited FTP server we all used for
backups. A distressing amount of the world's most important data lives in object
storage buckets because it's the best place to put it. This is why having an
"undo" button matters, it's what makes it safe to trust your backups in the
cloud. To err is human, and mistakes are a "when" to plan for, not an "if" that
you hopefully never have happen. The blast radius of one overly wide
--recursive flag is measured in years of people's lives.
One of the biggest usecases that comes to mind is ransomware prevention. Imagine a case where an attacker downloads everything in your bucket, deletes it, and asks for a ransom to send you the files back. With Tigris, soft deletes means that the ransom can be ignored, you can un-delete your data, and be on your merry way with incident response. The other big usecase is for agents, where they somehow get the idea that deleting production data is the right way to solve a problem. Both cases mean you need a quick and fast way to go back to before things went wrong.
If you want true isolation instead of recovery, that's why we have bucket forking. Bucket forking needs to be enabled before a bucket is created, but you can enable soft deletion on any bucket in the dashboard whenever you want.
Every storage system is going to make you choose between ones that hide how the platform works and ones that expose the gorey internals to users. I think that hiding the internals and exposing the high level operations built on top of them is the right way to go, if only because the higher level operations are much easier to make safe in our globally distributed future.
Enable soft delete on any Tigris bucket, new or existing, and every delete becomes recoverable for up to 90 days. Restoring a whole bucket is one call. Read the soft delete docs.
Facts and circumstances may have changed since publication. Please contact me before jumping to conclusions if something seems wrong or unclear.
Tags: