Release Pingora version 0.1.0v0.1.0

Co-authored-by: Andrew Hauck <[email protected]>
Co-authored-by: Edward Wang <[email protected]>

8 files changed, 1622 insertions, 0 deletions

diff --git a/tinyufo/Cargo.toml b/tinyufo/Cargo.toml
new file mode 100644
index 0000000..a726715
--- /dev/null
+++ b/tinyufo/Cargo.toml
@@ -0,0 +1,41 @@
+[package]
+name = "TinyUFO"
+version = "0.1.0"
+authors = ["Yuchen Wu <[email protected]>"]
+edition = "2021"
+license = "Apache-2.0"
+description = "In-memory cache implementation with TinyLFU as the admission policy and S3-FIFO as the eviction policy"
+repository = "https://github.com/cloudflare/pingora"
+categories = ["algorithms", "caching"]
+keywords = ["cache", "pingora"]
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[lib]
+name = "tinyufo"
+path = "src/lib.rs"
+
+[dependencies]
+ahash = { workspace = true }
+flurry = "<0.5.0" # Try not to require Rust 1.71
+parking_lot = "0"
+crossbeam-queue = "0"
+
+[dev-dependencies]
+rand = "0"
+lru = "0"
+zipf = "7"
+moka = { version = "0", features = ["sync"] }
+dhat = "0"
+
+[[bench]]
+name = "bench_perf"
+harness = false
+
+[[bench]]
+name = "bench_hit_ratio"
+harness = false
+
+[[bench]]
+name = "bench_memory"
+harness = false
diff --git a/tinyufo/LICENSE b/tinyufo/LICENSE
new file mode 100644
index 0000000..d645695
--- /dev/null
+++ b/tinyufo/LICENSE
@@ -0,0 +1,202 @@
+
+                                 Apache License
+                           Version 2.0, January 2004
+                        http://www.apache.org/licenses/
+
+   TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+   1. Definitions.
+
+      "License" shall mean the terms and conditions for use, reproduction,
+      and distribution as defined by Sections 1 through 9 of this document.
+
+      "Licensor" shall mean the copyright owner or entity authorized by
+      the copyright owner that is granting the License.
+
+      "Legal Entity" shall mean the union of the acting entity and all
+      other entities that control, are controlled by, or are under common
+      control with that entity. For the purposes of this definition,
+      "control" means (i) the power, direct or indirect, to cause the
+      direction or management of such entity, whether by contract or
+      otherwise, or (ii) ownership of fifty percent (50%) or more of the
+      outstanding shares, or (iii) beneficial ownership of such entity.
+
+      "You" (or "Your") shall mean an individual or Legal Entity
+      exercising permissions granted by this License.
+
+      "Source" form shall mean the preferred form for making modifications,
+      including but not limited to software source code, documentation
+      source, and configuration files.
+
+      "Object" form shall mean any form resulting from mechanical
+      transformation or translation of a Source form, including but
+      not limited to compiled object code, generated documentation,
+      and conversions to other media types.
+
+      "Work" shall mean the work of authorship, whether in Source or
+      Object form, made available under the License, as indicated by a
+      copyright notice that is included in or attached to the work
+      (an example is provided in the Appendix below).
+
+      "Derivative Works" shall mean any work, whether in Source or Object
+      form, that is based on (or derived from) the Work and for which the
+      editorial revisions, annotations, elaborations, or other modifications
+      represent, as a whole, an original work of authorship. For the purposes
+      of this License, Derivative Works shall not include works that remain
+      separable from, or merely link (or bind by name) to the interfaces of,
+      the Work and Derivative Works thereof.
+
+      "Contribution" shall mean any work of authorship, including
+      the original version of the Work and any modifications or additions
+      to that Work or Derivative Works thereof, that is intentionally
+      submitted to Licensor for inclusion in the Work by the copyright owner
+      or by an individual or Legal Entity authorized to submit on behalf of
+      the copyright owner. For the purposes of this definition, "submitted"
+      means any form of electronic, verbal, or written communication sent
+      to the Licensor or its representatives, including but not limited to
+      communication on electronic mailing lists, source code control systems,
+      and issue tracking systems that are managed by, or on behalf of, the
+      Licensor for the purpose of discussing and improving the Work, but
+      excluding communication that is conspicuously marked or otherwise
+      designated in writing by the copyright owner as "Not a Contribution."
+
+      "Contributor" shall mean Licensor and any individual or Legal Entity
+      on behalf of whom a Contribution has been received by Licensor and
+      subsequently incorporated within the Work.
+
+   2. Grant of Copyright License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      copyright license to reproduce, prepare Derivative Works of,
+      publicly display, publicly perform, sublicense, and distribute the
+      Work and such Derivative Works in Source or Object form.
+
+   3. Grant of Patent License. Subject to the terms and conditions of
+      this License, each Contributor hereby grants to You a perpetual,
+      worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+      (except as stated in this section) patent license to make, have made,
+      use, offer to sell, sell, import, and otherwise transfer the Work,
+      where such license applies only to those patent claims licensable
+      by such Contributor that are necessarily infringed by their
+      Contribution(s) alone or by combination of their Contribution(s)
+      with the Work to which such Contribution(s) was submitted. If You
+      institute patent litigation against any entity (including a
+      cross-claim or counterclaim in a lawsuit) alleging that the Work
+      or a Contribution incorporated within the Work constitutes direct
+      or contributory patent infringement, then any patent licenses
+      granted to You under this License for that Work shall terminate
+      as of the date such litigation is filed.
+
+   4. Redistribution. You may reproduce and distribute copies of the
+      Work or Derivative Works thereof in any medium, with or without
+      modifications, and in Source or Object form, provided that You
+      meet the following conditions:
+
+      (a) You must give any other recipients of the Work or
+          Derivative Works a copy of this License; and
+
+      (b) You must cause any modified files to carry prominent notices
+          stating that You changed the files; and
+
+      (c) You must retain, in the Source form of any Derivative Works
+          that You distribute, all copyright, patent, trademark, and
+          attribution notices from the Source form of the Work,
+          excluding those notices that do not pertain to any part of
+          the Derivative Works; and
+
+      (d) If the Work includes a "NOTICE" text file as part of its
+          distribution, then any Derivative Works that You distribute must
+          include a readable copy of the attribution notices contained
+          within such NOTICE file, excluding those notices that do not
+          pertain to any part of the Derivative Works, in at least one
+          of the following places: within a NOTICE text file distributed
+          as part of the Derivative Works; within the Source form or
+          documentation, if provided along with the Derivative Works; or,
+          within a display generated by the Derivative Works, if and
+          wherever such third-party notices normally appear. The contents
+          of the NOTICE file are for informational purposes only and
+          do not modify the License. You may add Your own attribution
+          notices within Derivative Works that You distribute, alongside
+          or as an addendum to the NOTICE text from the Work, provided
+          that such additional attribution notices cannot be construed
+          as modifying the License.
+
+      You may add Your own copyright statement to Your modifications and
+      may provide additional or different license terms and conditions
+      for use, reproduction, or distribution of Your modifications, or
+      for any such Derivative Works as a whole, provided Your use,
+      reproduction, and distribution of the Work otherwise complies with
+      the conditions stated in this License.
+
+   5. Submission of Contributions. Unless You explicitly state otherwise,
+      any Contribution intentionally submitted for inclusion in the Work
+      by You to the Licensor shall be under the terms and conditions of
+      this License, without any additional terms or conditions.
+      Notwithstanding the above, nothing herein shall supersede or modify
+      the terms of any separate license agreement you may have executed
+      with Licensor regarding such Contributions.
+
+   6. Trademarks. This License does not grant permission to use the trade
+      names, trademarks, service marks, or product names of the Licensor,
+      except as required for reasonable and customary use in describing the
+      origin of the Work and reproducing the content of the NOTICE file.
+
+   7. Disclaimer of Warranty. Unless required by applicable law or
+      agreed to in writing, Licensor provides the Work (and each
+      Contributor provides its Contributions) on an "AS IS" BASIS,
+      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+      implied, including, without limitation, any warranties or conditions
+      of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+      PARTICULAR PURPOSE. You are solely responsible for determining the
+      appropriateness of using or redistributing the Work and assume any
+      risks associated with Your exercise of permissions under this License.
+
+   8. Limitation of Liability. In no event and under no legal theory,
+      whether in tort (including negligence), contract, or otherwise,
+      unless required by applicable law (such as deliberate and grossly
+      negligent acts) or agreed to in writing, shall any Contributor be
+      liable to You for damages, including any direct, indirect, special,
+      incidental, or consequential damages of any character arising as a
+      result of this License or out of the use or inability to use the
+      Work (including but not limited to damages for loss of goodwill,
+      work stoppage, computer failure or malfunction, or any and all
+      other commercial damages or losses), even if such Contributor
+      has been advised of the possibility of such damages.
+
+   9. Accepting Warranty or Additional Liability. While redistributing
+      the Work or Derivative Works thereof, You may choose to offer,
+      and charge a fee for, acceptance of support, warranty, indemnity,
+      or other liability obligations and/or rights consistent with this
+      License. However, in accepting such obligations, You may act only
+      on Your own behalf and on Your sole responsibility, not on behalf
+      of any other Contributor, and only if You agree to indemnify,
+      defend, and hold each Contributor harmless for any liability
+      incurred by, or claims asserted against, such Contributor by reason
+      of your accepting any such warranty or additional liability.
+
+   END OF TERMS AND CONDITIONS
+
+   APPENDIX: How to apply the Apache License to your work.
+
+      To apply the Apache License to your work, attach the following
+      boilerplate notice, with the fields enclosed by brackets "[]"
+      replaced with your own identifying information. (Don't include
+      the brackets!)  The text should be enclosed in the appropriate
+      comment syntax for the file format. We also recommend that a
+      file or class name and description of purpose be included on the
+      same "printed page" as the copyright notice for easier
+      identification within third-party archives.
+
+   Copyright [yyyy] [name of copyright owner]
+
+   Licensed under the Apache License, Version 2.0 (the "License");
+   you may not use this file except in compliance with the License.
+   You may obtain a copy of the License at
+
+       http://www.apache.org/licenses/LICENSE-2.0
+
+   Unless required by applicable law or agreed to in writing, software
+   distributed under the License is distributed on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+   See the License for the specific language governing permissions and
+   limitations under the License.
diff --git a/tinyufo/README.md b/tinyufo/README.md
new file mode 100644
index 0000000..50e2dd3
--- /dev/null
+++ b/tinyufo/README.md
@@ -0,0 +1,49 @@
+# TinyUFO
+
+TinyUFO is a fast and efficient in-memory cache. It adopts the state-of-the-art [S3-FIFO](https://s3fifo.com/) as well as [TinyLFU](https://arxiv.org/abs/1512.00727) algorithms to achieve high throughput and high hit ratio as the same time.
+
+## Usage
+
+See docs
+
+## Performance Comparison
+We compare TinyUFO with [lru](https://crates.io/crates/lru), the most commonly used cache algorithm and [moka](https://crates.io/crates/moka), another [great](https://github.com/rust-lang/crates.io/pull/3999) cache library that implements TinyLFU.
+
+### Hit Ratio
+
+The table below show the cache hit ratio of the compared algorithm under different size of cache, zipf=1.
+
+|cache size / total assets | TinyUFO | TinyUFO - LRU | TinyUFO - moka (TinyLFU) |
+| -------- | ------- | ------- | ------ |
+| 0.5% | 45.26% | +14.21pp | -0.33pp
+| 1% | 52.35% | +13.19pp | +1.69pp
+| 5% | 68.89% | +10.14pp | +1.91pp
+| 10% | 75.98% | +8.39pp | +1.59pp
+| 25% | 85.34% | +5.39pp | +0.95pp
+
+Both TinyUFO and moka greatly improves hit ratio from lru. TinyUFO is the one better in this workload.
+[This paper](https://dl.acm.org/doi/pdf/10.1145/3600006.3613147) contains more thorough cache performance
+evaluations S3-FIFO, which TinyUFO varies from, against many caching algorithms under a variety of workloads.
+
+### Speed
+
+The table below shows the number of operations performed per second for each cache library. The tests are performed using 8 threads on a x64 Linux desktop.
+
+| Setup | TinyUFO | LRU | moka |
+| -------- | ------- | ------- | ------ |
+| Pure read | 148.7 million ops | 7.0 million ops | 14.1 million ops
+| Mixed read/write | 80.9 million ops | 6.8 million ops | 16.6 million ops
+
+Because of TinyUFO's lock-free design, it greatly outperforms the others.
+
+### Memory overhead
+
+The table below show the memory allocation (in bytes) of the compared cache library under certain workloads to store zero-sized assets.
+
+| cache size | TinyUFO | LRU | moka |
+| -------- | ------- | ------- | ------ |
+| 100 | 39,409 | 9,408 | 354,376
+| 1000 | 236,053 | 128,512 | 535,888
+| 10000 | 2,290,635 | 1,075,648 | 2,489,088
+
+Whether these overheads matter depends on the actual sizes and volume of the assets. The more advanced algorithms are likely to be less memory efficient than the simple LRU.
\ No newline at end of file
diff --git a/tinyufo/benches/bench_hit_ratio.rs b/tinyufo/benches/bench_hit_ratio.rs
new file mode 100644
index 0000000..72dacd5
--- /dev/null
+++ b/tinyufo/benches/bench_hit_ratio.rs
@@ -0,0 +1,100 @@
+// Copyright 2024 Cloudflare, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use rand::prelude::*;
+use std::num::NonZeroUsize;
+
+const ITEMS: usize = 10_000;
+const ITERATIONS: usize = 5_000_000;
+
+fn bench_one(zip_exp: f64, cache_size_percent: f32) {
+    print!("{zip_exp:.2}, {cache_size_percent:4}\t\t\t");
+    let cache_size = (cache_size_percent * ITEMS as f32).round() as usize;
+    let mut lru = lru::LruCache::<u64, ()>::new(NonZeroUsize::new(cache_size).unwrap());
+    let moka = moka::sync::Cache::new(cache_size as u64);
+    let tinyufo = tinyufo::TinyUfo::new(cache_size, cache_size);
+
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(ITEMS, zip_exp).unwrap();
+
+    let mut lru_hit = 0;
+    let mut moka_hit = 0;
+    let mut tinyufo_hit = 0;
+
+    for _ in 0..ITERATIONS {
+        let key = zipf.sample(&mut rng) as u64;
+
+        if lru.get(&key).is_some() {
+            lru_hit += 1;
+        } else {
+            lru.push(key, ());
+        }
+
+        if moka.get(&key).is_some() {
+            moka_hit += 1;
+        } else {
+            moka.insert(key, ());
+        }
+
+        if tinyufo.get(&key).is_some() {
+            tinyufo_hit += 1;
+        } else {
+            tinyufo.put(key, (), 1);
+        }
+    }
+
+    print!("{:.2}%\t\t", lru_hit as f32 / ITERATIONS as f32 * 100.0);
+    print!("{:.2}%\t\t", moka_hit as f32 / ITERATIONS as f32 * 100.0);
+    println!("{:.2}%", tinyufo_hit as f32 / ITERATIONS as f32 * 100.0);
+}
+
+/*
+cargo bench --bench bench_hit_ratio
+
+zipf & cache size               lru             moka            TinyUFO
+0.90, 0.005                     19.23%          33.46%          33.35%
+0.90, 0.01                      26.21%          37.88%          40.10%
+0.90, 0.05                      45.59%          55.34%          57.81%
+0.90,  0.1                      55.73%          64.22%          66.34%
+0.90, 0.25                      71.18%          77.15%          78.53%
+1.00, 0.005                     31.09%          45.65%          45.13%
+1.00, 0.01                      39.17%          50.69%          52.23%
+1.00, 0.05                      58.73%          66.95%          68.81%
+1.00,  0.1                      67.57%          74.35%          75.93%
+1.00, 0.25                      79.91%          84.34%          85.27%
+1.05, 0.005                     37.68%          51.77%          51.26%
+1.05, 0.01                      46.11%          57.07%          58.41%
+1.05, 0.05                      65.04%          72.33%          73.91%
+1.05,  0.1                      73.11%          78.96%          80.22%
+1.05, 0.25                      83.77%          87.45%          88.16%
+1.10, 0.005                     44.48%          57.86%          57.25%
+1.10, 0.01                      52.97%          63.18%          64.23%
+1.10, 0.05                      70.94%          77.27%          78.57%
+1.10,  0.1                      78.11%          83.05%          84.06%
+1.10, 0.25                      87.08%          90.06%          90.62%
+1.50, 0.005                     85.25%          89.89%          89.68%
+1.50, 0.01                      89.88%          92.79%          92.94%
+1.50, 0.05                      96.04%          97.09%          97.25%
+1.50,  0.1                      97.52%          98.17%          98.26%
+1.50, 0.25                      98.81%          99.09%          99.10%
+ */
+
+fn main() {
+    println!("zipf & cache size\t\tlru\t\tmoka\t\tTinyUFO",);
+    for zif_exp in [0.9, 1.0, 1.05, 1.1, 1.5] {
+        for cache_capacity in [0.005, 0.01, 0.05, 0.1, 0.25] {
+            bench_one(zif_exp, cache_capacity);
+        }
+    }
+}
diff --git a/tinyufo/benches/bench_memory.rs b/tinyufo/benches/bench_memory.rs
new file mode 100644
index 0000000..e55a561
--- /dev/null
+++ b/tinyufo/benches/bench_memory.rs
@@ -0,0 +1,120 @@
+// Copyright 2024 Cloudflare, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#[global_allocator]
+static ALLOC: dhat::Alloc = dhat::Alloc;
+
+use rand::prelude::*;
+use std::num::NonZeroUsize;
+
+const ITERATIONS: usize = 5_000_000;
+
+fn bench_lru(zip_exp: f64, items: usize, cache_size_percent: f32) {
+    let cache_size = (cache_size_percent * items as f32).round() as usize;
+    let mut lru = lru::LruCache::<u64, ()>::new(NonZeroUsize::new(cache_size).unwrap());
+
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(items, zip_exp).unwrap();
+
+    for _ in 0..ITERATIONS {
+        let key = zipf.sample(&mut rng) as u64;
+
+        if lru.get(&key).is_none() {
+            lru.push(key, ());
+        }
+    }
+}
+
+fn bench_moka(zip_exp: f64, items: usize, cache_size_percent: f32) {
+    let cache_size = (cache_size_percent * items as f32).round() as usize;
+    let moka = moka::sync::Cache::new(cache_size as u64);
+
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(items, zip_exp).unwrap();
+
+    for _ in 0..ITERATIONS {
+        let key = zipf.sample(&mut rng) as u64;
+
+        if moka.get(&key).is_none() {
+            moka.insert(key, ());
+        }
+    }
+}
+
+fn bench_tinyufo(zip_exp: f64, items: usize, cache_size_percent: f32) {
+    let cache_size = (cache_size_percent * items as f32).round() as usize;
+    let tinyufo = tinyufo::TinyUfo::new(cache_size, (cache_size as f32 * 1.0) as usize);
+
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(items, zip_exp).unwrap();
+
+    for _ in 0..ITERATIONS {
+        let key = zipf.sample(&mut rng) as u64;
+
+        if tinyufo.get(&key).is_none() {
+            tinyufo.put(key, (), 1);
+        }
+    }
+}
+
+/*
+cargo bench --bench bench_memory
+
+total items 1000, cache size 10%
+lru
+dhat: At t-gmax: 9,408 bytes in 106 blocks
+moka
+dhat: At t-gmax: 354,232 bytes in 1,581 blocks
+TinyUFO
+dhat: At t-gmax: 37,337 bytes in 351 blocks
+
+total items 10000, cache size 10%
+lru
+dhat: At t-gmax: 128,512 bytes in 1,004 blocks
+moka
+dhat: At t-gmax: 535,320 bytes in 7,278 blocks
+TinyUFO
+dhat: At t-gmax: 236,053 bytes in 2,182 blocks
+
+total items 100000, cache size 10%
+lru
+dhat: At t-gmax: 1,075,648 bytes in 10,004 blocks
+moka
+dhat: At t-gmax: 2,489,088 bytes in 62,374 blocks
+TinyUFO
+dhat: At t-gmax: 2,290,635 bytes in 20,467 blocks
+*/
+
+fn main() {
+    for items in [1000, 10_000, 100_000] {
+        println!("\ntotal items {items}, cache size 10%");
+        {
+            let _profiler = dhat::Profiler::new_heap();
+            bench_lru(1.05, items, 0.1);
+            println!("lru");
+        }
+
+        {
+            let _profiler = dhat::Profiler::new_heap();
+            bench_moka(1.05, items, 0.1);
+            println!("\nmoka");
+        }
+
+        {
+            let _profiler = dhat::Profiler::new_heap();
+            bench_tinyufo(1.05, items, 0.1);
+            println!("\nTinyUFO");
+        }
+    }
+}
diff --git a/tinyufo/benches/bench_perf.rs b/tinyufo/benches/bench_perf.rs
new file mode 100644
index 0000000..1295fb2
--- /dev/null
+++ b/tinyufo/benches/bench_perf.rs
@@ -0,0 +1,290 @@
+// Copyright 2024 Cloudflare, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use rand::prelude::*;
+use std::num::NonZeroUsize;
+use std::sync::Mutex;
+use std::thread;
+use std::time::Instant;
+
+const ITEMS: usize = 100;
+
+const ITERATIONS: usize = 5_000_000;
+const THREADS: usize = 8;
+
+/*
+cargo bench  --bench bench_perf
+
+Note: the performance number vary a lot on different planform, CPU and CPU arch
+Below is from Linux + Ryzen 5 7600 CPU
+
+lru read total 150.423567ms, 30ns avg per operation, 33239472 ops per second
+moka read total 462.133322ms, 92ns avg per operation, 10819389 ops per second
+tinyufo read total 199.007359ms, 39ns avg per operation, 25124698 ops per second
+
+lru read total 5.402631847s, 1.08µs avg per operation, 925474 ops per second
+...
+total 6960329 ops per second
+
+moka read total 2.742258211s, 548ns avg per operation, 1823314 ops per second
+...
+total 14072430 ops per second
+
+tinyufo read total 208.346855ms, 41ns avg per operation, 23998444 ops per second
+...
+total 148691408 ops per second
+
+lru mixed read/write 5.500309876s, 1.1µs avg per operation, 909039 ops per second, 407431 misses
+...
+total 6846743 ops per second
+
+moka mixed read/write 2.368500882s, 473ns avg per operation, 2111040 ops per second 279324 misses
+...
+total 16557962 ops per second
+
+tinyufo mixed read/write 456.134531ms, 91ns avg per operation, 10961678 ops per second, 294977 misses
+...
+total 80865792 ops per second
+*/
+
+fn main() {
+    // we don't bench eviction here so make the caches large enough to hold all
+    let lru = Mutex::new(lru::LruCache::<u64, ()>::unbounded());
+    let moka = moka::sync::Cache::new(ITEMS as u64 + 10);
+    let tinyufo = tinyufo::TinyUfo::new(ITEMS + 10, 10);
+
+    // populate first, then we bench access/promotion
+    for i in 0..ITEMS {
+        lru.lock().unwrap().put(i as u64, ());
+        moka.insert(i as u64, ());
+        tinyufo.put(i as u64, (), 1);
+    }
+
+    // single thread
+    let mut rng = thread_rng();
+    let zipf = zipf::ZipfDistribution::new(ITEMS, 1.03).unwrap();
+
+    let before = Instant::now();
+    for _ in 0..ITERATIONS {
+        lru.lock().unwrap().get(&(zipf.sample(&mut rng) as u64));
+    }
+    let elapsed = before.elapsed();
+    println!(
+        "lru read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+        elapsed / ITERATIONS as u32,
+        (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let before = Instant::now();
+    for _ in 0..ITERATIONS {
+        moka.get(&(zipf.sample(&mut rng) as u64));
+    }
+    let elapsed = before.elapsed();
+    println!(
+        "moka read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+        elapsed / ITERATIONS as u32,
+        (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let before = Instant::now();
+    for _ in 0..ITERATIONS {
+        tinyufo.get(&(zipf.sample(&mut rng) as u64));
+    }
+    let elapsed = before.elapsed();
+    println!(
+        "tinyufo read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+        elapsed / ITERATIONS as u32,
+        (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    // concurrent
+
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(ITEMS, 1.03).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    lru.lock().unwrap().get(&(zipf.sample(&mut rng) as u64));
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "lru read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(ITEMS, 1.03).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    moka.get(&(zipf.sample(&mut rng) as u64));
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "moka read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(ITEMS, 1.03).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    tinyufo.get(&(zipf.sample(&mut rng) as u64));
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "tinyufo read total {elapsed:?}, {:?} avg per operation, {} ops per second",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    ///// bench mixed read and write /////
+    const CACHE_SIZE: usize = 1000;
+    let items: usize = 10000;
+    const ZIPF_EXP: f64 = 1.3;
+
+    let lru = Mutex::new(lru::LruCache::<u64, ()>::new(
+        NonZeroUsize::new(CACHE_SIZE).unwrap(),
+    ));
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut miss_count = 0;
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(items, ZIPF_EXP).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    let key = zipf.sample(&mut rng) as u64;
+                    let mut lru = lru.lock().unwrap();
+                    if lru.get(&key).is_none() {
+                        lru.put(key, ());
+                        miss_count += 1;
+                    }
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "lru mixed read/write {elapsed:?}, {:?} avg per operation, {} ops per second, {miss_count} misses",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let moka = moka::sync::Cache::new(CACHE_SIZE as u64);
+
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut miss_count = 0;
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(items, ZIPF_EXP).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    let key = zipf.sample(&mut rng) as u64;
+                    if moka.get(&key).is_none() {
+                        moka.insert(key, ());
+                        miss_count += 1;
+                    }
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "moka mixed read/write {elapsed:?}, {:?} avg per operation, {} ops per second {miss_count} misses",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32
+                );
+            });
+        }
+    });
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+
+    let tinyufo = tinyufo::TinyUfo::new(CACHE_SIZE, CACHE_SIZE);
+    let before = Instant::now();
+    thread::scope(|s| {
+        for _ in 0..THREADS {
+            s.spawn(|| {
+                let mut miss_count = 0;
+                let mut rng = thread_rng();
+                let zipf = zipf::ZipfDistribution::new(items, ZIPF_EXP).unwrap();
+                let before = Instant::now();
+                for _ in 0..ITERATIONS {
+                    let key = zipf.sample(&mut rng) as u64;
+                    if tinyufo.get(&key).is_none() {
+                        tinyufo.put(key, (), 1);
+                        miss_count +=1;
+                    }
+                }
+                let elapsed = before.elapsed();
+                println!(
+                    "tinyufo mixed read/write {elapsed:?}, {:?} avg per operation, {} ops per second, {miss_count} misses",
+                    elapsed / ITERATIONS as u32,
+                    (ITERATIONS as f32 / elapsed.as_secs_f32()) as u32,
+                );
+            });
+        }
+    });
+
+    let elapsed = before.elapsed();
+    println!(
+        "total {} ops per second",
+        (ITERATIONS as f32 * THREADS as f32 / elapsed.as_secs_f32()) as u32
+    );
+}
diff --git a/tinyufo/src/estimation.rs b/tinyufo/src/estimation.rs
new file mode 100644
index 0000000..19d84d4
--- /dev/null
+++ b/tinyufo/src/estimation.rs
@@ -0,0 +1,188 @@
+// Copyright 2024 Cloudflare, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+use ahash::RandomState;
+use std::hash::Hash;
+use std::sync::atomic::{AtomicU8, AtomicUsize, Ordering};
+
+struct Estimator {
+    estimator: Box<[(Box<[AtomicU8]>, RandomState)]>,
+}
+
+impl Estimator {
+    fn optimal_paras(items: usize) -> (usize, usize) {
+        use std::cmp::max;
+        // derived from https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
+        // width = ceil(e / ε)
+        // depth = ceil(ln(1 − δ) / ln(1 / 2))
+        let error_range = 1.0 / (items as f64);
+        let failure_probability = 1.0 / (items as f64);
+        (
+            max((std::f64::consts::E / error_range).ceil() as usize, 16),
+            max((failure_probability.ln() / 0.5f64.ln()).ceil() as usize, 2),
+        )
+    }
+
+    fn optimal(items: usize) -> Self {
+        let (slots, hashes) = Self::optimal_paras(items);
+        Self::new(hashes, slots)
+    }
+
+    /// Create a new `Estimator` with the given amount of hashes and columns (slots).
+    pub fn new(hashes: usize, slots: usize) -> Self {
+        let mut estimator = Vec::with_capacity(hashes);
+        for _ in 0..hashes {
+            let mut slot = Vec::with_capacity(slots);
+            for _ in 0..slots {
+                slot.push(AtomicU8::new(0));
+            }
+            estimator.push((slot.into_boxed_slice(), RandomState::new()));
+        }
+
+        Estimator {
+            estimator: estimator.into_boxed_slice(),
+        }
+    }
+
+    pub fn incr<T: Hash>(&self, key: T) -> u8 {
+        let mut min = u8::MAX;
+        for (slot, hasher) in self.estimator.iter() {
+            let hash = hasher.hash_one(&key) as usize;
+            let counter = &slot[hash % slot.len()];
+            let (_current, new) = incr_no_overflow(counter);
+            min = std::cmp::min(min, new);
+        }
+        min
+    }
+
+    /// Get the estimated frequency of `key`.
+    pub fn get<T: Hash>(&self, key: T) -> u8 {
+        let mut min = u8::MAX;
+        for (slot, hasher) in self.estimator.iter() {
+            let hash = hasher.hash_one(&key) as usize;
+            let counter = &slot[hash % slot.len()];
+            let current = counter.load(Ordering::Relaxed);
+            min = std::cmp::min(min, current);
+        }
+        min
+    }
+
+    /// right shift all values inside this `Estimator`.
+    pub fn age(&self, shift: u8) {
+        for (slot, _) in self.estimator.iter() {
+            for counter in slot.iter() {
+                // we don't CAS because the only update between the load and store
+                // is fetch_add(1), which should be fine to miss/ignore
+                let c = counter.load(Ordering::Relaxed);
+                counter.store(c >> shift, Ordering::Relaxed);
+            }
+        }
+    }
+}
+
+fn incr_no_overflow(var: &AtomicU8) -> (u8, u8) {
+    loop {
+        let current = var.load(Ordering::Relaxed);
+        if current == u8::MAX {
+            return (current, current);
+        }
+        let new = if current == u8::MAX - 1 {
+            u8::MAX
+        } else {
+            current + 1
+        };
+        if let Err(new) = var.compare_exchange(current, new, Ordering::Acquire, Ordering::Relaxed) {
+            // someone else beat us to it
+            if new == u8::MAX {
+                // already max
+                return (current, new);
+            } // else, try again
+        } else {
+            return (current, new);
+        }
+    }
+}
+
+// bare-minimum TinyLfu with CM-Sketch, no doorkeeper for now
+pub(crate) struct TinyLfu {
+    estimator: Estimator,
+    window_counter: AtomicUsize,
+    window_limit: usize,
+}
+
+impl TinyLfu {
+    pub fn get<T: Hash>(&self, key: T) -> u8 {
+        self.estimator.get(key)
+    }
+
+    pub fn incr<T: Hash>(&self, key: T) -> u8 {
+        let window_size = self.window_counter.fetch_add(1, Ordering::Relaxed);
+        // When window_size concurrently increases, only one resets the window and age the estimator.
+        // > self.window_limit * 2 is a safety net in case for whatever reason window_size grows
+        // out of control
+        if window_size == self.window_limit || window_size > self.window_limit * 2 {
+            self.window_counter.store(0, Ordering::Relaxed);
+            self.estimator.age(1); // right shift 1 bit
+        }
+        self.estimator.incr(key)
+    }
+
+    // because we use 8-bits counters, window size can be 256 * the cache size
+    pub fn new(cache_size: usize) -> Self {
+        Self {
+            estimator: Estimator::optimal(cache_size),
+            window_counter: Default::default(),
+            // 8x: just a heuristic to balance the memory usage and accuracy
+            window_limit: cache_size * 8,
+        }
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_cmk_paras() {
+        let (slots, hashes) = Estimator::optimal_paras(1_000_000);
+        // just smoke check some standard input
+        assert_eq!(slots, 2718282);
+        assert_eq!(hashes, 20);
+    }
+
+    #[test]
+    fn test_tiny_lfu() {
+        let tiny = TinyLfu::new(1);
+        assert_eq!(tiny.get(1), 0);
+        assert_eq!(tiny.incr(1), 1);
+        assert_eq!(tiny.incr(1), 2);
+        assert_eq!(tiny.get(1), 2);
+
+        assert_eq!(tiny.get(2), 0);
+        assert_eq!(tiny.incr(2), 1);
+        assert_eq!(tiny.incr(2), 2);
+        assert_eq!(tiny.get(2), 2);
+
+        assert_eq!(tiny.incr(3), 1);
+        assert_eq!(tiny.incr(3), 2);
+        assert_eq!(tiny.incr(3), 3);
+        assert_eq!(tiny.incr(3), 4);
+
+        // 8 incr(), now reset
+
+        assert_eq!(tiny.incr(3), 3);
+        assert_eq!(tiny.incr(1), 2);
+        assert_eq!(tiny.incr(2), 2);
+    }
+}
diff --git a/tinyufo/src/lib.rs b/tinyufo/src/lib.rs
new file mode 100644
index 0000000..879e373
--- /dev/null
+++ b/tinyufo/src/lib.rs
@@ -0,0 +1,632 @@
+// Copyright 2024 Cloudflare, Inc.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+//! A In-memory cache implementation with TinyLFU as the admission policy and [S3-FIFO](https://s3fifo.com/) as the eviction policy.
+//!
+//! TinyUFO improves cache hit ratio noticeably compared to LRU.
+//!
+//! TinyUFO is lock-free. It is very fast in the systems with a lot concurrent reads and/or writes
+
+use ahash::RandomState;
+use crossbeam_queue::SegQueue;
+use flurry::HashMap;
+use std::marker::PhantomData;
+use std::sync::atomic::AtomicUsize;
+use std::sync::atomic::{
+    AtomicBool, AtomicU8,
+    Ordering::{Acquire, Relaxed, SeqCst},
+};
+mod estimation;
+use estimation::TinyLfu;
+use std::hash::Hash;
+
+const SMALL: bool = false;
+const MAIN: bool = true;
+
+// Indicate which queue an item is located
+#[derive(Debug, Default)]
+struct Location(AtomicBool);
+
+impl Location {
+    fn new_small() -> Self {
+        Self(AtomicBool::new(SMALL))
+    }
+
+    fn value(&self) -> bool {
+        self.0.load(Relaxed)
+    }
+
+    fn is_main(&self) -> bool {
+        self.value()
+    }
+
+    fn move_to_main(&self) {
+        self.0.store(true, Relaxed);
+    }
+}
+
+// We have 8 bits to spare but we still cap at 3. This is to make sure that the main queue
+// in the worst case can find something to evict quickly
+const USES_CAP: u8 = 3;
+
+#[derive(Debug, Default)]
+struct Uses(AtomicU8);
+
+impl Uses {
+    pub fn inc_uses(&self) {
+        loop {
+            let uses = self.uses();
+            if uses >= USES_CAP {
+                return;
+            }
+            if let Err(new) = self.0.compare_exchange(uses, uses + 1, Acquire, Relaxed) {
+                // someone else beat us to it
+                if new >= USES_CAP {
+                    // already above cap
+                    return;
+                } // else, try again
+            } else {
+                return;
+            }
+        }
+    }
+
+    // decrease uses, return the previous value
+    pub fn decr_uses(&self) -> u8 {
+        loop {
+            let uses = self.uses();
+            if uses == 0 {
+                return 0;
+            }
+            if let Err(new) = self.0.compare_exchange(uses, uses - 1, Acquire, Relaxed) {
+                // someone else beat us to it
+                if new == 0 {
+                    return 0;
+                } // else, try again
+            } else {
+                return uses;
+            }
+        }
+    }
+
+    pub fn uses(&self) -> u8 {
+        self.0.load(Relaxed)
+    }
+}
+
+type Key = u64;
+type Weight = u16;
+
+/// The key-value pair returned from cache eviction
+#[derive(Clone)]
+pub struct KV<T> {
+    /// NOTE: that we currently don't store the Actual key in the cache. This returned value
+    /// is just the hash of it.
+    pub key: Key,
+    pub data: T,
+    pub weight: Weight,
+}
+
+// the data and its metadata
+struct Bucket<T> {
+    uses: Uses,
+    queue: Location,
+    weight: Weight,
+    data: T,
+}
+
+impl<T: Clone> Bucket<T> {
+    fn update_bucket(&self, main_queue: bool, data: T, weight: Weight) -> Self {
+        Self {
+            uses: Uses(self.uses.uses().into()),
+            queue: Location(main_queue.into()),
+            weight,
+            data,
+        }
+    }
+}
+
+const SMALL_QUEUE_PERCENTAGE: f32 = 0.1;
+
+struct FiFoQueues<T> {
+    total_weight_limit: usize,
+
+    small: SegQueue<Key>,
+    small_weight: AtomicUsize,
+
+    main: SegQueue<Key>,
+    main_weight: AtomicUsize,
+
+    // this replaces the ghost queue of S3-FIFO with similar goal: track the evicted assets
+    estimator: TinyLfu,
+
+    _t: PhantomData<T>,
+}
+
+type Buckets<T> = HashMap<Key, Bucket<T>, RandomState>;
+
+impl<T: Clone + Send + Sync> FiFoQueues<T> {
+    fn admit(
+        &self,
+        key: Key,
+        data: T,
+        weight: u16,
+        ignore_lfu: bool,
+        buckets: &Buckets<T>,
+    ) -> Vec<KV<T>> {
+        // Note that we only use TinyLFU during cache admission but not cache read.
+        // So effectively we mostly sketch the popularity of less popular assets.
+        // In this way the sketch is a bit more accurate on these assets.
+        // Also we don't need another separated window cache to address the sparse burst issue as
+        // this sketch doesn't favor very popular assets much.
+        let new_freq = self.estimator.incr(key);
+
+        assert!(weight > 0);
+        let new_bucket = {
+            let pinned_buckets = buckets.pin();
+            let bucket = pinned_buckets.get(&key);
+            let Some(bucket) = bucket else {
+                let mut evicted = self.evict_to_limit(weight, buckets);
+                // TODO: figure out the right way to compare frequencies of different weights across
+                // many evicted assets. For now TinyLFU is only used when only evicting 1 item.
+                let (key, data, weight) = if !ignore_lfu && evicted.len() == 1 {
+                    // Apply the admission algorithm of TinyLFU: compare the incoming new item
+                    // and the evicted one. The more popular one is admitted to cache
+                    let evicted_first = &evicted[0];
+                    let evicted_freq = self.estimator.get(evicted_first.key);
+                    if evicted_freq > new_freq {
+                        // put it back
+                        let first = evicted.pop().expect("just check non-empty");
+                        // return the put value
+                        evicted.push(KV { key, data, weight });
+                        (first.key, first.data, first.weight)
+                    } else {
+                        (key, data, weight)
+                    }
+                } else {
+                    (key, data, weight)
+                };
+
+                let bucket = Bucket {
+                    queue: Location::new_small(),
+                    weight,
+                    uses: Default::default(), // 0
+                    data,
+                };
+                let old = pinned_buckets.insert(key, bucket);
+                if old.is_none() {
+                    // Always push key first before updating weight
+                    // If doing the other order, another concurrent thread might not
+                    // find things to evict
+                    self.small.push(key);
+                    self.small_weight.fetch_add(weight as usize, SeqCst);
+                } // else: two threads are racing adding the item
+                  // TODO: compare old.weight and update accordingly
+                return evicted;
+            };
+
+            // the item exists, in case weight changes
+            let old_weight = bucket.weight;
+            bucket.uses.inc_uses();
+
+            fn update_atomic(weight: &AtomicUsize, old: u16, new: u16) {
+                if old == new {
+                    return;
+                }
+                if old > new {
+                    weight.fetch_sub((old - new) as usize, SeqCst);
+                } else {
+                    weight.fetch_add((new - old) as usize, SeqCst);
+                }
+            }
+            if bucket.queue.is_main() {
+                update_atomic(&self.main_weight, old_weight, weight);
+                bucket.update_bucket(MAIN, data, weight)
+            } else {
+                update_atomic(&self.small_weight, old_weight, weight);
+                bucket.update_bucket(SMALL, data, weight)
+            }
+        };
+
+        // replace the existing one
+        buckets.pin().insert(key, new_bucket);
+
+        // NOTE: there is a chance that the item itself is evicted if it happens to be the one selected
+        // by the algorithm. We could avoid this by checking if the item is in the returned evicted items,
+        // and then add it back. But to keep the code simple we just allow it to happen.
+        self.evict_to_limit(0, buckets)
+    }
+
+    // the `extra_weight` is to essentially tell the cache to reserve that amount of weight for
+    // admission. It is used when calling `evict_to_limit` before admitting the asset itself.
+    fn evict_to_limit(&self, extra_weight: Weight, buckets: &Buckets<T>) -> Vec<KV<T>> {
+        let mut evicted = if self.total_weight_limit
+            < self.small_weight.load(SeqCst) + self.main_weight.load(SeqCst) + extra_weight as usize
+        {
+            Vec::with_capacity(1)
+        } else {
+            vec![]
+        };
+        while self.total_weight_limit
+            < self.small_weight.load(SeqCst) + self.main_weight.load(SeqCst) + extra_weight as usize
+        {
+            if let Some(evicted_item) = self.evict_one(buckets) {
+                evicted.push(evicted_item);
+            } else {
+                break;
+            }
+        }
+
+        evicted
+    }
+
+    fn evict_one(&self, buckets: &Buckets<T>) -> Option<KV<T>> {
+        let evict_small = self.small_weight_limit() <= self.small_weight.load(SeqCst);
+
+        if evict_small {
+            let evicted = self.evict_one_from_small(buckets);
+            // evict_one_from_small could just promote everything to main without evicting any
+            // so need to evict_one_from_main if nothing evicted
+            if evicted.is_some() {
+                return evicted;
+            }
+        }
+        self.evict_one_from_main(buckets)
+    }
+
+    fn small_weight_limit(&self) -> usize {
+        (self.total_weight_limit as f32 * SMALL_QUEUE_PERCENTAGE).floor() as usize + 1
+    }
+
+    fn evict_one_from_small(&self, buckets: &Buckets<T>) -> Option<KV<T>> {
+        loop {
+            let Some(to_evict) = self.small.pop() else {
+                // empty queue, this is caught between another pop() and fetch_sub()
+                return None;
+            };
+            let pinned_buckets = buckets.pin();
+            let maybe_bucket = pinned_buckets.get(&to_evict);
+
+            let Some(bucket) = maybe_bucket.as_ref() else {
+                //key in queue but not bucket, shouldn't happen, but ignore
+                continue;
+            };
+
+            let weight = bucket.weight;
+            self.small_weight.fetch_sub(weight as usize, SeqCst);
+
+            if bucket.uses.uses() > 1 {
+                // move to main
+                bucket.queue.move_to_main();
+                self.main.push(to_evict);
+                self.main_weight.fetch_add(weight as usize, SeqCst);
+                // continue until find one to evict
+                continue;
+            }
+            // move to ghost
+
+            let data = bucket.data.clone();
+            let weight = bucket.weight;
+            pinned_buckets.remove(&to_evict);
+            return Some(KV {
+                key: to_evict,
+                data,
+                weight,
+            });
+        }
+    }
+
+    fn evict_one_from_main(&self, buckets: &Buckets<T>) -> Option<KV<T>> {
+        loop {
+            let Some(to_evict) = self.main.pop() else {
+                return None;
+            };
+            let buckets = buckets.pin();
+            let maybe_bucket = buckets.get(&to_evict);
+            if let Some(bucket) = maybe_bucket.as_ref() {
+                if bucket.uses.decr_uses() > 0 {
+                    // put it back
+                    self.main.push(to_evict);
+                    // continue the loop
+                } else {
+                    // evict
+                    let weight = bucket.weight;
+                    self.main_weight.fetch_sub(weight as usize, SeqCst);
+                    let data = bucket.data.clone();
+                    buckets.remove(&to_evict);
+                    return Some(KV {
+                        key: to_evict,
+                        data,
+                        weight,
+                    });
+                }
+            } // else: key in queue but not bucket, shouldn't happen
+        }
+    }
+}
+
+/// [TinyUfo] cache
+pub struct TinyUfo<K, T> {
+    queues: FiFoQueues<T>,
+    buckets: HashMap<Key, Bucket<T>, RandomState>,
+    random_status: RandomState,
+    _k: PhantomData<K>,
+}
+
+impl<K: Hash, T: Clone + Send + Sync> TinyUfo<K, T> {
+    /// Create a new TinyUfo cache with the given weight limit and the given
+    /// size limit of the ghost queue.
+    pub fn new(total_weight_limit: usize, estimated_size: usize) -> Self {
+        let queues = FiFoQueues {
+            small: SegQueue::new(),
+            small_weight: 0.into(),
+            main: SegQueue::new(),
+            main_weight: 0.into(),
+            total_weight_limit,
+            estimator: TinyLfu::new(estimated_size),
+            _t: PhantomData,
+        };
+        TinyUfo {
+            queues,
+            buckets: HashMap::with_capacity_and_hasher(estimated_size, RandomState::new()),
+            random_status: RandomState::new(),
+            _k: PhantomData,
+        }
+    }
+
+    // TODO: with_capacity()
+
+    /// Read the given key
+    ///
+    /// Return Some(T) if the key exists
+    pub fn get(&self, key: &K) -> Option<T> {
+        let key = self.random_status.hash_one(key);
+        let buckets = self.buckets.pin();
+        buckets.get(&key).map(|p| {
+            p.uses.inc_uses();
+            p.data.clone()
+        })
+    }
+
+    /// Put the key value to the [TinyUfo]
+    ///
+    /// Return a list of [KV] of key and `T` that are evicted
+    pub fn put(&self, key: K, data: T, weight: Weight) -> Vec<KV<T>> {
+        let key = self.random_status.hash_one(key);
+        self.queues.admit(key, data, weight, false, &self.buckets)
+    }
+
+    /// Always put the key value to the [TinyUfo]
+    ///
+    /// Return a list of [KV] of key and `T` that are evicted
+    ///
+    /// Similar to [Self::put] but guarantee the assertion of the asset.
+    /// In [Self::put], the TinyLFU check may reject putting the current asset if it is less
+    /// popular than the once being evicted.
+    ///
+    /// In some real world use cases, a few reads to the same asset may be pending for the put action
+    /// to be finished so that they can read the asset from cache. Neither the above behaviors are ideal
+    /// for this use case.
+    ///
+    /// Compared to [Self::put], the hit ratio when using this function is reduced by about 0.5pp or less in
+    /// under zipf workloads.
+    pub fn force_put(&self, key: K, data: T, weight: Weight) -> Vec<KV<T>> {
+        let key = self.random_status.hash_one(key);
+        self.queues.admit(key, data, weight, true, &self.buckets)
+    }
+
+    #[cfg(test)]
+    fn peek_queue(&self, key: K) -> Option<bool> {
+        let key = self.random_status.hash_one(key);
+        self.buckets.pin().get(&key).map(|p| p.queue.value())
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_uses() {
+        let uses: Uses = Default::default();
+        assert_eq!(uses.uses(), 0);
+        uses.inc_uses();
+        assert_eq!(uses.uses(), 1);
+        for _ in 0..USES_CAP {
+            uses.inc_uses();
+        }
+        assert_eq!(uses.uses(), USES_CAP);
+
+        for _ in 0..USES_CAP + 2 {
+            uses.decr_uses();
+        }
+        assert_eq!(uses.uses(), 0);
+    }
+
+    #[test]
+    fn test_evict_from_small() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+
+        let evicted = cache.put(4, 4, 3);
+        assert_eq!(evicted.len(), 2);
+        assert_eq!(evicted[0].data, 1);
+        assert_eq!(evicted[1].data, 2);
+
+        assert_eq!(cache.peek_queue(1), None);
+        assert_eq!(cache.peek_queue(2), None);
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+    }
+
+    #[test]
+    fn test_evict_from_small_to_main() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        cache.get(&1);
+        cache.get(&1); // 1 will be moved to main during next eviction
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+
+        let evicted = cache.put(4, 4, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 2);
+
+        assert_eq!(cache.peek_queue(1), Some(MAIN));
+        // 2 is evicted because 1 is in main
+        assert_eq!(cache.peek_queue(2), None);
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+        assert_eq!(cache.peek_queue(4), Some(SMALL));
+    }
+
+    #[test]
+    fn test_evict_reentry() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+
+        let evicted = cache.put(4, 4, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 1);
+
+        assert_eq!(cache.peek_queue(1), None);
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+        assert_eq!(cache.peek_queue(4), Some(SMALL));
+
+        let evicted = cache.put(1, 1, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 2);
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), None);
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+        assert_eq!(cache.peek_queue(4), Some(SMALL));
+    }
+
+    #[test]
+    fn test_evict_entry_denied() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+
+        // trick: put a few times to bump their frequencies
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+
+        let evicted = cache.put(4, 4, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 4); // 4 is returned
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+        assert_eq!(cache.peek_queue(4), None);
+    }
+
+    #[test]
+    fn test_force_put() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+
+        // trick: put a few times to bump their frequencies
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+
+        // force put will replace 1 with 4 even through 1 is more popular
+        let evicted = cache.force_put(4, 4, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 1); // 1 is returned
+
+        assert_eq!(cache.peek_queue(1), None);
+        assert_eq!(cache.peek_queue(2), Some(SMALL));
+        assert_eq!(cache.peek_queue(3), Some(SMALL));
+        assert_eq!(cache.peek_queue(4), Some(SMALL));
+    }
+
+    #[test]
+    fn test_evict_from_main() {
+        let cache = TinyUfo::new(5, 5);
+
+        cache.put(1, 1, 1);
+        cache.put(2, 2, 2);
+        cache.put(3, 3, 2);
+        // cache full now
+
+        // all 3 will qualify to main
+        cache.get(&1);
+        cache.get(&1);
+        cache.get(&2);
+        cache.get(&2);
+        cache.get(&3);
+        cache.get(&3);
+
+        let evicted = cache.put(4, 4, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 1);
+
+        // 1 kicked from main
+        assert_eq!(cache.peek_queue(1), None);
+        assert_eq!(cache.peek_queue(2), Some(MAIN));
+        assert_eq!(cache.peek_queue(3), Some(MAIN));
+        assert_eq!(cache.peek_queue(4), Some(SMALL));
+
+        let evicted = cache.put(1, 1, 1);
+        assert_eq!(evicted.len(), 1);
+        assert_eq!(evicted[0].data, 4);
+
+        assert_eq!(cache.peek_queue(1), Some(SMALL));
+        assert_eq!(cache.peek_queue(2), Some(MAIN));
+        assert_eq!(cache.peek_queue(3), Some(MAIN));
+        assert_eq!(cache.peek_queue(4), None);
+    }
+}