one RW mutex would mean you'd lock the whole array; that way data access becomes pretty much single-threaded. simplest solution that comes to mind: AtomicIntegerArray (or whatever it is in your language of choice).

you could also implement a bitset over AtomicLongArray.

more complicated: partition into x*x chunks and rw-locking those. this could be backed by an mmap'ed a million bytes for persistence, but no idea if that'd make the app disk io bound or something.