Queue-based fixed-duration memory cache

Question

I used to use the MemoryCache in .Net but recently read about a DB using using a linked-list, which only had to check the prefix of the list in \$O(1)\$ complexity, to time values out, as opposed to ln N; the heap-based approach that's default for variable timeout, min-heaps.

I'd appreciate a review of this code; in terms of how optimal it is and if there are obvious mistakes in it, that I'm missing. The general idea is that count(R) >>> count(W).

I considered using ReaderWriterLockSlim in upgradeable mode, but I may very well have two threads with read locks trying to acquire a write upgrade simultaneously in this piece of code, so I decided against. The check of the queue head is supposed to be quick enough to avoid contention around this resource.

This code is intended to be used in a low-latency F# API as part of Logibit Hawk.

I'd also like this code to be non-allocating, besides the single int64 that's the Instant (x2) and the allocated-outside string reference. Returning Choice-values (allocating) is intentional however, and will be changed to Result in the future.

module Settings =
  open NodaTime
  open System.Collections.Generic
  open System.Collections.Concurrent

  let private tsem = obj ()
  let private runTimeouts (timeouts: Queue<_>) (cache: ConcurrentDictionary<string, Instant>) (now: Instant) =
    /// Iterate until the head is due later than now. Tail-recursion needed.
    let rec iter () =
      if timeouts.Count = 0 then () else
      let struct (nonce, timeout) = timeouts.Peek()
      if timeout > now then () else
      ignore (timeouts.Dequeue())
      ignore (cache.TryRemove nonce)
      iter ()
    lock tsem iter

  let nonceValidatorMem (clock: IClock) (keepFor: Duration) =
    // We will use a queue, because it's O(1) on dequeue/peek and since the duration is a constant for the
    // life time of this validator, we know the head is due closest in time.
    let timeouts = Queue<_>()
    // The cache stores the nonces and when they were added
    let cache = ConcurrentDictionary<_, _>()

    fun (nonce: string, ts: Instant) ->
      let now = clock.GetCurrentInstant()
      do runTimeouts timeouts cache now
      // https://docs.microsoft.com/en-us/dotnet/api/system.collections.concurrent.concurrentdictionary-2.tryadd?view=netframework-4.7.1
      // returns true if the nonce was successfully added
      if cache.TryAdd (nonce, now) then
        do lock tsem (fun () -> timeouts.Enqueue (struct (nonce, now + keepFor)))
        Choice1Of2 ()
      else
        Choice2Of2 AlreadySeen