Storing a million images in the filesystem

Question

I have a project that will generate a huge number of images. Around 1,000,000 for start. They are not large images so I will store them all on one machine at start.

How do you recommended on storing these images efficiently? (NTFS file system currently)

I am considering a naming scheme... for start all the images will have an incremental name from 1 up I hope this will help me sort them later if needed, and throw them in different folders.

what would be a better naming scheme:

a/b/c/0 ... z/z/z/999

or

a/b/c/000 ... z/z/z/999

any idea on this ?

Answer 1

I'd recommend using a regular file system instead of databases. Using file system is easier than a database, you can use normal tools to access files, file systems are designed for this kind of usage etc. NTFS should work just fine as a storage system.

Do not store the actual path to database. Better to store the image's sequence number to database and have function that can generate path from the sequence number. e.g:

 File path = generatePathFromSequenceNumber(sequenceNumber);

It is easier to handle if you need to change directory structure some how. Maybe you need to move the images to different location, maybe you run out of space and you start storing some of the images on the disk A and some on the disk B etc. It is easier to change one function than to change paths in database.

I would use this kind of algorithm for generating the directory structure:

1. First pad you sequence number with leading zeroes until you have at least 12 digit string. This is the name for your file. You may want to add a suffix:
   • 12345 -> 000000012345.jpg
2. Then split the string to 2 or 3 character blocks where each block denotes a directory level. Have a fixed number of directory levels (for example 3):
   • 000000012345 -> 000/000/012
3. Store the file to under generated directory:
   • Thus the full path and file filename for file with sequence id 123 is 000/000/012/00000000012345.jpg
   • For file with sequence id 12345678901234 the path would be 123/456/789/12345678901234.jpg

Some things to consider about directory structures and file storage:

• Above algorithm gives you a system where every leaf directory has maximum of 1000 files (if you have less that total of 1 000 000 000 000 files)
• There may be limits how many files and subdirectories a directory can contain, for example ext3 files system on Linux has a limit of 31998 sub-directories per one directory.
• Normal tools (WinZip, Windows Explorer, command line, bash shell, etc.) may not work very well if you have large number of files per directory (> 1000)
• Directory structure itself will take some disk space, so you'll do not want too many directories.
• With above structure you can always find the correct path for the image file by just looking at the filename, if you happen to mess up your directory structures.
• If you need to access files from several machines, consider sharing the files via a network file system.
• The above directory structure will not work if you delete a lot of files. It leaves "holes" in directory structure. But since you are not deleting any files it should be ok.

Answer 2

I'm going to put my 2 cents worth in on a piece of negative advice: Don't go with a database.

I've been working with image storing databases for years: large (1 meg->1 gig) files, often changed, multiple versions of the file, accessed reasonably often. The database issues you run into with large files being stored are extremely tedious to deal with, writing and transaction issues are knotty and you run into locking problems that can cause major train wrecks. I have more practice in writing dbcc scripts, and restoring tables from backups than any normal person should ever have.

Most of the newer systems I've worked with have pushed the file storage to the file system, and relied on databases for nothing more than indexing. File systems are designed to take that sort of abuse, they're much easier to expand, and you seldom lose the whole file system if one entry gets corrupted.

Answer 3

I think most sites that have to deal with this use a hash of some sort to make sure that the files get evenly distributed in the folders.

So say you have a hash of a file that is something like this 515d7eab9c29349e0cde90381ee8f810
You could have this stored in the following location and you can use how ever many levels deep you need to keep the number of files in each folder low.
\51\5d\7e\ab\9c\29\349e0cde90381ee8f810.jpg

I've seen this approach taken many times. You still need a database to map these file hashes to a human readable name and what ever other metadata you need to store. But this approach scales pretty well b/c you can start to distribute the hash address space between multiple computers and or storage pools, etc.

Answer 4

Ideally, you should run some tests on random access times for various structures, as your specific hard drive setup, caching, available memory, etc. can change these results.

Assuming you have control over the filenames, I would partition them at the level of 1000s per directory. The more directory levels you add, the more inodes you burn, so there's a push-pull here.

E.g.,

/root/[0-99]/[0-99]/filename

Note, http://technet.microsoft.com/en-us/library/cc781134(WS.10).aspx has more details on NTFS setup. In particular, "If you use large numbers of files in an NTFS folder (300,000 or more), disable short-file name generation for better performance, and especially if the first six characters of the long file names are similar."

You should also look into disabling filesystem features you don't need (e.g., last access time). http://www.pctools.com/guides/registry/detail/50/

Answer 5

Whatever you do, don't store them all in one directory.

Depending on the distribution of the names of these images, you could create a directory structure where you have single letter top level folders where you would have another set of subfolders for the 2nd letter of images etc.

So:

Folder img\a\b\c\d\e\f\g\ would contain the images starting with 'abcdefg' and so on.

You could introduce your own appropriate depth required.

The great thing about this solution is that the directory structure effectively acts like a hashtable/dictionary. Given an image file name, you will know its directory and given a directory, you will know a subset of images that go there.

Answer 6

We have an photo store system with 4 million images. We use database only for meta data and all images are stored on the file system using an inversed naming system, where folder names are generated from last digit of the file, last-1, and so on. e.g.: 000001234.jpg is stored in directory structure like 4\3\2\1\000001234.jpg.

This scheme works very well with identity index in the database, because it fills evenly whole directory structure.

Answer 7

I would store these on the file system but it depends on how fast will the number of files grow. Are these files hosted on the web? How many users would access these file? These are the questions that need to be answered before I could give you a better recommendation. I would also look at Haystack from Facebook, they have a very good solution for storing and serving up images.

Also if you choose file system you will need to partition these files with directories. I been looking at this issue and proposed a solution but its not a perfect one by any means. I am partitioning by hash table and users you can read more on my blog.

Answer 8

The new MS SQL 2008 has a new feature to handle such cases, it's called the FILESTREAM. Take a look:

Microsoft TechNet FILESTREAM Overview

Answer 9

Quick point, you don't need to store a file path in you DB. You can just store a numeric value, if your files are named in the way you describe. Then using one of the well-defined storage schemes already discussed, you can get the index as a number and very quickly find the file by traversing the directory structure.

Answer 10

Will your images need to be named uniquely? Can the process that generates these images produce the same filename more than once? Hard to say without knowing what device is creating the filename but say that device is 'reset' and upon restart it begins naming the images as it did the last time it was 'reset' - if that is such a concern..

Also, you say that you will hit 1 million images in one month's time. How about after that? How fast will these images continue to fill the file system? Will they top off at some point and level out at about 1 million TOTAL images or will it continue to grow and grow, month after month?

I ask because you could begin designing your file system by month, then by image. I might be inclined to suggest that you store the images in such a directory structure:

imgs\yyyy\mm\filename.ext

where: yyyy = 4 digit year
         mm = 2 digit month

example:  D:\imgs\2009\12\aaa0001.jpg
          D:\imgs\2009\12\aaa0002.jpg
          D:\imgs\2009\12\aaa0003.jpg
          D:\imgs\2009\12\aaa0004.jpg
                   |
          D:\imgs\2009\12\zzz9982.jpg
          D:\imgs\2010\01\aaa0001.jpg (this is why I ask about uniqueness)
          D:\imgs\2010\01\aab0001.jpg

Month, year, even day is good for security type images. Not sure if this is what you are doing but I did that with a home security camera that snapped a photo every 10 seconds... This way your application can drill down to specific time or even a range where you might think the image was generated. Or, instead of year, month - is there some other "meaning" that can be derived from the image file itself? Some other descriptors, other than the date example I gave?

I would not store the binary data in the DB. Never had good performance / luck with that sort of thing. Cant imagine it working well with 1 million images. I would store the filename and that is it. If they are all going to be JPG then dont even store the extension. I would create a control table that stored a pointer to the file's server, drive, path, etc. This way you can move those images to another box and still locate them. Have you a need to keyword tag your images? If so then you would want to build the appropriate tables that allow that sort of tagging.

You / others may have addressed these ideas while I was replying.. Hope this helps..

Answer 11

While I haven't served pictures on that scale, I've previously written a small gallery app for serving ~25k pictures on a 400MHz machine w. 512 MB of RAM or so. Some experiences;

• Avoid a relational databases at all costs; while databases, no doubt, are smart about handling data, they aren't designed for such use (we got specialized, hierarchal key-value databases for that called file systems). While I have nothing more than a hunch, I'd wager that the DB cache goes out the window, if you throw really large blobs at it. While my available hardware was in the small end, not touching the DB at all on image lookup gave orders of magnitude better speed.

• Research how the file system behaves; on ext3 (or was it ext2 at the time - can't remember), the limit of being able to efficiently look up sub-directories and files was around the 256 mark; so having only that many files and folders in any given folder. Again, noticeable speedup. While I do not known about NTFS, stuff like XFS (which uses B-trees, as far as I remember) is extremely fast, simply because they can do lookups extremely fast.

• Distribute data evenly; when I experimented with the above, I tried to distribute the data evenly over all directories (I did an MD5 of the URL and used that for directories; /1a/2b/1a2b...f.jpg). That way it takes longer to hit whatever performance limit there is (and file system cache is void at such large datasets anyway). (contrarily, you might want to see where the limits are early on; then you want to throw everything in the first available directory.

Answer 12

I would be inclined to create a date based folder structure, e.g. \year\month\day, and use timestamps for the filenames. If necessary, the timestamps can have an additional counter component if the images are to be created so fast that there may be more than one within a millisecond. By using a most significant to least significant sequence for the naming sorting, finding and maintenance are a breeze. e.g. hhmmssmm[seq].jpg

Answer 13

I am involved in a project that stores 8.4 million images in the course of a year for documenting status of various devices. More recent images are accessed more frequently, and older images are rarely sought unless a condition was discovered which prompted someone to dig into the archives.

My solution, based on this usage, was to incrementally zip the images into compressed files. The images are JPGs, each approximately 20kB and do not compress much, so the ZIP compression scheme is none. This is done merely for concatenating them into one filesystem entry which greatly helps NTFS in terms of speed when it comes to moving them from drive to drive, or looking through the list of files.

Images older than a day are combined into a "daily" zip; zips older than a month are combined into their respective "monthly" zip; and finally anything over a year is no longer needed and consequently deleted.

This system works well because users can browse the files (either via the operating system or a number of client applications) and everything is named based on device names and timestamps. Generally a user knows these two pieces of information and can quickly locate any one of the millions of images.

I understand this is probably not related to your particular details, but I thought I would share.

Answer 14

Might be late to the game on this. But one solution (if it fits your use-case) could be file name hashing. It is a way to create an easily reproducible file path using the name of the file while also creating a well distributed directory structure. For example, you can use the bytes of the filename's hashcode as it's path:

String fileName = "cat.gif";
int hash = fileName.hashCode();
int mask = 255;
int firstDir = hash & mask;
int secondDir = (hash >> 8) & mask;

This would result in the path being:

/172/029/cat.gif

You can then find cat.gif in the directory structure by reproducing the algorithm.

Using HEX as the directory names would be as easy as converting the int values:

String path = new StringBuilder(File.separator)
        .append(String.format("%02x", firstDir))
        .append(File.separator)
        .append(String.format("%02x", secondDir)
        .toString();

Resulting in:

/AC/1D/cat.gif

I wrote an article about this a few years ago and recently moved it to Medium. It has a few more details and some sample code: File Name Hashing: Creating a Hashed Directory Structure. Hope this helps!

Answer 15

Perhaps a creation date based naming scheme - either including all the info in the file name or (better for browsing later) splitting it up in directories. I can think of the following, depending on how often you generate images:

• Several images generated each day: Year/Month/Day/Hour_Minute_Second.png
• A couple a month: Year/Month/Day_Hour_Minute_Second.png

etc. You get my point... =)

Answer 16

Are you considering disaster recovery?

Some of the proposed solutions here end up mangling the file name (such that if the physical file was moved you would lose track of what file it really is). I recommend maintaining a unique physical file name so that if your master list of file locations gets corrupted, you can regenerate it with a small shell, er, powershell, script ;)

From what I read here it sounds like all these files would be stored on one file system. Consider storing them across multiple file systems on multiple machines. If you have the resources, determine a system of storing each file on two different machines in case you lose a power supply and the replacement is 2 days out.

Consider what kinds of procedures you would need to create to migrate files between machines or file systems. The ability to do this with your system is live and online may save you considerable headache down the road.

You might consider using a GUID as a physical file name instead of an incremental number in case your incremental number counter (the database identity column?) gets messed up.

If appropriate, consider using a CDN such as Amazon S3.

Answer 17

I just ran a test on zfs because I love zfs, and I had a 500gig partition that I had compression on. I wrote a script that generated 50-100k files and placed them in nested directories 1/2/3/4/5/6/7/8 (5-8 levels deep) and let it run for I think 1 week. (it wasn't a great script.) It filled up the disk and ended up having about 25 million files or so. Access to any one file with a known path was instant. Listing any directory with a known path was instant.

Getting a count of the list of files however (via find) took 68 hours.

I also ran a test putting a lot of files in one directory. I got up to about 3.7 million files in one directory before I stopped. Listing the directory to get a count took about 5 minutes. Deleting all the files in that directory took 20 hours. But lookup and access to any file was instant.

Answer 18

I see other mention a database, but see no mention of that in your post. In any case, my opinion on this particular point is: either stick to a database or file system. If you have to mix the two, be careful about it. Things get more complicated. But you might have to. Storing a million photos in a database does not sound the best idea.

You might be interested by the following specification, most digital cameras follow it to manage file storage: https://en.wikipedia.org/wiki/Camera_Image_File_Format

Essentially, a folder is created, such as 000OLYMPUS and photos are added to that folder (for example DSC0000.RAW). When the file name counter reaches DSC9999.RAW a new folder is created (001OLYMPUS) and image are added again, resetting the counter, possibly with a different prefix (ex: P_0000.RAW).

Alternatively you could also create folders based on parts of the file name (already mentioned several times). For example, if you photo is named IMG_A83743.JPG, store it at IMG_\A8\3\IMG_A83743.JPG. It is more complicated to implement but will make your files easier to find.

Depending on the filesystem (this will require some research), you might be able to just dump all the images in a single folder, but, in my experience, this would usually cause performance issues.

Answer 19

If you are on windows how about on an exFat filessytem

http://msdn.microsoft.com/en-us/library/aa914353.aspx

it was designed with storing media files in mind, and available now.

Answer 20

If they ALL are not immediately required and you can generate them on-the-fly and these are small images, why not implement an LRU memory- or disk-cache above your image generator?

This could save you from the storage and keep the hot images to be served from mem?

Answer 21

You might want to be look at ZFS (file system, volume manager from Sun) Regards

Answer 22

A clean way to generate the path from a large number is to easily convert it into hex then split it!

for example 1099496034834 > 0xFFFF1212 > FF/FF/12/12

public string GeneratePath(long val)
{  
    string hex = val.ToString("X");
    hex=hex.PadLeft(10, '0');
    string path="";
    for(int i=0; i<hex.Length; i+=2 )
    {
        path += hex.Substring(i,2);
        if(i+2<hex.Length)
            path+="/";
    }
    return path;
}

Store and load :

public long Store(Stream doc)
{
   var newId = getNewId();
   var fullpath = GeneratePath(newId)
   // store into fullpath 
   return newId;
}

public Stream Load(long id)
{
   var fullpath = GeneratePath(newId)
   var stream = ... 
   return stream;
}

Full source codes : https://github.com/acrobit/AcroFS

Answer 23

Unfortunately filesystems are very bad (performance with many files per directory or deep directory trees, checking times on restart, reliability) at managing lots of small files, so the solution above that involves ZIP files is best if you want to use a filesystem.

Using a database manager is by far the best option; a simple one like BDB or GDBM for example; even a relatrional DBMS like MySQL would be better. Only lazy people who don't understand filesystems and databases (e.g. those who dismiss transactions) tend to use filesystems as databases (or somewhat more rarely, viceversa).

Answer 24

How about a database with a table containing an ID and a BLOB to store the image? Then you can add new table(s) whenever you want to associate more data elements with a photo.

If you're expecting to scale, why not scale now? You'll save time both now and later IMO. Implement the database layer once, which is fairly easy to start with. Or implement some thing with folders and filenames and blah blah blah, and later switch to something else when you start blowing up MAX_PATH.