[original file is ccache_celf_2007-08-31_jp.pdf by Ikeda, NEC]
[translated by ikoma]


CELF Technical Jamboree #16
Aug. 31, 2007


[See original file for figures] (c) NEC Corporation 2006


Overview and Issues of Compressed Cache

Aug 31st, 2007[BR] IKEDA, Munehiro[BR]

m-ikeda at ds dot jp dot nec dot com


Page 2 (c) NEC Corporation 2006

Contents

* What is Compressed Cache?

* Overview of Implementation

* Evaluation of Effectiveness

* Issues

* Personal View for the Future

* Appendix : Resources


Page 3 (c) NEC Corporation 2006

What is Compressed Cache?

* Overview

* History

* Status


Page 4 (c) NEC Corporation 2006

Overview of Implementation

[see original file for figure]

* Relation of data on memory and block device (vanilla)

   +-----------+   +-------------+
   |   swap    |   | file system |
   +-----------+   +-------------+
        ^                ^               block device
--------|----------------|---------------------------
        v                v               memory
   +----------+    +------------+
   | anon mem |    | page cache |
   +----------+    +------------+


Page 5 (c) NEC Corporation 2006

Overview of Implementation

[see original file for figure]

* Relation of data on memory and block device (compressed cache)

   +-----------+   +-------------+
   |   swap    |   | file system |
   +-----------+   +-------------+
        ^                ^               block device
--------|----------------|---------------------------
        v                v               memory
   +----------+    +------------+
   | anon mem |    | page cache |
   +----------+    +------------+
        ^                ^
        |                |
        v                |
+ - - - - - - - - +      |
   +------------+ |      |
|  |virtual swap|<-------|---------------virtual swap devce
   +------------+ |      |               swap_info_struct.prio==100
|        ^               |               (default : <0)
         |        + - - -|- - - - - +
|        v               v         
   +-----------------------------+  |
|  |           ccache            |<------compressed data storage area
   +-----------------------------+  |
+ - - - - - - - - - - - - - - - - - + 
                               Compressed Cache implements this scope


Page 6 (c) NEC Corporation 2006

Overview of Implementation

* State transition of page (vanilla)

   +--------+        +----------+
   | active | <----- | inactive |
   |        | -----> |          |
   +--------+        +----------+

                          * struct page is maintained with LRU
                          * data is "raw"


Page 7 (c) NEC Corporation 2006

Overview of Implementation

* State transition of page (compressed cache)

             +--------+        +----------+
             | active | <----- | inactive |
             |        | -----> |          |
             +--------+        +----------+
                  ^                  /
                   \                /   * struct page is maintained with LRU
                    \              /    * data is "raw"
  ---------------------------------------------------------
                      \          /      * data is managed with struct chunk_head and struct chunk
 find_*_page*()        \        /       * data is compressed and stored in ccache area
 --> handle_cache_fault()      /   pageout()
 --> cc_readpage()       \    V    --> cc_writepage()
                     +------------+
                     | compressed |
                     +------------+

* Pages stored in cache


Page 8 (c) NEC Corporation 2006

Overview of Implementation

* Data management of ccache region

         /    +-----------------+           +-----------------+
         |    |struct chunk_head|           |struct chunk_head|
 (in use)|    +-----------------+           +-----------------+
         |       |  +------------+             |  +------------+  +------------+  +------------+
         |       +--|struct chunk|-|           +--|struct chunk|--|struct chunk|--|struct chunk|-|
         \          +------------+                +------------+  +------------+  +------------+
                       |                               |                     |      |
                       v                               v                     v      v
                 ------+------------------------------------------------------------------------------------
                       +            |      +           |     |  +            |      +    |               +
                       +            |      +           |     |  +            |      +<--physical page--->+
                       +            |      +           |     |  +            |      +    |               +
                 ------+-------------------------------------------------------------------------------------
                                    ^      ^                  ^  ^                        ^
                                    |      |                  |  |                        |
                      +-------------+      |                  |  +------+                 |
         /            |                    |                  |         |                 |
         |         +------------+   +------------+   +------------+   +------------+   +------------+
(vacant) |         |struct chunk|-->|struct chunk|-->|struct chunk|-->|struct chunk|-->|struct chunk|--|
         |         +------------+   +------------+   +------------+   +------------+   +------------+
         \                  ^
                                  |
                               struct chunk *free_head


Page 9 (c) NEC Corporation 2006

Overview of Implementation

* Data storage into ccache

* Data read from ccache


Page 10 (c) NEC Corporation 2006

Overview of Implementation

* Compression algorithms

* Tuning Knobs


Page 11 (c) NEC Corporation 2006

Overview of Implementation

* Patch size

include/linux/WK4x4.h      | 91 +++
include/linux/WKdm.h       | 81 +++
include/linux/ccache.h     | 155 +++++
include/linux/errno.h      | 3 +
include/linux/lzoconf.h    | 499 ++++++++++++++
include/linux/minilzo.h    | 97 +++
include/linux/page-flags.h | 17 +
include/linux/swap.h       | 1 +
include/linux/sysctl.h     | 2 +
kernel/sysctl.c            | 22 +
lib/LZO/README.LZO         | 123 ++++
lib/LZO/minilzo.c          | 1574 ++++++++++++++++++++++++++++++++++++++++++++
lib/Makefile               | 3 +-
lib/WK4x4/README           | 70 ++
lib/WK4x4/WK4x4.c          | 999 ++++++++++++++++++++++++++++
lib/WKdm/WKdm.c            | 779 ++++++++++++++++++++++
mm/Makefile                | 2 +-
mm/ccache.c                | 889 +++++++++++++++++++++++++
mm/filemap.c               | 133 ++++-
mm/swapfile.c              | 143 ++++-
mm/vmscan.c                | 39 +-
21 files changed, 5711 insertions(+), 11 deletions(-)


Page 12 (c) NEC Corporation 2006

Evaluation of Effects(1): Effect to Increase Maximum Use of Memory

* Evaluation method


Page 13 (c) NEC Corporation 2006

Evaluation of Effects(1): Effect to Increase Maximum Use of Memory

* Evaluation results

  [see original file for graphs]
    Read size/times till OOM (text file)
    Read size/times till OOM (JPEG file)


Page 14 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation method


Page 15 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation results (sys time)

  [see original file for graphs]

    Spent time to read and invert bits
                 mem=32MB + swap : sys
    Spent time to read and invert bits
                 mem=32MB / ccache=16MB : sys


Page 16 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation results (user time)

  [see original file for graphs]

    Spent time to read and invert bits
                mem=32MB + swap : user
    Spent time to read and invert bits
                mem=32MB / ccache=16MB : user


Page 17 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation results (real time)

  [see original file for graphs]

    Spent time to read and invert bits
                mem=32MB + swap : real
    Spent time to read and invert bits
                mem=32MB / ccache=16MB : real


Page 18 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation resuls (supplement: wait time)

  [see original file for graphs]

    Spent time to read and invert bits
                mem=32MB + swap : wait = real - (user + sys)
    Spent time to read and invert bits
                mem=32MB / ccache=16MB : wait = real - (user + sys)


Page 19 (c) NEC Corporation 2006

Evaluation of Effects(2): Performance

* Evaluation results(supplement: result when abundant memory available)

  [see original file for graphs]
   Spent time to read and invert bits
          mem=96MB : sys
   Spent time to read and invert bits
          mem=96MB : user
   Spent time to read and invert bits
          mem=96MB : real


Page 20 (c) NEC Corporation 2006

Issues

* Issue on design and configuration


Page 21 (c) NEC Corporation 2006

Issues

* Issues on implementation


Page 22 (c) NEC Corporation 2006

Personal View for the Future

* VSTore

* Layer structure


Page 23 (c) NEC Corporation 2006

Appendix : resources

* Project page / Wiki

* Mailing list

* OLS Papers / Presentations

(Anderson Farias Briglia, Allan Bezerra, Leonid Moiseichuk, Nitin Gupta)


Thank you


Jamboree16Ccache (last edited 2008-05-07 18:22:19 by localhost)