Chapter 47: Design Instagram

Redis Data Structure

// Feed cache (Redis List)
Key:   feed:{user_id}
Value: [post_id:1234:ts:1715500000, post_id:1235:ts:1715499800, ...]
TTL:   3 days
Size:  Top 1000 posts (LTRIM)

// Feed metadata (Redis Hash)
Key:   feed_meta:{user_id}
Value: {last_updated: 1715500100, version: 5}
TTL:   3 days

// Celebrity posts (sorted by time)
Key:   celeb_posts:{celeb_user_id}
Type:  Sorted Set (score = timestamp)
Value: post_id
TTL:   7 days
Size:  Top 100 posts

function GenerateFeed(user_id, limit=20, cursor=null):
    // 1. Fetch from cache (fanout-on-write posts)
    cached_posts = redis.LRANGE(f"feed:{user_id}", 0, 999)

    // 2. Get celebrity follows
    following = graph.GetFollowing(user_id)
    celebrities = [u for u in following if u.follower_count >= 1M]

    // 3. Fetch celebrity posts (fanout-on-read)
    celeb_posts = []
    for celeb in celebrities:
        posts = redis.ZREVRANGE(f"celeb_posts:{celeb.id}", 0, 49)
        celeb_posts.extend(posts)

    // 4. Merge and deduplicate
    all_posts = MergePosts(cached_posts, celeb_posts)

    // 5. Rank with ML model
    ranked_posts = ml_service.RankPosts(user_id, all_posts)

    // 6. Paginate
    return Paginate(ranked_posts, limit, cursor)

function FanoutOnWrite(post_id, author_id):
    // Only for non-celebrities
    author = user_service.GetUser(author_id)
    if author.follower_count >= 1M:
        // Store in celebrity index
        redis.ZADD(f"celeb_posts:{author_id}", time.now(), post_id)
        return

    // Fanout to all followers
    followers = graph.GetFollowers(author_id)
    for follower_id in followers:
        redis.LPUSH(f"feed:{follower_id}", post_id)
        redis.LTRIM(f"feed:{follower_id}", 0, 999)
        redis.EXPIRE(f"feed:{follower_id}", 3 * 86400)

function RankPosts(user_id, posts):
    features = []
    for post in posts:
        f = ExtractFeatures(user_id, post)
        features.append(f)

    // Stage 1: Lightweight filter
    scores_stage1 = lightweight_model.Predict(features)
    top_200 = TopK(posts, scores_stage1, k=200)

    // Stage 2: Heavy ranking
    embeddings = embedding_service.GetEmbeddings(user_id, top_200)
    scores_stage2 = heavy_model.Predict(embeddings)

    // Apply diversity penalty
    ranked = DiversifyRanking(top_200, scores_stage2)

    return TopK(ranked, scores_stage2, k=20)

function ExtractFeatures(user_id, post):
    return {
        'recency_hours': (now - post.created_at) / 3600,
        'relationship_score': GetRelationshipScore(user_id, post.author_id),
        'like_count': post.like_count,
        'comment_count': post.comment_count,
        'engagement_velocity': post.likes_last_hour / (post.age_hours + 1),
        'user_liked_similar': UserLikedSimilarContent(user_id, post.hashtags),
        'author_follower_count': post.author.follower_count,
        'is_verified': post.author.is_verified,
        'content_type': post.type  // image, carousel, etc
    }

// Redis Sorted Set (per user)
Key:   stories:{user_id}
Type:  Sorted Set
Score: timestamp (created_at)
Value: story_id
TTL:   24 hours

// Story metadata (Redis Hash)
Key:   story:{story_id}
Value: {
    user_id: 12345,
    media_url: "s3://bucket/story/xyz.jpg",
    cdn_url: "cdn.instagram.com/story/xyz.jpg",
    created_at: 1715500000,
    expires_at: 1715586400,
    view_count: 4523,
    viewers: [viewer_id_1, viewer_id_2, ...]  // capped at 1000
}
TTL:   24 hours

// Story ring status (Redis Hash)
Key:   story_ring:{viewer_id}
Value: {user_id: last_viewed_timestamp}
TTL:   24 hours

function GetStoriesFeed(viewer_id):
    // 1. Get following list
    following = graph.GetFollowing(viewer_id)

    // 2. Check which users have active stories
    active_stories = []
    for user_id in following:
        count = redis.ZCOUNT(f"stories:{user_id}", now-86400, now)
        if count > 0:
            last_viewed = redis.HGET(f"story_ring:{viewer_id}", user_id)
            has_new = CheckNewStories(user_id, last_viewed)
            active_stories.append({
                'user_id': user_id,
                'story_count': count,
                'has_new': has_new,
                'last_story_ts': redis.ZSCORE(f"stories:{user_id}", -1)
            })

    // 3. Sort: new stories first, then by recency, then by relationship
    sorted_stories = SortStories(active_stories, viewer_id)

    return sorted_stories

function GetStoriesForUser(user_id, viewer_id):
    // Fetch all stories for user
    story_ids = redis.ZREVRANGE(f"stories:{user_id}", 0, -1)
    stories = [redis.HGETALL(f"story:{sid}") for sid in story_ids]

    // Mark as viewed
    redis.HSET(f"story_ring:{viewer_id}", user_id, time.now())

    // Increment view count
    for story_id in story_ids:
        redis.HINCRBY(f"story:{story_id}", "view_count", 1)
        redis.LPUSH(f"story:{story_id}:viewers", viewer_id)
        redis.LTRIM(f"story:{story_id}:viewers", 0, 999)

    return stories

function CollaborativeFiltering(user_id):
    // 1. Find similar users (cosine similarity on interaction vectors)
    user_embedding = embedding_service.GetUserEmbedding(user_id)
    similar_users = vector_db.SimilaritySearch(user_embedding, k=1000)

    // 2. Get posts they liked (that user hasn't seen)
    candidate_posts = set()
    for similar_user in similar_users:
        liked_posts = GetRecentLikes(similar_user.id, days=7)
        candidate_posts.update(liked_posts)

    // 3. Filter out posts from users already following
    following = graph.GetFollowing(user_id)
    candidate_posts = [p for p in candidate_posts if p.author_id not in following]

    // 4. Remove posts already seen
    seen_posts = GetSeenPosts(user_id)
    candidate_posts = [p for p in candidate_posts if p.id not in seen_posts]

    return candidate_posts[:10000]  // Top 10K by similarity score

function DetectTrendingPosts():
    // Time-decayed engagement score
    // score = (likes + 2*comments + 3*shares) / (hours_since_post + 2)^1.5

    recent_posts = GetPostsInTimeWindow(hours=24)
    scored_posts = []

    for post in recent_posts:
        age_hours = (now - post.created_at) / 3600
        engagement = post.like_count + 2*post.comment_count + 3*post.share_count
        score = engagement / pow(age_hours + 2, 1.5)

        scored_posts.append({
            'post_id': post.id,
            'score': score,
            'velocity': engagement / (age_hours + 1)  // interactions per hour
        })

    // Store in Redis sorted set
    for item in scored_posts:
        redis.ZADD("trending_posts", item.score, item.post_id)

    redis.EXPIRE("trending_posts", 3600)  // Refresh every hour

    return redis.ZREVRANGE("trending_posts", 0, 999)

CREATE TABLE users (
    user_id BIGSERIAL PRIMARY KEY,
    username VARCHAR(30) UNIQUE NOT NULL,
    email VARCHAR(255) UNIQUE NOT NULL,
    password_hash VARCHAR(255) NOT NULL,
    full_name VARCHAR(100),
    bio TEXT,
    profile_pic_url VARCHAR(500),
    follower_count INT DEFAULT 0,
    following_count INT DEFAULT 0,
    post_count INT DEFAULT 0,
    is_verified BOOLEAN DEFAULT FALSE,
    is_private BOOLEAN DEFAULT FALSE,
    created_at TIMESTAMP DEFAULT NOW(),
    updated_at TIMESTAMP DEFAULT NOW()
);

CREATE INDEX idx_users_username ON users(username);
CREATE INDEX idx_users_email ON users(email);

CREATE TABLE posts (
    post_id UUID PRIMARY KEY,
    user_id BIGINT,
    caption TEXT,
    image_urls LIST,  // [original, large, medium, small, thumb]
    hashtags SET,
    mentions SET,
    location TEXT,
    like_count COUNTER,
    comment_count COUNTER,
    share_count COUNTER,
    save_count COUNTER,
    created_at TIMESTAMP,
    updated_at TIMESTAMP
) WITH CLUSTERING ORDER BY (created_at DESC);

// User's posts (timeline)
CREATE TABLE posts_by_user (
    user_id BIGINT,
    post_id UUID,
    created_at TIMESTAMP,
    PRIMARY KEY (user_id, created_at, post_id)
) WITH CLUSTERING ORDER BY (created_at DESC);

// Hashtag index
CREATE TABLE posts_by_hashtag (
    hashtag TEXT,
    post_id UUID,
    created_at TIMESTAMP,
    PRIMARY KEY (hashtag, created_at, post_id)
) WITH CLUSTERING ORDER BY (created_at DESC);

// Adjacency list representation (optimized for reads)

// Followers: who follows user X
CREATE TABLE followers (
    user_id BIGINT,
    follower_id BIGINT,
    created_at TIMESTAMP,
    PRIMARY KEY (user_id, follower_id)
);

// Following: who does user X follow
CREATE TABLE following (
    user_id BIGINT,
    following_id BIGINT,
    created_at TIMESTAMP,
    PRIMARY KEY (user_id, following_id)
);

// Both tables denormalized for fast lookups
// Trade-off: 2× storage, but O(1) lookups in both directions

CREATE INDEX idx_followers_follower ON followers(follower_id);
CREATE INDEX idx_following_following ON following(following_id);

CREATE TABLE likes (
    post_id UUID,
    user_id BIGINT,
    created_at TIMESTAMP,
    PRIMARY KEY (post_id, user_id)
);

CREATE TABLE likes_by_user (
    user_id BIGINT,
    post_id UUID,
    created_at TIMESTAMP,
    PRIMARY KEY (user_id, created_at, post_id)
) WITH CLUSTERING ORDER BY (created_at DESC);