Add multi core support for compression

[Byron]

Duplicity compresses and decompresses with a single process atm. Performance can be increased by parallelizing this process. This in turn could be done using something like mgzip.

https://code.launchpad.net/~byronester/duplicity/duplicity

[Kenneth Loafman (kenneth-loafman)]

We need to look into https://facebook.github.io/zstd as it seems to be the up and coming multithreaded compressor. It is in use now in the Linux kernel and other major software. It should be stable and hopefully have a long life.

A proper Python interface lives at https://pypi.python.org/pypi/zstandard.
We would still have to support gzip decompression for a long while.

[Byron (byronester)]

Ok, I've had a bit more of a look and play with zstd.
Unfortunately it isn't gzip compatible. I was hoping it would be.
That interferes with my plan on improving duplicity for everyone out of the
box, no changes required.

Have you heard of MiGz? https://github.com/linkedin/migz
Multithreaded and gzip compatible from LinkedIn. Downside being that it's
only Java based atm.
We could do a Python conversion though...?
Oh, the source mentions the size penalty of parallel compression and extra
headers being about 1%. Sounds reasonable.

What do you think? Personal preference for me is to continue supporting
gzip but with better performance.

On Thu, 6 Feb 2020 at 00:30, Kenneth Loafman <email address hidden> wrote:

> We need to look into https://facebook.github.io/zstd as it seems to be
> the up and coming multithreaded compressor. It is in use now in the
> Linux kernel and other major software. It should be stable and
> hopefully have a long life.
>
> A proper Python interface lives at https://pypi.python.org/pypi/zstandard.
>
> We would still have to support gzip decompression for a long while.
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1860200
>
> Title:
> Add multi core support for compression
>
> Status in Duplicity:
> New
>
> Bug description:
> Duplicity compresses and decompresses with a single process atm.
> Performance can be increased by parallelizing this process. This in
> turn could be done using something like mgzip.
>
> https://code.launchpad.net/~byronester/duplicity/duplicity
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/duplicity/+bug/1860200/+subscriptions
>

[Kenneth Loafman (kenneth-loafman)]

The goal I have is to move things around a bit so that the backends can be multitasked, like so:

duplicity --> [sockets] --> [backend-pool]

where each task in [backend-pool] runs the process:

socket --> gpg|gzip|plain --> remote-storage

While each task is inherently single threaded, multiple tasks can make use of multiple cores.  If we throw a multithreaded gzip into the mix balancing plays a big role.  I'm not sure it's worth the effort at this point.

duplicity itself would remain single threaded until we are pure Python 3 and can make use of async I/O it provides.

Take a look at the GIL, Global Interpreter Lock, and its issues for multithreading, thus multitasking over multithreading.

[Byron (byronester)]

Sorry, I find this comment a little confusing...

You mentioned zstd earlier. I would've thought a multithreaded gzip would be comparable to zstd in terms of what you propose with your goal of moving things around.

Did you change your mind since proposing zstd or am I misunderstanding something?

[Kenneth Loafman (kenneth-loafman)]

OK, my thinking is this. I may be wrong.

There are three modes in storage: encrypted, compressed, plain. Duplicity is primarily used in the encrypted mode and that's where it needs the most help since encryption is inherently slow and suitable for only one CPU, AFAIK. The other modes I would discourage unless you are storing to an encrypted drive locally (big fan of encryption for privacy). Remote encryption means they have control of your keys and big brother can easily watch.

What that means to me is that enhancing one path through the process is good, but we should really concentrate on making use of multithreading/multiprocessing where we can do the most good across all the modes.

By making the backends individually responsible for one output file and one connection in each task we get a combination of multi-core and multi-connection savings by multitasking. Overall, I think that would be a better solution overall. However, it will require a bit of work.

That said, I would not reject compression routine that is multithreaded. I would even help in the development some. I'm just looking at the big picture and offering tradeoffs.

Sorry for the confusion.

[Byron (byronester)]

Could you please have a look at
https://bugs.debian.org/cgi-bin/bugreport.cgi?bug=848951 for discussion
around parallelizing gpg encryption (with reference to Duplicity)?
The conclusion I take away is that unless we push for change it probably
won't happen by itself anytime soon.
As mentioned at the end though, there is a wishlist category for gnupg and
the possibility to add this feature.

Does this have any influence on how you think about Duplicity?
Does is influence how you/we might approach parallelizing compression and
decompression?

On Thu, 20 Feb 2020 at 00:51, Kenneth Loafman <email address hidden> wrote:

> OK, my thinking is this. I may be wrong.
>
> There are three modes in storage: encrypted, compressed, plain.
> Duplicity is primarily used in the encrypted mode and that's where it
> needs the most help since encryption is inherently slow and suitable for
> only one CPU, AFAIK. The other modes I would discourage unless you are
> storing to an encrypted drive locally (big fan of encryption for
> privacy). Remote encryption means they have control of your keys and
> big brother can easily watch.
>
> What that means to me is that enhancing one path through the process is
> good, but we should really concentrate on making use of
> multithreading/multiprocessing where we can do the most good across all
> the modes.
>
> By making the backends individually responsible for one output file and
> one connection in each task we get a combination of multi-core and
> multi-connection savings by multitasking. Overall, I think that would
> be a better solution overall. However, it will require a bit of work.
>
> That said, I would not reject compression routine that is multithreaded.
> I would even help in the development some. I'm just looking at the big
> picture and offering tradeoffs.
>
> Sorry for the confusion.
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1860200
>
> Title:
> Add multi core support for compression
>
> Status in Duplicity:
> In Progress
>
> Bug description:
> Duplicity compresses and decompresses with a single process atm.
> Performance can be increased by parallelizing this process. This in
> turn could be done using something like mgzip.
>
> https://code.launchpad.net/~byronester/duplicity/duplicity
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/duplicity/+bug/1860200/+subscriptions
>

[Kenneth Loafman (kenneth-loafman)]

It looks like the gnupg folks are working towards a parallel solution, and will probably have it before we can get a solution into duplicity. I will join in and post a wishlist bug to them to get it done soon. I don't think either theirs or ours will be soon in any sense of the word.

[Byron (byronester)]

I think there may be some confusion in this conversation Ken. Sorry, let me
just explain where I currently stand.

I don't think it would be possible for us to parallelize the encryption in
Duplicity without it being done first in gnupg.
This is because you don't do the encryption yourself, but outsource it to
the gnupg process. So it's the gnupg process
that needs parallelizing.

Compression on the other hand is a completely separate problem that needs
to be tackled separately.
You're the one doing the compression inside of the Duplicity process,
through the use of libraries, so it's up to you to parallelize it.
This I believe is achievable.

To reiterate, I don't think you can't implement parallelization for both
encryption and compression in Duplicity.
Compression we can do, but it's up to gnupg to parallelize the encryption.

On Mon, 24 Feb 2020 at 22:20, Kenneth Loafman <email address hidden> wrote:

> It looks like the gnupg folks are working towards a parallel solution,
> and will probably have it before we can get a solution into duplicity.
> I will join in and post a wishlist bug to them to get it done soon. I
> don't think either theirs or ours will be soon in any sense of the word.
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1860200
>
> Title:
> Add multi core support for compression
>
> Status in Duplicity:
> In Progress
>
> Bug description:
> Duplicity compresses and decompresses with a single process atm.
> Performance can be increased by parallelizing this process. This in
> turn could be done using something like mgzip.
>
> https://code.launchpad.net/~byronester/duplicity/duplicity
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/duplicity/+bug/1860200/+subscriptions
>

[Kenneth Loafman (kenneth-loafman)]

Go back and read #3 again. I'm talking about running like this:

duplicity--->backend process 1
         --->backend process 2
         ...
         --->backend process N

Where each backend process handles gzip,gpg,plain as needed. This gives N-way multiprocessing and uses N cores for both IO and processing. In this scenario a multithreaded gzip would actually slow down the processing if it were to use all cores.

[Byron (byronester)]

Ok, thanks. I don't think I fully understood that part of the conversation.
Thanks Ken and sorry for the confusion.
I think with all of these parallel compression/decompression libraries,
I've always seen an option to specify the level
of parallelism. MGZip for example has a threads parameter. If you force it
to use all cores, it will, but by no means do
you have to do that.

On Thu, 27 Feb 2020 at 00:25, Kenneth Loafman <email address hidden> wrote:

> Go back and read #3 again. I'm talking about running like this:
>
> duplicity--->backend process 1
> --->backend process 2
> ...
> --->backend process N
>
> Where each backend process handles gzip,gpg,plain as needed. This gives
> N-way multiprocessing and uses N cores for both IO and processing. In
> this scenario a multithreaded gzip would actually slow down the
> processing if it were to use all cores.
>
> --
> You received this bug notification because you are subscribed to the bug
> report.
> https://bugs.launchpad.net/bugs/1860200
>
> Title:
> Add multi core support for compression
>
> Status in Duplicity:
> In Progress
>
> Bug description:
> Duplicity compresses and decompresses with a single process atm.
> Performance can be increased by parallelizing this process. This in
> turn could be done using something like mgzip.
>
> https://code.launchpad.net/~byronester/duplicity/duplicity
>
> To manage notifications about this bug go to:
> https://bugs.launchpad.net/duplicity/+bug/1860200/+subscriptions
>

[TimSmall (tim-seoss)]

I was wondering why zstd was considered a no-go? Given that zstd is so much more CPU and/or space efficient (in a single thread), I suspect it would be a win to use zstd (with or without multithreaded operation).

In my particular application I'm interested in reducing network bandwidth and disk storage usage.

On my test data (90 megabytes of source code and object files):

For less CPU usage (40% fewer CPU cycles consumed - single threaded), zstd -15 gives output which is also ~21% smaller than zlib -9 (this obviously has additional savings in reduced encryption time in the next stage too).

If instead the target is to achieve the same compression ratio as zlib, but with minimised CPU usage, then:

For MUCH less CPU usage (95% (!!) fewer CPU cycles consumed - single threaded), zstd -2 gives output which is slightly smaller than zlib -9.

These numbers came from:

tar cf - dir/ | time zstd -c -16 | dd of=/dev/null

vs.

tar cf - dir/ | time zstd -c -2 | dd of=/dev/null

vs.

tar cf - dir/ | time gzip -c -9 | dd of=/dev/null

So at a first approximation, to achieve the same compression ratio: single-threaded zstd would be as fast as zlib running on 10 cores (I know you're considering a different zlib compatible implementation, but still, the numbers shouldn't be hugely different)...

[Kenneth Loafman (kenneth-loafman)]

Please go back and read at least #5 https://bugs.launchpad.net/duplicity/+bug/1860200/comments/5.

I am not against multiprocessing compression, I just think that my time is best spent elsewhere.

If you will put up an MR at https://gitlab.com/duplicity/duplicity I'll consider it, but I think you're tackling the wrong problem overall.