idea: support for transactional groups of writes

[ianopolous]

I had a brief discussion with @whyrusleeping and wanted to start the ball rolling on a public discussion here.

Motivation:
The ability to implement an ACID database or other transactional system in a highly concurrent environment. In my use case with Peergos I am imagining many users concurrently writing to the same IPFS daemon. This means that the GC will essentially need to be called at random relative to each thread. Each user will be building up trees of objects using object.patch, before eventually committing (pinning).

Implementation:
What I had in mind was an optional parameter to all IPFS write commands which was a transaction ID (and maybe a timeout as well). Then all writes are tagged with this temporary ID within a transaction. IPFS just keeps a map from transaction ID to a set of hashes, and these form new object roots during GC. Then when a transaction is complete you could call a completeTransaction(tid) which dumps the mapping (or let it time out). This gives you guarantees that an object you've just written won't be GC'd regardless of the GC activity before you are finished with it.

[jbenet]

Good ideas 👍

[whyrusleeping]

this could be done on top of the files api, where the 'token' is just part of the path element. And then we have the root of the database namespace 'pinned' with the soon-to-be-created ipfs files pin command

[jbenet]

@ianopolous thanks for bringing this up again (in irc) -- i'm still not entirely sure what the best way to do this is. we should outline the needs and constraints, how operations function (how they may fail, how to recover), and how to implement proper consistency/safety (oplogs? journals?)

this also relates to ipfs-cluster and the "transaction oplog" we're making there. cc @hsanjuan

[wking]

Another approach to this would be use creation / access timestamps per object, and only collect garbage older than $TIMEOUT [1]. That is less stateful than tracking transactions, which is nice for robustness and simplicity. However, the timestamp-based approach doesn't give you a way to release objects once you no longer need to protect them from garbage collection. And, as @whyrusleeping points out [2], there's a lot of overlap between your proposed transaction semantics and existing pinning behavior. Maybe you're asking for pins that have an expiration date? Like [3], but for pins instead of signatures. This issue is related to #11. [1]: https://github.com/ipfs/go-ipfs/pull/1274/files#r31234525 [2]: #106 (comment) [3]: https://github.com/ipfs/specs/tree/7c897fb2057e998d61d92d5e8fb34df152104673/iprs-interplanetary-record-system#signed-expiring-after-a-time-to-live

[ianopolous]

@wking I don't think that would give you any guarantees. Consider the example where a user is doing a single add of a large file, which can take arbitrarily long. Half way through writing this file, someone else calls GC. I believe (correct me if I'm wrong @whyrusleeping ) but this would gc all the objects written for the first half of the file. Even if that is handled correctly internally, and the sub objects aren't able to be gc'd, it proves that the user needs to control the timeout of the transaction.

There isn't any overlap between my proposal and object pinning: It would work in conjunction with pinning.
e.g.

add object X with transactionID T, giving multihash H
pin (H)
completeTransaction(T)

or a more complex example:

add object X with transactionID T, giving multihash H1
add object Y (which has a merkle link to H1) with transactionID T, giving multihash H2
pin -r (H2)
completeTransaction(T)

To me this is a very simple mental model which gives you real guarantees and thus allows you to construct algorithms which are robust under concurrency.

[wking]

On Thu, Dec 22, 2016 at 02:20:11PM -0800, Ian Preston wrote: Consider the example where a user is doing a single add of a large file…

This is not an atomic push of a single object. The file gets chunked and sharded. You push chunks 1, 2, 3, …, and then fan-out objects i, ii, iii, …. You only need the expiring pin (which can be explicit or creation-time based) on one object to last long enough for you to push the parent (after which the expiring pin on the parent will protect its ancestors from garbage collection). With deep, skinny trees (e.g. Git histories), the time-until-you-push-a-parent is going to be fairly constant. With wide, bushy trees (e.g. huge files with multiple fan-out layers), the time-to-parent is going to increase exponentially by fan-out layer. With a configurable expiration time, you can still handle wide, bushy trees safely if the expiration times are configurable. For example, “I won't get a parent for this object for around 2 hours. Please don't GC it for the next three hours”. Or maybe “My network is flaky. Please keep everything I push for 24 hours”.

… completeTransaction(T) ``` To me this is a very simple mental model which gives you real guarantees and thus allows you to construct algorithms which are robust under concurrency.

The issue here is “what happens if the client dies while pushing and never releases the transaction?”. Unless your transactions expire (in which case, they're back to looking like expiring pins), the server will eventually get bogged down tracking an always-increasing number of opened-but-abandoned transactions.

[ianopolous]

With a configurable expiration time,
you can still handle wide, bushy trees safely if the expiration times
are configurable.

The timeout would have to be configurable on a call by call basis, which is exactly what I'm suggesting.

All the calls I'm suggesting have a user controlled timeout (see the first comment), in my code examples I left it as an implicit parameter. This means the behaviour is well defined for ipfs crashes and restarts, assuming the return from the write command means that the transactionID + timeout and hash have been "written to disk". Upon restart, ipfs just continues the timeout. To be clear, all transactions would have a timeout controlled by the user. This would also play well with ipfs-cluster, where "write to disk" means safely committed to as many nodes as the cluster setup requires, or erasure coded or whatever.

Let's assume that ipfs can handle the internal writing of a large file correctly under concurrency. The timeout would need to be from completion of writing of the final root object, whatever the write command called. The timeout for a transaction would get updated with every write in the same transaction, so you can "keep asking for more time" effectively (another property lacking in an expiring pin model).

Expiring pins cannot help here. Consider the following interleaving:

add object X with transactionID T, timeout t, giving multihash H
gc (from another thread)
pin (H)
completeTransaction(T)

We've lost our object immediately because of another thread calling gc. This can't be fixed by any modification to the pin call, because the damage is already done before the pin call starts.

[wking]

The timeout for a transaction would get updated with every write in the same transaction, so you can "keep asking for more time" effectively (another property lacking in an expiring pin model).

I agree that you'd need a way to ask for more time, but I don't see why you couldn't get that with expiring pins. And it would give you a way to guard an existing object:

err = pin(object.hash, expiration=estimated_time_to_patent + buffer)
If err == DoesNotExist:
    push(object.content, expiration=estimated_time_to_patent + buffer)

... the damage is already done before the pin call starts.

Yeah, you'd need either a default expiring pin on all objects that lasts long enough for the explicit pin placement or a way to set (expiring) pins atomically with the push.

But these expiring pins look a lot like your expiring transactions. The trade off is that transactions can be explicitly closed/canceled if you finish early but require per-(object, transaction) tracking on the server, while expiring pins are not cancelable (unless your OK with Bob removing Alice's pin) and only require a single value (the max expiration time) to be tracked per object.

[jbenet]

We've considered a similar heuristic like "dont gc things added in less than sec" that may help some, but may introduce other problems.

I think good transactional semantics are useful to define, and ipfs (at least the repo business) is quite simple; this should be easy.

I think a place to start would be to go over the core api, refine the functions we want to "transactionize" (i suspect they're likely the same as for ipfs-cluster cc @hsanjuan) and then propose how we would do the transaction on each.

How we do GC can definitely be rethought quite a bit to support these operations safely.

[ianopolous]

For a concrete example of a complex operation I'd like to put in a transaction, have a look at Peergos' write to a merkle-btree, the recursive put method: https://github.com/Peergos/Peergos/blob/master/src/peergos/shared/merklebtree/TreeNode.java#L80

Note that's written in an asynchronous way using CompletableFutures so that it can be automatically compiled to Javascript and use native Promises in a browser. Ordinarily I'd just use synchronous Java code which is easier to read. You can ignore the UserPublicKey argument, and the ContentAddressedStorage argument is IPFS.

Essentially, it has to modify ~ log(tree size) nodes resulting in a new root which I then pin. Non leaf nodes have merkle links to other nodes, and leaf nodes have merkle links to larger data objects.

A much simpler use case at my day job is a single add-and-pin of a large file.

[ianopolous]

@whyrusleeping Another, much simpler, idea I had to solve all these use cases is to give every write command an option to also pin (recursively) the result (the assumption is that each command itself is atomic internally with respect to gc). This would then allow the user to build up arbitrary structures, then when the final root is written and pinned) explicitly unpin all the child pins. Obviously then the burden is on the client to keep track of all their intermediate pins in a transaction, but that is easy.

[jbenet]

@ianopolous yeah i think that would work. that -- as a baseline -- should be possible. i woudl like to support larger transaction batches though

[whyrusleeping]

Let's make an issue to add pinning options to all write commands for now. That will at least help the short term

…

On Sat, Dec 24, 2016, 14:27 Juan Benet ***@***.***> wrote: @ianopolous <https://github.com/ianopolous> yeah i think that would work. that -- as a baseline -- should be possible. i woudl like to support larger transaction batches though — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#106 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABL4HMJS9zAODhIF7kwVN72B0ntbuHLHks5rLR2mgaJpZM4HQMdV> .