Best way to cache a collection of objects. Together or as individual items?

Question

Say I have a collection of Users. Each user has a User_ID, Username and Tenant_ID.

Sometimes I need all Users for a specific Tenant_ID.
Sometimes I need a specific User based on User_ID".
Sometimes I need a User based on Username.

I will always have the Tenant_ID available to use as part of the lookup.

What is the ideal way to implement a cache layer for this data?
What considerations should I make since I'm dealing with a multi-tenant system?
What is the best way to manage all the possible cache keys involved?

Option #1: Store all Users together under a single key of "Tenant_1_Users"

The problem with this is that I will be transferring a lot of unwanted data over the wire. If I just need to find a specific user then I need to do the lookup in code using LINQ or something after retrieving the whole collections.

Option #2: Duplicate the same User object under different keys such as "TenantID_1_UserID_5" and "TenantID_1_Username_Jason".

The problem here is managing all the various Keys and location of User objects. Especially if I need to flush a specific User because it has been updated in the database. I now need to know all the possible places it could be stored. Also uses more memory since the same User can be under different keys.

Related: AppFabric Cache 'Design' - Caching Individual Items or Collections?
The problem is that Azure AppFabric Caching does not support Regions, Tags or Notifications.

Answer 1

For what its worth, I would tend to not want to cache the same object under multiple keys, because if you need to update or delete that record later, you'll have to remember to update/delete all the possible keys that it could have used.

Answer 2

In the past I have added items to the cache individually, keying the cache off of the primary key of the record. Then, where needed, I maintained a dictionary object that gave me a fast lookup to find the primary key(s) based on some other value. When I needed this I would create a custom collection class that wrapped up all of the logic for maintaining the dictionary, looking up records that had expired from the cache, searching for records that were never added to the cache, providing accessors for retrieving items by their various values, etc. This structure made it so that each data item could expire individually without taking the rest of the collection with it, but my dictionaries would still maintain the list of which keys belonged with which secondary values so I could restore an expired item easily no matter which accessor was used to request it.

Can’t say this is necessarily the best way, but it seemed to work well for reducing trips to the data store without bogging down the app server because it had too much crammed in memory. I was working with standard ASP.NET and a SQL backend when I developed this technique but I can't see any reason why it could not be converted over to a cloud environment.