123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126 |
- // Copyright (C) 2020 The Syncthing Authors.
- //
- // This Source Code Form is subject to the terms of the Mozilla Public
- // License, v. 2.0. If a copy of the MPL was not distributed with this file,
- // You can obtain one at https://mozilla.org/MPL/2.0/.
- package model
- import (
- "github.com/syncthing/syncthing/lib/config"
- "github.com/syncthing/syncthing/lib/protocol"
- "github.com/syncthing/syncthing/lib/rand"
- "sort"
- )
- type blockPullReorderer interface {
- Reorder(blocks []protocol.BlockInfo) []protocol.BlockInfo
- }
- func newBlockPullReorderer(order config.BlockPullOrder, id protocol.DeviceID, otherDevices []protocol.DeviceID) blockPullReorderer {
- switch order {
- case config.BlockPullOrderRandom:
- return randomOrderBlockPullReorderer{}
- case config.BlockPullOrderInOrder:
- return inOrderBlockPullReorderer{}
- case config.BlockPullOrderStandard:
- fallthrough
- default:
- return newStandardBlockPullReorderer(id, otherDevices)
- }
- }
- type inOrderBlockPullReorderer struct{}
- func (inOrderBlockPullReorderer) Reorder(blocks []protocol.BlockInfo) []protocol.BlockInfo {
- return blocks
- }
- type randomOrderBlockPullReorderer struct{}
- func (randomOrderBlockPullReorderer) Reorder(blocks []protocol.BlockInfo) []protocol.BlockInfo {
- rand.Shuffle(blocks)
- return blocks
- }
- type standardBlockPullReorderer struct {
- myIndex int
- count int
- shuffle func(interface{}) // Used for test
- }
- func newStandardBlockPullReorderer(id protocol.DeviceID, otherDevices []protocol.DeviceID) *standardBlockPullReorderer {
- allDevices := append(otherDevices, id)
- sort.Slice(allDevices, func(i, j int) bool {
- return allDevices[i].Compare(allDevices[j]) == -1
- })
- // Find our index
- myIndex := -1
- for i, dev := range allDevices {
- if dev == id {
- myIndex = i
- break
- }
- }
- if myIndex < 0 {
- panic("bug: could not find my own index")
- }
- return &standardBlockPullReorderer{
- myIndex: myIndex,
- count: len(allDevices),
- shuffle: rand.Shuffle,
- }
- }
- func (p *standardBlockPullReorderer) Reorder(blocks []protocol.BlockInfo) []protocol.BlockInfo {
- if len(blocks) == 0 {
- return blocks
- }
- // Split the blocks into len(allDevices) chunks. Chunk count might be less than device count, if there are more
- // devices than blocks.
- chunks := chunk(blocks, p.count)
- newBlocks := make([]protocol.BlockInfo, 0, len(blocks))
- // First add our own chunk. We might fall off the list if there are more devices than chunks...
- if p.myIndex < len(chunks) {
- newBlocks = append(newBlocks, chunks[p.myIndex]...)
- }
- // The rest of the chunks we fetch in a random order in whole chunks.
- // Generate chunk index slice and shuffle it
- indexes := make([]int, 0, len(chunks)-1)
- for i := 0; i < len(chunks); i++ {
- if i != p.myIndex {
- indexes = append(indexes, i)
- }
- }
- p.shuffle(indexes)
- // Append the chunks in the order of the index slices.
- for _, idx := range indexes {
- newBlocks = append(newBlocks, chunks[idx]...)
- }
- return newBlocks
- }
- func chunk(blocks []protocol.BlockInfo, partCount int) [][]protocol.BlockInfo {
- if partCount == 0 {
- return [][]protocol.BlockInfo{blocks}
- }
- count := len(blocks)
- chunkSize := (count + partCount - 1) / partCount
- parts := make([][]protocol.BlockInfo, 0, partCount)
- for i := 0; i < count; i += chunkSize {
- end := i + chunkSize
- if end > count {
- end = count
- }
- parts = append(parts, blocks[i:end])
- }
- return parts
- }
|