In this section, we will describe the most important operations, policies and algorithm used in the final prototype. We will start describing the data structures used and then, the four main operations will be explained with some detail. We have to keep in mind that only the main ideas are described and that technical issues such as locking or very infrequent situations are not presented in the paper.
Regarding some implementation details, the prototype has been built
in the Linux operating system (kernel version 2.0.34) [2].
The compression algorithm chosen has been lzo [11]
which is based on the Ziv-Lempel data compressor [17]. This
algorithm was chosen as it obtained a good ratio between speed and
compression. On one hand, it achieved compression ratios better than
50% in most of the experiments (Table 1). On the other
hand, the average time needed to compress a 4Kbyte page is about 300
microseconds while the one needed to decompress a buffer is only about
50 microseconds 
.