go.mod

module github.com/fudanchii/ring

go 1.20

require (
	github.com/samber/lo v1.38.1
	github.com/zeebo/xxh3 v1.0.2
	go.mongodb.org/mongo-driver v1.11.6
)

require (
	github.com/klauspost/cpuid/v2 v2.0.9 // indirect
	golang.org/x/exp v0.0.0-20220303212507-bbda1eaf7a17 // indirect
)

ring.go

package main

import (
	"fmt"

	"github.com/samber/lo"
	"github.com/zeebo/xxh3"
	"go.mongodb.org/mongo-driver/bson/primitive"
)

func Shard(key []byte, slots uint) uint {
	return uint(xxh3.Hash(key) % uint64(slots))
}

type Exam struct {
	ID                  primitive.ObjectID
	StudentGroupID      primitive.ObjectID
	StudentGroupShardID uint
	Students            []Student
}

type StudentGroup struct {
	ID       primitive.ObjectID
	Students []Student
}

type Student struct {
	ID primitive.ObjectID
}

type IntermediaryExamGroup struct {
	Class            StudentGroup
	AssignedStudents []Student
}

func generateStudent(n int) []Student {
	students := []Student{}
	for i := 0; i < n; i++ {
		students = append(students, Student{
			ID: primitive.NewObjectID(),
		})
	}
	return students
}

func generateStudentGroup(student int) StudentGroup {
	sg := StudentGroup{}
	sg = StudentGroup{
		ID:       primitive.NewObjectID(),
		Students: generateStudent(student),
	}
	return sg
}

func AssignExam(maxStudents int, groups []IntermediaryExamGroup) []Exam {
	results := []Exam{}
	for _, sg := range groups {
		examSlots := 1
		if len(sg.Class.Students) > maxStudents {
			examSlots = len(sg.Class.Students) / maxStudents
		}
		exams := []Exam{}
		for slot := 0; slot < examSlots; slot++ {
			exams = append(exams, Exam{
				ID:                  primitive.NewObjectID(),
				StudentGroupID:      sg.Class.ID,
				StudentGroupShardID: uint(slot),
				Students:            []Student{},
			})
		}
		for _, student := range sg.AssignedStudents {
			mergedID := append([]byte{}, sg.Class.ID[:]...)
			mergedID = append(mergedID, student.ID[:]...)
			shardLoc := Shard(mergedID, uint(examSlots))
			exams[shardLoc].Students = append(exams[shardLoc].Students, student)
		}
		results = append(results, exams...)
	}
	return results
}

func FindExam(exams []Exam, sg StudentGroup, student Student, shards int) []Exam {
	candidates := lo.Filter(exams, func(ex Exam, _ int) bool {
		mergedID := append([]byte{}, sg.ID[:]...)
		mergedID = append(mergedID, student.ID[:]...)
		shardLoc := Shard(mergedID, uint(len(sg.Students)/shards))
		return ex.StudentGroupID == sg.ID && ex.StudentGroupShardID == shardLoc
	})
	return candidates
}

func examCount(studentCounts, maxStudentsPerShards int) int {
	count := studentCounts / maxStudentsPerShards
	if count < 1 {
		return 1
	}
	return count
}

func main() {
	classA := generateStudentGroup(100)
	classB := generateStudentGroup(50)
	classC := generateStudentGroup(10)
	maxStudentsPerShards := 20
	exams := AssignExam(maxStudentsPerShards, []IntermediaryExamGroup{
		{classA, classA.Students},
		{classB, classB.Students[0:5]},
		{classC, classC.Students},
	})

	totalExamsCreated := examCount(len(classA.Students), maxStudentsPerShards) +
		examCount(len(classB.Students), maxStudentsPerShards) +
		examCount(len(classC.Students), maxStudentsPerShards)
	if len(exams) != totalExamsCreated {
		fmt.Printf("ERROR, exams count != %d, count: %d\n", totalExamsCreated, len(exams))
	} else {
		fmt.Printf("OK, exams count == %d\n", len(exams))
	}

	for _, exam := range exams {
		fmt.Printf("exam: %s\tstudent group: %s\t student count: %d\n", exam.ID, exam.StudentGroupID, len(exam.Students))
	}

	fmt.Printf("Try finding exam for students:\n")

	theClass := classB
	theStudent := theClass.Students[3]
	examCandidates := FindExam(exams, theClass, theStudent, maxStudentsPerShards)
	if len(examCandidates) != 1 {
		fmt.Printf("ERROR, exams count != 1, count: %d\n", len(examCandidates))
		return
	} else {
		fmt.Printf("OK, exams count == %d\n", len(examCandidates))
	}

	if lo.Contains(examCandidates[0].Students, theStudent) {
		fmt.Printf("Exam correctly found!\n")
		fmt.Printf("exam: %s\tstudent: %s\n", examCandidates[0].ID, theStudent.ID)
		for _, st := range examCandidates[0].Students {
			fmt.Printf("%s\n", st.ID)
		}
	} else {
		fmt.Printf("student: %s is not assigned to this exam: %s\n", theStudent.ID, examCandidates[0].ID)
	}
}