desync: use destination chunks as an additional seed source

[vigneshraman]

Problem description:
Desync should use the existing chunks in the destination as another source of seed. Users would like OS updates to be as small as possible when applying an update.

Desync is currently doing the following:

• Uses the existing active partition as a seed
• As it writes chunks to the destination, they are recorded in a so called
  "self-seed"

This means that only already encountered chunks will form the "self-seed".

Use case:
Users switching between two update branches:

Old:  [Chunk A][Chunk B][Chunk C][Chunk D]  (update branch v1)
New:  [Chunk B][Chunk A][Chunk D][Chunk C]  (update branch v2)

Desync would download all 4 chunks, even though all 4 are already on disk, but at the different positions.

We can add an option to desync extract (--destination-as-seed). Desync would start with a read pass over the destination, identify which chunks are needed but not in their expected position (B, A, D, C in this case), save them in memory, and use them during assembly.

Without --destination-as-seed:  4 chunks downloaded
With    --destination-as-seed:  0 chunks downloaded

It benefits devices that frequently switch between OS branches. Consider a device that was on branch v1, switched to v2, and is now switching back to v1. The destination partition still contains the v1 OS from the last time it was running. Most of the chunks needed are already on disk, just at different positions. Current Desync ignores this and downloads. With this change, those chunks would be identified during the pre-scan and reused directly, reducing download size.

I would like to work on this feature and wanted to check before spending time in implementation. Does the overall design seem sensible to you? Appreciate any feedback on this. Thanks.

[folbricht]

Interesting idea. Are you thinking specifically about in-place extraction of files? If it's no in-place, then this could be solved quite easily, perhaps even with the existing features.

Keeping chunks in memory seems a little risky. There's no upper bounds on how much can be stored in memory, and given that this is used on embedded systems, it could cause some issues if not careful. Maybe the data could be stored on disk instead, though again, this could be done already with a little bit of scripting. Or if the filesystem supports cloning, the chunks could be read from that.

What exact use-case are you trying to address? It may already be possible to do this with some scripting.

[RyuzakiKK]

@vigneshraman's colleague here.

Are you thinking specifically about in-place extraction of files?

Yes, this is for in-place extraction

Or if the filesystem supports cloning, the chunks could be read from that.

We are writing to an entire disk partition, so cloning the destination is unfortunately not an option for us.

What exact use-case are you trying to address?

We use an A/B partition scheme and we have multiple branches that clients can choose from for their OS updates. E.g. stable and beta.
Consecutive updates in specific branches are usually somewhat similar between one another, e.g. an update in stable usually only have a few hundred MB of different blocks, and they could be in a shifted position. But if you go from stable to beta, it is likely that the requested update will be considerably different from your currently active image.

To give you a practical example, let's assume in stable we have 3.7.1, while in beta we have 3.8.1. If a client is running 3.7.1 and switches to beta, it will download a lot of data to apply the 3.8.1 update (expected). After a few days 3.7.2 gets released in stable and the client decided to switch back to the stable branch. This time the 3.8.1 -> 3.7.2 update will again require a lot of data to be downloaded because the self-seed of 3.8.1 doesn't have much in common with the requested update. And, even if the destination already had a quite similar 3.7.1, only the blocks that are already in the exact position will be reused.

---

Instead of storing the blocks in memory, what about going over the destination data and moving the chunks that we'll need, but are at the wrong position, into the right offset?
If we do that as the very first step, then the assemble operation could be left as-is, because it will notice that the destination already has the correct chunk at the expected position.

[folbricht]

Thanks. The example you gave, going 3.7.1 -> 3.8.1 -> 3.7.2 would in the regular case be solved by keeping the old image+index around as a seed, but that's not an option since you don't have enough space on the target. Just to make sure I understand, you start with a state like this

A == 3.8.1 (active)
B == 3.7.1

And you want to get to

A == 3.8.1
B == 3.7.2 (active)

And during the upgrade of B to 3.7.2, you want to use A as a regular seed (do you keep the indexes around?), and also the old B (containing 3.7.1) as a self-seed.

It could be quite tricky to get this right but it's possible. Do you still have the 3.7.1 index around or are you planning on chunking it in-place? The way I would try to implement this is to re-arrange the chunks in a first steps, any chunk already present in the file is copied to their new locations, then fill the gaps with new data. And you need to potentially deal with the truncation of the file to the right size if different.

[RyuzakiKK]

Just to make sure I understand, you start with a state like this

A == 3.8.1 (active)
B == 3.7.1

And you want to get to

A == 3.8.1
B == 3.7.2 (active)

And during the upgrade of B to 3.7.2, you want to use A as a regular seed (do you keep the indexes around?), and also the old B (containing 3.7.1) as a self-seed.

Yes, that's exactly the situation we are in at the moment. And we do keep the caibx of the active partition around, to avoid re chunking it in-place each time.

Do you still have the 3.7.1 index around or are you planning on chunking it in-place?

Currently we don't keep it, given that there was no practical use for it. But we could start to save it as well.

The way I would try to implement this is to re-arrange the chunks in a first steps, any chunk already present in the file is copied to their new locations, then fill the gaps with new data. And you need to potentially deal with the truncation of the file to the right size if different.

Right. That would mean something like:

• Parse the caibx of the update
• Parse the list of chunks that are currently stored in the destination
  • If we have its caibx, we don't need to do the chunking in-place
• For the chunks that we need (i.e. are on the destination and are also in the update's caibx):
  • If they are already in the correct position, do nothing
  • Otherwise copy them to the expected location

After that, applying an update as usual should take care of only filling the gaps.

[folbricht]

Adding this feature would make things a lot more efficient for sure. I thought about it during the self-seed implementation but didn't do it due to complexity. I never went back to doing that.

There's a few edge-cases that'll need to be handled gracefully, especially if concurrency is involved. Think about a layout like this:

Old:  [Chunk A][Chunk B]
New:  [Chunk B][Chunk A]

Here the data can't just be copied. Either one of the chunks is stored locally, or read from the store. And this can get arbitrarily complex:

Old:  [Chunk A][Chunk B][Chunk C]
New:  [Chunk B][Chunk C][Chunk A]

You could solve this by just loading clashing chunks from the store as usual. Or temporarily store them locally somewhere. Keeping them in memory would be an option, but would require a configurable limit to avoid surprising OOMs.

If I was implementing this, I'd probably create a plan that lays out what part goes where, what is to be loaded from the store, and what dependency on the ordering exist (as in the case of the collisions above). Then once there's a clear plan, it could then be executed in parallel. Even the current assembly logic could be updated to use a plan like that. It could even replace the self-seed if it supports proper ordering of operations.

[folbricht]

Are you planning on working on this? That code (assemble.go) is rather complex and in need of a refactor I think. You'd have to basically rewrite most of it. I may be able to take that on, but can't promise anything due to limited time.

[RyuzakiKK]

@folbricht if you'd be able to work on it, that would be great, thanks!
@vigneshraman and me can still give you an hand in case you need some help with parts of the implementation or testing.

[folbricht]

I've started looking into this, but it's slow-going given the complexities involved. Will definitely appreciate any help with testing once I get there.

[folbricht]

#316 contains a significant refactor of how files are assembled. This will build a full plan before executing. It doesn't yet move chunks that are present in the target file, but it's a foundation that'll make that possible later. The self-seed is handled very differently as well. Would you be able to try it out? I don't work with large files anymore so just relied on unit tests. The things to look out for would be:

• Is the final file correct (of course)
• Is performance comparable to before
• Does it handle seeds correctly

[RyuzakiKK]

@folbricht thank you. We'll try to do some thorough test on #316 this week.

[folbricht]

I extended it further and made a new PR (#323). This one has the features we discussed. It'll use chunks present in the target file and re-arrange everything first, before filling any gaps with other seeds or from the store. To make use of it, you'll have to provide the target file itself (and it's index) as a seed with --seed. In theory, if all chunks are present somewhere in the file already, it doesn't need to copy from a store at all.

Keeping it separate from #316 for now as the changes are a lot more complex. It contains #316 which will be closed unmerged if #323 turns out to work as expected.

[RyuzakiKK]

Thanks! @vigneshraman started to do some preliminary tests on #316, and it seems like the generated output is done correctly. Even though there is a bit of a performance hit (about 3m30s vs 4m), but I'd like to have more data before coming to conclusions about this aspect.

I skimmed your PR and it seems like the handling of invalid seeds changed. Apparently the seeds are validated only at the beginning. So, a seed that is initially valid but then changes its content during the assembly phase, it will not be regenerated on the fly, nor gets discarded. Even if we use the --regenerate-invalid-seeds option.
On top of that, it seems like it is also missing the validation of written chunks as well? Potentially leading to writing something unexpected on the destination?