《互联网产品的服务端架构·内容、社交与实时互动》5.3 关系链的存储与查询

SELECT friend_id, COUNT(*)
FROM relation
WHERE from_id IN ('u1', 'u2', ..., 'u10000')
  AND kind = 'friend'
GROUP BY friend_id
ORDER BY COUNT(*) DESC
LIMIT 20;

// file: internal/social/graph.go
// tier: L1
// verify: go test ./internal/social/

package social

import "sort"

// Graph 是按发起方索引的关系图。Out[id] 通常只放 From == id 的边，
// 但查询函数会遍历所有分桶，重复边和分桶错误都不会改变结果。
type Graph struct {
	Out map[string][]Edge
}

// Followers 返回关注 id 的用户，按 ID 升序去重。
// 这里只统计 follow 边；friend 是另一种关系，不自动折算成关注。
func Followers(g Graph, id string) []string {
	seen := make(map[string]struct{})
	for _, edges := range g.Out {
		for _, e := range edges {
			if e.From != "" && e.From != e.To && e.To == id && e.Kind == Follow {
				seen[e.From] = struct{}{}
			}
		}
	}
	return sortedIDs(seen)
}

// Following 返回 id 关注的用户，按 ID 升序去重。
func Following(g Graph, id string) []string {
	seen := make(map[string]struct{})
	for _, edges := range g.Out {
		for _, e := range edges {
			if e.From == id && e.To != "" && e.From != e.To && e.Kind == Follow {
				seen[e.To] = struct{}{}
			}
		}
	}
	return sortedIDs(seen)
}

// Common 返回 a 与 b 的共同好友，按 ID 升序去重。
// 好友必须双向：共同好友 X 要同时与 a、b 各有两条方向的 friend 边。
func Common(g Graph, a, b string) []string {
	if a == "" || b == "" || a == b {
		return []string{}
	}
	fa := friendSet(g, a)
	fb := friendSet(g, b)
	seen := make(map[string]struct{})
	for id := range fa {
		if _, ok := fb[id]; ok {
			seen[id] = struct{}{}
		}
	}
	return sortedIDs(seen)
}

// friendSet 收集与 id 互为好友的节点。先分别收集出边和入边，
// 再取交集，避免把单条 friend 边误判成好友。
func friendSet(g Graph, id string) map[string]struct{} {
	out := make(map[string]struct{})
	in := make(map[string]struct{})
	for _, edges := range g.Out {
		for _, e := range edges {
			if e.Kind != Friend {
				continue
			}
			if e.From == id && e.To != "" && e.From != e.To {
				out[e.To] = struct{}{}
			}
			if e.To == id && e.From != "" && e.From != e.To {
				in[e.From] = struct{}{}
			}
		}
	}
	both := make(map[string]struct{})
	for other := range out {
		if _, ok := in[other]; ok {
			both[other] = struct{}{}
		}
	}
	return both
}

func sortedIDs(set map[string]struct{}) []string {
	ids := make([]string, 0, len(set))
	for id := range set {
		ids = append(ids, id)
	}
	sort.Strings(ids)
	return ids
}

// file: internal/social/graph_test.go
// tier: L1
// verify: go test ./internal/social/

package social

import (
	"reflect"
	"testing"
)

func TestFollowersDedupSort(t *testing.T) {
	g := Graph{Out: map[string][]Edge{
		"u3": {{From: "u3", To: "u1", Kind: Follow}},
		"u2": {{From: "u2", To: "u1", Kind: Follow}, {From: "u2", To: "u1", Kind: Follow}},
		"u1": {{From: "u1", To: "u1", Kind: Follow}},
	}}
	got := Followers(g, "u1")
	want := []string{"u2", "u3"}
	if !reflect.DeepEqual(got, want) {
		t.Fatalf("Followers = %v, want %v", got, want)
	}
}

func TestFollowingDedupSort(t *testing.T) {
	g := Graph{Out: map[string][]Edge{
		"u1": {
			{From: "u1", To: "u3", Kind: Follow},
			{From: "u1", To: "u2", Kind: Follow},
			{From: "u1", To: "u3", Kind: Follow},
			{From: "u1", To: "u2", Kind: Friend},
		},
	}}
	got := Following(g, "u1")
	want := []string{"u2", "u3"}
	if !reflect.DeepEqual(got, want) {
		t.Fatalf("Following = %v, want %v", got, want)
	}
}

func TestCommonNeedsMutualFriendship(t *testing.T) {
	g := Graph{Out: map[string][]Edge{
		"u1": {
			{From: "u1", To: "u3", Kind: Friend},
			{From: "u1", To: "u4", Kind: Friend},
			{From: "u1", To: "u5", Kind: Follow},
		},
		"u2": {
			{From: "u2", To: "u3", Kind: Friend},
			{From: "u2", To: "u4", Kind: Friend},
			{From: "u2", To: "u5", Kind: Follow},
		},
		"u3": {
			{From: "u3", To: "u1", Kind: Friend},
			{From: "u3", To: "u2", Kind: Friend},
		},
		"u4": {
			{From: "u4", To: "u1", Kind: Friend},
		},
		"u5": {
			{From: "u5", To: "u1", Kind: Friend},
			{From: "u5", To: "u2", Kind: Friend},
		},
	}}
	got := Common(g, "u1", "u2")
	want := []string{"u3"}
	if !reflect.DeepEqual(got, want) {
		t.Fatalf("Common = %v, want %v", got, want)
	}
}

func TestCommonDuplicateEdgesDoNotChangeResult(t *testing.T) {
	g := Graph{Out: map[string][]Edge{
		"u1": {
			{From: "u1", To: "u3", Kind: Friend},
			{From: "u1", To: "u3", Kind: Friend},
		},
		"u2": {{From: "u2", To: "u3", Kind: Friend}},
		"u3": {
			{From: "u3", To: "u1", Kind: Friend},
			{From: "u3", To: "u2", Kind: Friend},
		},
	}}
	got := Common(g, "u1", "u2")
	want := []string{"u3"}
	if !reflect.DeepEqual(got, want) {
		t.Fatalf("Common with duplicates = %v, want %v", got, want)
	}
}

func TestEmptyGraphReturnsEmptySlices(t *testing.T) {
	for name, got := range map[string][]string{
		"followers": Followers(Graph{}, "u1"),
		"following": Following(Graph{}, "u1"),
		"common":    Common(Graph{}, "u1", "u2"),
	} {
		if got == nil {
			t.Fatalf("%s returned nil", name)
		}
		if len(got) != 0 {
			t.Fatalf("%s = %v, want empty", name, got)
		}
	}
}

cd .local/checks/webapp-lab && go test ./internal/social/ -run 'TestFollowers|TestFollowing|TestCommon|TestEmptyGraph' -count=1 -v

=== RUN   TestFollowersDedupSort
--- PASS: TestFollowersDedupSort (0.00s)
=== RUN   TestFollowingDedupSort
--- PASS: TestFollowingDedupSort (0.00s)
=== RUN   TestCommonNeedsMutualFriendship
--- PASS: TestCommonNeedsMutualFriendship (0.00s)
=== RUN   TestCommonDuplicateEdgesDoNotChangeResult
--- PASS: TestCommonDuplicateEdgesDoNotChangeResult (0.00s)
=== RUN   TestEmptyGraphReturnsEmptySlices
--- PASS: TestEmptyGraphReturnsEmptySlices (0.00s)
PASS
ok  	webapp/internal/social	0.278s