Tool (database, filesystem, etc.) or strategy for providing fast consistent random access to tens of millions of small data chunks

Question

I'm working on code for a personal project and I have the need to store potentially tens of millions of small, similarly but not equally sized pieces of data, between 128KB and 1MB each (average around 512KB or so). Ultimately, the data chunks need to be accessible via a web URL, possibly with authentication (which could be handled by middleware). It's important that, within reason, locating and starting to retrieve any random piece of data takes on average the same amount of time as any other piece of data given no other external factors that might slow things down.

Requirements:

• Store tens of millions of data objects, not equally sized but all relatively small (<4MB).
• Be able to, as quickly as possible and with reasonably equal access times, (accounting for disk/SSD/etc. speed and other latencies inherent to the system), retrieve any random data object, ultimately via a web URL.
  • The storage layer doesn't need to support web URL access directly, since the web API can handle that, but it's a plus - see "Niceties" below.
• Backend storage on standard media - hard drives or SSDs. I normally use RAID setups like mdraid or zfs, but an entire filesystem is something I'm happy to explore (it must support spanning multiple disks for scalability).
• Runs on Linux.
• Consistency in access times is more important than short access times. Roughly consistent 15ms access times is better than 0.5ms access times that only happen half the time. Obviously within reason - 5000ms access times even if consistent is too long. (See Caveats below)

Strong preferences:

• Open source or otherwise no cost to use noncommercially.
  • Since this is a personal, educational project with no profit goals, something with significant expense is not desirable. Something with a small one-time cost can be considered though.
• If it's not something like an entire filesystem, ability to run the database/storage layer/etc. in Docker.

Niceties but not required at all:

• Inherent URL access to objects (e.g. via the S3 API) without extra work. Access control is not required since that can be provided by a proxying API.
• Some sort of inherent statistics engine - number of files, total size, etc. able to be retrieved.
• Able to attach metadata to data objects at the filesystem layer. (Not essential because this can also be done in my own separate database.)

Caveats that I already am aware of:

• Backend storage access times. Obviously, a hard drive's seek times aren't consistent, but the software side of things is where I want to have relatively predictable access times. For example, if accessing one random record takes 5ms, accessing some other random record should not take 500ms.
  • Similarly, I'm not counting the time to actually transfer the data. I'm focused on the amount of time it takes to locate and start delivering the data. With data chunks as small as 1MB, my application would probably just load each chunk directly into RAM and then deliver it to the client at whatever speed is available.
  • Finally, I'm also aware that multiple parallel accesses will impact performance. Again though, this should not be affected by inefficiencies in the filesystem itself. For example, assuming accessing one file takes 5ms, accessing two files with each taking 8ms is fine, but if accessing one file means accessing another file simultaneously will make that second file take 500ms, that's not ideal. In other words, it's better for all threads to lag roughly equally than for one thread to be lagged longer by orders of magnitude.
• I'll most likely store objects with a key such as a SHA hash, and manage the logical meaning of objects in a separate database. A typical DBMS like MySQL can reasonably handle tables with millions of records already.

So far, I have considered these options:

1. Store files with random hash values (e.g. SHA1 values) on a traditional filesystem in a hierarchy based on the first few characters of each hash. For example: /data/d/f/8/cba1923f84c0912c293ff8cabc8e. This gives the effect of roughly equal directory list sizes, but still does not scale well for millions of items and beyond - there is a significant lag when accessing very large directory listings, so once any folder exceeds a couple thousand files, time to locate files goes up significantly and unpredictably.
2. Store the binary blobs directly in a traditional database. For small datasets this works well, but it doesn't seem to scale too well. Especially if the data needs to span multiple disks, the DBMS then needs to support storing the database files on multiple disks, or traditional RAID needs to be run underneath. Garbage collection can also become an issue if objects are ever deleted.
3. Use a tool like MinIO. I'm not sure precisely how Minio works, but I think it just drops objects onto the filesystem as files, so it's really not too different from option 1. It might have some internal efficiency improvements, so if I'm missing some great insight into MinIO and you can explain why it's a good choice, I'd be up for trying it as well. (Note that S3 API access is not a requirement, but it's a viable choice for the URL access part of the project.)