5 ms·

During my young naïve programming days (which coming to think of it haven't really ended) I thought to myself "Why bother using some third party database when I

by JonRB 10y ago

During my young naïve programming days (which coming to think of it haven't really ended) I thought to myself "Why bother using some third party database when I could just store user information in text files, the OS handles that sort of thing really well, right?". I looked into it as much as I could be bothered and found no huge red flags. After a few years of this server merrily creating a new file for each user I found that my disk was full, as this poster did. After a lot of hunting around, I found out that I had hit my inode limit, a concept I was completely unaware of. I know for sure I won't be making THAT mistake again.

bArray 10y ago
"After a lot of hunting around, I found out that I had hit my inode limit, a concept I was completely unaware of." What was the number you hit? I have a flat file system for something I'm prototyping. The files are in a database with a random SHA256 filename associated with them. I was thinking about doing what Git does with creating folders for parts of the string to alleviate the number of files in one single directory. I'm sure that makes file retrieval a prettier process. Do all the files for have to be in the same directory for the iNode limit to be reached or just there in general? NOTE: I ask because the prototype isn't ever meant to go into production, but my customer keeps getting confused and I'm concerned this very important system may inherit (or even use) my design.
- LukeShu 10y ago
  It's a global limit per filesystem. You can check what the limits are for your filesysems, and what the current use is with `df -i`. The thing that git does is for speed.
  - bArray 10y ago
    I've apparently used 1241165 out of 19005440, or about 6.53% on my development machine. It's not inconceivable to have 19 million files, though, if you had one per user. That's not great. How is that number calculated? It's less than 2^25 but greater than 2^24, so I imagine it's even awkward to store. I guess that has something to do with the file table size for HDD - you can't have more nodes than you have addressable space for those nodes. I knew Git did it for speed, but I was wondering whether it was also about the number of files that can exist in a single directory. EDIT: Corrected percentage.
    - LukeShu 10y ago
      It's a property of the filesystem that is set when it was created. In the case of the mkfs.ext{2,3,4}, you can set the number of inodes with the -N flag, but by default, it is the size of the filesystem divided by inode_ratio (probably 4096).
      - bArray 10y ago
        Seems to be about 16k for the ratio? 19,000,000 * 16,000 ~= 300GB - which is about the size of my disk partition. That's crazy. Thanks for that information.
        danieldk 10y ago
        Your filesystem's block size is probably 4KiB. So, it's one inode per for blocks. That's crazy. Why? Do you expect to store many files less than 16KiB?
        bArray 10y ago
        Each user has some small arbitrary information associated with them, with potentially tens of millions of users (and no doubt more in the future). There's not really a structure due to the nature of the project, each user needs personalised information and structure associated to them. I don't think that amount of information is really suitable for a database? It may be larger in some cases too, so there's not guarantees I can even make about size.
        danieldk 10y ago
        Ah, sorry, I missed that you were still referring to the 'filesystem as a database'-project :).
        Xylakant 10y ago
        Document stores shine in that case. Depending on the exact case something like postgres's HSTORE, couchdb, couchbase, mongodb or similar would work. They're all capable of storing arbitrary json docs under a given key and efficiently retrieve it. Partial indexing is possible as well.
  - ptman 10y ago
    I really like the fact that Mac OS X df(1) by defaults shows inode stats https://developer.apple.com/legacy/library/documentation/Darwin/Reference/ManPages/man1/df.1.html https://developer.apple.com/legacy/library/documentation/Dar... Maybe Linux and the BSDs could adopt that as well.
- lotyrin 10y ago
  The whole FS has a limited number of inodes, additionally some FS have limited number of files or directories inside a directory. If you don't control the FS chosen by your customer, I'd design conservatively (find the dumbest set of limits, stay under them).
jfoutz 10y ago
Completely reasonable thing to do, for a little while. Ycombinator itself did this initially. The key is knowing you'll need to do something better soon.
jfoutz 10y ago
Completely reasonable thing to do, for a little while. Ycombinator itself did this initially. The key is knowing you'll need to do something better soon.
dvcrn 10y ago
inodes are by the way a great topic to talk about in a job interview. People working with unix based systems should know about them, or at least encountered them once in their career. Another good one that even less people know about is the sticky bit.
- danieldk 10y ago
  Indeed. One of the types questions were people typically bomb (this is also one in Google's telephone interview arsenal): where is a filename stored? People who have the vague notion of 'an inode stores metadata' will usually answer this incorrectly.
Johnny555 10y ago
I did the same thing to support about 10 million customer websites, but had the opposite experience - it worked pretty well, we used UFS and a 4 level directory structure (i.e. customer "apple" went into '/a/p/p/l/apple' and just wrote a simple apache module to map URL's to this directory structure.(using a hash of the filename would have given more even distribution, but this naive algorithm worked pretty effectively) It was much easier than coding a database back-end, with no need to run a database server. And, when we needed to scale beyond one machine, it was trivial to use a central NFS server (read-only NFS worked really well for this) and multiple front-end web servers. Though we did know how many files we'd be hosting, so we sized the number of bytes per inode appropriately.
jbpetersen 10y ago
Now I'm wondering whether that makes for a good design assuming you're using a filesystem that surpasses that limitation. Btrfs?
- rbanffy 10y ago
  It's worth checking that out, but I suspect the folder solution described on a sibling comment is a better solution. If a file system gets too full, it's trivial to move the files in a folder to another file system an mount it where the folder originally was. Also, spreading the files across multiple NFS mounts is also trivial.
oxplot 10y ago
Standard practice to store a large number of files but in such a way that they don't end up in a single directory, is to create a crypto hash of your object names and use the first n characters as the directory name. Properties of hash functions will ensure that the files are distributed evenly between all the directories. git is an example of a program that uses this technique (among others) to store blobs. In case of git, the blob names are already SHA-1 hashes.
- majewsky 10y ago
  You don't actually need a cryptographic hash here [1]. I'd rather use a fast hash like Murmur instead. [1] Exception: I don't know how prone Murmur is to hash collisions, so if collision-based attacks are part of your threat model, a randomly salted cryptographic hash might be appropriate.

by JonRB 10y ago

bArray 10y ago

"After a lot of hunting around, I found out that I had hit my inode limit, a concept I was completely unaware of." What was the number you hit? I have a flat file system for something I'm prototyping. The files are in a database with a random SHA256 filename associated with them. I was thinking about doing what Git does with creating folders for parts of the string to alleviate the number of files in one single directory. I'm sure that makes file retrieval a prettier process. Do all the files for have to be in the same directory for the iNode limit to be reached or just there in general? NOTE: I ask because the prototype isn't ever meant to go into production, but my customer keeps getting confused and I'm concerned this very important system may inherit (or even use) my design.

LukeShu 10y ago
It's a global limit per filesystem. You can check what the limits are for your filesysems, and what the current use is with `df -i`. The thing that git does is for speed.
- bArray 10y ago
  I've apparently used 1241165 out of 19005440, or about 6.53% on my development machine. It's not inconceivable to have 19 million files, though, if you had one per user. That's not great. How is that number calculated? It's less than 2^25 but greater than 2^24, so I imagine it's even awkward to store. I guess that has something to do with the file table size for HDD - you can't have more nodes than you have addressable space for those nodes. I knew Git did it for speed, but I was wondering whether it was also about the number of files that can exist in a single directory. EDIT: Corrected percentage.
  - LukeShu 10y ago
    It's a property of the filesystem that is set when it was created. In the case of the mkfs.ext{2,3,4}, you can set the number of inodes with the -N flag, but by default, it is the size of the filesystem divided by inode_ratio (probably 4096).
    - bArray 10y ago
      Seems to be about 16k for the ratio? 19,000,000 * 16,000 ~= 300GB - which is about the size of my disk partition. That's crazy. Thanks for that information.
      - danieldk 10y ago
        Your filesystem's block size is probably 4KiB. So, it's one inode per for blocks. That's crazy. Why? Do you expect to store many files less than 16KiB?
        bArray 10y ago
        Each user has some small arbitrary information associated with them, with potentially tens of millions of users (and no doubt more in the future). There's not really a structure due to the nature of the project, each user needs personalised information and structure associated to them. I don't think that amount of information is really suitable for a database? It may be larger in some cases too, so there's not guarantees I can even make about size.
        danieldk 10y ago
        Ah, sorry, I missed that you were still referring to the 'filesystem as a database'-project :).
        Xylakant 10y ago
        Document stores shine in that case. Depending on the exact case something like postgres's HSTORE, couchdb, couchbase, mongodb or similar would work. They're all capable of storing arbitrary json docs under a given key and efficiently retrieve it. Partial indexing is possible as well.
- ptman 10y ago
  I really like the fact that Mac OS X df(1) by defaults shows inode stats https://developer.apple.com/legacy/library/documentation/Darwin/Reference/ManPages/man1/df.1.html https://developer.apple.com/legacy/library/documentation/Dar... Maybe Linux and the BSDs could adopt that as well.
lotyrin 10y ago
The whole FS has a limited number of inodes, additionally some FS have limited number of files or directories inside a directory. If you don't control the FS chosen by your customer, I'd design conservatively (find the dumbest set of limits, stay under them).

jfoutz 10y ago

Completely reasonable thing to do, for a little while. Ycombinator itself did this initially. The key is knowing you'll need to do something better soon.

jfoutz 10y ago

Completely reasonable thing to do, for a little while. Ycombinator itself did this initially. The key is knowing you'll need to do something better soon.

dvcrn 10y ago

inodes are by the way a great topic to talk about in a job interview. People working with unix based systems should know about them, or at least encountered them once in their career. Another good one that even less people know about is the sticky bit.

danieldk 10y ago
Indeed. One of the types questions were people typically bomb (this is also one in Google's telephone interview arsenal): where is a filename stored? People who have the vague notion of 'an inode stores metadata' will usually answer this incorrectly.

Johnny555 10y ago

I did the same thing to support about 10 million customer websites, but had the opposite experience - it worked pretty well, we used UFS and a 4 level directory structure (i.e. customer "apple" went into '/a/p/p/l/apple' and just wrote a simple apache module to map URL's to this directory structure.(using a hash of the filename would have given more even distribution, but this naive algorithm worked pretty effectively) It was much easier than coding a database back-end, with no need to run a database server. And, when we needed to scale beyond one machine, it was trivial to use a central NFS server (read-only NFS worked really well for this) and multiple front-end web servers. Though we did know how many files we'd be hosting, so we sized the number of bytes per inode appropriately.

jbpetersen 10y ago

Now I'm wondering whether that makes for a good design assuming you're using a filesystem that surpasses that limitation. Btrfs?

rbanffy 10y ago
It's worth checking that out, but I suspect the folder solution described on a sibling comment is a better solution. If a file system gets too full, it's trivial to move the files in a folder to another file system an mount it where the folder originally was. Also, spreading the files across multiple NFS mounts is also trivial.

oxplot 10y ago

Standard practice to store a large number of files but in such a way that they don't end up in a single directory, is to create a crypto hash of your object names and use the first n characters as the directory name. Properties of hash functions will ensure that the files are distributed evenly between all the directories. git is an example of a program that uses this technique (among others) to store blobs. In case of git, the blob names are already SHA-1 hashes.

majewsky 10y ago
You don't actually need a cryptographic hash here [1]. I'd rather use a fast hash like Murmur instead. [1] Exception: I don't know how prone Murmur is to hash collisions, so if collision-based attacks are part of your threat model, a randomly salted cryptographic hash might be appropriate.