Add 'ipfs pin update' command

[whyrusleeping]

Usecase: I have a large graph pinned. I make a change to this graph, and now i want to pin the new root, and unpin the old root.

You can accomplish this today by just ipfs pin add <NEW> and ipfs pin rm <OLD> but this has a couple drawbacks. First, it has to rescan the entire new graph. If we had the context of the old pin around, we could skip traversing subtrees that are in the old graph since theyre already pinned (and guaranteed as far as this process is concerned to be there). This would make the pin update process much faster. The second concern, which is relatively minor in comparison is that doing add and rm is two operations on the pinset, where an update could be coalesced into just one. Pinset modifications currently get expensive with a very large number of pins, and this might be noticeable.

[whyrusleeping]

cc @ianopolous for further usecase discussion

[kevina]

This sounds fairly easy and self-contained. @whyrusleeping is this what you had in mind for the syntax?

ipfs pin update <OLD> <NEW>

[whyrusleeping]

@kevina Yeap! That is indeed

[kevina]

Okay I will work on implementing it this week.

[ianopolous]

Let me give some more details around our use case:
Currently when a user commits a write to their file system in Peergos we have a 3 step process:

1. pin the new file system root
2. CAS in the new root into our IPNS equivalent
3. unpin the old root

This allows us to guarantee to not be in an inconsistent state if the process aborts at any stage, including relative to arbitrary concurrent GCs. If the process aborts after 1, the IPNS is still pointing to the old root which is still pinned. If it aborts after 2, then we have committed the write, but just have an extra pin which is fine, and can be corrected later.

For us to be able to use this in step 1 it can't unpin the old root, that would still need to be step 3. That could be an option though, whether or not to unpin the old root. Thoughts? @whyrusleeping

[whyrusleeping]

Yeah, we can definitely have a --unpin-old option that defaults to true.

[kevina]

Based on my understand how pin add and pin rm work currently the potential for saving is limited. In order to "skip traversing subtrees that are in the old graph since they are already pinned" we would have to know what those subtrees are, which will mean traversing the old graph. Currently as far as I know pin rm does not do that for recursive pins, so just to discover the pinned nodes we would likely need to traverse the graph anyway. Now if the new pin uses the root of the old pin, there is a savings there. Also if the new pin uses nodes at a shallow dept, for example if the graph was:

     a
  /   |  \
b    c   d
| 
e

and the new pin uses b c or d we could optimize the code to a depth limited traversal of the old pin to discover likely pinned subtrees to be used by the new pin. (My apologizes if I made a mistake in my analysis here.)

Let me know if you still think it is worth it.

Another option I consider is to rework the pinning code to support batch operations. I am not sure how much we can save here for this use case, but in the case when a full traversal of all recursive pins is required the savings can be significant.

[ianopolous]

Our use case involves a btree. If our btree is depth n it has O(16^n) nodes. During a write, we only have to modify O(n) elements, from the new/modified element down to the root. So if you lazily traverse the old graph to discover already pinned sub-trees as you pin the new one, you will get reduction from O(16^n) to O(n) for the pin add component.

[whyrusleeping]

@kevina This is the optimization, lets say we have a pin on node a here.

     a
  /   |  \
b    c   d
| 
e

And lets say 'a' is a directory that we patch a new file into:

       a
  /   |  \   \
b    c   d   f
| 
e

Now, with ipfs pin update X Y we can start a traversal from both roots simultaneously. Since both roots have a child named 'b' with the same hash, we can skip going down that route. Now both roots also share c and d, so we can skip those as well. The only difference is the new pin has 'f' and the old one does not. So we will have to traverse through 'f' to ensure all those blocks are around.

The savings here get much high the larger the graphs are, this is a very common thing, and it will actually make mfs changes MUCH faster

[ianopolous]

The relevant PR is #3846

[kevina]

Removing my assignment. @whyrusleeping decided to do the p.r.

[whyrusleeping]

PR is up, will likely merge in 0.4.10

[magik6k]

closing as #3846 has been merged