I don't know about Redis, but MongoDB allows you to put indexes on nested documents and even documents nested in arrays.
When you choose the first option, you would need to create an index for each attribute you want to ckeck for.
db.collection.ensureIndex({ attributes.is_admin: 1 },{ sparse:true });
Or for the second option:
db.collection.ensureIndex({ attribute_key: 1 },{ sparse:true });
When you do not know how many attributes you will have and want to create only one index which covers all current attributes and any new attributes you are going to add in the future, you should put the attributes into an array of key/value pairs:
{ id: <user-id>,
attributes: [
{ key: "isAdmin", value:true },
{ key: "favoriteFood", value:"Waffles" },
{ key: "maximumSize", value:42 }
]
}
With that schema you could create an index like this:
db.collection.ensureIndex({ "attributes.key": 1 });
and you will be able to quickly find documents by attribute. You can also create an index like this:
db.collection.ensureIndex({ "attributes": 1});
and you can search for exact key/value pairs, but not for keys without supplying an exact value or values without keys. When you also want to search for keys only, for value-ranges or sort by value, use a compound-index like this:
db.collection.ensureIndex({ "attributes.key": 1, "attributes.value": 1 });