bug: Severe Lock Convoy in DecayMap and bbolt backend on High Core CPU under heavy Load

[eternal-flame-AD]

This is not really an unknown "security" issue as any off the shelf solvers (especially GPU powered ones which this is not) on GitHub will be able to achieve this (and thus would all be technically "PoC"s).

Thus I believe it is more of a performance bug.

Describe the bug

Currently what happens:

• Last exclusive writer calls .Unlock(),
• up to GOMAXPROC pending reader acquisition wake up at once -
• some goroutines piled up on the runtime immediately ask for .Lock()
• all GOMAXPROC threds serializes themselves in CAS spin loops (or, park but by the time it resolves the CPU has expended more cycles in total than what would be needed to compute the proof).

Solutions:

1. Quick but mid: Do not do .RUnlock() then immediately .Lock(), it creates synchronization points and causes lock convoys. Defer all decay deletion requests through a channel into one dedicated cleanup coroutine that batch process them.
2. More reliable: Consider using sharded or lock free data structures (i.e. challenge states packed entirely into atomic 64-bit numbers) in the long run for better scaling.

To Reproduce

You need a high core processor to reproduce this, but since you have a 7950X3D I have an 7950X, I am pretty certain the situations will be similar.

Hit a local instance with a native solver and notice that the solver is emitting proofs faster than Anubis can respond to requests even under "extreme suspiction" (4).

> target/release/simd-mcaptcha live --api-type anubis --host http://localhost:8923/ \
                                                    --n-workers 64 &

You are hitting host http://localhost:8923/, n_workers: 64
[0.0s] proofs accepted: 0, failed: 0, 5s: 0.0pps, 5s_failed: 0.0rps, 0.00% iowait
[5.0s] proofs accepted: 53805, failed: 0, 5s: 10761.0pps, 5s_failed: 0.0rps, 74.91% http_wait
[10.0s] proofs accepted: 108805, failed: 0, 5s: 11000.0pps, 5s_failed: 0.0rps, 74.34% http_wait
[15.0s] proofs accepted: 164656, failed: 0, 5s: 11170.2pps, 5s_failed: 0.0rps, 73.92% http_wait
[20.0s] proofs accepted: 220786, failed: 0, 5s: 11226.0pps, 5s_failed: 0.0rps, 73.65% http_wait
[25.0s] proofs accepted: 277543, failed: 0, 5s: 11351.4pps, 5s_failed: 0.0rps, 73.43% http_wait
[30.0s] proofs accepted: 335189, failed: 0, 5s: 11529.2pps, 5s_failed: 0.0rps, 73.10% http_wait
[35.0s] proofs accepted: 392865, failed: 0, 5s: 11535.2pps, 5s_failed: 0.0rps, 72.80% http_wait
[40.0s] proofs accepted: 450552, failed: 0, 5s: 11537.4pps, 5s_failed: 0.0rps, 72.56% http_wait
[45.0s] proofs accepted: 508698, failed: 0, 5s: 11629.2pps, 5s_failed: 0.0rps, 72.35% http_wait
[50.0s] proofs accepted: 566663, failed: 0, 5s: 11593.0pps, 5s_failed: 0.0rps, 72.20% http_wait
[55.0s] proofs accepted: 624373, failed: 0, 5s: 11542.0pps, 5s_failed: 0.0rps, 72.08% http_wait
[60.0s] proofs accepted: 681909, failed: 0, 5s: 11507.2pps, 5s_failed: 0.0rps, 71.99% http_wait

Instrument your server to verify the lock convoy:

func init() {
	runtime.SetMutexProfileFraction(1000) // 1 out of 1000 mutex ops

	go http.ListenAndServe(":9000", nil)
}

Collect go pprof for a minute while loading it.

Expected behavior

Regardless whether native solvers are considered "fair exchange", "bypass", "ethical", "attack", or not (and I do not have any interest in arguing with that). As a "security solution" against mass scrapers it should maintain a load asymmetry (i.e. cost less to book-keep the challenges than for the client to solve challenges) under any circumstance.

Screenshots

This is classic wakeup "thundering herd" where every write->read transition lock up the runtime:

Server version: v1.22.0-12-g9430d0e

Additional context

Policy deployed:

thresholds:
  # For clients that are browser like and have gained many points from custom rules
  - name: extreme-suspicion
    expression: weight >= 0
    action: CHALLENGE
    challenge:
      # https://anubis.techaro.lol/docs/admin/configuration/challenges/proof-of-work
      algorithm: fast
      difficulty: 4
      report_as: 4

[Xe]

Note for myself so I can make a better response later: most production usecases will have disk or database backed storage engine in the mix, meaning that decaymap will not be hit here.

[eternal-flame-AD]

I am pretty sure disk or database backed storage will be more expensive, all your DB backends enforce consistency and at 11kPPS * 3-4 txn/proof repetitive insert, select, select, delete sequences that is not going to hold (at least not going to take less cycles than to just compute the PoW).

If you could pack the challenges into 64-bit states (and expand "salt" using HKDF only when needed), you can saturate any realistic network bandwidth without running out of memory.

A quick back of the envelope computation: let's say 64-bytes of traffic are required for Anubis to register a challenge and every challenge has a 5 minute lifetime . Using a 10gbps NIC that is still only 30GB absolute max - deployments at scale definitely have that memory.

[eternal-flame-AD]

Reproducible on bbolt as well with even worse throughput:

/tmp is on a ramfs:

store:
  backend: bbolt
  parameters:
    path: /tmp/anubis.bdb

You are hitting host http://localhost:8923/, n_workers: 32
[0.0s] proofs accepted: 0, failed: 0, 5s: 0.0pps, 5s_failed: 0.0rps, 0.00% http_wait
[5.0s] proofs accepted: 20908, failed: 0, 5s: 4181.6pps, 5s_failed: 0.0rps, 88.17% http_wait
[10.0s] proofs accepted: 42616, failed: 0, 5s: 4341.6pps, 5s_failed: 0.0rps, 88.01% http_wait
[15.0s] proofs accepted: 64229, failed: 0, 5s: 4322.6pps, 5s_failed: 0.0rps, 87.90% http_wait
[20.0s] proofs accepted: 88472, failed: 0, 5s: 4848.6pps, 5s_failed: 0.0rps, 87.37% http_wait
[25.0s] proofs accepted: 113007, failed: 0, 5s: 4907.0pps, 5s_failed: 0.0rps, 87.03% http_wait
[30.0s] proofs accepted: 137701, failed: 0, 5s: 4938.8pps, 5s_failed: 0.0rps, 86.78% http_wait
[35.0s] proofs accepted: 162293, failed: 0, 5s: 4918.4pps, 5s_failed: 0.0rps, 86.62% http_wait
[40.0s] proofs accepted: 187073, failed: 0, 5s: 4956.0pps, 5s_failed: 0.0rps, 86.49% http_wait
[45.0s] proofs accepted: 212344, failed: 0, 5s: 5054.2pps, 5s_failed: 0.0rps, 86.37% http_wait
[50.0s] proofs accepted: 237740, failed: 0, 5s: 5079.2pps, 5s_failed: 0.0rps, 86.27% http_wait
[55.0s] proofs accepted: 263157, failed: 0, 5s: 5083.4pps, 5s_failed: 0.0rps, 86.18% http_wait
[60.0s] proofs accepted: 288606, failed: 0, 5s: 5089.8pps, 5s_failed: 0.0rps, 86.10% http_wait

[Xe]

Would using something like the actor pattern or sync.Map help here or is this just kind of architecturally unavoidable?

[eternal-flame-AD]

This can 100% be done lock free just whether you need it (for example the current difficulty is too low for high perf solvers)-if you solve that first 22k PPS probably won't come in easily.

To do it lock free you do something like (which should take much more than 22k PPS):

Use HKDF to expand any random things you want from a single 64-bit number. For each challenge only generate 8 bytes of secure random and pack them into one atomic number. (it is small for a persistent secret but for something only valid for 5 minutes more than enough)

Put them into an insert-only map (you can try if sync.Map works, maybe it is enough maybe more subtractive engineering is required).

type IssuedAt uint64

type TimeSliceState struct {
   Secret []byte // the HKDF/HMAC key you keep secret
   Chellenges InsertOnlyMap[VisitorId, IssuedAt] // a map that only need to support insert and clearAll() 
   // can be made lock free if need, maybe you can also find a library or hand write one
}

Randomdata can be obtained by HKDF_expand(Secret, Info: "Secret for Challenger 0xabcd at timestamp 0x1234", len: howeverLongYouWant). Send the timestamp, ID and HKDF output to the client (if you want to prevent invalid things spamming you can optionally sign it with an HMAC)..

And then triple buffer (if the challenge expiration is 2 minutes):

type BufferSet struct {
   Buffers [3]TimeSliceState
   WhichIsActive uint8
}

On PassChallenge you have the user send the ID timestamp back to you, you check the HMAC to make sure you issued it, lookup in both maps and use atomic.AndUint64(0) (which returns IssuedAt if the challenge is still valid, 0 if not) to atomically mark the challenge as being committed (issued at 0 = already expired), no locks or expensive deletion needed.

Every two minutes you increment WhichIsActive to swap the buffer, the last one is the "read only but potentially valid" one (which you CHECK for Passchallenge but never insert), second to last is the standby one (which one single goroutine manage exclusively by clearing and generate a new HKDF secret), the active one gets both inserts and queries.

But yeah, always benchmark as not doing that easily lead to over or under enginnering.

[eternal-flame-AD]

Re. Actor pattern - it could work but entirely depends on the schedulers effectiveness, you really have to try yourself and load test .. I think it is not needed as you really want to save unnecessary operations, for 22K ops you don't have time for potential spinning.

The current lock convoy happens because Go mutex has optimistic spinning for up to 1ms (which is more time than what is needed to solve that challenge), plus RWMutex must wake up all readers to prevent deadlock - channels might behave better as it doesn't have that semantics. I would tread carefully with pre-built synchronous primitives (channels. mutexes, etc) if you want to build for 20-50K RPS scale as they usually involve heuristics that can definitely regress.

https://go.dev/src/internal/sync/mutex.go

[Xe]

I think that the mechanisms you're proposing for very high request rates (over 20k Bq) are out of scope for now. I'm going to add the Actor pattern for the bbolt backend, but overall I think that #1106 fixes a lot of the badness here.

[eternal-flame-AD]

Your call, what to do when unexpected load happens is entirely dependent on how you define what is "graceful". For a QoS system I would say this is suboptimal but if recall (for abuse) is more important than selectivity then that is pragmatic ..

But yes if you are not into atomics or want asymptotic scaling this can be solved with other ways like horizontal scaling features. Just FYI.

My 20k churn rate perf expectation came from a cost analysis: the CPU resource required to sustain 22k PPS @ difficulty=4 for a month (that is proof per second, not request per second) using cloud computing can be acquired for about two trips to McDonald's (~35 EUR). For me I would expect a high-volume scraping mitigation security project to handle that.

[Xe]

Oh for the record, I don't mean "20kBq is out of scope", I mean the stuff around insert-only maps and key derivation functions being out of scope. I'm going to submit a PR that uses haxmap or something to back the decaymap data and I'm working on actorification of the bbolt backend.