4 ms·

Mutable Value Chains

28 points by c-rack 11y ago

kushti 11y ago
So Datomic over KV storage or DHT? Could be useful, in case of a very efficient implementation.
amelius 11y ago
> I’ve been wondering how to do this for years, and suddenly it occurred to me how to do this. One way that doesn’t work is to view the sequence of values as some kind of linked list, where each value has an invisible write-once-only pointer to the next value. The write-once-pointer gets updated when the value is updated, unfortunately this is difficult to implement and there are problems with consistency. Why? > The solution is blindingly simple (once you see it) - we represent the sequence as a set Key-Value pairs where the Keys are taken from an iterated sequence of SHA1 checksums. The first key is a random number, thereafter Key[i] = sha(Key[i-1]). Why not simply use Key[0] = 0, and Key[i] = Key[i-1]+1, or, in other words Key[i] = i?
- vannevar 11y ago
  Because, as I read the article, each key[i=0] represents a single value chain and you're going to have many chains in the store, presumably being written by multiple processes. So if you were inserting based on some global incrementing counter, you couldn't be sure that key[n+1] belonged to the same chain as key[n]. Using iterated SHA1 gives reasonable assurance that key[i+1] will be unique while at the same time making it a function of key[i] so that it can easily be found given that initial key.
  - amelius 11y ago
    Then how about using a double key (i,j) where j is the global chain number?
pjc50 11y ago
Part CRDT, part blockchain.
gardnr 11y ago
It sounds smart. Just swap out the sha1 for public-key signatures and rename the "value chain" to "block chain" and Bob's your uncle. No but seriously: "SHA which I have chosen in this article has 160 bits, so after more than 2^160 entries have been put into the DHT collisions will occur" Collisions are largely related to the content that you are hashing. If you are hashing sequential 160 bit chunks of data then Joe's math is theoretically correct. If you are hashing DVD ISO images then you can use math to predict why you should never use sha1. If you needed to cram it into 160 bits for some hardware reason then you could implement some form of write failure recovery to redistribute writes over them remaining available key space but this would get slower and slower the less and less space you have unless you implement some kind of free space map.
- vosper 11y ago
  So it's just about the address space? SHA 512 would be fine / sufficiently unlikely to collide in real life?
contravariant 11y ago
>If the sequence of X’s is huge then multiple workers can be started tell them to start computing values at different points in the value chain. How? All the keys need to be calculated sequentially which, depending on the application, can take a significant amount of time. Worse this time grows linearly with the number of cores, so massively parallel calculations with several hundreds, thousands, of cores will become increasingly inefficient.

28 points by c-rack 11y ago

So Datomic over KV storage or DHT? Could be useful, in case of a very efficient implementation.

> I’ve been wondering how to do this for years, and suddenly it occurred to me how to do this. One way that doesn’t work is to view the sequence of values as some kind of linked list, where each value has an invisible write-once-only pointer to the next value. The write-once-pointer gets updated when the value is updated, unfortunately this is difficult to implement and there are problems with consistency. Why? > The solution is blindingly simple (once you see it) - we represent the sequence as a set Key-Value pairs where the Keys are taken from an iterated sequence of SHA1 checksums. The first key is a random number, thereafter Key[i] = sha(Key[i-1]). Why not simply use Key[0] = 0, and Key[i] = Key[i-1]+1, or, in other words Key[i] = i?

vannevar 11y ago
Because, as I read the article, each key[i=0] represents a single value chain and you're going to have many chains in the store, presumably being written by multiple processes. So if you were inserting based on some global incrementing counter, you couldn't be sure that key[n+1] belonged to the same chain as key[n]. Using iterated SHA1 gives reasonable assurance that key[i+1] will be unique while at the same time making it a function of key[i] so that it can easily be found given that initial key.
- amelius 11y ago
  Then how about using a double key (i,j) where j is the global chain number?

pjc50 11y ago

Part CRDT, part blockchain.

gardnr 11y ago

It sounds smart. Just swap out the sha1 for public-key signatures and rename the "value chain" to "block chain" and Bob's your uncle. No but seriously: "SHA which I have chosen in this article has 160 bits, so after more than 2^160 entries have been put into the DHT collisions will occur" Collisions are largely related to the content that you are hashing. If you are hashing sequential 160 bit chunks of data then Joe's math is theoretically correct. If you are hashing DVD ISO images then you can use math to predict why you should never use sha1. If you needed to cram it into 160 bits for some hardware reason then you could implement some form of write failure recovery to redistribute writes over them remaining available key space but this would get slower and slower the less and less space you have unless you implement some kind of free space map.

vosper 11y ago
So it's just about the address space? SHA 512 would be fine / sufficiently unlikely to collide in real life?

contravariant 11y ago

>If the sequence of X’s is huge then multiple workers can be started tell them to start computing values at different points in the value chain. How? All the keys need to be calculated sequentially which, depending on the application, can take a significant amount of time. Worse this time grows linearly with the number of cores, so massively parallel calculations with several hundreds, thousands, of cores will become increasingly inefficient.