How to implement List in .Net?

What's the best way to implement a (consistent) list type on top of memcached?

• With some googling I've come across three ways: 1) Atomic operations via lock keys 2) STM (Software Transactional Memory) with CAS 3) Atomically appending/prepending onto a value (http://code.google.com/p/memcached/wiki/FAQ#Storing_lists_of_data) #1 and #2 both require some form of spinning with random exponential back-off and #3 would require some form of locking after some point anyway to reformat the list as it nears the cache line limit of 1MB. Edit: I was hesitant on #1 and #2 was because I was unclear how one could scale to infinity without the average access time increasing to infinity.  I realized that if too much contention occurs, one could start partitioning out the list based on value into N buckets where N increases based on some average access time.

• Answer:

  If memcahed is not a requirement you can take a look at Redis, it has already list and other data structures. http://redis.io/topics/data-types