haasn commented

(Migrated from github.com)

Mainly for the record. As we've discussed before, my previous algorithm for choosing the file retention based on the
filesize alone has some short-comings:

It fails to down-scale to a low volume server. If there are not enough uploads per second, then the retention period is too short, leading to files being deleted even if there is plenty of space left.
It fails to up-scale to a high volume server. If there are too many uploads per second, disk space will run out requiring manual re-tuning from the administrator.
It doesn't take into account the difference between a popular file and an unpopular one. Deleting an unpopular file is generally preferred to deleting a popular file.

Having though about these problems a bit, I've come up with some methods of potentially addressing these shortcomings

Method A: Priority Queue

Instead of tracking a retention time, insert files into a big priority queue based around their “score”. This score could be assigned as a function of the time (preferring younger files) and filesize (preferring smaller files), and it could also be dynamically updated on hits (preferring more popular files). This would have O(log n) behavior for all operations.

Whenever the free space drops below a threshold, make space by going through the priority queue, vacuuming up the files with the lowest score first, only stopping once there's room. The main downside with this approach is that it would be potentially very difficult to come up with a good “balance” for the factors feeding into the calculation of the score, and would require some manual tuning and evaluation.

It could be made resistant to flushing/DoS by ensuring that there's an upper bound on how much popularity you can generate with a brand new, or very large, file, but I think it's ultimately a problem that will be hard to solve.

Method B: Dynamic Retention

A simple method of solving problems 1 and 2 would be to just adjust the retention curve as a function of the current disk capacity. If the disk is close to 0% full, files would be very long-lived. As the disk gets closer and closer to 100% full, files would get shorter lived and shorter lived. As long as the popularity of a server only changes slowly, this would allow the algorithm to self-tune in order to keep the capacity at some reasonable usage level, like 90%.

The downside of this method is that it wouldn't deal well with rapid popularity spikes - older files from when the server was less popular would stick around almost indefinitely. That said, this same property would give it some amount of flushing/DoS resistance while also subtly rewarding older users over newer users, so it can be argued to have some merit. (“I was using 0x0 before it was cool”)

Method c: Size Buckets

Have log(maximum filesize) many buckets, one per filesize. For example, you'd have a 512 MiB bucket, a 256 MiB bucket, a 128 MiB bucket, and so on. When a user uploads a file, insert it into the corresponding bucket of that size. All operations could be done in amortized O(1) since you only need access to the head and tail of each bucket.

In order to make space, one would be to assign a quota to each bucket, and only delete other files from that same bucket to keep it within quota. The main issue here is that a strict quota would lead to wasted space on the server unless we assume all buckets are highly loaded. One way to sidestep around that issue would be to keep the number of buckets low (high log base), a fancier way would be to implement a "quota stealing" algorithm where over-utilized buckets can borrow quota from under-utilized buckets, until those buckets start requesting it back.

But instead of assigning a quota to each bucket, you could also just delete the files from the bucket that is currently consuming the most space in total. That way, all filesizes would be roughly evenly balanced in terms of how much file size they're consuming, which I think would be a good fit. (i.e. assuming fully even usage you'd always store twice as many 256 MiB files as 512 MiB files, and so on)

To combat DoS, you could check for a threshold number of bucket deletions per second. If that threshold is exceeded, freeze that bucket temporarily. This method of DoS prevention even automatically tailors itself to the specific attack pattern, to some extent. For example, an attacker trying to flood your server with 512 MiB files will soon find himself unable to upload any new files, while somebody making e.g. a 4 KiB paste would experience no difference.

Mainly for the record. As we've discussed before, my previous algorithm for choosing the file retention based on the filesize alone has some short-comings: 1. It fails to down-scale to a low volume server. If there are not enough uploads per second, then the retention period is too short, leading to files being deleted even if there is plenty of space left. 2. It fails to up-scale to a high volume server. If there are too many uploads per second, disk space will run out requiring manual re-tuning from the administrator. 3. It doesn't take into account the difference between a popular file and an unpopular one. Deleting an unpopular file is generally preferred to deleting a popular file. Having though about these problems a bit, I've come up with some methods of potentially addressing these shortcomings # Method A: Priority Queue Instead of tracking a retention time, insert files into a big priority queue based around their “score”. This score could be assigned as a function of the time (preferring younger files) and filesize (preferring smaller files), and it could also be dynamically updated on hits (preferring more popular files). This would have O(log n) behavior for all operations. Whenever the free space drops below a threshold, make space by going through the priority queue, vacuuming up the files with the lowest score first, only stopping once there's room. The main downside with this approach is that it would be potentially very difficult to come up with a good “balance” for the factors feeding into the calculation of the score, and would require some manual tuning and evaluation. It could be made resistant to flushing/DoS by ensuring that there's an upper bound on how much popularity you can generate with a brand new, or very large, file, but I think it's ultimately a problem that will be hard to solve. # Method B: Dynamic Retention A simple method of solving problems 1 and 2 would be to just adjust the retention curve as a function of the current disk capacity. If the disk is close to 0% full, files would be very long-lived. As the disk gets closer and closer to 100% full, files would get shorter lived and shorter lived. As long as the popularity of a server only changes slowly, this would allow the algorithm to self-tune in order to keep the capacity at some reasonable usage level, like 90%. The downside of this method is that it wouldn't deal well with rapid popularity spikes - older files from when the server was less popular would stick around almost indefinitely. That said, this same property would give it some amount of flushing/DoS resistance while also subtly rewarding older users over newer users, so it can be argued to have some merit. (“I was using 0x0 before it was cool”) # Method c: Size Buckets Have `log(maximum filesize)` many buckets, one per filesize. For example, you'd have a 512 MiB bucket, a 256 MiB bucket, a 128 MiB bucket, and so on. When a user uploads a file, insert it into the corresponding bucket of that size. All operations could be done in amortized O(1) since you only need access to the head and tail of each bucket. In order to make space, one would be to assign a quota to each bucket, and only delete other files from that same bucket to keep it within quota. The main issue here is that a strict quota would lead to wasted space on the server unless we assume all buckets are highly loaded. One way to sidestep around that issue would be to keep the number of buckets low (high log base), a fancier way would be to implement a "quota stealing" algorithm where over-utilized buckets can borrow quota from under-utilized buckets, until those buckets start requesting it back. But instead of assigning a quota to each bucket, you could also just delete the files from the bucket that is currently consuming the most space in total. That way, all filesizes would be roughly evenly balanced in terms of how much file size they're consuming, which I think would be a good fit. (i.e. assuming fully even usage you'd always store twice as many 256 MiB files as 512 MiB files, and so on) To combat DoS, you could check for a threshold number of bucket deletions per second. If that threshold is exceeded, freeze that bucket temporarily. This method of DoS prevention even automatically tailors itself to the specific attack pattern, to some extent. For example, an attacker trying to flood your server with 512 MiB files will soon find himself unable to upload any new files, while somebody making e.g. a 4 KiB paste would experience no difference.

👍 4

haasn commented

2018-05-24 00:13:33 +02:00

(Migrated from github.com)

Also, for method C, you could incorporate the popularity of a file by moving it towards the front of the buckets (which would most likely be implemented as queues anyway) on a hit. That way, more popular files will naturally find themselves away from the "deletion end" of the queue.

haasn commented

2018-05-24 00:21:07 +02:00

(Migrated from github.com)

Also it probably goes without mentioning but the buckets should be cut off at 4 KiB in size, since as I understand it, that's the minimum size of a file on disk on typical filesystems.

namibj commented

2020-04-17 12:32:25 +02:00

(Migrated from github.com)

Also it probably goes without mentioning but the buckets should be cut off at 4 KiB in size, since as I understand it, that's the minimum size of a file on disk on typical filesystems.

On btrfs that's kinda-wrong, because it can store small files inline with the metadata, bypassing extend allocation and storing with minimal overhead (on top of the file existing at all).

> Also it probably goes without mentioning but the buckets should be cut off at 4 KiB in size, since as I understand it, that's the minimum size of a file on disk on typical filesystems. On btrfs that's kinda-wrong, because it can store small files inline with the metadata, bypassing extend allocation and storing with minimal overhead (on top of the file existing at all).

mia added the

enhancement

label 2022-12-01 03:00:31 +01:00

Optimizing 0x0's usage of available space #9

Method A: Priority Queue

Method B: Dynamic Retention

Method c: Size Buckets