《互联网产品的服务端架构·交易、增长与平台化》7.1 邀请关系与归因

// file: internal/growth/invite.go
// tier: L1
// verify: go test ./internal/growth/

// Package growth 提供邀请归因、奖励发放与增长实验度量的纯函数。
package growth

import (
	"errors"
	"fmt"
)

var (
	// ErrInvalidInvite 表示邀请记录或邀请链存在空字段或非法值。
	ErrInvalidInvite = errors.New("growth: invalid invite")
	// ErrAlreadyBound 表示被邀请人已经绑定过邀请人。
	ErrAlreadyBound = errors.New("growth: invitee already bound")
	// ErrCycle 表示邀请关系已经或将要形成环。
	ErrCycle = errors.New("growth: invite cycle")
	// ErrDepthExceeded 表示归因深度超过调用方允许的上限。
	ErrDepthExceeded = errors.New("growth: attribution depth exceeded")
)

// Invite 是一条邀请绑定记录。Code 是邀请码，At 是绑定发生的 Unix 秒。
// InviterID 是发出邀请的人，InviteeID 是接受邀请的人，方向不能反过来。
type Invite struct {
	Code      string
	InviterID string
	InviteeID string
	At        int64
}

// Bind 把 inv 写入 bound：bound[InviteeID] = InviterID。
//
// 邀请关系是单向的：被邀请人只能绑定一次，绑定后不会因为邀请人后来
// 又绑定了别人而改变。写入前会沿着已有链向上检查，如果邀请人已经
// 在被邀请人的下游，这次绑定就会形成环，直接拒绝。
func Bind(bound map[string]string, inv Invite) error {
	if bound == nil {
		return fmt.Errorf("%w: nil bound map", ErrInvalidInvite)
	}
	if inv.Code == "" || inv.InviterID == "" || inv.InviteeID == "" {
		return fmt.Errorf("%w: empty field", ErrInvalidInvite)
	}
	if inv.InviterID == inv.InviteeID {
		return fmt.Errorf("%w: self invite %s", ErrInvalidInvite, inv.InviterID)
	}
	if _, ok := bound[inv.InviteeID]; ok {
		return fmt.Errorf("%w: %s", ErrAlreadyBound, inv.InviteeID)
	}
	// 从邀请人向上走，如果遇到被邀请人，说明被邀请人已经在邀请人的
	// 上游，再绑定就会首尾相接。
	cur := inv.InviterID
	seen := map[string]bool{}
	for {
		if cur == inv.InviteeID {
			return fmt.Errorf("%w: %s -> %s", ErrCycle, inv.InviteeID, inv.InviterID)
		}
		if seen[cur] {
			return fmt.Errorf("%w: broken chain at %s", ErrCycle, cur)
		}
		seen[cur] = true
		next, ok := bound[cur]
		if !ok {
			break
		}
		cur = next
	}
	bound[inv.InviteeID] = inv.InviterID
	return nil
}

// Attribution 沿 chain 从 userID 向上找到最顶层的邀请人。
// chain[user] = inviter，通常就是 Bind 写入的同一张表。
//
// 用户没有邀请记录时返回空字符串和 nil，表示自然流量。每向上一步
// 计一层，超过 maxDepth 返回 ErrDepthExceeded；链中出现环返回
// ErrCycle。函数只读 chain，不会修改入参。
func Attribution(chain map[string]string, userID string, maxDepth int) (string, error) {
	if userID == "" {
		return "", fmt.Errorf("%w: empty user id", ErrInvalidInvite)
	}
	if maxDepth < 0 {
		return "", fmt.Errorf("%w: max depth %d", ErrInvalidInvite, maxDepth)
	}
	cur, top, depth := userID, "", 0
	seen := map[string]bool{userID: true}
	for {
		parent, ok := chain[cur]
		if !ok {
			return top, nil
		}
		if parent == "" {
			return "", fmt.Errorf("%w: empty parent of %s", ErrInvalidInvite, cur)
		}
		if seen[parent] {
			return "", fmt.Errorf("%w: revisit %s", ErrCycle, parent)
		}
		depth++
		if depth > maxDepth {
			return "", fmt.Errorf("%w: %s depth %d > %d", ErrDepthExceeded, userID, depth, maxDepth)
		}
		seen[parent] = true
		top = parent
		cur = parent
	}
}

// file: internal/growth/invite_test.go
// tier: L1
// verify: go test ./internal/growth/

package growth

import (
	"errors"
	"testing"
)

func TestBindWritesOneWayRelation(t *testing.T) {
	bound := map[string]string{}
	if err := Bind(bound, Invite{Code: "A1", InviterID: "u1", InviteeID: "u2", At: 100}); err != nil {
		t.Fatalf("Bind u1->u2 = %v, want nil", err)
	}
	if err := Bind(bound, Invite{Code: "A2", InviterID: "u2", InviteeID: "u3", At: 200}); err != nil {
		t.Fatalf("Bind u2->u3 = %v, want nil", err)
	}
	if got := bound["u2"]; got != "u1" {
		t.Fatalf("bound[u2] = %q, want u1", got)
	}
	if got := bound["u3"]; got != "u2" {
		t.Fatalf("bound[u3] = %q, want u2", got)
	}
	top, err := Attribution(bound, "u3", 5)
	if err != nil {
		t.Fatalf("Attribution u3 = %v, want nil", err)
	}
	if top != "u1" {
		t.Fatalf("Attribution u3 = %q, want u1", top)
	}
	top, err = Attribution(bound, "u1", 5)
	if err != nil || top != "" {
		t.Fatalf("Attribution u1 = %q, %v; want empty, nil", top, err)
	}
}

func TestAttributionMissingChain(t *testing.T) {
	for name, chain := range map[string]map[string]string{
		"nil":   nil,
		"empty": {},
	} {
		t.Run(name, func(t *testing.T) {
			top, err := Attribution(chain, "nobody", 3)
			if err != nil || top != "" {
				t.Fatalf("Attribution = %q, %v; want empty, nil", top, err)
			}
		})
	}
}

func TestAttributionDepthLimit(t *testing.T) {
	chain := map[string]string{"u4": "u3", "u3": "u2", "u2": "u1"}
	top, err := Attribution(chain, "u4", 3)
	if err != nil || top != "u1" {
		t.Fatalf("Attribution depth 3 = %q, %v; want u1, nil", top, err)
	}
	if _, err := Attribution(chain, "u4", 2); !errors.Is(err, ErrDepthExceeded) {
		t.Fatalf("Attribution depth 2 = %v, want ErrDepthExceeded", err)
	}
	if _, err := Attribution(chain, "u2", 0); !errors.Is(err, ErrDepthExceeded) {
		t.Fatalf("Attribution depth 0 = %v, want ErrDepthExceeded", err)
	}
}

func TestAttributionDetectsCycle(t *testing.T) {
	chain := map[string]string{"a": "b", "b": "a"}
	if _, err := Attribution(chain, "a", 10); !errors.Is(err, ErrCycle) {
		t.Fatalf("Attribution cycle = %v, want ErrCycle", err)
	}
}

func TestBindRejectsInvalidInput(t *testing.T) {
	cases := []struct {
		name string
		inv  Invite
		want error
	}{
		{"empty-code", Invite{InviterID: "u1", InviteeID: "u2"}, ErrInvalidInvite},
		{"empty-inviter", Invite{Code: "c", InviteeID: "u2"}, ErrInvalidInvite},
		{"empty-invitee", Invite{Code: "c", InviterID: "u1"}, ErrInvalidInvite},
		{"self-invite", Invite{Code: "c", InviterID: "u1", InviteeID: "u1"}, ErrInvalidInvite},
	}
	for _, c := range cases {
		t.Run(c.name, func(t *testing.T) {
			if err := Bind(map[string]string{}, c.inv); !errors.Is(err, c.want) {
				t.Fatalf("Bind = %v, want %v", err, c.want)
			}
		})
	}
	if err := Bind(nil, Invite{Code: "c", InviterID: "u1", InviteeID: "u2"}); !errors.Is(err, ErrInvalidInvite) {
		t.Fatalf("Bind nil map = %v, want ErrInvalidInvite", err)
	}
}

func TestBindRejectsAlreadyBound(t *testing.T) {
	bound := map[string]string{"u2": "u1"}
	err := Bind(bound, Invite{Code: "c", InviterID: "u9", InviteeID: "u2"})
	if !errors.Is(err, ErrAlreadyBound) {
		t.Fatalf("Bind = %v, want ErrAlreadyBound", err)
	}
	if got := bound["u2"]; got != "u1" {
		t.Fatalf("bound[u2] = %q, want original u1", got)
	}
}

func TestBindRejectsCycle(t *testing.T) {
	bound := map[string]string{"u2": "u1"}
	err := Bind(bound, Invite{Code: "c", InviterID: "u2", InviteeID: "u1"})
	if !errors.Is(err, ErrCycle) {
		t.Fatalf("direct cycle = %v, want ErrCycle", err)
	}
	if _, ok := bound["u1"]; ok {
		t.Fatalf("failed Bind wrote bound[u1] = %q", bound["u1"])
	}

	bound = map[string]string{"u2": "u1", "u3": "u2"}
	err = Bind(bound, Invite{Code: "c", InviterID: "u3", InviteeID: "u1"})
	if !errors.Is(err, ErrCycle) {
		t.Fatalf("indirect cycle = %v, want ErrCycle", err)
	}
	if _, ok := bound["u1"]; ok {
		t.Fatalf("failed Bind wrote bound[u1] = %q", bound["u1"])
	}
}

cd .local/checks/webapp-lab && go test ./internal/growth/ -run 'TestBind|TestAttribution' -count=1 -v

=== RUN   TestBindWritesOneWayRelation
--- PASS: TestBindWritesOneWayRelation (0.00s)
=== RUN   TestAttributionMissingChain
=== RUN   TestAttributionMissingChain/nil
=== RUN   TestAttributionMissingChain/empty
--- PASS: TestAttributionMissingChain (0.00s)
    --- PASS: TestAttributionMissingChain/nil (0.00s)
    --- PASS: TestAttributionMissingChain/empty (0.00s)
=== RUN   TestAttributionDepthLimit
--- PASS: TestAttributionDepthLimit (0.00s)
=== RUN   TestAttributionDetectsCycle
--- PASS: TestAttributionDetectsCycle (0.00s)
=== RUN   TestBindRejectsInvalidInput
=== RUN   TestBindRejectsInvalidInput/empty-code
=== RUN   TestBindRejectsInvalidInput/empty-inviter
=== RUN   TestBindRejectsInvalidInput/empty-invitee
=== RUN   TestBindRejectsInvalidInput/self-invite
--- PASS: TestBindRejectsInvalidInput (0.00s)
    --- PASS: TestBindRejectsInvalidInput/empty-code (0.00s)
    --- PASS: TestBindRejectsInvalidInput/empty-inviter (0.00s)
    --- PASS: TestBindRejectsInvalidInput/empty-invitee (0.00s)
    --- PASS: TestBindRejectsInvalidInput/self-invite (0.00s)
=== RUN   TestBindRejectsAlreadyBound
--- PASS: TestBindRejectsAlreadyBound (0.00s)
=== RUN   TestBindRejectsCycle
--- PASS: TestBindRejectsCycle (0.00s)
PASS
ok  	webapp/internal/growth	0.257s