SeaweedFS is a distributed storage system for object storage (S3), file systems, Iceberg table buckets, and Lance vector buckets, designed to handle billions of files with O(1) disk access and effortless horizontal scaling.
Go blob-storagecloud-drivedistributed-file-systemdistributed-storageerasure-codingfusehadoop-hdfshdfskuberneteslancelancedbobject-storageposixs3s3-storageseaweedfstiered-file-systemvector-search
package plugin
import (
"sync"
"time"
"github.com/seaweedfs/seaweedfs/weed/pb/plugin_pb"
)
// queuedJob is one scheduled spec parked on a home worker's admin-side queue.
type queuedJob struct {
job *plugin_pb.JobSpec
home string
}
// workerJobQueues holds per-worker FIFOs for one dispatch batch.
// Home assignment is done once up front; run goroutines only pop/steal.
// leftover is the homeless FIFO: replica hostnames with no currently
// registered worker. Orphan grace does not apply here.
type workerJobQueues struct {
mu sync.Mutex
q map[string][]*queuedJob
leftover []*queuedJob
remaining int
missingSince map[string]time.Time
homes map[string]struct{}
}
func newWorkerJobQueues() *workerJobQueues {
return &workerJobQueues{
q: make(map[string][]*queuedJob),
missingSince: make(map[string]time.Time),
homes: make(map[string]struct{}),
}
}
func (qs *workerJobQueues) hasHome(workerID string) bool {
if qs == nil || workerID == "" {
return false
}
_, ok := qs.homes[workerID]
return ok
}
func (qs *workerJobQueues) push(home string, job *plugin_pb.JobSpec) {
if qs == nil || job == nil {
return
}
item := &queuedJob{job: job, home: home}
qs.mu.Lock()
defer qs.mu.Unlock()
qs.pushLocked(item, false)
}
func (qs *workerJobQueues) pushFront(item *queuedJob) {
if qs == nil || item == nil {
return
}
qs.mu.Lock()
defer qs.mu.Unlock()
qs.pushLocked(item, true)
}
func (qs *workerJobQueues) pushLocked(item *queuedJob, front bool) {
qs.remaining++
if item.home == "" {
if front {
qs.leftover = append([]*queuedJob{item}, qs.leftover...)
return
}
qs.leftover = append(qs.leftover, item)
return
}
if front {
qs.q[item.home] = append([]*queuedJob{item}, qs.q[item.home]...)
return
}
qs.q[item.home] = append(qs.q[item.home], item)
}
func (qs *workerJobQueues) isEmpty() bool {
if qs == nil {
return true
}
qs.mu.Lock()
defer qs.mu.Unlock()
return qs.remaining == 0
}
func (qs *workerJobQueues) queueLen(workerID string) int {
if qs == nil {
return 0
}
qs.mu.Lock()
defer qs.mu.Unlock()
return len(qs.q[workerID])
}
func (qs *workerJobQueues) leftoverLen() int {
if qs == nil {
return 0
}
qs.mu.Lock()
defer qs.mu.Unlock()
return len(qs.leftover)
}
func (qs *workerJobQueues) drain() []*queuedJob {
if qs == nil {
return nil
}
qs.mu.Lock()
defer qs.mu.Unlock()
out := make([]*queuedJob, 0, qs.remaining)
for id, qq := range qs.q {
out = append(out, qq...)
qs.q[id] = nil
}
out = append(out, qs.leftover...)
qs.leftover = nil
qs.remaining = 0
return out
}
func popFront(qq []*queuedJob) (*queuedJob, []*queuedJob) {
item := qq[0]
if len(qq) == 1 {
return item, nil
}
return item, qq[1:]
}
// assignJobsToWorkerQueues parks each job on the least-loaded replica-host
// worker. A home exists only if a currently registered worker's -address
// hostname matches a replica host. Otherwise the job is homeless: global
// leftover FIFO, no fake home, no K, no orphan grace. Single-threaded.
func (r *Plugin) assignJobsToWorkerQueues(
jobType string,
jobs []*plugin_pb.JobSpec,
_ schedulerPolicy,
) *workerJobQueues {
qs := newWorkerJobQueues()
executors, err := r.registry.ListExecutors(jobType)
queued := make(map[string]int, len(executors))
for _, job := range jobs {
if job == nil {
continue
}
if err != nil || len(executors) == 0 {
qs.push("", job)
continue
}
pref, _ := partitionByPreferredHost(executors, JobReplicaHosts(job))
if len(pref) == 0 {
// Never registered for that hostname: homeless, not an orphan.
qs.push("", job)
continue
}
for _, e := range pref {
if e != nil && e.WorkerID != "" {
qs.homes[e.WorkerID] = struct{}{}
}
}
sortExecutorsByLoad(pref, func(e *WorkerSession) int {
return r.executorWorkerLoad(e) + queued[e.WorkerID]
})
home := pref[0].WorkerID
qs.push(home, job)
queued[home]++
r.bindQueuedJobWorker(job, home)
}
return qs
}
// takeQueuedJob pops a job for a free worker.
// Home worker (hostname matched a replica / has a home-queue identity):
// 1. own home queue
// 2. steal from another home if len>=K, or orphan past OrphanRehomeGrace
// 3. homeless leftover FIFO
// No-home worker (no matching replica, no home-queue identity):
// 1. homeless leftover FIFO
// 2. only if leftover empty: steal (K / orphan), same rules
func (r *Plugin) takeQueuedJob(
qs *workerJobQueues,
jobType string,
policy schedulerPolicy,
) (item *queuedJob, targetID string) {
if qs == nil {
return nil, ""
}
executors, err := r.registry.ListExecutors(jobType)
if err != nil || len(executors) == 0 {
return nil, ""
}
pin := policy.LocalQueuePin
defer func() {
if item != nil && targetID != "" {
r.bindQueuedJobWorker(item.job, targetID)
}
}()
qs.mu.Lock()
defer qs.mu.Unlock()
if qs.remaining == 0 {
return nil, ""
}
var bestHome *WorkerSession
bestLoad := 0
for _, exec := range executors {
if len(qs.q[exec.WorkerID]) == 0 {
continue
}
if !r.executorHasCapacity(exec, jobType, policy) {
continue
}
load := r.executorWorkerLoad(exec)
if bestHome == nil || load < bestLoad || (load == bestLoad && exec.WorkerID < bestHome.WorkerID) {
bestHome = exec
bestLoad = load
}
}
if bestHome != nil {
id := bestHome.WorkerID
item, qs.q[id] = popFront(qs.q[id])
qs.remaining--
return item, id
}
var thief *WorkerSession
for _, exec := range executors {
if !r.executorHasCapacity(exec, jobType, policy) {
continue
}
if thief == nil || exec.WorkerID < thief.WorkerID {
thief = exec
}
}
if thief == nil {
return nil, ""
}
takeLeftover := func() (*queuedJob, string) {
if len(qs.leftover) == 0 {
return nil, ""
}
item, qs.leftover = popFront(qs.leftover)
qs.remaining--
return item, thief.WorkerID
}
if !qs.hasHome(thief.WorkerID) {
if item, id := takeLeftover(); item != nil {
return item, id
}
}
live := make(map[string]struct{}, len(executors))
for _, exec := range executors {
live[exec.WorkerID] = struct{}{}
delete(qs.missingSince, exec.WorkerID)
}
now := time.Now()
grace := policy.OrphanRehomeGrace
victimID := ""
victimLen := 0
victimOrphan := false
for id, qq := range qs.q {
if len(qq) == 0 {
delete(qs.missingSince, id)
continue
}
_, isLive := live[id]
orphan := !isLive
if isLive {
if pin > 0 && len(qq) < pin {
continue
}
} else {
if _, ok := qs.missingSince[id]; !ok {
qs.missingSince[id] = now
}
if grace > 0 && now.Sub(qs.missingSince[id]) < grace {
continue
}
}
better := victimID == ""
if !better && orphan != victimOrphan {
better = orphan
}
if !better && orphan == victimOrphan {
better = len(qq) > victimLen || (len(qq) == victimLen && id < victimID)
}
if better {
victimID = id
victimLen = len(qq)
victimOrphan = orphan
}
}
if victimID != "" {
item, qs.q[victimID] = popFront(qs.q[victimID])
qs.remaining--
return item, thief.WorkerID
}
return takeLeftover()
}