Design a social news feed

package main
 
import "fmt"
 
func main() {
	type account struct {
		name             string
		followers, posts int // posts per day
	}
	accounts := []account{
		{"typical user", 200, 3},
		{"popular creator", 50_000, 10},
		{"celebrity", 60_000_000, 5},
	}
	for _, a := range accounts {
		writes := a.followers * a.posts
		fmt.Printf("%-16s push: %11d timeline writes/day   pull: %d posts read from it per follower visit\n",
			a.name, writes, min(a.posts, 20))
	}
}

typical user     push:         600 timeline writes/day   pull: 3 posts read from it per follower visit
popular creator  push:      500000 timeline writes/day   pull: 10 posts read from it per follower visit
celebrity        push:   300000000 timeline writes/day   pull: 5 posts read from it per follower visit

feed/
├── go.mod
├── main.go                     HTTP API + demo data
├── main_test.go
├── internal/feed/feed.go       graph, posts, timelines
├── internal/feed/feed_test.go
└── web/index.html              follow, post, scroll

mkdir feed && cd feed && go mod init feed
mkdir -p internal/feed web

module feed
 
go 1.24

// Package feed implements home timelines with hybrid fan-out:
// push for ordinary accounts, pull for celebrities.
package feed
 
import (
	"errors"
	"math"
	"regexp"
	"slices"
	"strings"
	"sync"
	"time"
	"unicode/utf8"
)
 
// Post is one published post. IDs increase over time.
type Post struct {
	ID     int64     `json:"id"`
	Author string    `json:"author"`
	Text   string    `json:"text"`
	At     time.Time `json:"at"`
}
 
// UserInfo describes an account as seen by a viewer.
type UserInfo struct {
	Name      string `json:"name"`
	Followers int    `json:"followers"`
	Celebrity bool   `json:"celebrity"`
	Followed  bool   `json:"followed"` // does the viewer follow this account?
}
 
var (
	ErrInvalidName = errors.New("names are 1 to 20 characters: a-z, 0-9 or _")
	ErrInvalidText = errors.New("posts are 1 to 280 characters")
	ErrSelfFollow  = errors.New("you cannot follow yourself")
)
 
var validName = regexp.MustCompile(`^[a-z0-9_]{1,20}$`)
 
// Store keeps everything in memory behind one lock.
type Store struct {
	mu        sync.RWMutex
	threshold int // followers at which an account stops being pushed
	inboxCap  int // timeline entries kept per user
	now       func() time.Time
	nextID    int64
	users     map[string]bool
	posts     map[int64]Post
	byAuthor  map[string][]int64 // ascending
	followers map[string]map[string]bool
	following map[string]map[string]bool
	celebs    map[string]bool
	inbox     map[string][]int64 // precomputed timelines, ascending, at most inboxCap
	writes    int                // timeline inserts done by fan-out
}
 
// New creates a store. Accounts with at least threshold followers are pulled, not pushed.
func New(threshold, inboxCap int, now func() time.Time) *Store {
	if now == nil {
		now = time.Now
	}
	return &Store{
		threshold: threshold, inboxCap: inboxCap, now: now,
		users: map[string]bool{}, posts: map[int64]Post{}, byAuthor: map[string][]int64{},
		followers: map[string]map[string]bool{}, following: map[string]map[string]bool{},
		celebs: map[string]bool{}, inbox: map[string][]int64{},
	}
}
 
func (s *Store) ensureLocked(name string) {
	if !s.users[name] {
		s.users[name] = true
		s.followers[name] = map[string]bool{}
		s.following[name] = map[string]bool{}
	}
}
 
// AddUser registers an account (posting or following also registers it).
func (s *Store) AddUser(name string) error {
	if !validName.MatchString(name) {
		return ErrInvalidName
	}
	s.mu.Lock()
	defer s.mu.Unlock()
	s.ensureLocked(name)
	return nil
}
 
// Publish stores a post and, unless the author is a celebrity, pushes its ID to every follower.
func (s *Store) Publish(author, text string) (Post, error) {
	if !validName.MatchString(author) {
		return Post{}, ErrInvalidName
	}
	if n := utf8.RuneCountInString(text); n == 0 || n > 280 {
		return Post{}, ErrInvalidText
	}
	s.mu.Lock()
	defer s.mu.Unlock()
	s.ensureLocked(author)
	s.nextID++
	p := Post{ID: s.nextID, Author: author, Text: text, At: s.now().UTC()}
	s.posts[p.ID] = p
	s.byAuthor[author] = append(s.byAuthor[author], p.ID)
	if len(s.followers[author]) >= s.threshold {
		s.celebs[author] = true
	}
	if !s.celebs[author] {
		for f := range s.followers[author] {
			s.inbox[f] = s.capped(append(s.inbox[f], p.ID))
			s.writes++
		}
	}
	return p, nil
}
 
func (s *Store) capped(ids []int64) []int64 {
	if extra := len(ids) - s.inboxCap; extra > 0 {
		return slices.Delete(ids, 0, extra)
	}
	return ids
}
 
// Follow adds an edge and backfills the followee's recent posts (unless they are pulled anyway).
func (s *Store) Follow(follower, followee string) error {
	if !validName.MatchString(follower) || !validName.MatchString(followee) {
		return ErrInvalidName
	}
	if follower == followee {
		return ErrSelfFollow
	}
	s.mu.Lock()
	defer s.mu.Unlock()
	s.ensureLocked(follower)
	s.ensureLocked(followee)
	if s.following[follower][followee] {
		return nil
	}
	s.following[follower][followee] = true
	s.followers[followee][follower] = true
	if !s.celebs[followee] {
		recent := s.byAuthor[followee]
		recent = recent[max(0, len(recent)-s.inboxCap):]
		merged := append(slices.Clone(s.inbox[follower]), recent...)
		slices.Sort(merged)
		s.inbox[follower] = s.capped(slices.Compact(merged))
	}
	return nil
}
 
// Unfollow removes the edge and the followee's posts from the follower's timeline.
func (s *Store) Unfollow(follower, followee string) {
	s.mu.Lock()
	defer s.mu.Unlock()
	if !s.following[follower][followee] {
		return
	}
	delete(s.following[follower], followee)
	delete(s.followers[followee], follower)
	s.inbox[follower] = slices.DeleteFunc(s.inbox[follower], func(id int64) bool { return s.posts[id].Author == followee })
}
 
// Timeline returns up to limit posts with IDs below before (0 means from the newest), newest
// first, plus the cursor for the next page (0 when there is nothing more).
func (s *Store) Timeline(user string, before int64, limit int) ([]Post, int64) {
	s.mu.RLock()
	defer s.mu.RUnlock()
	if before <= 0 {
		before = math.MaxInt64
	}
	var ids []int64
	take := func(list []int64) { // list is ascending: take the newest limit IDs below the cursor
		i, _ := slices.BinarySearch(list, before)
		ids = append(ids, list[max(0, i-limit):i]...)
	}
	take(s.inbox[user])    // pushed: ordinary accounts
	take(s.byAuthor[user]) // your own posts
	for f := range s.following[user] {
		if s.celebs[f] {
			take(s.byAuthor[f]) // pulled: celebrities
		}
	}
	slices.Sort(ids)
	ids = slices.Compact(ids)
	slices.Reverse(ids)
	ids = ids[:min(limit, len(ids))]
 
	posts := make([]Post, len(ids))
	for i, id := range ids {
		posts[i] = s.posts[id]
	}
	var next int64
	if len(posts) == limit {
		next = posts[len(posts)-1].ID
	}
	return posts, next
}
 
// Users lists every account, sorted by name, from the viewer's point of view.
func (s *Store) Users(viewer string) []UserInfo {
	s.mu.RLock()
	defer s.mu.RUnlock()
	out := make([]UserInfo, 0, len(s.users))
	for name := range s.users {
		out = append(out, UserInfo{Name: name, Followers: len(s.followers[name]), Celebrity: s.celebs[name], Followed: s.following[viewer][name]})
	}
	slices.SortFunc(out, func(a, b UserInfo) int { return strings.Compare(a.Name, b.Name) })
	return out
}
 
// Writes reports how many timeline inserts fan-out has done so far.
func (s *Store) Writes() int {
	s.mu.RLock()
	defer s.mu.RUnlock()
	return s.writes
}

package feed
 
import (
	"errors"
	"fmt"
	"slices"
	"strings"
	"testing"
	"time"
)
 
func texts(ps []Post) []string {
	var out []string
	for _, p := range ps {
		out = append(out, p.Text)
	}
	return out
}
 
func newStore(threshold int) *Store {
	return New(threshold, 800, func() time.Time { return time.Unix(0, 0) })
}
 
func TestFanOutOnWrite(t *testing.T) {
	s := newStore(100)
	s.Follow("ann", "bob")
	s.Follow("cat", "bob")
	for _, txt := range []string{"b1", "b2", "b3"} {
		s.Publish("bob", txt)
	}
	s.Publish("ann", "a1")
	posts, next := s.Timeline("ann", 0, 10)
	if got := texts(posts); !slices.Equal(got, []string{"a1", "b3", "b2", "b1"}) {
		t.Errorf("ann's timeline = %v", got)
	}
	if next != 0 {
		t.Errorf("next = %d, want 0 (no more)", next)
	}
	if s.Writes() != 6 {
		t.Errorf("writes = %d, want 6 (3 posts x 2 followers)", s.Writes())
	}
}
 
func TestBackfillAndUnfollow(t *testing.T) {
	s := newStore(100)
	s.Publish("bob", "old post")
	s.Follow("ann", "bob")
	if got := texts(must(s.Timeline("ann", 0, 10))); !slices.Equal(got, []string{"old post"}) {
		t.Errorf("after follow = %v, want the backfilled post", got)
	}
	s.Unfollow("ann", "bob")
	if got := must(s.Timeline("ann", 0, 10)); len(got) != 0 {
		t.Errorf("after unfollow = %v", texts(got))
	}
}
 
func TestCelebritiesArePulled(t *testing.T) {
	s := newStore(2)
	s.Follow("ann", "star")
	s.Follow("bob", "star")
	s.Follow("ann", "bob")
	s.Publish("bob", "b1")
	s.Publish("star", "s1") // 2 followers: becomes a celebrity, nothing pushed
	s.Publish("bob", "b2")
	if s.Writes() != 2 {
		t.Errorf("writes = %d, want 2 (only bob's posts to ann)", s.Writes())
	}
	if got := texts(must(s.Timeline("ann", 0, 10))); !slices.Equal(got, []string{"b2", "s1", "b1"}) {
		t.Errorf("merged timeline = %v", got)
	}
	s.Unfollow("bob", "star") // dropping below the threshold does not flip it back
	s.Publish("star", "s2")
	if s.Writes() != 2 {
		t.Errorf("celebrity status should be sticky; writes = %d", s.Writes())
	}
}
 
func TestCursorPagination(t *testing.T) {
	s := newStore(100)
	s.Follow("ann", "bob")
	for i := 1; i <= 25; i++ {
		s.Publish("bob", fmt.Sprint(i))
	}
	var all []string
	var cursor int64
	pages := 0
	for {
		posts, next := s.Timeline("ann", cursor, 10)
		all = append(all, texts(posts)...)
		pages++
		if next == 0 {
			break
		}
		s.Publish("bob", "new") // new posts arriving must not shift the pages we still read
		cursor = next
	}
	if pages != 3 || len(all) != 25 || all[0] != "25" || all[24] != "1" {
		t.Errorf("%d pages, %d posts: %v", pages, len(all), all)
	}
}
 
func TestInboxCapAndValidation(t *testing.T) {
	s := New(100, 3, nil)
	s.Follow("ann", "bob")
	for i := range 5 {
		s.Publish("bob", fmt.Sprint(i))
	}
	if got := texts(must(s.Timeline("ann", 0, 10))); !slices.Equal(got, []string{"4", "3", "2"}) {
		t.Errorf("capped timeline = %v", got)
	}
	if err := s.Follow("ann", "ann"); !errors.Is(err, ErrSelfFollow) {
		t.Errorf("self follow: %v", err)
	}
	if err := s.Follow("Ann!", "bob"); !errors.Is(err, ErrInvalidName) {
		t.Errorf("bad name: %v", err)
	}
	for _, txt := range []string{"", strings.Repeat("x", 281)} {
		if _, err := s.Publish("ann", txt); !errors.Is(err, ErrInvalidText) {
			t.Errorf("text of %d chars: %v", len(txt), err)
		}
	}
}
 
func must(ps []Post, _ int64) []Post { return ps }

package main
 
import (
	_ "embed"
	"encoding/json"
	"log/slog"
	"net/http"
	"os"
	"strconv"
	"time"
 
	"feed/internal/feed"
)
 
//go:embed web/index.html
var indexHTML []byte
 
func writeJSON(w http.ResponseWriter, code int, v any) {
	w.Header().Set("Content-Type", "application/json")
	w.WriteHeader(code)
	json.NewEncoder(w).Encode(v)
}
 
func newServer(s *feed.Store) http.Handler {
	mux := http.NewServeMux()
	mux.HandleFunc("GET /{$}", func(w http.ResponseWriter, r *http.Request) {
		w.Header().Set("Content-Type", "text/html; charset=utf-8")
		w.Write(indexHTML)
	})
	mux.HandleFunc("GET /api/users", func(w http.ResponseWriter, r *http.Request) {
		writeJSON(w, http.StatusOK, map[string]any{"users": s.Users(r.URL.Query().Get("viewer")), "writes": s.Writes()})
	})
	mux.HandleFunc("GET /api/timeline", func(w http.ResponseWriter, r *http.Request) {
		q := r.URL.Query()
		before, _ := strconv.ParseInt(q.Get("before"), 10, 64)
		limit, err := strconv.Atoi(q.Get("limit"))
		if err != nil || limit < 1 || limit > 100 {
			limit = 20
		}
		posts, next := s.Timeline(q.Get("user"), before, limit)
		writeJSON(w, http.StatusOK, map[string]any{"posts": posts, "next": next})
	})
	mux.HandleFunc("POST /api/posts", func(w http.ResponseWriter, r *http.Request) {
		var in struct{ Author, Text string }
		if json.NewDecoder(http.MaxBytesReader(w, r.Body, 1<<14)).Decode(&in) != nil {
			writeJSON(w, http.StatusBadRequest, map[string]string{"error": "invalid JSON"})
			return
		}
		p, err := s.Publish(in.Author, in.Text)
		if err != nil {
			writeJSON(w, http.StatusBadRequest, map[string]string{"error": err.Error()})
			return
		}
		writeJSON(w, http.StatusCreated, p)
	})
	mux.HandleFunc("POST /api/follow", func(w http.ResponseWriter, r *http.Request) {
		var in struct {
			Follower, Followee string
			Unfollow           bool
		}
		if json.NewDecoder(http.MaxBytesReader(w, r.Body, 1<<12)).Decode(&in) != nil {
			writeJSON(w, http.StatusBadRequest, map[string]string{"error": "invalid JSON"})
			return
		}
		if in.Unfollow {
			s.Unfollow(in.Follower, in.Followee)
		} else if err := s.Follow(in.Follower, in.Followee); err != nil {
			writeJSON(w, http.StatusBadRequest, map[string]string{"error": err.Error()})
			return
		}
		w.WriteHeader(http.StatusNoContent)
	})
	return mux
}
 
// seed creates a small network: "nasa" has enough followers to be a celebrity.
func seed(s *feed.Store) {
	for _, u := range []string{"ann", "bob", "cat", "dan"} {
		s.Follow(u, "nasa")
	}
	s.Follow("ann", "bob")
	s.Follow("ann", "cat")
	s.Follow("bob", "ann")
	s.Publish("bob", "Just finished the consistent hashing lesson.")
	s.Publish("nasa", "A new image of the Pillars of Creation, in infrared.")
	s.Publish("cat", "Go 1.24 iterators are great for paginated APIs.")
	s.Publish("ann", "Hello, feed!")
}
 
func main() {
	s := feed.New(4, 800, nil) // 4 followers makes a celebrity, so the demo shows both paths
	seed(s)
	port := os.Getenv("PORT")
	if port == "" {
		port = "8080"
	}
	slog.Info("listening", "port", port)
	srv := &http.Server{Addr: ":" + port, Handler: newServer(s), ReadHeaderTimeout: 5 * time.Second}
	if err := srv.ListenAndServe(); err != nil {
		slog.Error("server", "err", err)
		os.Exit(1)
	}
}

package main
 
import (
	"encoding/json"
	"net/http/httptest"
	"strings"
	"testing"
 
	"feed/internal/feed"
)
 
func TestAPI(t *testing.T) {
	s := feed.New(4, 800, nil)
	seed(s)
	h := newServer(s)
	call := func(method, url, body string) *httptest.ResponseRecorder {
		rec := httptest.NewRecorder()
		h.ServeHTTP(rec, httptest.NewRequest(method, url, strings.NewReader(body)))
		return rec
	}
 
	var page struct {
		Posts []feed.Post
		Next  int64
	}
	json.NewDecoder(call("GET", "/api/timeline?user=ann", "").Body).Decode(&page)
	var authors []string
	for _, p := range page.Posts {
		authors = append(authors, p.Author)
	}
	if got := strings.Join(authors, ","); got != "ann,cat,nasa,bob" {
		t.Errorf("ann's timeline authors = %s", got)
	}
 
	if rec := call("POST", "/api/follow", `{"follower":"dan","followee":"dan"}`); rec.Code != 400 {
		t.Errorf("self follow: %d", rec.Code)
	}
	if rec := call("POST", "/api/follow", `{"follower":"dan","followee":"cat"}`); rec.Code != 204 {
		t.Errorf("follow: %d", rec.Code)
	}
	if rec := call("POST", "/api/posts", `{"author":"cat","text":"hi dan"}`); rec.Code != 201 {
		t.Errorf("post: %d", rec.Code)
	}
	json.NewDecoder(call("GET", "/api/timeline?user=dan&limit=1", "").Body).Decode(&page)
	if len(page.Posts) != 1 || page.Posts[0].Text != "hi dan" || page.Next == 0 {
		t.Errorf("dan's first page = %+v", page)
	}
	if rec := call("POST", "/api/posts", `{"author":"cat","text":""}`); rec.Code != 400 {
		t.Errorf("empty post: %d", rec.Code)
	}
}

<!doctype html>
<html lang="en">
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>Feed</title>
  <style>
    body { font-family: system-ui, sans-serif; max-width: 860px; margin: 2rem auto; padding: 0 1rem; }
    select, input, button { padding: .45rem .7rem; border-radius: 8px; border: 1px solid #999; font: inherit; background: #fff; }
    button { cursor: pointer; }
    #wrap { display: grid; grid-template-columns: 1fr 220px; gap: 1.5rem; }
    .post { border-bottom: 1px solid #ddd; padding: .7rem 0; } .post b { margin-right: .4rem; } .post small { color: #888; font-family: monospace; }
    .user { display: flex; justify-content: space-between; align-items: center; padding: .3rem 0; font-size: 14px; }
    form { display: flex; gap: .5rem; margin: 1rem 0; } form input { flex: 1; }
    #stats { color: #666; font-size: 13px; }
  </style>
</head>
<body>
  <h1>Feed</h1>
  <p>You are <select id="me"></select> <span id="stats"></span></p>
  <div id="wrap">
    <div>
      <form id="compose"><input id="text" maxlength="280" placeholder="What's happening?"><button>Post</button></form>
      <div id="posts"></div>
      <p><button id="more" hidden>Load older</button></p>
    </div>
    <div><b>People</b><div id="people"></div></div>
  </div>
  <script>
    let next = 0;
    const api = (url, body) => fetch(url, body ? { method: "POST", body: JSON.stringify(body) } : undefined);
    async function loadUsers() {
      const data = await (await api(`/api/users?viewer=${me.value}`)).json();
      if (!me.options.length) for (const u of data.users) me.add(new Option(u.name, u.name));
      stats.textContent = `timeline writes so far: ${data.writes}`;
      people.innerHTML = "";
      for (const u of data.users) {
        if (u.name === me.value) continue;
        const row = document.createElement("div");
        row.className = "user";
        row.textContent = `${u.celebrity ? "★ " : ""}${u.name} (${u.followers})`;
        const b = document.createElement("button");
        b.textContent = u.followed ? "Unfollow" : "Follow";
        b.onclick = async () => {
          await api("/api/follow", { follower: me.value, followee: u.name, unfollow: u.followed });
          refresh();
        };
        row.append(b);
        people.append(row);
      }
    }
    async function loadPage(reset) {
      if (reset) { posts.innerHTML = ""; next = 0; }
      const data = await (await api(`/api/timeline?user=${me.value}&limit=5&before=${next}`)).json();
      for (const p of data.posts) {
        const d = document.createElement("div");
        d.className = "post";
        const who = document.createElement("b"); who.textContent = p.author;
        const id = document.createElement("small"); id.textContent = `#${p.id}`;
        d.append(who, id, document.createElement("br"), document.createTextNode(p.text));
        posts.append(d);
      }
      next = data.next;
      more.hidden = !next;
    }
    async function refresh() { await loadUsers(); await loadPage(true); }
    me.onchange = refresh;
    more.onclick = () => loadPage(false);
    compose.onsubmit = async (e) => {
      e.preventDefault();
      if (!text.value.trim()) return;
      await api("/api/posts", { author: me.value, text: text.value });
      text.value = "";
      refresh();
    };
    loadUsers().then(refresh);
  </script>
</body>
</html>

go test -race ./...
go run .
# open http://localhost:8080
curl -s "localhost:8080/api/timeline?user=ann&limit=2"
# {"next":3,"posts":[{"id":4,"author":"ann",...},{"id":3,"author":"cat",...}]}
curl -s "localhost:8080/api/timeline?user=ann&limit=2&before=3"