Mantendo uma lista de
friend_ids em um usuário, é o que eu recomendo. Poucas razões, 1. Você consulta um usuário e tem uma lista de todos os amigos disponíveis antecipadamente.
2.As solicitações (pendentes, aceitas) também podem ser tratadas, desde que um respectivo ids esteja presente na lista de amigos de ambos os usuários. Assim, posso obter uma lista de amigos reais e aceitos consultando
my_id, my_friend_ids = user._id, user.friend_ids
my_friends = db.users.find({'_id':{'$in': my_friend_ids}, 'friend_ids': my_id})
Sim, ao remover uma amizade, você precisa
$pull da lista de amigos de ambos os usuários, mas a frequência disso seria muito menor. Mas você consulta menos para obter a lista de amigos, que seria usada com frequência. 
