4 ms·

Sadly, this article gets some stuff about btrfs wrong. Allow me to clarify: * First off, btrfs does not use "hash tables". Instead, it uses hashes to create ke

Sadly, this article gets some stuff about btrfs wrong. Allow me to clarify: * First off, btrfs does not use "hash tables". Instead, it uses hashes to create keys that index into B-Trees. The problem is that hash collisions are not handled with an efficient approach. btrfs is forced to do a lot of work to deal with these collisions. * ZFS uses two distinct data structures to represent the contents of a directory: the so-called "micro-ZAP" and the so-called "fat-ZAP" micro-ZAPs are for small directories. This is OK as the number of collisions is limited by the relatively small size of the micro-ZAP. fat-ZAPs are like on-disk extensible hash-tables. They both use CRC64, I think that fat-ZAPs might have a problem.

ajross 14y ago
That's interesting. Is there any guidance as to why the tree keys are derived hashes instead of the actual file names? Obviously the original space is invulnerable to collisions by definition. Was the point simply to make the keys smaller to fit in a single machine word? Is that really helpful for performance vs. an optimized strcmp? I'm generally a big btrfs fan, but here it seems like they got caught due to a senseless overoptimization...
- cokernel_hacker 14y ago
  Variable length keys are difficult to implement efficiently. The alternative is not doing file name lookups by key query which would damage performance in unpatholgical cases.
  - ajross 14y ago
    Really? I'm not sure I buy that. B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound. That's just not going to be sensitive to the handful of cycles you save except in the case of tiny directories that are already in L1/L2 cache. But there, you're paying the up-front cost of hashing the input file name as "extra" and it's not even clear to me you'd save anything overall. Basically, this just smells like a premature optimization to me. If it were my project and lacked the hashing feature, and someone wanted to add it, I'd really want to see some numbers before accepting it.
    - Someone 14y ago
      "B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound." I am not an expert on file systems, but have you thought about the following: - using file names in disk blocks rather than file name hashes means fewer entries per disk block. That, in turn, changes the constant of your B-tree traversal. - with variable-length keys, keeping your B-trees balanced is tricky, if not practically impossible. EDIT: disadvantage of using hashes would be that you need to read the filename proper (with small hashes, you cannot ignore hash collisions). That would be an extra I/O. So I guess this would not be beneficial for small directories. Maybe you could start out by having in-block hashes amd filenames and only move the names to a separate block when you need a second block?
      - cokernel_hacker 14y ago
        The most common implementation technique that I know of is to include a small constant number (~4) bytes of the actual name next to the hash.
        Someone 14y ago
        I can see how that would help if your filenames are bin, dev, opt, usr, and var, but in the general case, I do not see how that beats having a longer hash (or a second, independent hash). Four bytes of the name will have less entropy than such data, and having part of the filename around will not help making sure that a matching hash implies a matching filename. Can you give explain this or give a name of a filesystem doing this?

ajross 14y ago

That's interesting. Is there any guidance as to why the tree keys are derived hashes instead of the actual file names? Obviously the original space is invulnerable to collisions by definition. Was the point simply to make the keys smaller to fit in a single machine word? Is that really helpful for performance vs. an optimized strcmp? I'm generally a big btrfs fan, but here it seems like they got caught due to a senseless overoptimization...

cokernel_hacker 14y ago
Variable length keys are difficult to implement efficiently. The alternative is not doing file name lookups by key query which would damage performance in unpatholgical cases.
- ajross 14y ago
  Really? I'm not sure I buy that. B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound. That's just not going to be sensitive to the handful of cycles you save except in the case of tiny directories that are already in L1/L2 cache. But there, you're paying the up-front cost of hashing the input file name as "extra" and it's not even clear to me you'd save anything overall. Basically, this just smells like a premature optimization to me. If it were my project and lacked the hashing feature, and someone wanted to add it, I'd really want to see some numbers before accepting it.
  - Someone 14y ago
    "B-tree traversal in real world cases is virtually always going to be I/O or memory bandwidth bound." I am not an expert on file systems, but have you thought about the following: - using file names in disk blocks rather than file name hashes means fewer entries per disk block. That, in turn, changes the constant of your B-tree traversal. - with variable-length keys, keeping your B-trees balanced is tricky, if not practically impossible. EDIT: disadvantage of using hashes would be that you need to read the filename proper (with small hashes, you cannot ignore hash collisions). That would be an extra I/O. So I guess this would not be beneficial for small directories. Maybe you could start out by having in-block hashes amd filenames and only move the names to a separate block when you need a second block?
    - cokernel_hacker 14y ago
      The most common implementation technique that I know of is to include a small constant number (~4) bytes of the actual name next to the hash.
      - Someone 14y ago
        I can see how that would help if your filenames are bin, dev, opt, usr, and var, but in the general case, I do not see how that beats having a longer hash (or a second, independent hash). Four bytes of the name will have less entropy than such data, and having part of the filename around will not help making sure that a matching hash implies a matching filename. Can you give explain this or give a name of a filesystem doing this?