memcached / memcached/memcached

Reduce extstore item header size by 1-2 bytes

Open
#726 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

idea
Dominant language
C
Stars
14.3k
Forks
3.3k
PR merge metrics
No merged PRs in 30d

Description

An extstore item header requires 10 bytes of memory:

  • 4b page version for authentication
  • 4b offset into the page
  • 2b page id.

Internally the page version is used to sort pages and the lowest version is used for fast-evicting pages. The version from an item header is checked whenever extstore is being accessed, and if the page has been reused the item is deemed invalid and removed.

Thinking about two ideas for cutting 1-2 bytes off this header:

  • Cut version to 3 or 2 bytes. Make version local to each page rather than a global counter. Add a created or filled timestamp to the page memory. Use the timestamp to sort pages for eviction/compaction and only use version to validate data.

With a 4 byte global version; in order to have a bad fetch item data would have to remain untouched by the LRU crawler, delete, TTL, get, etc for 136 years at the rate of one page allocation per second. With 3 bytes that's 194 days. 2 bytes would be 0.75 days. Typically the same page will not be quickly reused: evictions take the oldest page, which is likely hours old. Compaction reads back the original data and evicts or re-writes memory, so there won't be dangling data.

Need to: audit the code again to ensure the version check is only truly useful on page eviction and there aren't any holes for compaction. IE: in compact readback items are locked, rather than trylocked, so there aren't any cases where it could leave an item in memory.

Some math on how long it takes for pages to get reused might justify 2 byte versions.

  • Cut offset to 3 bytes. Multiply the offset by a configured chunk size.

3b * 32 byte chunk alignment would give a max page size of 500 megabytes. The default page size is 64 megabytes. The max number of pages is 65k. Thus: the max disk size at 64m pages is 4TB. At 32b alignment the max disk space is 33 terabytes. 16T with 16b alignment.

The tradeoff is wasted disk space in the offset. If someone has many small values a chunk alignment of 8 bytes would still give a max disk usage of 8T... which with tiny enough objects you'll be out of RAM regardless. With larger than absolute minimum size values the disk space overhead of fragmentation should be a bulk of the disk space inefficiency anyway.

Downside is additional configuration options, and the system is already pretty confusing. A default chunk size of 8 or 16b and clamping page sizes with good error messages is probably enough.


Would want to do this work before adding extstore cache restart support.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by locating the extstore item-header handling, page version checks, page eviction, and compaction readback paths described in the issue. Audit whether version validation is needed only after eviction, then evaluate the proposed version and offset reductions; done means a chosen design is justified without leaving stale items or compaction cases unsafe.

Written by the indexing model from the issue text.

Assessment

Tech stack
c
Domain
backend, performance
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.