Reducing SquashFS delta size through partial decompression

In a previous article titled ‘using deltas to speed up SquashFS ebuild repository updates’, the author has considered benefits of using binary deltas to update SquashFS images. The proposed method has proven very efficient in terms of disk I/O, memory and CPU time use. However, the relatively large size of deltas made network bandwidth a bottleneck.

The rough estimations done at the time proved that this is not a major issue for a common client with a moderate-bandwidth link such as ADSL. Nevertheless, the size is an inconvenience both to clients and to mirror providers. Assuming that there is an upper bound on disk space consumed by snapshots, the extra size reduces the number of snapshots stored on mirrors, and therefore shortens the supported update period.

The most likely cause for the excessive delta size is the complexity of correlation between input and compressed output. Changes in input files are likely to cause much larger changes in the SquashFS output that the tested delta algorithms fail to express efficiently.

For example, in the LZ family of compression algorithms, a change in input stream may affect the contents of the dictionary and therefore the output stream following it. In block-based compressors such as bzip2, a change in input may shift all the following data moving it across block boundaries. As a result, the contents of all the blocks following it change, and therefore the compressed output for each of them.

Since SquashFS splits the input into multiple blocks that are compressed separately, the scope of this issue is much smaller than in plain tarballs. Nevertheless, small changes occurring in multiple blocks are able to grow delta two to four times as large as it would be if the data was not compressed. In this paper, the author explores the possibility of introducing a transparent decompression in the delta generation process to reduce the delta size.

Read on… [PDF]

A few words on lzip compressor

Some of you may already have noticed that sys-apps/ed and sys-fs/ddrescue packages started pulling in lzip archiver. «Is this some new fancy archiver?» you may ask. The answer is «no. It’s been around for a very long time, and it never got any real interest.»

You can read some of the background story in New Options in the World of File Compression Linux Gazette article. Long story short, lzip was created before xz as a response to the limitations of .lzma format used by lzma-utils. However, it never got any real attention and when xz-utils was released as a direct successor to lzma-utils it became practically redundant. And the two projects co-existed silently until lately…

Over the past five years, Antonio Diaz Diaz, lzip’s author, and a few project supporters were trying to convince the community that the lzip format is superior to xz. However, they were never able to provide any convincing arguments to the community, and while xz gained popularity lzip stayed in the shadow. And it was used mostly by the projects Diaz was member of.

It seems that he has finally decided that advocacy will not help his pet project in gaining popularity. Instead, he decided to take advantage of his administrator position in the mentioned GNU projects and discontinue providing non-.lz tarballs. As he says, «surely every user of ddrescue would like to know about lzip […]».

So, Gentoo user, would you like to know about lzip? Let’s try to get a few fair points here.

Continue reading

Using deltas to speed up SquashFS updates

The ebuild repository format that is used by Gentoo generally fits well in the developer and power user work flow. It has a simple design that makes reading, modifying and adding ebuilds easy. However, the large number of separate small files with many similarities do not make it very space efficient and often impacts performance. The update (rsync) mechanism is relatively slow compared to distributions like Arch Linux, and is only moderately bandwidth efficient.

There were various attempts at solving at least some of those issues. Various filesystems were used in order to reduce the space consumption and improve performance. Delta updates were introduced through the emerge-delta-webrsync tool to save bandwidth. Sadly, those solutions usually introduce other inconveniences.

Using a separate filesystem for the repositories involves additional maintenance. Using a read-only filesystem makes updates time-consuming. Similarly, the delta update mechanism — while saving bandwidth — usually takes more time than plain rsync update.

In this article, the author proposes a new solution that aims both to save disk space and reduce update time significantly, bringing Gentoo closer to the features of binary distributions. The ultimate goal of this project would be to make it possible to use the package manager efficiently without having to perform additional administrative tasks such as designating an extra partition.

Read on… [PDF]

Getting tokens for verification

Recently I’ve been working on implementing SSL authentication in Okupy (as you can see from the previous post). The specifics of chosen solution required the authentication to occur on a separate virtual host. Due to specifics of django, it was impossible to directly access the initial session from the dedicated vhost.

I had two possibilities. The supposedly simpler one involved passing the session identifier to the dedicated vhost so that it would be able to access the session information and store the authentication result there. But it involved hacking a fair bit of django (since the new versions no longer give access to the session identifier directly), starting the session early (it needn’t be started until the user is actually authenticated) and could introduce security issues.

The other involved passing the authentication results outside of the session framework and using dedicated tokens to claim the results. Those tokens have similar requirements to the tokens used e.g. for e-mail address verification.

First of all, the tokens must be guaranteed to be unique. Otherwise, there would be a finite probability that two users will be given same token. In case of e-mail address verification, this would mean that one user could confirm the other user’s (possibly invalid) e-mail address. In case of SSL authentication, one user would be able to claim other user’s login.

Secondly, the tokens need to be semi-random and hard to guess. The user, being able to obtain multiple valid authentication tokens in sequence (e.g. through requesting multiple valid e-mail account verifications), must not be able to predict the value of the token for another (possibly invalid) address. At least with reasonable resources.

Continue reading

SSL certificate login for okupy

In this year’s GSoC, I’m co-working on identity.gentoo.org that intends to become a central place for logging in to various Gentoo sites. One of the fancy features that I’d like to implement is SSL-certificate based login.

The client certificate-based authentication is a kind of public key authentication. In order to login, you provide the server with your certificate (containing your public key) and a signature made with your private key. Your private key is never exposed to the server which greatly improves security, and you don’t have to have a store of random passwords.

Unlike many common authentication methods that are implemented in application space, client certificates are part of the SSL/TLS protocols. As a result, they’re supported quite widely by web browsers. But this also introduces a few limitations that will affect the use.

Continue reading