Cloud Drive Storage Accounting: Quotas, Trash and Shared Drives

Cloud Drive Storage Accounting: Quotas, Trash and Shared Drives

You've joined the Storage Platform team behind a cloud drive. Customers upload files, every upload of an existing path creates a new version, deleted files sit in a trash, and each account has a byte quota. Billing and support both read the numbers this service produces, so they have to be exactly right: an off-by-one at the trash boundary is a support ticket, and a wrong "read-only" verdict locks a customer out of their own drive. The current service (v0) only *reports* usage and enforces nothing. Three tickets are queued: DRV-1182 (quotas, retention and trash), DRV-1190 (shared drives) and DRV-1203 (a pricing change from Finance). All sizes are integer bytes.

Codebase

How your code is run

run(operations: list[list]) -> list executes the operations in order against a fresh service and returns one result per operation. Every operation is [name, ts, ...args]; ts is an integer number of seconds (>= 0) and never decreases from one operation to the next. Errors are returned as "error: <code>" strings, never raised.

Every request is processed in this order:

1. A request that is not a list of at least two items, whose name is not a string or whose ts is not an integer >= 0 (booleans are not integers) is "error: bad request". The clock does not move.
2. The service clock advances to ts (DriveService.advance). Anything time-based happens here, before the request is looked at any further, even if the request is about to fail.
3. An unknown operation name is "error: unknown operation".
4. Arguments that do not fit the operation (wrong count, wrong type, an invalid path) are "error: bad request". Names (user, drive, prefix, ...) are non-empty strings; sizes, quotas and counts are integers >= 0.
5. The operation's own errors, in the order its table row lists them.

Paths look like /docs/plan.txt: they start with /, have no empty, . or .. segments and no trailing / (see drive/paths.py). A folder is / or a path, and contains only what sits below it (/docs contains /docs/a.txt, not /docs2/a.txt).

Operations available in the starter (v0)

upload_many and delete_many exist so load tests can be written compactly. upload_many performs count ordinary uploads of prefix0 ... prefix{count-1} (prefix is a valid path, e.g. /bulk/f), all of size bytes, each exactly like a separate upload at this ts; a rejected one is counted in rejected and does not stop the rest. With distinct > 0, upload i carries content = "<prefix>c<i % distinct>", otherwise no content. delete_many does the same with delete, skipping paths that are not live. usage_over_time reads usage at samples moments, ts, ts + step, ts + 2*step, ...; every one of them is a real clock tick, so everything time-based (Part 1 rule 6) happens between samples. The service clock then stands at the last sample, and the next operation's ts is never earlier than that. content is an opaque content-hash string (non-empty, or null); until Part 3 it is stored and otherwise ignored.

Part 1 — Retention, trash and quotas (DRV-1182)

Goal: make the quota real. Keep only recent versions, turn delete into a trash that still counts against the quota until it is purged, and put accounts that are over quota into read-only mode. Add restore and empty_trash.

1. Usage is the sum of the sizes of every stored version, of live files and of files in the trash.
2. Retention. A file keeps its newest KEEP_VERSIONS (3) versions. Version numbers start at 1 for a new file, increase by one per accepted upload, and are never reused: after four uploads the surviving versions are 2, 3 and 4. A path that was deleted and is then uploaded again is a new file and starts at version 1 again.
3. Upload order. (a) refuse with read-only if the account is read-only; (b) add the new version; (c) prune the oldest versions beyond three; (d) only now compare usage to the quota: if usage would be greater than the quota, reject with quota exceeded and change *nothing* (no new version, nothing pruned, the version number is not used up). A file at its version limit can therefore be replaced by a similar-sized one even when the account has no spare room.
4. Delete moves the whole file, every version, to the trash and records the timestamp. It frees nothing. A path can be in the trash several times (deleted, re-created, deleted again).
5. Restore brings back the most recently deleted trash item for the path with its version history and version numbers intact (a later upload continues the numbering). Usage does not change. not in trash if the path has no trash item; path exists if the path is live again.
6. Purge. A trash item is permanently removed as soon as ts - deleted_at >= TRASH_TTL (30 days = 2,592,000 s). The boundary is inclusive: at exactly deleted_at + TRASH_TTL the item is gone. Every operation purges for every account first (step 2 above), so a purge always happens before the operation's own checks: an upload at the boundary instant sees the freed space and a restore there finds nothing.
7. empty_trash permanently removes every trash item of the account and returns how many bytes that freed (usage before minus usage after).
8. Read-only. An account is read-only while usage > quota. Usage exactly equal to the quota is fine. Read-only refuses upload only (even a 0-byte upload, even one that would prune the account back under quota); delete, restore, empty_trash and set_quota keep working. It ends the moment usage is <= quota again (a purge, empty_trash, a bigger quota...). set_quota can lower a quota below current usage, which is how this state arises.
9. Scale. Grading includes accounts with thousands of files and trash items and thousands of operations after them. Usage is consulted by every upload and every purge runs on every operation, so neither may rescan the file tree or the whole trash each time.

Worked example 1

[["create_user", 1, "alice", 100],
 ["upload", 2, "alice", "/a.txt", 40],
 ["upload", 3, "alice", "/a.txt", 30],
 ["usage", 4, "alice"],
 ["delete", 5, "alice", "/a.txt"],
 ["usage", 6, "alice"],
 ["upload", 7, "alice", "/b.txt", 40],
 ["empty_trash", 8, "alice"],
 ["upload", 9, "alice", "/b.txt", 40],
 ["status", 10, "alice"]]

returns

[true, 1, 2, 70, true, 70, "error: quota exceeded", 70, 1, {"used": 40, "quota": 100, "read_only": false}]

Deleting /a.txt freed nothing (70 bytes still in trash), so the 40-byte upload is rejected; emptying the trash frees 70.

Worked example 2 (quota 100, /f uploaded as 30, 30, 30, then 20)

[["create_user", 1, "alice", 100],
 ["upload", 2, "alice", "/f", 30], ["upload", 3, "alice", "/f", 30], ["upload", 4, "alice", "/f", 30],
 ["upload", 5, "alice", "/f", 20],
 ["usage", 6, "alice"], ["versions", 7, "alice", "/f"],
 ["upload", 8, "alice", "/g", 25]]

returns

[true, 1, 2, 3, 4, 80, [[4, 20], [3, 30], [2, 30]], "error: quota exceeded"]

The fourth upload briefly makes 110 bytes, but version 1 is pruned before the quota check, leaving 80.

Part 2 — Shared drives (DRV-1190)

Goal: teams get shared drives with their own quota. A file in a shared drive is charged to the drive, never to whoever uploaded it, and files can be moved between a user's My Drive and the shared drives they belong to.

Drive names always start with d/ ("d/eng"; "d/" alone and names without the prefix are bad request), and no *user* name may start with d/ (create_user returns bad request). add_member is idempotent. set_quota also accepts a drive name (unknown drive if it does not exist; any name starting d/ is a drive).

1. Drive argument. upload, delete, restore, empty_trash, versions, list (after folder; pass null for the whole drive), largest, usage, status, upload_many, delete_many and usage_over_time take an optional last drive argument. Without it (or null) they act on the user's My Drive, as before. With it they act on that drive's files, trash and quota.
2. Access. The check order for any operation with a drive is: unknown user, unknown drive, not a member; then the operation's own errors. Every member may do everything. Membership is never removed.
3. Everything in Part 1 applies per account: version retention, trash, purge, read-only and the upload procedure work identically for a drive, using the drive's quota. A user's read-only state does not affect their uploads to a drive and a read-only drive does not affect anyone's My Drive. Users never get charged for what they upload to a drive.
4. A drive's trash is shared: any member can restore or empty it.
5. move(user, path, source, target) moves one live file, with its entire version history and numbering, from source to target. Each of source and target is "me" (the user's My Drive) or a drive name. Usage moves with it: the source is credited, the target is charged for all of the file's stored versions. Trash items for the same path stay where they are.
6. move checks, in order: unknown user; resolve source completely (unknown drive, then not a member), then target the same way; same scope if they are the same account; not found (no *live* file at path in the source); path exists (a live file at path in the target); read-only (the target account is read-only, even for a 0-byte file; a read-only *source* may move files out); quota exceeded (target usage after the move would be greater than its quota). A rejected move changes nothing at all. An argument that is not "me" or a valid drive name is bad request.

Worked example

[["create_user", 1, "alice", 100], ["create_user", 1, "bob", 100],
 ["create_drive", 1, "d/eng", 100], ["add_member", 1, "d/eng", "alice"], ["add_member", 1, "d/eng", "bob"],
 ["upload", 5, "bob", "/spec.md", 70, null, "d/eng"],
 ["usage", 6, "bob"],
 ["usage", 7, "alice", "d/eng"],
 ["upload", 8, "alice", "/plan.md", 40, null, "d/eng"],
 ["upload", 9, "alice", "/notes.md", 20],
 ["move", 10, "alice", "/notes.md", "me", "d/eng"],
 ["upload", 11, "alice", "/big.bin", 50],
 ["move", 12, "alice", "/big.bin", "me", "d/eng"],
 ["status", 13, "alice", "d/eng"],
 ["status", 14, "alice"]]

returns

[true, true, true, true, true, 1, 0, 70, "error: quota exceeded", 1, true, 1, "error: quota exceeded",
 {"used": 90, "quota": 100, "read_only": false}, {"used": 50, "quota": 100, "read_only": false}]

Bob's 70 bytes are charged to d/eng, not to Bob. The /notes.md move fits (70 + 20 = 90); the /big.bin move would reach 140 and is rejected whole.

Part 3 — Deduplication (DRV-1203)

Goal: Finance is changing how storage is billed: identical content is charged once. This replaces the "every stored version counts in full" rule from Part 1 and changes what "freeing space" means. Every earlier operation must keep working under the new accounting.

content on upload / upload_many is now meaningful. It is a content hash: two stored versions with the same hash within the same account are byte-for-byte identical.

1. Usage of an account is the sum of the size of each *distinct* content hash stored in the account, plus the sizes of all stored versions that have no content hash (null). "Stored" means any version, of any file or any path, live or in the trash. Different accounts never share: each user's My Drive and each drive deduplicates on its own.
2. A hash has one size. While a hash is stored in an account, an upload (or a move into that account) carrying that hash with a *different* size is rejected with content mismatch. It is checked after read-only and before quota exceeded (for move: after read-only, before quota exceeded, as part of the same order as above). Once no version with the hash is stored, it may reappear with any size.
3. Upload keeps the Part 1 procedure, with usage as defined here: add the new version, prune, then compare the resulting usage to the quota. Bytes of a pruned version are released only if no other stored version in the account carries the same hash, and the new version's hash counts as stored even if the version it replaces carried the same one. A duplicate costs nothing, so it is accepted even when usage equals the quota (but a read-only account still refuses it).
4. Freeing. Pruning, purging and empty_trash release bytes only for hashes that are no longer stored by any remaining version. delete still frees nothing (the trash holds the references); restore changes nothing. empty_trash returns the bytes that were actually freed, which can be less than the size of what it removed, down to 0.
5. move charges the target only for hashes it does not already store, and credits the source only for hashes that no other stored version in the source (live or trash) still holds. Quota and read-only checks use these dedup-aware numbers.
6. New operation savings(user, drive?) returns logical - usage, where logical is the sum of the sizes of all stored versions (live and trash) counted without any deduplication. Errors as for usage.
7. largest is unchanged: a file's size is still the plain sum of its stored versions.

Worked example

[["create_user", 1, "alice", 100],
 ["upload", 2, "alice", "/a", 40, "h1"],
 ["upload", 3, "alice", "/b", 40, "h1"],
 ["usage", 4, "alice"], ["savings", 5, "alice"],
 ["delete", 6, "alice", "/a"], ["empty_trash", 7, "alice"],
 ["delete", 8, "alice", "/b"], ["usage", 9, "alice"],
 ["empty_trash", 10, "alice"], ["usage", 11, "alice"]]

returns

[true, 1, 1, 40, 40, true, 0, true, 40, 40, 0]

Both files share one 40-byte blob. Emptying the trash after deleting /a frees nothing because /b still holds the content; only after /b is gone and the trash is emptied do the 40 bytes go.

Running the tests

tests/ holds the example tests you can run locally. Grading runs your run against the hidden cases for all three parts, including everything from earlier parts after later ones are in place.