I'm using Kyoto Cabinet (a key-value store) for my project. The specific type of DB I'm using is DirDB which creates a lot of files in a directory to store the key-value pairs. The server I'm running this project on has ext4 filesystem. The problem I'm encountering is that the I/O latency increases as the number of files in the directory increases. Also, when the directory has too many files (say over 1 million files), when I try to delete the whole folder, it takes forever (already more than 5 hours and still running). Can someone explains why I/O latency increases as the number of files increases and why rm takes forever to delete the folder?
migrated from stackoverflow.com Jun 9 '13 at 17:19
This question came from our site for professional and enthusiast programmers.
The simplest example of delays is that, obviously, the time to list the entire directory will vary with how big the directory is.
Secondly, depending on the filesystem settings, ext4 uses either linked lists, or a hashed b-tree for directory lookups. You need only look up how those two data structures work, to get some idea of the differences that incorrect configuration might make. The short version is that linked lists are pretty slow, and only suitable for small directories, whereas that hashes are much faster, and much better suited to large directories.
Processing a linked list means going through each and every item in the list, because, most of the time, only item n-1 knows where item n is, so you must read item n first.
Processing a hash tree involves calculating a number in memory, and jumping directly to details based on that number. Although it may have to do this a few times for big directories, it's much faster than processing every node.
Anyway, if you really want to understand the details, all the documentation is available online. You could start here, for instance: https://ext4.wiki.kernel.org/index.php/Ext4_Disk_Layout#Hash_Tree_Directories