Sebastien How

experiments on all things.

Hashed Directory File Storage

| Comments

A reasonable way to store a small multitude of files on a file system is through a hashed directory structure with details on the files kept in a database table. One advantage of this method is that it keeps directory reads and file access times quick by not putting too many files into a single directory. The requirements for a system like this are; spread files evenly throughout all possible directories, keep the hashed file names from colliding (ie having the same file name) and to make it harder for someone to guess a files name (especially usefull if you want all your files to be publicly accessable but prefer to share them on your terms).

To solve the problem of spreading files evenly we can hash something or everything about the file, it can be the full file itself, the files name, the date we received the file, anything. Since the purpose of this has is to decide where to store the file we dont need to worry about hash collisions and length of the hash other then making sure its long enough for the given directory depth structure. MD5 and SHA1 are perfectly reasonable algorithms for hashing here, MD5 being faster. As an example of what text Ive used for hashing is Original fileName + current datetime + something else random or unique like and id.

The problem of keeping the file names unique falls to the database where file details will be kept. Each file on the drive will have a unique id in the database in addition to some other usefull data about the file (new file name, original file name, mime type, datetime added, perhaps even who uploaded it, a checksum, description, etc). The Id for that record is the most important item and it will be appended to the files new name to keep the file names unique. It can be added as a plain numeric or can be encoded into base16 or some other base soas to keep it consistant with the encoding of the previous hash.

Making it harder to guess a file name is simple, just add random (printable character) noise to the end of the file name. The longer the string of randomness the harder it will be to get a lucky guess.

Personally I feel that directory names of length two and having a depth of two is more than reasonable for any regular storage requirements need. When the hash is base16 encoded and using directory names with length of two chars (AA, AB, AC, etc…) and a directory depth of two (AB/CD, AB/EF, etc…) this provides us with 256 possible folders in the root dir. In each of first level folders there can be 256 second level folders. This gives us a total of 256 * 256 = 65,536 folders to place files in. Asuming that we will put at max 1000 files into each directory, this structure can handle about 65 million files. The flavor your file system (ext3, ext4, zfs, ntfs, etc..) will inform a reasonable max number of files to keep the file system performant. If each file is about 2MB in size a full directory tree will take up 125TB of space.

If you need or think you’ll fill up even half of this file system structure you should probably look into implementing something with a higher complexity and resilience. Facebooks Haystack is where I pulled some basics for the above system.

Now for sample code to do the things I mentioned above.

1
2
3
4
5
6
7
public class FileData {
    private Long id;
  private String fileName;
  private String originalName;
  private Long size;
  private String mimeType;
}

Hash function

1
2
3
4
5
6
7
8
9
10
11
12
13
public String hashText(final String text){
  try {
      MessageDigest md = MessageDigest.getInstance("MD5");
      md.update(text.getBytes("UTF-8"), 0, text.length());
      return new BigInteger(1, md.digest()).toString(16);

  } catch (NoSuchAlgorithmException e) {
      logger.warn("Could not find hash algorithm", e);
  } catch (UnsupportedEncodingException e) {
      logger.warn("Could not encode text", e);
  }
  return null;
}

Figuring out the directory path from the hash or file name

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Takes the given fileName string and chops it up into 2 character long directory names which are appended to the root and then the fileName appended to the dir structure.
 * A fileName of ABC12D45LG43SD1VO.ZIP where the path depth is 2 would turn into a string /rootDir/AB/C1/ABC12D45LG43SD1VO.ZIP
 * @param fileName
 * @return
 */
private String fullFilePath(String fileName){
  if(dirDepth == null) this.dirDepth = 2;
  StringBuilder sb = new StringBuilder();
  
  sb.append(rootDir);
  sb.append("/");
  
  for(int x=0; x < dirDepth; x++){
      int i = 2*x;
      sb.append(fileName.substring(i, i+2));
      sb.append("/");
  }
  sb.append(fileName);
  return sb.toString();
}

Parse the original file names extension to add it to our new file

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * returns the extension from the original filename.
 * @param fileName
 * @return
 */
private String parseExtension(final String fileName){
  String[] split = fileName.split("\\.");
  if(split.length > 1){
      return split[split.length-1];
  }
  return null;
}

Generate the new file name from an Id, a hash and an extension, notice that Im only keeping the first 8 characters of the hash, which is really twice as much as I need.

1
2
3
4
5
6
7
8
9
10
11
private String generateFileName(Long id, String hash, String ext){
  StringBuilder sb = new StringBuilder();   
  
  sb.append(hash.substring(0,8));
  sb.append(id);
  sb.append(generateCode(8));
  sb.append(".");
  sb.append(ext);
  
  return sb.toString();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public void storeFile(MultipartFile file) {
  FileData fileData = fileDataDao.reserveId();

  fileData.setOriginalName(file.getOriginalFilename());
  fileData.setSize(file.getSize());
  fileData.setMimeType(file.getContentType());


  //Random hash to use as directory for a file
  String hash = hashText(fileData.getId()+file.getOriginalFilename()+(new GregorianCalendar()).getTimeInMillis());
  String ext = parseExtension(file.getOriginalFilename());

  fileData.setFileName(generateFileName(fileData.getId(), hash, ext));

  String fullPath = fullFilePath(fileData.getFileName());
  String saveDir = fullPath.substring(0, fullPath.lastIndexOf("/")+1);


  try {
      //Create the directory to store the file in.
      new File(saveDir).mkdirs();
      File fileToSave = new File(fullPath);

      FileUtils.copyInputStreamToFile(file.getInputStream(), fileToSave);
      
  } catch (IOException e) {
  }

  //Save details to database;
  fileDataDao.saveOrUpdate(fileData);
}

Comments