Memory Hierarchy Design for Caching Middleware in the Age of NVM

Jenny Lam; Sandy Irani; Shahram Ghandeharizadeh

REVIEW 4 major objections 6 minor 27 references

Memory Hierarchy Design for Caching Middleware in the Age of NVM

T0 review · 4 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The Cache Configuration Problem—choosing stashes, capacities, and tiering versus replication under a fixed budget—is an instance of the Multiple Choice Knapsack Problem, solved near-optimally by a greedy LP algorithm.

desk verdict Useful MCKP framing for cache design, but the 'provably optimal' claim is not backed by the math and the failure-rate formula in Section 4.1 is inverted as written. read the letter →

arxiv 2506.05071 v1 pith:F3VCWKJ2 submitted 2025-06-05 cs.DB cs.ARcs.DS

Shahram Ghandeharizadeh , Sandy Irani , Jenny Lam This is my paper

classification cs.DBcs.ARcs.DS

keywords Non-volatilememorycachingmiddlewarecachehierarchymultiplechoiceknapsackproblemtieringvsreplicationkey-valuestorehost-sideconfiguration

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper addresses the question a system designer faces when Non-Volatile Memory (NVM) joins DRAM, SSD, and disk as cache options: with a fixed budget, which storage media should form the cache, how much of each should be bought, and should a data item be tiered (one copy) or replicated (copies on several stashes). The paper claims all three decisions can be solved together by formulating the Cache Configuration Problem as a Multiple Choice Knapsack Problem (MCKP), where each key-value pair or disk page picks one placement option with a benefit and a price. It then shows that a greedy algorithm that repeatedly applies the upgrade with the highest benefit-per-dollar solves the linear-programming relaxation exactly, and that truncating the last fractional upgrade gives a near-optimal integer solution. Trace-driven experiments for a host-side cache (disk blocks) and a key-value store conclude that with a slim failure rate and frequent writes, tiering outperforms replication; selective replication pays only for specific failure and workload regimes. If correct, this gives cache designers a principled way to evaluate memory mixes, budget thresholds, and replication policies before buying hardware.

What carries the argument

The load-bearing mechanism is the Multiple Choice Knapsack Problem (MCKP) together with a greedy algorithm on its linear-programming relaxation. Each candidate stash contributes placement options for a data item; a preprocessing step keeps only options on the convex hull of the price-benefit points, eliminating placements that are dominated by another option that is cheaper and more beneficial for that item. The greedy step repeatedly finds the item whose next viable placement has the largest upgrade gradient, defined as the increase in benefit divided by the increase in price, and performs that upgrade until the budget or the positive-gradient upgrades run out. This procedure is known to return the optimal fractional solution, and the integer solution obtained by stopping before the last partial upgrade is the near-optimal approximation the paper uses. The running time of the paper's priority-queue implementation is $O(np \log np)$ for $n$ data items and $p$ placement options.

What would settle it

Calculate the gap between the greedy integer solution and the LP-optimal fractional solution for constructed MCKP instances where a single data item consumes a large fraction of the budget, or for worst-case instances with large integrality gaps; if the gap exceeds the benefit of the last upgrade by a substantial margin, the near-optimality claim fails. A simpler concrete check: run the paper's greedy algorithm on an instance with one very large item and one very small item under a tight budget and compare service times to the true integer optimum.

Watch

Extended reading notes

Core claim

The central discovery is a reduction: the simultaneous choice of stashes, their capacities, and per-item placement—the Cache Configuration Problem—is exactly an instance of the Multiple Choice Knapsack Problem. For every data item, each subset of stashes that may hold a copy defines a placement option with a benefit (expected service time saved versus keeping the item only in permanent storage) and a price (the bytes it consumes on each chosen stash). The objective is to maximize total benefit while respecting the budget, with each item assigned exactly one option. Because the LP relaxation of MCKP is solved optimally by upgrading items in decreasing order of benefit-to-price gradient, discarding only the final fractional upgrade yields an integer solution whose benefit is bounded by the value of that one partial upgrade. The paper concludes from trace-driven evaluation that on realistic workloads the optimal policy is usually tiering rather than replication when failures are rare and writes are frequent, and that forced replication can be much worse, while selective replication is beneficial for rarely written items.

Load-bearing premise

The load-bearing premise is that each data item is small relative to the total budget, so dropping the last fractional upgrade leaves a solution close to the integer optimum; the paper asserts this without quantifying the gap, and worst-case MCKP instances can make that gap large.

Editorial extensions

If this is right

A cache designer can feed device latencies, bandwidths, prices, failure rates, and workload access frequencies into one algorithm and obtain a specific list of which stashes to buy, at what capacities, and where to put each item.
Under the workloads studied, budget expenditure past a threshold yields almost no further service-time improvement, so the algorithm identifies when additional cache spending is wasted.
Tiering is the better default with slim failure rates and frequent updates; replication should be reserved for rarely written, highly valued items, because maintaining extra copies on writes is expensive and forced replication was orders of magnitude worse in the mail-server experiment.
The optimal configuration can be matched by many very different placements with similar average service time; restricting the placement options allows designers to explore simpler configurations without large degradation.
The algorithm provides an offline optimal yardstick for comparing online replacement policies and cache hierarchies, and it subsumes earlier cache-tiering heuristics by admitting arbitrary mixes of media and replication.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper's own gradient ranking could be reused online as a priority order for admission and eviction, recomputing placement as access frequencies drift; the static model already yields all the marginal rates needed for such a policy.
The paper assumes independent requests and static probabilities, so a configuration tuned to one trace could be tested for robustness by replaying a shifted workload with new items or changing popularity skew and measuring how much service time degrades between recomputations.
The single-stash-failure assumption may understate the value of replication during correlated failures such as a power loss taking down all DRAM stashes; extending the model to multi-stash failure events is a testable way to see whether tiering's dominance persists.
The NVM parameters used in the evaluation are representative placeholders, so the tiering-over-replication conclusion should be re-tested as real NVM products with measured latencies, bandwidths, and prices arrive.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

This paper gives a clean way to formulate cache configuration—stash selection, capacities, and tiering-vs-replication under a budget—as a multiple choice knapsack problem. That framing is genuinely useful, and the paper is worth reading for it. But the optimality claim goes beyond what the math supports, and the failure-rate computation in Section 4.1 has a serious typo as written.

What's actually new: the combination of MCKP with replication, failure recovery, and a budget constraint is not in the cited caching literature. The counterexample to the Kim et al. placement heuristic in the appendix is a concrete, checkable result. The greedy LP algorithm is standard, but the application to cache design is reasonable. The trace-driven evaluation covers both host-side caches and key-value stores, and the qualitative findings—NVM2 often beats NVM1 for tight budgets, forced replication is terrible, optional replication is close to tiering—are plausible.

The main soft spot is the near-optimality claim. Section 3 shows only that GRint ≤ OPTint ≤ OPTfrac = GRfrac, then says the last fractional upgrade is insignificant because items are small. That is not a bound, and worst-case MCKP instances have large integrality gaps. The related-work section goes further and calls the method 'provably optimal,' which is unsupported for the integer problem. This is the thing to fix. A standard MCKP approximation guarantee or a measured gap on the actual traces would suffice.

The failure-rate paragraph in Section 4.1 says to multiply the number of requests per hour by (MTTF+MTTR). Given the model's definition of λ as a rate where 1/λ requests separate failures, that product is the inter-arrival, not the rate. As written, failure costs would be inflated by roughly (R·T)^2, which could flip the replication-versus-tiering conclusions. I suspect the implementation actually divides, but no code or data are released, so a reader cannot confirm. That is a reproducibility problem for a paper whose results depend on failure parameters.

Citation pattern is fine. The paper is properly situated in the multi-level cache and NVM tiering literature, and the knapsack references are the standard ones.

Bottom line: this deserves a serious referee. I would send it out, but I would require the authors to remove or substantiate the optimality claim and to correct the failure-rate formula. The framework is worth engaging with even with these caveats.

Referee Report

4 major / 6 minor

Summary. The paper formalizes the problem of designing a multi-stash caching hierarchy under a fixed monetary budget as a Cache Configuration Problem, in which the designer chooses which storage media to buy, their capacities, and, for each data item, whether to store it in one stash (tiering) or in several stashes (replication). The optimization is cast as a Multiple Choice Knapsack Problem (MCKP), and a greedy algorithm based on the LP relaxation is proposed as a near-optimal solver. The authors evaluate the method on trace-driven scenarios for a host-side cache (mail-server disk-block trace) and a key-value store (BG social-networking trace), comparing tiering, optional replication, and forced replication, and drawing lessons about which memory mixes are cost-effective and when replication is worthwhile.

Significance. If the technical issues are repaired, the paper's main contribution is a clean, general reduction of a practically important configuration problem to MCKP, together with a fast greedy algorithm that is provably optimal for the LP relaxation. The convex-hull-based viability pruning and the side-by-side comparison of tiering, optional replication, and forced replication across two middleware classes are useful and clearly presented. The explicit example showing that the placement heuristic of Kim et al. [15] is sub-optimal on a small instance is a nice addition. However, the paper does not ship code, data, or machine-checked proofs, and the numerical conclusions depend on a failure-rate formula that appears inverted as written and on an unquantified approximation gap.

major comments (4)

[Section 4.1 with Section 2.2] The failure-rate computation is inverted as written. Section 2.2 defines lambda so that the mean inter-arrival between failures is 1/lambda requests. Section 4.1 then says that to determine lambda_F for a single stash failure, one multiplies the number of requests per hour by (MTTF+MTTR) (or (MTBF+MTTR) for DRAM). If R is requests per hour and T is (MTTF+MTTR) in hours, the product R*T is the mean number of requests between failures, i.e. 1/lambda_F, not lambda_F. The correct value is lambda_F = 1/(R*T). Because the terms lambda_F * (restoreCost + retrievalCost) enter serv(P,k) linearly, using R*T in place of 1/(R*T) inflates failure penalties by a factor of roughly (R*T)^2, which is enormous for the Table 2 parameters (T on the order of years and R on the order of 10^6 requests/hour). This can change the relative ordering of tiering and replication, so the numerical conclusions in Sections 4.2 and 4.3 must be recomputed with the corrected formula unless the text is reporting the reciprocal of what the implementation actually uses.
[Section 3 and Section 5] The central near-optimality claim is asserted, not established. The chain GRint <= OPTint <= OPTfrac = GRfrac only shows that the integral greedy solution is no worse than the integer optimum's upper bound; the sentence 'Since individual key-value pairs are small... the effect of not including the last partial upgrade is not significant' provides no bound and is not generally valid for MCKP instances, where a single small item can carry a large benefit and the integrality gap can be arbitrarily large. In addition, Algorithm 2 stops when the next upgrade's price exceeds the remaining budget; it does not consider later viable upgrades that have smaller prices and might fit, so the implementation may not even be the standard integral greedy solution that discards only the last fractional upgrade. Section 5's statement that 'our method is provably optimal' is therefore inaccurate for the integral Cache Configuration Problem. Please provide a formal approximation guarantee (e.g., a bounded greedy analysis or a PTAS-style bound) or report measured gaps between GRint and the LP upper bound on the actual traces, and correct the Section 5 wording.
[Abstract, Section 4.2, and Section 4.3] The headline conclusion that 'with a slim failure rate and frequent data updates, tiering ... is superior to replication' is not supported by the data reported in the paper. In Figure 10 (host-side cache, Flash+NVM1), optional replication gives about 0.9 microseconds average service time at the high budget range, while tiering gives about 1.4 microseconds, so replication is substantially better. In Figure 13 (KVS, NVM2+DRAM), the tiering and optional replication lines are indistinguishable, which supports 'no worse than' rather than 'superior to.' Moreover, the KVS trace is 99% reads and 1% writes, so it does not exercise 'frequent data updates.' The abstract and the Section 1 lessons should be narrowed to the specific conditions under which the comparison actually holds, or the evaluation should be extended to workloads with genuinely frequent updates.
[Sections 4.1-4.3 and Appendix] Because no code or data are released, the reader cannot determine whether the implementation follows the multiply formula in Section 4.1 or the reciprocal that matches Section 2.2's definition. This ambiguity is load-bearing: the reported optimal placements in Figures 5 and 9 are driven by expected failure costs, and the tiering-versus-replication comparison in Figures 10 and 13 depends on those costs. The paper should state the exact implemented formula for lambda_F and, ideally, release the trace-processing and placement code so the numerical results can be independently reproduced.

minor comments (6)

[Section 2.2] The definition of lambda would be clearer if it stated the units explicitly: lambda is failures per request, and 1/lambda is the mean number of requests between failures.
[Section 3, Algorithms 1-3] The notation is inconsistent: Section 2 uses x_{P,k}, while Section 3 and the pseudocode use x_{p,S}; please unify the notation.
[Section 4.2, Figure 7] The phrase 'NVM2 generally does better than NVM1 for anything but the full $225 budget' should specify that 'better' means lower average service time; the y-axis of Figure 7 is not labeled with units.
[Section 4.3, Figure 13] The tiering and optional replication lines are said to be extremely close, but no numerical difference is given; adding a zoomed inset or a table of values would make the comparison concrete and would support the subsequent conclusion.
[Section 5] The related-work discussion describes the method as 'provably optimal' and a 'measuring yardstick'; even after the algorithm is fixed, the paper should use 'LP-optimal' or 'near-optimal with a stated bound' rather than 'provably optimal' for the integral problem.
[General] The paper has no conclusion section; the lessons from Section 1 are not restated or reconciled with the later figures, which is especially noticeable because the abstract's claim about tiering superiority is stronger than the results.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the MCKP formulation takes external device and workload parameters as inputs, and no prediction reduces to a fitted parameter or self-citation by construction.

full rationale

This paper's derivation chain is self-contained against external inputs. The Cache Configuration Problem is built from device specifications (read/write latencies and bandwidths, price, MTTF/MTTR) and workload statistics (fR, fW, sizes, comp time), all given as inputs; the optimal placement is the output of the MCKP optimization. The equivalence between the cache problem and MCKP is a direct transcription (placement option = item choice, price = weight, benefit = serv(empty)-serv(P)), not a renaming that presupposes the conclusions. The LP-greedy optimality is cited to [21], an external Operations Research reference, and the implementation complexity to [8,26]; no load-bearing step relies on the authors' own prior work. Self-references [1,10,11] are motivational or future-work only. The evaluation is trace-driven with externally published traces [13,16] and device parameters from Table 2. Two concerns in the paper—the unquantified 'last fractional upgrade' rounding step and the Section 4.1 lambda_F computation (which as written yields the mean number of requests between failures rather than the rate used in Section 2.2)—are correctness or rigor issues about whether the model's assumptions hold, not circularities in which a prediction is equivalent to its input by construction. Therefore no circular step is present.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

No new physical entities are postulated. NVM1 and NVM2 are representative parameter sets, not claimed to be real devices; the 'stash' and 'placement option' concepts are analytical constructs, not independent entities requiring falsifiable evidence.

free parameters (3)

NVM1 and NVM2 device parameters = Read/write latencies, bandwidths, price, MTTF (Table 2)
Chosen as representative values for NVM because current parameters are undetermined; they affect the numerical results but not the method.
Failure rate lambda_F calculation = Derived from request rate and MTTF/MTBF+MTTR
The method for converting wall-clock MTTF to a per-request failure rate is described imprecisely in Section 4.1; its orientation (product vs. reciprocal) is ambiguous.
Cost of computation comp(k) for KVS = From trace file
The time to recompute a key-value pair after a read miss is taken from the trace; not fitted to force a result.

assumptions (4)

domain assumption Query and update events are independent and the probabilities are stationary over time
Section 2 states the model assumes a stream of independent events with known a priori probabilities, enabling a static optimal placement.
domain assumption Only one stash fails at a time; failure events are rare enough to ignore simultaneous failures
Section 4.1: 'we only consider failure events that consist of a single device failure based on the assumption that failure events are sufficiently infrequent...'
standard math The greedy algorithm solves the LP relaxation of MCKP optimally, per Sinha and Zoltners [21]
Section 3 invokes [21] for the optimality of the greedy algorithm for the LP relaxation; the result is not derived in the paper.
ad hoc to paper Individual data items are small relative to budget, so truncating the fractional upgrade leaves a near-optimal solution
Section 3: 'Since individual key-value pairs are small with respect to the overall database size, the effect of not including the last partial upgrade is not significant.' This is the key assumption that makes the integral greedy a close approximation.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Memory Hierarchy Design for Caching Middleware in the Age of NVM." pith.science (2026). https://pith.science/paper/F3VCWKJ2

@misc{pith2026250605071,
  author       = {Pith},
  title        = {Pith review of: Memory Hierarchy Design for Caching Middleware in the Age of NVM},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/F3VCWKJ2}},
  note         = {Machine review of arXiv:2506.05071}
}

read the original abstract

Advances in storage technology have introduced Non-Volatile Memory, NVM, as a new storage medium. NVM, along with Dynamic Random Access Memory (DRAM), Solid State Disk (SSD), and Disk present a system designer with a wide array of options in designing caching middleware. Moreover, design decisions to replicate a data item in more than one level of a caching memory hierarchy may enhance the overall system performance with a faster recovery time in the event of a memory failure. Given a fixed budget, the key configuration questions are: Which storage media should constitute the memory hierarchy? What is the storage capacity of each hierarchy? Should data be replicated or partitioned across the different levels of the hierarchy? We model these cache configuration questions as an instance of the Multiple Choice Knapsack Problem (MCKP). This model is guided by the specification of each type of memory along with an application's database characteristics and its workload. Although MCKP is NP-complete, its linear programming relaxation is efficiently solvable and can be used to closely approximate the optimal solution. We use the resulting simple algorithm to evaluate design tradeoffs in the context of a memory hierarchy for a Key-Value Store (e.g., memcached) as well as a host-side cache (e.g., Flashcache). The results show selective replication is appropriate with certain failure rates and workload characteristics. With a slim failure rate and frequent data updates, tiering of data across the different storage media that constitute the cache is superior to replication.

Figures

Figures reproduced from arXiv: 2506.05071 by the authors.

**Figure 2.** Illustration of SetViableOptions. Before the first iteration, the viableList for k is initialized to [∅]. The algorithm examines each segment connecting P∅ to the three placements to the right and selects PF because the segment from P∅ to PF has the largest slope. The viableList for k is now [∅, F]. In the second iteration, the algorithm looks at the segments connecting PF to the two placements to the right and sele… view at source ↗

**Figure 3.** The viableList for the key on the left is [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Figures from the paper (10 more)

**Figure 4.** Figure 4: Three key-value pairs and their placement options. [PITH_FULL_IMAGE:figures/full_fig_p013_4.png]

**Figure 5.** Figure 5: The optimal partition of the disk pages among the stashes as the budget varies. [PITH_FULL_IMAGE:figures/full_fig_p016_5.png]

**Figure 6.** Figure 6: The average cost to service requests under the optimal cache configuration for [PITH_FULL_IMAGE:figures/full_fig_p016_6.png]

**Figure 7.** Figure 7: Average service time with only one stash. [PITH_FULL_IMAGE:figures/full_fig_p017_7.png]

**Figure 8.** Figure 8: The average cost to service requests when there are two stashes using a tiering [PITH_FULL_IMAGE:figures/full_fig_p017_8.png]

**Figure 9.** Figure 9: The optimal partition of disk pages among stashes when all 8 placements are [PITH_FULL_IMAGE:figures/full_fig_p018_9.png]

**Figure 10.** Figure 10: Comparison of tiering and optional replication with two stashes: Flash and [PITH_FULL_IMAGE:figures/full_fig_p018_10.png]

**Figure 11.** Figure 11: The optimal partition of the key-value pairs among the stashes as the budget [PITH_FULL_IMAGE:figures/full_fig_p019_11.png]

**Figure 12.** Figure 12: Comparison of cache configurations with two stashes with tiering. [PITH_FULL_IMAGE:figures/full_fig_p020_12.png]

**Figure 13.** Figure 13: A comparison of tiering and replication policies with a cache that includes [PITH_FULL_IMAGE:figures/full_fig_p020_13.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

[15]

L., and Chiu, L

Kim, H., Seshadri, S., Dickey, C. L., and Chiu, L. Evaluating Phase Change Memory for Enterprise Storage Systems: A Study of Caching and Tiering Approaches . In FAST 14\/ (2014)

work page 2014
[1]

A Comparison of Flashcache with IQ-Twemcached

Alabdulkarim, Y., Almaymoni, M., Cao, Z., Ghandeharizadeh, S., Nguyen, H., and Song, L. A Comparison of Flashcache with IQ-Twemcached . In IEEE CloudDM\/ (2016)

work page 2016
[2]

LinkBench: A Database Benchmark Based on the Facebook Social Graph

Armstrong, T., Ponnekanti, V., Borthakur, D., and Callaghan, M. LinkBench: A Database Benchmark Based on the Facebook Social Graph . ACM SIGMOD\/ (June 2013)

work page 2013
[3]

How to Build a Non-Volatile Memory Database Management System

Arulraj, J., and Pavlo, A. How to Build a Non-Volatile Memory Database Management System . In SIGMOD\/ (2017)

work page 2017
[4]

Write-behind Logging

Arulraj, J., Perron, M., and Pavlo, A. Write-behind Logging . VLDB 10 , 4 (2016)

work page 2016
[5]

BG: A Benchmark to Evaluate Interactive Social Networking Actions

Barahmand, S., and Ghandeharizadeh, S. BG: A Benchmark to Evaluate Interactive Social Networking Actions . CIDR\/ (January 2013)

work page 2013
[6]

J., and Venkataramani, V

Bronson, N., Amsden, Z., Cabrera, G., Chakka, P., Dimov, P., Ding, H., Ferris, J., Giardullo, A., Kulkarni, S., Li, H., Marchukov, M., Petrov, D., Puzar, L., Song, Y. J., and Venkataramani, V. TAO: Facebook s Distributed Data Store for the Social Graph . In USENIX ATC 13 \/ (San Jose, CA, 2013), pp. 49--60

work page 2013
[7]

Bronson, N., Lento, T., and Wiener, J. L. Open Data Challenges at Facebook . In ICDE \/ (2015), pp. 1516--1519

work page 2015

Show all 27 references

[8]

An O(n) Algorithm for the Multiple-Choice Knapsack Linear Program

Dyer, M. An O(n) Algorithm for the Multiple-Choice Knapsack Linear Program . Mathematical Programming 29 , 1 (1984), 57--63

1984
[9]

R., and Johnson, D

Garey, M. R., and Johnson, D. S. Computers and Intractability; A Guide to the Theory of NP-Completeness . W. H. Freeman & Co., New York, NY, USA, 1990

1990
[10]

CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores

Ghandeharizadeh, S., Irani, S., Lam, J., and Yap, J. CAMP: A Cost Adaptive Multi-Queue Eviction Policy for Key-Value Stores . Middleware\/ (2014)

2014
[11]

Host Side Caching: Solutions and Opportunities

Ghandeharizadeh, S., Menon, J., Kotzur, G., Sen, S., and Chawla, G. Host Side Caching: Solutions and Opportunities . In DB & IS\/ (July 2016)

2016
[12]

Adapting Server Systems for New Memory Technologies

Hunter, H., Lastras-Montano, L., and Bhattacharjee, B. Adapting Server Systems for New Memory Technologies . IEEE Computer 47 , 9 (Sept 2014), 78--84

2014
[13]

L., Zhang, Q., and Sharda, V

Kavalanekar, S., Worthington, B. L., Zhang, Q., and Sharda, V. Characterization of Storage Workload Traces from Production Windows Servers . In 4th International Symposium on Workload Characterization\/ (2008), pp. 119--128

2008
[14]

Knapsack Problems

Kellerer, H., Pferschy, U., and Pisinger, D. Knapsack Problems . Springer, Berlin, Germany, 2004

2004
[16]

I/O Deduplication: Utilizing Content Similarity to Improve I/O Performance

Koller, R., and Rangaswami, R. I/O Deduplication: Utilizing Content Similarity to Improve I/O Performance . In USENIX FAST \/ (2010)

2010
[17]

Knapsack Problems: Algorithms and Computer Implementations

Martello, S., and Toth, P. Knapsack Problems: Algorithms and Computer Implementations . John Wiley & Sons, Inc., New York, NY, USA, 1990

1990
[18]

Multi-level Caching in Distributed File Systems -or- Your cache ain't nuthin' but trash

Muntz, D., and Honeyman, P. Multi-level Caching in Distributed File Systems -or- Your cache ain't nuthin' but trash . In In Proceedings of the Winter 1992 USENIX\/ (1992), pp. 305--313

1992
[19]

A High Performance File System for Non-volatile Main Memory

Ou, J., Shu, J., and Lu, Y. A High Performance File System for Non-volatile Main Memory . In EuroSys\/ (2016)

2016
[20]

Persistent B+-Trees in Non-Volatile Main Memory

Shimin, C., and Qin, J. Persistent B+-Trees in Non-Volatile Main Memory . PVLDB 8 , 7 (2015)

2015
[21]

Sinha, P., and Zoltners, A. A. The Multiple-Choice Knapsack Problem . Operations Research 27 , 3 (1979), pp. 503--515

1979
[22]

B., Snider, G

Strukov, D. B., Snider, G. S., Stewart, D. R., and Williams, R. S. The Missing Memristor Found . Nature 7191\/ (2008), 80--83

2008
[23]

DP2: Reducing Transaction Overhead with Differential and Dual Persistency in Persistent Memory

Sun, L., Lu, Y., and Shu, J. DP2: Reducing Transaction Overhead with Differential and Dual Persistency in Persistent Memory . In CF\/ (2015)

2015
[24]

M., and Wilkes, J

Wong, T. M., and Wilkes, J. My Cache or Yours? Making Storage More Exclusive . In USENIX ATEC\/ (2002), pp. 161--175

2002
[25]

NVMcached: An NVM-based Key-Value Cache

Wu, X., Ni, F., Zhang, L., Wang, Y., Ren, Y., Hack, M., Shao, Z., and Jiang, S. NVMcached: An NVM-based Key-Value Cache . In ACM SIGOPS APSys\/ (2016)

2016
[26]

An O(N) Algorithm for the Linear Multiple Choice Knapsack Problem and Related Problems

Zemel, E. An O(N) Algorithm for the Linear Multiple Choice Knapsack Problem and Related Problems . Inf. Process. Lett. 18 , 3 (Mar. 1984), 123--128

1984
[27]

Second-Level Buffer Cache Management

Zhou, Y., Chen, Z., and Li, K. Second-Level Buffer Cache Management . IEEE Trans. Parallel Distrib. Syst. 15 , 6 (June 2004)

2004

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [15]

L., and Chiu, L

Kim, H., Seshadri, S., Dickey, C. L., and Chiu, L. Evaluating Phase Change Memory for Enterprise Storage Systems: A Study of Caching and Tiering Approaches . In FAST 14\/ (2014)

work page 2014

[2] [1]

A Comparison of Flashcache with IQ-Twemcached

Alabdulkarim, Y., Almaymoni, M., Cao, Z., Ghandeharizadeh, S., Nguyen, H., and Song, L. A Comparison of Flashcache with IQ-Twemcached . In IEEE CloudDM\/ (2016)

work page 2016

[3] [2]

LinkBench: A Database Benchmark Based on the Facebook Social Graph

Armstrong, T., Ponnekanti, V., Borthakur, D., and Callaghan, M. LinkBench: A Database Benchmark Based on the Facebook Social Graph . ACM SIGMOD\/ (June 2013)

work page 2013

[4] [3]

How to Build a Non-Volatile Memory Database Management System

Arulraj, J., and Pavlo, A. How to Build a Non-Volatile Memory Database Management System . In SIGMOD\/ (2017)

work page 2017

[5] [4]

Write-behind Logging

Arulraj, J., Perron, M., and Pavlo, A. Write-behind Logging . VLDB 10 , 4 (2016)

work page 2016

[6] [5]

BG: A Benchmark to Evaluate Interactive Social Networking Actions

Barahmand, S., and Ghandeharizadeh, S. BG: A Benchmark to Evaluate Interactive Social Networking Actions . CIDR\/ (January 2013)

work page 2013

[7] [6]

J., and Venkataramani, V

Bronson, N., Amsden, Z., Cabrera, G., Chakka, P., Dimov, P., Ding, H., Ferris, J., Giardullo, A., Kulkarni, S., Li, H., Marchukov, M., Petrov, D., Puzar, L., Song, Y. J., and Venkataramani, V. TAO: Facebook s Distributed Data Store for the Social Graph . In USENIX ATC 13 \/ (San Jose, CA, 2013), pp. 49--60

work page 2013

[8] [7]

Bronson, N., Lento, T., and Wiener, J. L. Open Data Challenges at Facebook . In ICDE \/ (2015), pp. 1516--1519

work page 2015