Copy-on-Write KV Pages

Problem

Simulate physical KV pages storing integer token markers. Initially there are no sequences or pages. Operations are ["new", id], ["append", id, token], ["fork", source, destination], and ["release", id]. Fork copies the block table and shares its physical pages.

On append, allocate a page if the sequence has no page or its last page is full. If its partial last page has multiple references, copy that page before appending; decrement the old reference count. Otherwise modify its unique partial page. Always allocate the smallest currently unused nonnegative page ID. Release removes a sequence and frees pages whose reference counts reach zero.

Return {"sequences": map from live IDs to ordered page-ID lists, "pages": live pages sorted by ID as {"id","tokens","refs"}, "peakPages": maximum simultaneously live physical page count}. No fixed pool capacity is imposed; the trace specifies a small allocator model.

def copy_on_write_pages(page_size, operations):

Constraints

• 1 ≤ page_size ≤ 8; 0..48 operations; token markers are integers.
• New/destination IDs are unused strings; source and release/append IDs exist.
• A fork shares whole pages including a partial tail; all sequences append only at the end.
• Inputs satisfy these constraints; invalid-input handling is not graded. Use only Python standard library and NumPy.

Examples

Arguments: [
  2,
  [
    [
      "new",
      "a"
    ],
    [
      "append",
      "a",
      1
    ]
  ]
]
Expected result: {
  "sequences": {
    "a": [
      0
    ]
  },
  "pages": [
    {
      "id": 0,
      "tokens": [
        1
      ],
      "refs": 1
    }
  ],
  "peakPages": 1
}

Arguments: [
  2,
  [
    [
      "new",
      "a"
    ],
    [
      "append",
      "a",
      1
    ],
    [
      "fork",
      "a",
      "b"
    ],
    [
      "append",
      "b",
      2
    ]
  ]
]
Expected result: {
  "sequences": {
    "a": [
      0
    ],
    "b": [
      1
    ]
  },
  "pages": [
    {
      "id": 0,
      "tokens": [
        1
      ],
      "refs": 1
    },
    {
      "id": 1,
      "tokens": [
        1,
        2
      ],
      "refs": 1
    }
  ],
  "peakPages": 2
}