1. what should work faster for access user dir with id 748332: /74/83/32/748332/ or /7/4/8/3/3/2/748332

   The reasoning behind placing files in directory structures formed by partitioning the name-space is to avoid huge numbers of files in a single directory which (on some file systems) have to be search linearly.

   Eg. If your 6-digit ID defines your ID space, then placing 1 million files in a single directory means on average, you have to inspect 500,000 entries to find the file you are looking for.

   But, if you split that into /xx/yy/zz.dat, then on average you will inspect 50 entries in the first level, 50 in the second and 50 in the final level. !50 inspections .v. 500,000 is a good trade.

   Using (a modified version of) your second schema /p/q/r/x/y/z.dat, it will (on average) be 5 in each of the 6 levels giving 30 inspections.

   The latter sounds like a good idea, but in practice the benefits can be outweighed by the complexities. This depends upon the actual file-system in use, and you will need to test to see what works best on your particular file-system.

2. Files in linux directory are indexed

   Again, this depends upon the file-system in use. AFAIK, ext2/ext3 are not indexed (or hashed), but other *nix file-sytems may be.

3. For example someone posted a message, what better : to save all the replies for this message in a singe file or save each reply in separate file in the folder that will be created for this message and when someone view the message to gather all the replies from the files

   Reading between the lines, I'm guessing your thinking of implementing a message-board type system (not unlike PM).

   If so, the "better" will depend upon many factors:

   • Will replies have their own IDs within the 6-digit ID space?
   • Will replies only be displayed subservient to their parent? Or will they be viewable individually?
   • Are replies to replies possible?

A comment: Your proposed schemas /74/83/32/748332/ & /7/4/8/3/3/2/748332/ both incorporate two levels of redundancy. There is no benefit in this.

Two questions:

• What happens if you design your schema to deal with 6-digit IDs, and you get more than a million "things"? </il>
• Why are you settled upon a "flat file database" rather than one of the other options? (RDBMS, HADOOP, NoSQL etc.)

If there a tutorial or book about flat files database it will be great !

The only paper I ever saw on the subject was an IBM RedBook, but that was 15 or 20 years ago, so my memory of it is vague. You could try searching that site, but I don't have any good keywords to offer you right now. Maybe some will come back to me.

1. I am trying to find the sweet spot between directory access time and the number of levels.
The folders hierarchy will be automatically created on the fly.
I mean if there is only 2374 , so the last user will have folder 2/3/7/4/2374
The same about 2 digits hierarchy, if there is more that million of id's another level will be added automatically.

At that point it's not for specific filesystem, but if the system will grow up I will move it to server with the suitable filesystem.

2.Ok , for now I'm using ext3 but I will move towards something better if needed.

3.Yes , I'm building an facebook/google+ like online community project.
I have already finished one project, it's working fast but when I benchmarked it there was some limitations on fequests per second but the CPU wasn't on 100% and still few gb of free memory...
I think it because of HD I/O limitations.Because of that i want to understand how to make it super fast.

q:Will replies have their own IDs within the 6-digit ID space?
a:yes , the replies will have an uniq id

q:Will replies only be displayed subservient to their parent? Or will they be viewable individually?
a:there will be post->replies structure.
Each post will have a file for it's replies
They won't be viewable individually,but there maybe will be an option to edit or delete the reply .So if the replies for specific post will be stored in the same file , it will need to be rewritten in a case some one want to edit only 1 reply.

q:Are replies to replies possible?
a:no

1-q: already answered .
2-q: I have a good experience with flat files databases, I started to read a book about mysql optimization and at some point I was upset .
It's not that simple as it seems to be. There is many tricks that need to know and that come with experience, to much options that I don't need.
I just afraid that in some point I will get stuck with it or the performance will be poor at some point.

Thanks for the informative post

replies will have an uniq id... Each post will have a file for it's replies.

There is a conflict there. If replies have uniq IDs, then their bodies will exist in the hierarchy, so what will you store in the "file of replies"?

My suggestion would be to store symlinks to the replies in the directory holding the body of the parent. That way, you do not have to traverse the hierarchy from the root to find them (as you would if you store a file containing the reply IDs).

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

See (OT) should i limit number of files in a directory, Efficient processing of large directory, Perl solution for storage of large number of small files, Comparison of file systems , read source of wwwboard, and Benchmark filesystem, BerkeleyDB, DBD::SQLite, Perl vs Java in Heavyweight Filesystem Processing, Perl solution for storage of large number of small files

You could search a few thousand bytes of directory data, even using linear search, in far less time than it would take you to access that data.

Sorry, whilst I'm no expert on *nix filesystems, I think you are wrong. At least as far as ext2 goes; and ext3 used in its default manner.

The problem is that in the former, and by default in the latter, the filename to inode mappings stored in the directory files are a single linked list that must be searched from the top each time.

Directories

Each directory is a list of directory entries. Each directory entry associates one file name with one inode number, and consists of the inode number, the length of the file name, and the actual text of the file name. To find a file, the directory is searched front-to-back for the associated filename. For reasonable directory sizes, this is fine. But for huge large directories this is inefficient, and ext3 offers a second way of storing directories that is more efficient than just a list of filenames.

So, not only does that mean that in a 1 million file directory, that you need to inspect 500,000 files on average each time, it also means that the VFS is unlikely to be able to retain the entire directory file in cache, which means frequent re-reads.

Ext3 has a mechanism (Htree) for improving this:Creating 100,000 files in a single directory took 38 minutes without directory indexing... and 11 seconds with the directory indexing turned on.. The trouble is, very few people use it.

A few years ago, (from memory, on BSD), moving ~100 million files from a single directory to a three level hierarchy improved the time taken to locate and read small (a few kb) files from whole seconds to 10 of milliseconds. Try it yourself to see the difference it makes.

By reducing the size of the directories to 100 or 256, the entire directory at any level can fit into a single block. The root level effectively gets locked in cache making the first reduction happen in microseconds. And for an application like the OPs where most accesses will be for the latest message IDs, the one or two second level directories that will be most accessed will also tend to remain cache resident. So in use, most accesses will not need to hit the disk at all until it comes to reading or writing the top level file.

The benefits are far less when there is no locality of reference -- ie. the files are accessed randomly -- but for the OPs application, they should be tangilble and very worthwhile.

I also agree that going too deep negates the benefits.

---

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

You could search a few thousand bytes of directory data, even using linear search, in far less time than it would take you to access that data.

Sorry, whilst I'm no expert on *nix filesystems, I think you are wrong.

Well, I did say a few thousand bytes of directory data, which isn't going to apply to 100,000 files, 1 million files or 100 million files. I was mostly trying to move the OP away from the directory-per-digit option. If the IDs are used to cross-reference messages (as they are for messages here in the monastery), then a database, rather than flat files, is even more compelling. I don't know how messages are stored in the monastery, but I strongly suspect it is via a database, not in flat files. You wouldn't want to run monastic searches against unindexed flat files, but that would be relatively easy to implement (efficiently) in most databases.

I have recently been trying to nudge the OP in the direction of databases, and that's a nudge I see reflected in many of the responses.

that's the point , I am searching for sweet spot for how much i need go deep?
also another thing i was thinking on ..each time user folder accessed , filesystem need to go like :
/var/www/cgi-bin/PROJECT/DB/1/2/3/123
what if i will put a link to DB in the root directory for faster access ? What do you think about that?
/user_db/1/2/3/123 Thanks

If your system is busy, the top level directory is likely to end up in buffer cache, no matter where it is rooted. (If it's not busy, a few extra milliseconds won't matter). Take a look at directory sizes for 1-digit/2-digit/3-digit prefixes. A "sweet spot" would be directories that (just) fit into whatever block size your filesystem uses, often 4KB. I'm guessing that will be 2- or 3-digit prefixes, depending on how dense the prefixes are and how the file system structures directories. You might let the top level directory get a bit larger, on the grounds that frequent access will keep it pinned in buffer cache.

Don't go nuts with premature optimization. Make it easy to alter the structure of the directories, like having a routine to return an array of components corresponding to the directory entries. Then measure performance with a few alternatives.

In the system that I recently (re-)designed, I allocated 1,000 elements at each level of the hierarchy (which replaced a monstrous blob-table), except the first, which contains 10.   I did this rather arbitrarily, and mainly so that a manual directory-listing would not be inconveniently long.   Most modern file systems are pretty smart, with B-tree index structures and a recently-used files/directories cache.   I think that the major consideration here should simply be, what do you find convenient to handle should you ever be working with these structures yourself, i.e. apart from the software.

In my directory table, I stored the reference number (from which the file-location is calculated on-the-fly in case the topology changes someday), and I also stored an SHA1 signature of the file’s content and its length in bytes.   If the application finds a mismatch, it throws an error.

Of course, ignore this if you just want to have a good time hacking away.

2-q: I have a good experience with flat files databases, I started to read a book about mysql optimization and at some point I was upset . It's not that simple as it seems to be. There is many tricks that need to know and that come with experience, to much options that I don't need. I just afraid that in some point I will get stuck with it or the performance will be poor at some point.
Also there is few things I don't know how to implement in mysql database , for example:
friends connection, in files i used to write it in dir of each user
top rated items list, in files i just make an index file that read from the top
searches that i make into /ab/cd/ef/de that are super fast as loading a simple page.
and more...

From what you described, I get the impression an SQL optimisation book is not what you need. Rather, try out whether a variant (e.g. SQLite, PostgreSQL) would suit your needs better (i.e. more easily, less painfully) than flat files do.

I don't know the scale nor expected use of your project, so it's hard to advise. SQL isn't that hard, yet it's powerful.

• A friendship (ID) could have two user(ID)s as its members, for instance.
• Top rated items would be selecting an x count of items sorted by their rating values in descending order.
• Indexes are fairly standard too.

Optimising seems more for your flat files design, given that you have more experience there. Using a routine to generate paths from IDs (as suggested earlier) would be a good way to start a benchmark schemes vs filesystem flavour and operating loads you expect to see.