4 ms·

Thanks, that answers my questions. Your snapshot system reminds of a reference counting GC - neat trick.

by smanek 18y ago

cperciva 18y ago
As it happens, tarsnap's snapshots work via reference counting -- fortunately, it works better for tarsnap than it does for garbage collection. (Reference counting breaks if you have circular references; this is a problem for garbage collection, but not for tarsnap.)
- eru 18y ago
  Why didn't you go for a 'real' GC?
  - cperciva 18y ago
    I have no clue what your question is trying to ask. Can you clarify?
    - eru 18y ago
      Why did you choose to do reference counting instead of more sophisticated techniques? I can imagine that ref. counting is much easier to implement and the drawbacks are unimportant in your domain. However I'd still like to read about the reasons for your decision, since you will have thought about that issue much longer and clearer. But I guess I should take a deeper look at http://www.daemonology.net/blog/2008-11-10-tarsnap-public-beta.html http://www.daemonology.net/blog/2008-11-10-tarsnap-public-be... before writing anything..
      - cperciva 18y ago
        Oh, now I understand. Methods such as reachability analysis require reading lots of memory locations; but for tarsnap, "memory locations" are blocks of data stored remotely, so this gets expensive (and slow) very quickly. With reference counting, the counts can be stored locally and no extraneous data needs to bs transferred to or from the server.
        pmjordan 18y ago
        I guess there's a precedent there in the fact that unix file systems use reference counting for file links, presumably for the same reasons. Considering how well-architected tarsnap seems to be, I suspect you've taken steps to avoid losing data via inconsistencies in the reference counter?
        cperciva 18y ago
        ... you've taken steps to avoid losing data via inconsistencies in the reference counter? There are some sanity checks built in, but in the extreme case what you're suggesting is impossible. Reference counts are managed on the client side, and the client has the keys necessary to delete blocks from the server; if the client is functioning correctly, it won't get the reference counts wrong, but if the client is malfunctioning then it could go berserk and delete blocks without even looking at the reference counts. I have taken care of the obvious issues, though -- as long as the OS implements fsync() properly, there's no way that tarsnap or the client system crashing will result in corruption.

Thanks, that answers my questions. Your snapshot system reminds of a reference counting GC - neat trick.

by smanek 18y ago

Thanks, that answers my questions. Your snapshot system reminds of a reference counting GC - neat trick.

As it happens, tarsnap's snapshots work via reference counting -- fortunately, it works better for tarsnap than it does for garbage collection. (Reference counting breaks if you have circular references; this is a problem for garbage collection, but not for tarsnap.)

eru 18y ago
Why didn't you go for a 'real' GC?
- cperciva 18y ago
  I have no clue what your question is trying to ask. Can you clarify?
  - eru 18y ago
    Why did you choose to do reference counting instead of more sophisticated techniques? I can imagine that ref. counting is much easier to implement and the drawbacks are unimportant in your domain. However I'd still like to read about the reasons for your decision, since you will have thought about that issue much longer and clearer. But I guess I should take a deeper look at http://www.daemonology.net/blog/2008-11-10-tarsnap-public-beta.html http://www.daemonology.net/blog/2008-11-10-tarsnap-public-be... before writing anything..
    - cperciva 18y ago
      Oh, now I understand. Methods such as reachability analysis require reading lots of memory locations; but for tarsnap, "memory locations" are blocks of data stored remotely, so this gets expensive (and slow) very quickly. With reference counting, the counts can be stored locally and no extraneous data needs to bs transferred to or from the server.
      - pmjordan 18y ago
        I guess there's a precedent there in the fact that unix file systems use reference counting for file links, presumably for the same reasons. Considering how well-architected tarsnap seems to be, I suspect you've taken steps to avoid losing data via inconsistencies in the reference counter?
        cperciva 18y ago
        ... you've taken steps to avoid losing data via inconsistencies in the reference counter? There are some sanity checks built in, but in the extreme case what you're suggesting is impossible. Reference counts are managed on the client side, and the client has the keys necessary to delete blocks from the server; if the client is functioning correctly, it won't get the reference counts wrong, but if the client is malfunctioning then it could go berserk and delete blocks without even looking at the reference counts. I have taken care of the obvious issues, though -- as long as the OS implements fsync() properly, there's no way that tarsnap or the client system crashing will result in corruption.