Size of redis database (2N or N^2)

Question

I have a redis database, and client for it, written in Ruby. What is the size of this database?

def follow!(user)
  $redis.multi do
    $redis.sadd(self.redis_key(:following), user.id)
    $redis.sadd(user.redis_key(:followers), self.id)
  end
end

def redis_key(str)
  "user:#{self.id}:#{str}"
end

# Usage:
userA.follow!(userB)

I think that it is 2N, but someone tell me that it is N^2, what is true?

Answer 1

The size of a Redis database is the used_memory_human value as returned by INFO. Because of memory optimizations, it is not really easy to guess the real size from a given data structure. It is better to test it on a limited number of items and extrapolate.

Here, supposing N is the number of users, you will have 2N sets in Redis keyspace. The size of these sets depends on the number of followers.

If all users have one follower and only one, you will get 2N sets of 1 item, so 2N items. If all users have all the other users as followers, you will get 2N sets of (N-1) items, resulting in 2N(N-1) total items.