Sets: Membership, Tags, and Set Algebra

In one line

A set holds unique, unordered strings with O(1) add, remove and membership checks, plus server-side intersection, union and difference. It's the natural fit for tags, permissions, unique visitors (at small scale) and social graphs.

0/6 · 0%

Think of it like this

A guest list at the door. A name is either on it or not, nobody appears twice, and two lists can be compared: "who's invited to both parties?" is an intersection, "who's invited to either?" is a union.

Key ideas

01
Commands: SADD, SREM, SISMEMBER, SMISMEMBER (6.2, several at once), SCARD, SMEMBERS (O(N)), SSCAN, SPOP/SRANDMEMBER (random picks, great for raffles and sampling), SMOVE, and the algebra commands SINTER, SUNION, SDIFF, their ...STORE variants, and SINTERCARD (7.0, returns just the size, with an optional LIMIT).
02
Complexity: SADD/SISMEMBER are O(1). SINTER is O(N×M) in the worst case, where N is the size of the smallest set and M the number of sets, because Redis iterates the smallest set and checks membership in the others. SUNION and SDIFF are O(total elements). On big sets these block the server.
03
Encodings: a set of only integers with up to set-max-intset-entries (512) elements is an intset, a sorted array of integers, very compact. Small sets of strings (Redis 7.2+) use a listpack (up to 128 entries of up to 64 bytes). Otherwise a hash table.
04
SMEMBERS returns everything at once, fine for 100 tags, dangerous for 5M followers. Use SSCAN key cursor COUNT 500 to iterate. Note that SSCAN can return duplicates and gives no ordering, so it's not pagination for UIs; if you need stable ordering, use a sorted set.
05
Typical uses: tags (tag:redis → {post ids}, post:1:tags → {tags}), permissions (user:123:roles), "has this user already voted" checks, deduplicating a batch, and relationships (following:123, followers:456).

Code & diagrams

mutual-friends.redisredis

127.0.0.1:6379> SADD friends:A B C D E
(integer) 4
127.0.0.1:6379> SADD friends:B C D F G
(integer) 4
127.0.0.1:6379> SINTER friends:A friends:B
1) "C"
2) "D"
127.0.0.1:6379> SINTERCARD 2 friends:A friends:B
(integer) 2
127.0.0.1:6379> SDIFF friends:B friends:A        # B's friends A might know
1) "F"
2) "G"
127.0.0.1:6379> SMISMEMBER friends:A B Z
1) (integer) 1
2) (integer) 0
127.0.0.1:6379> SSCAN friends:A 0 COUNT 100
1) "0"                     # cursor 0 = iteration finished
2) 1) "B" 2) "C" 3) "D" 4) "E"

set-algebra.mermaiddiagram

Rendering diagram…

Interview problem

The problem

Mutual friends

Given friends:A = {B,C,D,E} and friends:B = {C,D,F,G}, find mutual friends. Then discuss complexity, very large friend lists, memory, pagination, and SMEMBERS vs SSCAN.

You're given

Typical user: 300 friends
Celebrities: 10M followers
Shown on profile pages

The interviewer follows up

How would you suggest "people you may know"?

When it breaks

SMEMBERS on a set that grew to millions of members

What you see

Hundreds of milliseconds of blocking, huge reply buffers, application timeouts and memory spikes on both Redis and the client.

Fix & prevent

Replace with SSCAN, SRANDMEMBER samples, or SCARD counts; cap set sizes or split them by bucket.

SINTER works on a laptop, then fails in production Redis Cluster

What you see

CROSSSLOT Keys in request don't hash to the same slot errors.

Fix & prevent

Design keys that must be combined with a shared hash tag, or compute set operations in the application or offline.

Explain it without notes

Why does SINTER iterate the smallest set, and what does that mean for complexity?

When would you use a set, and when a sorted set, for followers?

Practice

Implement a simple tag system: tag posts, list posts with both tags "redis" and "java", and list tags on a post.

Pick 3 random winners from a set of entrants so nobody wins twice. Which command removes them, and which doesn't?

Trade-offs

↔
Server-side set algebra is fast and atomic but blocks on big inputs and doesn't work across cluster slots.
↔
Exact sets vs HyperLogLog for unique counting: exact membership and removal against a fixed 12 KB with ~0.81% error (Topic 4.2).

Done when you can

I can use set algebra and know its complexity.
I know why SSCAN replaces SMEMBERS on big sets and what SSCAN guarantees.
I can explain the CROSSSLOT limitation for set operations.

Command Palette