Rustで作るインメモリキャッシュ

2020-10-18

Rust

# Rustで作るインメモリキャッシュ
----------------------
[RustのLT会 Shinjuku.rs #12 @オンライン - connpass](https://forcia.connpass.com/event/187287/)

===

# About Me
---------
![κeenのアイコン](/images/kappa2_vest.png)

* κeen
 * [@blackenedgold](https://twitter.com/blackenedgold)
 * Github: [KeenS](https://github.com/KeenS)
 * GitLab: [blackenedgold](https://gitlab.com/blackenedgold)
 * [Idein Inc.](https://idein.jp/)のエンジニア
 * Lisp, ML, Rust, Shell Scriptあたりを書きます

===

# モチベーション
--------------

* アプリケーションでキャッシュしたいよね
  + アクセス数の80%はアクセス頻度上位20%のアイテム
  + もうちょっと極端なケースも
* 例えば [crates.io](https://crates.io)のmost downloaded
* 少量ならメモリに載るのでDBアクセスを省きたい

===

# ハッシュマップ？
--------------

```rust
struct CachedDao { cache: HashMap<Key, Value>, dao: Dao }
impl CacheedDao {
    fn get(&mut self, key: &Key) -> Result<Option<Value>> {
        match self.cache.get(key) {
            Some(v) => Ok(Some(v)),
            None => {
                let v = dao.get(key)?;
                if let Some(v) = &v {
                    self.cache.insert(k.clone(), v.clone())
                }
                Ok(v)
            }
        }
    }
}
```

===

# 🙅‍
-------

* 使ってないデータを捨てる処理がない
* 最終的に全てのデータをメモリに載せてしまう
* →メモリ使用量制限のあるハッシュマップを作ろう
  + 現実にはアイテム数制限
===

# インメモリキャッシュ
----------------------

* ほとんどハッシュマップと一緒
* 容量が足りなくなったときの挙動が違う

<table style="align:center;border-collapse:separate;border-spacing:8px; display: inline">
  <tr><th style="border-bottom: solid 1px;">マップ</th><th  style="border-bottom: solid 1px;">キャッシュ</th></tr>
  <tr><td>容量を増やす</td><td>アイテムを削除</td></tr>
</table>

===

# キャッシュポリシー
--------------------

* 容量が一杯になったときにどのアイテムを削除するか？
* 色々ポリシーがある
  + ランダム
  + ハッシュが衝突したもの
  + 一番古い要素(FIFO)
  + …
* ポリシーによってパフォーマンス（ヒット率）が変わる

===

# Least Recently Used
---------------------

* 最後に参照したのが最も古いアイテムを削除
* そこそこキャッシュヒット率が良いことで知られる
* →これで実装してみよう

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#new-1" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#new-1" />
    <use xlink:href="#arrow-top" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-1" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-1" />
    <use xlink:href="#new-2" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-1" />
    <use xlink:href="#new-2" />
    <use xlink:href="#arrow-top" />
    <use xlink:href="#arrow-1-2" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-2-1" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-2-1" />
    <use xlink:href="#new-3" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-2-1" />
    <use xlink:href="#new-3" />
    <use xlink:href="#arrow-top" />
    <use xlink:href="#arrow-1-2" />
    <use xlink:href="#arrow-2-3" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-3-2-1" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-3-2-1" />
    <use xlink:href="#new-4" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-3-2-1" />
    <use xlink:href="#new-4" />
    <use xlink:href="#arrow-1-2" />
    <use xlink:href="#arrow-2-3" />
    <use xlink:href="#arrow-3-out" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item--3-2-1out" />
    <use xlink:href="#new-4" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item--3-2-1out" />
    <use xlink:href="#new-4" />
    <use xlink:href="#arrow-top" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-4-3-2" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-4-3-2" />
    <use xlink:href="#new-2" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-4-3-2" />
    <use xlink:href="#new-2" />
    <use xlink:href="#arrow-1-2" />
    <use xlink:href="#arrow-2-3" />
    <use xlink:href="#arrow-3-1" />
  </g>
</svg>

===

# LRU Explained
----------------

<svg width="640" height="480" xmlns:xlink="http://www.w3.org/1999/xlink">
  <g transform="scale(4)">
    <use xlink:href="#base-box" />
    <use xlink:href="#item-2-4-3" />
  </g>
</svg>

===

# 実装
------

* LRU + ハッシュマップ

<svg
   xmlns:dc="http://purl.org/dc/elements/1.1/"
   xmlns:cc="http://creativecommons.org/ns#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
   width="640"
   height="480"
   viewBox="0 0 169.33333 127"
   version="1.1"
   id="svg136"
   inkscape:version="0.92.5 (2060ec1f9f, 2020-04-08)"
   sodipodi:docname="fully-associative-cache.svg">
  <defs
     id="defs130" />
  <metadata
     id="metadata133">
    <rdf:RDF>
      <cc:Work
         rdf:about="">
        <dc:format>image/svg+xml</dc:format>
        <dc:type
           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
        <dc:title />
      </cc:Work>
    </rdf:RDF>
  </metadata>
  <g
     inkscape:label="レイヤー 1"
     inkscape:groupmode="layer"
     id="layer1"
     transform="translate(0,-169.99998)">
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186"
       width="13.49711"
       height="13.49711"
       x="32.205978"
       y="177.5305" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-2"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="191.02762" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-7"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="204.52473" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-0"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="218.02185" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-9"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="231.51897" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-3"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="258.51318" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-6"
       width="13.497111"
       height="13.497111"
       x="32.205978"
       y="245.01608" />
    <g
       id="g275">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,13.497116)"
       id="g275-1">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-8">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-7"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-9"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,26.994232)"
       id="g275-2">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-0">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-23"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-7"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,40.491348)"
       id="g275-5">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-9">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-22"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-8"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,53.988464)"
       id="g275-9">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-7">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-3"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-6"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,67.48558)"
       id="g275-12">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-93">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-1"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-94"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <g
       transform="translate(0,80.982696)"
       id="g275-7">
      <g
         transform="translate(6.2140111,0.73500061)"
         id="g264-84">
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-5"
           width="30.468723"
           height="13.497116"
           x="67.552376"
           y="176.7955" />
        <rect
           style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
           id="rect186-06-2-0"
           width="30.468723"
           height="13.497116"
           x="98.021103"
           y="176.7955" />
      </g>
    </g>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:12.69999981px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="37.782455"
       y="290.31824"
       id="text2526"><tspan
         sodipodi:role="line"
         x="37.782455"
         y="290.31824"
         id="tspan2524"
         style="stroke-width:0.26458332px"><tspan
           x="37.782455"
           y="290.31824"
           id="tspan2522"
           style="stroke-width:0.26458332px">LRU</tspan></tspan></text>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:12.69999981px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="104.63589"
       y="290.31824"
       id="text2532"><tspan
         sodipodi:role="line"
         x="104.63589"
         y="290.31824"
         id="tspan2530"
         style="stroke-width:0.26458332px"><tspan
           x="104.63589"
           y="290.31824"
           id="tspan2528"
           style="stroke-width:0.26458332px">HashMap</tspan></tspan></text>
  </g>
</svg>

===

# 実装
------

* LRU + ハッシュマップ
* LRUは リスト（あるいはベクタ）で簡単に実装できる
  + しかし効率が悪い
  + $O(n)$ の計算量
* ハッシュマップは標準ライブラリのものを使える
  + でもちょっと無駄がある

===

# 実装(LRU)
------

* 少数（定数）個のバケットを保持するブロックに分ける

<svg
   xmlns:dc="http://purl.org/dc/elements/1.1/"
   xmlns:cc="http://creativecommons.org/ns#"
   xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
   xmlns:svg="http://www.w3.org/2000/svg"
   xmlns="http://www.w3.org/2000/svg"
   xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
   xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
   width="640"
   height="480"
   viewBox="0 0 169.33333 127"
   version="1.1"
   id="svg136"
   inkscape:version="0.92.5 (2060ec1f9f, 2020-04-08)"
   sodipodi:docname="way-assosiative-cache.svg">
  <defs
     id="defs130">
    <marker
       inkscape:stockid="Arrow1Mend"
       orient="auto"
       refY="0.0"
       refX="0.0"
       id="marker1753"
       style="overflow:visible;"
       inkscape:isstock="true">
      <path
         id="path1751"
         d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1;fill:#000000;fill-opacity:1"
         transform="scale(0.4) rotate(180) translate(10,0)" />
    </marker>
    <marker
       inkscape:isstock="true"
       style="overflow:visible;"
       id="marker1711"
       refX="0.0"
       refY="0.0"
       orient="auto"
       inkscape:stockid="Arrow1Mend"
       inkscape:collect="always">
      <path
         transform="scale(0.4) rotate(180) translate(10,0)"
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1;fill:#000000;fill-opacity:1"
         d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
         id="path1709" />
    </marker>
    <marker
       inkscape:stockid="Arrow1Mend"
       orient="auto"
       refY="0.0"
       refX="0.0"
       id="Arrow1Mend"
       style="overflow:visible;"
       inkscape:isstock="true"
       inkscape:collect="always">
      <path
         id="path1390"
         d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1;fill:#000000;fill-opacity:1"
         transform="scale(0.4) rotate(180) translate(10,0)" />
    </marker>
    <marker
       inkscape:stockid="Arrow1Lend"
       orient="auto"
       refY="0.0"
       refX="0.0"
       id="Arrow1Lend"
       style="overflow:visible;"
       inkscape:isstock="true">
      <path
         id="path1384"
         d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z "
         style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;stroke-opacity:1;fill:#000000;fill-opacity:1"
         transform="scale(0.8) rotate(180) translate(12.5,0)" />
    </marker>
  </defs>
  <sodipodi:namedview
     id="base"
     pagecolor="#ffffff"
     bordercolor="#666666"
     borderopacity="1.0"
     inkscape:pageopacity="0.0"
     inkscape:pageshadow="2"
     inkscape:zoom="1.979899"
     inkscape:cx="298.24583"
     inkscape:cy="324.53951"
     inkscape:document-units="px"
     inkscape:current-layer="layer1"
     showgrid="false"
     units="px"
     showguides="true"
     inkscape:guide-bbox="true"
     inkscape:snap-bbox="false"
     inkscape:bbox-nodes="true"
     inkscape:snap-text-baseline="true"
     inkscape:snap-nodes="false"
     inkscape:snap-others="true"
     inkscape:window-width="3840"
     inkscape:window-height="2096"
     inkscape:window-x="0"
     inkscape:window-y="27"
     inkscape:window-maximized="1">
    <sodipodi:guide
       position="41.827681,25.247366"
       orientation="0,1"
       id="guide377"
       inkscape:locked="false" />
    <sodipodi:guide
       position="-74.701832,58.932931"
       orientation="0,1"
       id="guide1791"
       inkscape:locked="false" />
  </sodipodi:namedview>
  <metadata
     id="metadata133">
    <rdf:RDF>
      <cc:Work
         rdf:about="">
        <dc:format>image/svg+xml</dc:format>
        <dc:type
           rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
        <dc:title />
      </cc:Work>
    </rdf:RDF>
  </metadata>
  <g
     inkscape:label="レイヤー 1"
     inkscape:groupmode="layer"
     id="layer1"
     transform="translate(0,-169.99998)">
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-0"
       width="3.8892272"
       height="3.8892272"
       x="33.23521"
       y="250.15901" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-9"
       width="3.8892272"
       height="3.8892272"
       x="33.23521"
       y="254.04823" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-3"
       width="3.8892272"
       height="3.8892272"
       x="33.23521"
       y="261.82672" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-6"
       width="3.8892272"
       height="3.8892272"
       x="33.23521"
       y="257.93747" />
    <g
       id="g264-9"
       transform="matrix(0.28815256,0,0,0.28815256,25.745557,199.21494)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-22"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-8"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-7"
       transform="matrix(0.28815256,0,0,0.28815256,25.745557,203.10417)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-3"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-6"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-93"
       transform="matrix(0.28815256,0,0,0.28815256,25.745557,206.9934)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-1"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-94"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-84"
       transform="matrix(0.28815256,0,0,0.28815256,25.745557,210.88262)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-5"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-0"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="35.195225"
       y="271.70081"
       id="text2441"><tspan
         sodipodi:role="line"
         x="35.195225"
         y="271.70081"
         id="tspan2439"
         style="stroke-width:0.07624036px"><tspan
           x="35.195225"
           y="271.70081"
           id="tspan2437"
           style="stroke-width:0.07624036px">LRU</tspan></tspan></text>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="54.187115"
       y="271.75262"
       id="text2447"><tspan
         sodipodi:role="line"
         x="54.187115"
         y="271.75262"
         id="tspan2445"
         style="stroke-width:0.07624036px"><tspan
           x="54.187115"
           y="271.75262"
           id="tspan2443"
           style="stroke-width:0.07624036px">HashMap</tspan></tspan></text>
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-0-3"
       width="3.8892272"
       height="3.8892272"
       x="82.619118"
       y="250.15901" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-9-6"
       width="3.8892272"
       height="3.8892272"
       x="82.619118"
       y="254.04823" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-3-1"
       width="3.8892272"
       height="3.8892272"
       x="82.619118"
       y="261.82672" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-6-0"
       width="3.8892272"
       height="3.8892272"
       x="82.619118"
       y="257.93747" />
    <g
       id="g264-9-6"
       transform="matrix(0.28815257,0,0,0.28815257,75.129461,199.21494)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-22-3"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-8-2"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-7-0"
       transform="matrix(0.28815257,0,0,0.28815257,75.129461,203.10417)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-3-6"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-6-1"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-93-5"
       transform="matrix(0.28815257,0,0,0.28815257,75.129461,206.99341)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-1-5"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-94-4"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-84-7"
       transform="matrix(0.28815257,0,0,0.28815257,75.129461,210.88262)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-5-6"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-0-5"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="84.445496"
       y="271.75262"
       id="text2453"><tspan
         sodipodi:role="line"
         x="84.445496"
         y="271.75262"
         id="tspan2451"
         style="stroke-width:0.07624036px"><tspan
           x="84.445496"
           y="271.75262"
           id="tspan2449"
           style="stroke-width:0.07624036px">LRU</tspan></tspan></text>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="103.83829"
       y="271.75262"
       id="text2459"><tspan
         sodipodi:role="line"
         x="103.83829"
         y="271.75262"
         id="tspan2457"
         style="stroke-width:0.07624036px"><tspan
           x="103.83829"
           y="271.75262"
           id="tspan2455"
           style="stroke-width:0.07624036px">HashMap</tspan></tspan></text>
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-0-4"
       width="3.8892272"
       height="3.8892272"
       x="134.0685"
       y="250.15903" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-9-7"
       width="3.8892272"
       height="3.8892272"
       x="134.0685"
       y="254.04825" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-3-4"
       width="3.8892272"
       height="3.8892272"
       x="134.0685"
       y="261.82672" />
    <rect
       style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:0.30496144;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
       id="rect186-6-4"
       width="3.8892272"
       height="3.8892272"
       x="134.0685"
       y="257.93747" />
    <g
       id="g264-9-3"
       transform="matrix(0.28815257,0,0,0.28815257,126.57885,199.21494)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-22-0"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-8-7"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-7-8"
       transform="matrix(0.28815257,0,0,0.28815257,126.57885,203.10417)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-3-68"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-6-8"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-93-4"
       transform="matrix(0.28815257,0,0,0.28815257,126.57885,206.99341)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-1-3"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-94-1"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <g
       id="g264-84-4"
       transform="matrix(0.28815257,0,0,0.28815257,126.57885,210.88262)">
      <rect
         y="176.7955"
         x="67.552376"
         height="13.497116"
         width="30.468723"
         id="rect186-06-5-9"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
      <rect
         y="176.7955"
         x="98.021103"
         height="13.497116"
         width="30.468723"
         id="rect186-06-2-0-2"
         style="opacity:1;fill:none;fill-opacity:1;stroke:#1a1a1a;stroke-width:1.05833328;stroke-linecap:round;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1" />
    </g>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="136.56305"
       y="271.75262"
       id="text2465"><tspan
         sodipodi:role="line"
         x="136.56305"
         y="271.75262"
         id="tspan2463"
         style="stroke-width:0.07624036px"><tspan
           x="136.56305"
           y="271.75262"
           id="tspan2461"
           style="stroke-width:0.07624036px">LRU</tspan></tspan></text>
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:3.65953732px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.07624036px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="155.0204"
       y="271.75262"
       id="text2471"><tspan
         sodipodi:role="line"
         x="155.0204"
         y="271.75262"
         id="tspan2469"
         style="stroke-width:0.07624036px"><tspan
           x="155.0204"
           y="271.75262"
           id="tspan2467"
           style="stroke-width:0.07624036px">HashMap</tspan></tspan></text>
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.79374999;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#Arrow1Mend)"
       d="M 100.49334,187.86098 53.587541,237.30584"
       id="path574"
       inkscape:connector-curvature="0"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.79374999;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#marker1711)"
       d="m 100.22607,188.12825 0.40091,49.17759"
       id="path1701"
       inkscape:connector-curvature="0"
       sodipodi:nodetypes="cc" />
    <path
       style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.79374999;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;marker-end:url(#marker1753)"
       d="m 100.35971,188.39552 46.77216,48.91032"
       id="path1743"
       inkscape:connector-curvature="0"
       sodipodi:nodetypes="cc" />
    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:19.7555542px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="25.726702"
       y="265.3584"
       id="text121"><tspan
         sodipodi:role="line"
         x="25.726702"
         y="265.3584"
         id="tspan119"
         style="stroke-width:0.26458332px"><tspan
           x="25.726702"
           y="265.3584"
           id="tspan117"
           style="stroke-width:0.26458332px">{</tspan></tspan></text>
    <flowRoot
       xml:space="preserve"
       id="flowRoot2221"
       style="fill:black;stroke:none;stroke-opacity:1;stroke-width:1px;stroke-linejoin:miter;stroke-linecap:butt;fill-opacity:1;font-family:'源ノ角ゴシック JP';font-style:normal;font-weight:normal;font-size:64px;line-height:134.00000334%;letter-spacing:0px;word-spacing:0px;-inkscape-font-specification:'源ノ角ゴシック JP';font-stretch:normal;font-variant:normal;text-anchor:middle;text-align:center"><flowRegion
         id="flowRegion2223"><rect
           id="rect2225"
           width="45.961941"
           height="122.73354"
           x="10.606602"
           y="288.57608" /></flowRegion><flowPara
         id="flowPara2227" /></flowRoot>    <flowRoot
       xml:space="preserve"
       id="flowRoot2237"
       style="fill:black;stroke:none;stroke-opacity:1;stroke-width:1px;stroke-linejoin:miter;stroke-linecap:butt;fill-opacity:1;font-family:'源ノ角ゴシック JP';font-style:normal;font-weight:normal;font-size:29.33333333px;line-height:134.00000334%;letter-spacing:0px;word-spacing:0px;-inkscape-font-specification:'源ノ角ゴシック JP';font-stretch:normal;font-variant:normal;text-anchor:middle;text-align:center;"><flowRegion
         id="flowRegion2239"
         style="font-size:29.33333333px;"><rect
           id="rect2241"
           width="40.406101"
           height="91.455101"
           x="10.606602"
           y="293.12177"
           style="font-size:29.33333333px;" /></flowRegion><flowPara
         id="flowPara2243" /></flowRoot>    <flowRoot
       xml:space="preserve"
       id="flowRoot2245"
       style="fill:black;stroke:none;stroke-opacity:1;stroke-width:1px;stroke-linejoin:miter;stroke-linecap:butt;fill-opacity:1;font-family:'源ノ角ゴシック JP';font-style:normal;font-weight:normal;font-size:29.33333333px;line-height:134.00000334%;letter-spacing:0px;word-spacing:0px;-inkscape-font-specification:'源ノ角ゴシック JP';font-stretch:normal;font-variant:normal;text-anchor:middle;text-align:center;"><flowRegion
         id="flowRegion2247"
         style="font-size:29.33333333px;"><rect
           id="rect2249"
           width="46.467018"
           height="115.66247"
           x="-1.0101526"
           y="296.15222"
           style="font-size:29.33333333px;" /></flowRegion><flowPara
         id="flowPara2251" /></flowRoot>    <flowRoot
       xml:space="preserve"
       id="flowRoot2259"
       style="fill:black;stroke:none;stroke-opacity:1;stroke-width:1px;stroke-linejoin:miter;stroke-linecap:butt;fill-opacity:1;font-family:'源ノ角ゴシック JP';font-style:normal;font-weight:normal;font-size:32px;line-height:134.00000334%;letter-spacing:0px;word-spacing:0px;-inkscape-font-specification:'源ノ角ゴシック JP';font-stretch:normal;font-variant:normal;text-anchor:middle;text-align:center;"><flowRegion
         id="flowRegion2261"
         style="font-size:32px;"><rect
           id="rect2263"
           width="124.24876"
           height="177.78685"
           x="-72.73098"
           y="236.04816"
           style="font-size:32px;" /></flowRegion><flowPara
         id="flowPara2265" /></flowRoot>    <text
       xml:space="preserve"
       style="font-style:normal;font-variant:normal;font-weight:normal;font-stretch:normal;font-size:7.76111126px;line-height:134.00000334%;font-family:'源ノ角ゴシック JP';-inkscape-font-specification:'源ノ角ゴシック JP';text-align:center;letter-spacing:0px;word-spacing:0px;text-anchor:middle;fill:#000000;fill-opacity:1;stroke:none;stroke-width:0.26458332px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
       x="12.310418"
       y="262.11868"
       id="text2435"><tspan
         sodipodi:role="line"
         x="12.310418"
         y="262.11868"
         id="tspan2433"
         style="stroke-width:0.26458332px"><tspan
           x="12.310418"
           y="262.11868"
           id="tspan2431"
           style="stroke-width:0.26458332px">fixed</tspan></tspan></text>
  </g>
</svg>

===

# 実装(LRU)
------

* LRUを効率的に実装したい
* 少数（定数）個のバケットを保持するブロックに分ける
  + 今回は16個
  + 少数ならビット演算でLRUを実装できる
* ブロックへの振り分けはハッシュ値を使う
  + 下4bitをブロック内の振り分けに
  + 5bit目以降をブロックの振り分けに
* キャッシュヒット率を捨てて速度をとった

===

# 実装(ハッシュマップ)
------

* ハッシュマップにはキャッシュに必要のない機能がある
  + 容量が足りなくなったら拡大など
* LRUで管理する関係上ハッシュマップ内部のインデックスを使いたい

===

# hashbrown
------------

* [hashbrown](https://crates.io/crates/hashbrown)
* 標準ライブラリのハッシュマップはcrates.ioに公開されている
* 低レベルAPIの[`RawTable`](https://docs.rs/hashbrown/0.9.1/hashbrown/raw/struct.RawTable.html)が公開されている
* → これを使うと実装できそう

===

# chechire
-----------

* [blackenedgold/chechire](https://gitlab.com/blackenedgold/chechire)
  + 発音はチェシャ猫のcheshireと同じ
* 16-way assosiativeなhashbrownベースのキャッシュ
* ほぼ標準ライブラリの `HashMap` と同じAPI
* 時間の都合で紹介は省略

===
# ベンチマーク
--------------

* 以下の3つが対象
  + chechire
  + LRUを `Vec` で実装した簡易キャッシュ
  + LRUを `VecDeque` で〃
* キャッシュサイズ16348
* ベキ分布なランダムアクセス1,000,000回
* キャッシュミスすると500usのスリープ
  + DB叩くとだいたいこのくらい？

===
# 結果
------

<style type="text/css">
.graph{
  background:#aaa;
  border-radius:5px;
  white-space: nowrap;
  text-align: left;
}
td {
  white-space: nowrap;
}
</style>
<table>
<thead>
<tr>
<th style="text-align:left">subject</th>
<th>hit rate</th>
<th>time</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:left">chechire</td>
<td>98.9537%</td>
<td><div class="graph" style="width:calc( 5958px * 0.05 );">5958ms</div></td>
</tr>
<tr>
<td style="text-align:left">easy cache (vec)</td>
<td>99.1176%</td>
<td><div class="graph" style="width:calc( 6266px * 0.05 );">6266ms</div></td>
</tr>
<tr>
<td style="text-align:left">easy cache (deque)</td>
<td>99.1117%</td>
<td><div class="graph" style="width:calc( 6469px * 0.05 );">6469ms</div></td>
</tr>
</tbody>
</table>
<p>===</p>
<h1 id="まとめ">まとめ</h1>
<hr>
<ul>
<li>定数個のアイテムを保持できるキャッシュを作ったよ</li>
<li>アイテム管理にはLRUというポリシーがあるよ</li>
<li>fully associativeだと遅いから16-wayくらいにしたよ</li>
<li>Rustの <code>HashMap</code> は改造できるよ</li>
</ul>