Skip to question

Q154FreeFirmware

Expiring Key-Value Store

Difficulty
Hard
Topic
Data Structures
Language
SV
Interview prompt

Question

Design a cycle-based key-value store in which every entry has a time-to-live (TTL). Expired values must never be returned, and expiration processing must avoid scanning the entire map every cycle. Use the complete SystemVerilog class under serialized method calls. Construction starts at cycle zero; only tick advances time. A put at cycle c with ttl>0 is readable while cycle<c+ttl and expires when tick reaches c+ttl, so ttl=1 lasts through the insertion cycle and expires on the next tick. ttl=0 reports an error without changing stored state. For this finite simulation exercise, callers keep cycle+ttl and every per-key version within unsigned 64-bit range, never tick past that range, and retain at most 2^31-1 heap records. Keys use a legal associative-array index type without X/Z. Values use normal assignment-copy semantics. get returns zero on a miss, and its output value is meaningful only when it returns one. Heap work includes due stale records left by updates and erasures, not only values that expire.

Candidate starting point

Implementation scaffold

class ExpiringStore #(type key_t = int, type value_t = int);
  typedef struct {
    value_t value;
    longint unsigned due;
    longint unsigned version;
  } entry_t;
  typedef struct {
    key_t key;
    longint unsigned due;
    longint unsigned version;
  } expiry_t;

  local entry_t current[key_t];
  local longint unsigned next_version[key_t];
  local expiry_t deadline_heap[$];
  local longint unsigned cycle;

  // Standard binary-min-heap helpers ordered by expiry_t.due.
  local function void heap_push(expiry_t e);
    int i;
    // TODO: implement this method.
  endfunction

  local function expiry_t heap_pop_min();
    expiry_t root = deadline_heap[0];
    // TODO: implement this method.
  endfunction

  local function void expire_due();
    // TODO: implement this method.
  endfunction

  function new();
    cycle = 0;
  endfunction

  function void put(key_t key, value_t value, int unsigned ttl);
    entry_t e;
    // TODO: implement this method.
  endfunction

  function bit get(key_t key, output value_t value);
    // TODO: implement this method.
  endfunction

  function bit erase(key_t key);
    // TODO: implement this method.
  endfunction

  function void tick();
    // TODO: implement this method.
  endfunction
endclass
Reviewed example

Trace one case

Input
t=10: put(key=7, value=0xAA, ttl=5)
t=14: get(7)
t=15: get(7)
Expected output
t=14 -> 0xAA
t=15 -> MISS

The value is readable before its absolute expiry time and is removed or ignored exactly at expiry.

What to cover

Requirements

  1. Define precisely whether ttl=1 survives the current cycle or the next cycle.
  2. Updating an existing key replaces both its value and expiration time.
  3. Ignore stale expiration records created by prior updates to the same key.
  4. Process only due scheduling records, including stale records, with heap/map overhead rather than scanning the complete current-value map each cycle.
Continue practicing
Q042 · Data StructuresReturn the first unique value in a streamEasyQ071 · Data StructuresDynamic arrays and queuesEasy