memcached and Storage of Friend list

My first post, please be gentle. I know it is long. You are all like doctors - the more info, the better the diagnosis.

What is the best way to store a list of all of your friends in the memcached cache (a simple boolean saying “yes this user is your friend”, or “no”)? Think Robert Scoble (26,000+ “friends”) on He views a list of ALL existing users, and in this list, his friends are highlighted.

I came up with 4 possible methods:
--store in memcache as an array, a list of all the "yes" friend ID's
--store your friend ID's as individual elements.
--store as a hash of arrays based on last 3 digits of friend's ID -- so have up to 1000 arrays for you.
--comma-delimited string of ID's as one element

I'm using the second one because I think it is faster to update. The single array or hash of arrays feels like too much overhead calculating and updating – and even just loading – to check for existence of a friend.

The key is FRIEND[small ID#]_[big ID#]. The value is 1.
This way there are no dupes. (I add u as friend, it always adds me as ur friend...I remove u, u remove me).
Store with it 2 additional flags: One denotes start of entries. One denotes end of entries.
As friends are added, the end flag position relative to new friends will become meaningless, but that is ok (I think).
To see if someone is your friend, the system checks if both start and end flags exist.
If both exist, it can check for existence of friend ID - if exists, then friend.
Start flag is required. If start flag is pushed out of cache, we must assume some friends were also pushed out.

Currently, the system loads from DB in a daemon in the background after you log in (if two flags are not already set).
Until the two flags are set, it does db lookups.
There is no timeout on the data in cache.
Adding/removing friends to your account adds/removes to/from memcache - so, theoretically, it might never have to pre-load anything.

Downside of my method is if the elements span multiple servers and one dies, you loose some of your friends (that's the upside of using arrays).
I don't know how to resolve if the lost box didn't contain either of the flags -- in that case, the users' info will NEVER get refreshed. This is my concern.

Any ideas?

Thanks so much!!!