3 ms·

Can you elaborate a bit on how the hashing and chunking works? There's a rolling hash for determining chunk boundaries, and also SHA-512/256 somewhere. Does t

by ah- 10y ago

Can you elaborate a bit on how the hashing and chunking works? There's a rolling hash for determining chunk boundaries, and also SHA-512/256 somewhere. Does the same data chunked differently have a different hash?

aboodman 10y ago
Briefly, there are two main hash functions in use in noms. sha-2 is used to compute the hash of individual chunks. This is the classic use of hashing in content-addressed systems. We also use a rolling hash to compute chunk boundaries. We do this in the typical way that tools like bup, camlistore, rsync, and others do for large files. But our observation was that if you squint your eyes, a merkle tree looks a little like a b-tree. So we use a rolling hash to break up huge lists, maps, and sets into trees where nodes are roughly 4KB. So it's a kind of self-balancing, probabilistic, deterministic b-tree thing.
aboodman 10y ago
We never chunk the same data differently. An inviolable rule of Noms is that the same logical value is always chunked the same way and always has the same hash. If I start with integers 1-1000000 and you start with integers 0-999999, and we both make mutations to converge at the same list, we will end up with the exact same tree, with the exact same hashes. This is what makes efficient synchronization and diff of noms data possible.
- ah- 10y ago
  Thanks. So it's building a hash tree with deterministic chunking and that means you can cheaply update the hash after updating parts of the tree as you only have to rehash certain bits? Does that mean that your chunk sizes are kind of fixed? Do you think there's a way to retain that advantage and be able to coalesce smaller chunks into larger ones? Say your smallest nodes are 4KB but for more efficient storage you might want to go up to 4MB chunks. Could that be done while retaining the same hash for the same underlying data?
  - bkalman 10y ago
    Keep in mind (if this wasn't clear) that the chunks are only probabilistically 4K: https://github.com/attic-labs/noms/blob/master/go/types/rolling_value_hasher.go#L16 https://github.com/attic-labs/noms/blob/master/go/types/roll.... I.e. the thing that's "fixed" here is the chunk size we're aiming for. The chunks themselves could be of any size. In any case, that's a good question - we might want to do something about that down the line. But, if we did change that constant, the structure of the trees will change, and all[1] the hashes will change. [1] a small number will stay the same

by ah- 10y ago

aboodman 10y ago

Briefly, there are two main hash functions in use in noms. sha-2 is used to compute the hash of individual chunks. This is the classic use of hashing in content-addressed systems. We also use a rolling hash to compute chunk boundaries. We do this in the typical way that tools like bup, camlistore, rsync, and others do for large files. But our observation was that if you squint your eyes, a merkle tree looks a little like a b-tree. So we use a rolling hash to break up huge lists, maps, and sets into trees where nodes are roughly 4KB. So it's a kind of self-balancing, probabilistic, deterministic b-tree thing.

aboodman 10y ago

We never chunk the same data differently. An inviolable rule of Noms is that the same logical value is always chunked the same way and always has the same hash. If I start with integers 1-1000000 and you start with integers 0-999999, and we both make mutations to converge at the same list, we will end up with the exact same tree, with the exact same hashes. This is what makes efficient synchronization and diff of noms data possible.

ah- 10y ago
Thanks. So it's building a hash tree with deterministic chunking and that means you can cheaply update the hash after updating parts of the tree as you only have to rehash certain bits? Does that mean that your chunk sizes are kind of fixed? Do you think there's a way to retain that advantage and be able to coalesce smaller chunks into larger ones? Say your smallest nodes are 4KB but for more efficient storage you might want to go up to 4MB chunks. Could that be done while retaining the same hash for the same underlying data?
- bkalman 10y ago
  Keep in mind (if this wasn't clear) that the chunks are only probabilistically 4K: https://github.com/attic-labs/noms/blob/master/go/types/rolling_value_hasher.go#L16 https://github.com/attic-labs/noms/blob/master/go/types/roll.... I.e. the thing that's "fixed" here is the chunk size we're aiming for. The chunks themselves could be of any size. In any case, that's a good question - we might want to do something about that down the line. But, if we did change that constant, the structure of the trees will change, and all[1] the hashes will change. [1] a small number will stay the same