Documentation
¶
Overview ¶
Package hashspacesolver plans how hash ranges move when an empty mount connects, a disk fills, a mount's capacity increases, the cluster balances, a disk claims a share, or a disk must leave. Solve handles one Event. A returned plan is a success: it meets the rules below, and it meets each event's goal as far as a legal cut allows. Planning is greedy. It prefers less data moved, then fewer fragments, and does not search for a globally smallest move.
A mount's capacity is its FreeSpace plus the hash-space bytes already on it, and that capacity stays fixed for the solve. Both hash spaces share it. A range is the half-open interval (StartHash, EndHash]. The file at StartHash belongs to the previous range, whose EndHash is that same hash. StartHash == EndHash is the whole circle except that one hash. Ranges in one space tile the circle once.
Rules ¶
These hold for every successful plan. Breaking one is an error, or the cut is not considered.
Every active disk ends with free space at or above zero, and with at most MAX_RANGES_PER_DISK ranges in each space. A cut that would exceed either limit is illegal. Repair runs before every event except vacate, and again before Solve returns. A repair that cannot lower an over-cap count fails the event.
A frozen disk accepts nothing. A mount marked Vacating starts frozen. Vacate freezes the named disk for the rest of the plan and leaves its capacity out of the room the other disks have. Shedding from a frozen disk is an error.
An EmptyMountConnected, MountCapacityIncreased, or fill cut stays within the receiver's room under REBALANCE_TARGET_PERCENT. A steal is no larger than the source's excess over that target. Vacate, range repair, and freeing a fragment slot may fill a receiver until its free space is zero.
Result.Diff names each moved byte once, from the disk that owned it at the start to the disk that holds it at the end. Adjacent transfers with the same endpoints are joined. Apply accepts the list in any order.
Goals ¶
EmptyMountConnected steals onto the new disk from disks above FILL_LIMIT_PERCENT, stopping when the new disk is at the rebalance target or no legal cut remains. Disks may stay above the fill line. The new disk need not reach the target.
Fill leaves a disk at or under the fill line alone, aside from repair. A disk above the line sheds toward the rebalance target. Stopping with no legal cut is success, so the disk may remain above the target.
Vacate must empty the disk. Empty ranges go to a neighbor and move no bytes. A circle of one empty range goes to any other active disk. Remaining ranges are placed largest first. Not enough capacity on the other disks, or a range that cannot be placed, fails the event.
MountCapacityIncreased steals the same way EmptyMountConnected does, onto the named disk.
Claim moves one step onto the named disk toward its capacity-weighted share of the bytes in use. Each source gives at most CLAIM_STEP_PERCENT of the smaller capacity, and only bytes above its own share. Callers repeat the event until it moves nothing. A frozen disk is left as it is.
Balance moves half the widest fill-percentage gap onto the emptier disk when that gap is at least SPREAD_POINTS. A smaller gap moves nothing. A frozen disk is neither end. The named disk is ignored.
Priorities ¶
A cut is a whole range, a prefix, or a suffix. Landing against a neighbor already on the destination absorbs, so that disk's range count stays the same or drops. Any other cut opens a fragment.
EmptyMountConnected and MountCapacityIncreased try absorbing cuts first, and open a fragment only when no absorbing cut remains. Among the cuts that fit, it prefers a larger cut, then more excess on the source, then a smaller range-count change, then the lower space, range, and cut kind.
Fill prefers a cut that covers the bytes still above the target, and among those the smaller cut. A cut that falls short prefers the larger one. Ties prefer a smaller range-count change, then the lower destination, space, and range. When nothing can be shed, the plan first donates a range off some other disk already at the range cap, and otherwise moves one byte off the fullest other disk, then retries.
Vacate places a range by the first of these that works: a whole move onto the disk that sits on both sides; a whole move with the smallest range-count change, then the most free space, then the lower disk index; a split across the two neighbors; a split onto any disk that has room, preferring a cut that adds no range and then a larger cut.
Claim uses the same cut order as balance, and takes from the source furthest above its share first.
Balance takes cuts from the fuller disk up to that byte budget. Among cuts that fit, it prefers one that adds no range, then a larger cut, then a smaller range-count change, then the lower space, range, and cut kind.
Repair, used by every event, gives away the smallest range another disk can take whole. Ties prefer a smaller range-count change, then the lower disk index. When no whole move fits, it splits that smallest range.
Index ¶
- Constants
- func BalanceBytes(usedHi, capHi, usedLo, capLo int64) int64
- func Contains(start, end, p []byte) bool
- func LinkStarts(ranges []Range)
- func SliceSize(r Range, start, end []byte) (int64, error)
- func Validate(state State) error
- type Event
- type EventKind
- type MountPoint
- type Range
- type Result
- type State
- type Transfer
Constants ¶
const CLAIM_STEP_PERCENT = 10
CLAIM_STEP_PERCENT caps one EventClaim step: bytes moved between a pair of disks stay within this percent of the smaller disk's capacity.
const FILL_LIMIT_PERCENT = 90
FILL_LIMIT_PERCENT is the rebalance line as a percent of a mount's capacity, FreeSpace plus the hash-space bytes on it. Only a disk above this line gives up data. A tight cluster may still sit above it after a best-effort plan; zero FreeSpace is the hard limit.
const MAX_RANGES_PER_DISK = 8
MAX_RANGES_PER_DISK is the maximum number of contiguous ranges a disk may hold in one space. Caps are per disk per space.
const REBALANCE_TARGET_PERCENT = 80
REBALANCE_TARGET_PERCENT is where a rebalance takes a disk above the line, and how full a receiving disk may get. The gap below FILL_LIMIT_PERCENT keeps a just-rebalanced disk from crossing the line on its next write.
const SPREAD_POINTS = 50
SPREAD_POINTS is the fill-percentage gap that starts a balance. A disk at 70% and a disk at 20% differ by 50 and rebalance; a smaller gap does not.
Variables ¶
This section is empty.
Functions ¶
func BalanceBytes ¶
BalanceBytes is the number of bytes to move from the fuller disk onto the emptier one so the emptier gains half their fill-percentage gap. Fill is the fraction used/cap on each disk, and half that gap times the emptier capacity is the byte count. It is zero when the gap is below SPREAD_POINTS.
func Contains ¶
Contains reports whether p lies in the half-open circle interval (start, end]. The endpoint end is included and start is excluded. A start equal to end covers the whole circle, including that point. Callers pass equal-width hashes. An empty p is outside every interval.
func LinkStarts ¶
func LinkStarts(ranges []Range)
LinkStarts sets each range's StartHash to the EndHash of the range before it in hash order. It is for callers that only store end hashes.
func SliceSize ¶
SliceSize returns how much of r's data lies in (start, end]. Both bounds must lie on r, with start no later than end. Data is treated as uniform across r, so the window is measured from r.StartHash: SliceSize(r, r.StartHash, r.EndHash) is r.Size, and a suffix ending at r.EndHash is r.Size minus the prefix before it.
Types ¶
type Event ¶
Event asks the solver to react to the mountpoint StorageID connecting empty, filling, vacating, gaining capacity, or claiming. EventBalance ignores StorageID.
type EventKind ¶
type EventKind int
EventKind selects which disk-lifecycle problem to solve.
const ( // EventEmptyMountConnected uses a newly added disk to take overflow off // other disks. // Steals grow an existing dest range when possible; a new fragment is // opened only while dest is under MAX_RANGES_PER_DISK. EventEmptyMountConnected EventKind = iota + 1 // EventFull sheds from a disk that is above FILL_LIMIT_PERCENT of its // capacity, down to REBALANCE_TARGET_PERCENT. EventFull // EventVacate empties a disk so it can leave the cluster. EventVacate // EventMountCapacityIncreased moves overflow onto a disk that gained // capacity. Bytes move only from disks above FILL_LIMIT_PERCENT, and // only until the destination // is at REBALANCE_TARGET_PERCENT or no legal cut remains. EventMountCapacityIncreased // EventBalance moves half the fill-percentage gap from a fuller disk // onto a disk at least SPREAD_POINTS behind it. EventBalance // EventClaim moves ranges onto a disk that already holds pieces from the // whole circle, one CLAIM_STEP_PERCENT step toward its capacity-weighted // share of all used bytes. Callers repeat it until it moves nothing. EventClaim )
type MountPoint ¶
type MountPoint struct {
FreeSpace int64
StorageID string
// Vacating marks a disk that must not receive ranges. Existing ranges
// stay until EventVacate moves them off.
Vacating bool
// Misplaced marks a disk that holds piece files outside its ranges, such as
// pieces migrated from piece-park. It is not a stuck hash-space range.
Misplaced bool
}
MountPoint is one disk, named by its storage path ID. FreeSpace is the bytes free on the drive now, not counting the hash-space ranges already stored there.
type Range ¶
type Range struct {
StartHash []byte
EndHash []byte
Size int64
StorageID string
Also []string
Problem []string
}
Range is the half-open hash interval (StartHash, EndHash] holding Size bytes on the mountpoint StorageID. StartHash == EndHash is the full circle. Within a hash space, each StartHash must equal the EndHash of the range before it. Also lists other disks that own the same range. Problem lists owners of this range that a stuck move should give up. The circle still has one range per end hash; Also is not a second range.
type Result ¶
Result is the finished assignment plus an order-independent work list.
func Solve ¶
Solve plans one event: empty mount connected, fill, vacate, mount capacity increased, balance, or claim. The finished assignment keeps every active disk's FreeSpace at or above zero and at or under MAX_RANGES_PER_DISK ranges per space. Planning is greedy.
A space may loop: FF00 - AABB includes AAAA, not BBBB. Cuts may come from either hash space.
Result.State is the finished layout. Result.Diff moves each byte at most once, from the disk that owned it at the start to the disk that holds it at the end. The list is order-independent.
type State ¶
type State struct {
MountPoints []MountPoint
HashSpaces [2][]Range
}
State is an assignment of ranges to mountpoints across the hash spaces.
Each HashSpaces entry is an independent circle; a nil entry is an unused space. Index 0 is open-pieces and index 1 is acl-pieces. All spaces draw on the same mount free space.
func Apply ¶
Apply returns a copy of state with all transfers applied. Transfers may be applied in any order when they are disjoint within a space. A negative size is skipped. An empty transfer, or one that covers a whole range, moves that range. Anything else must be a prefix, a suffix, or a strict middle of one range, and Size must match the layout bytes in the interval. Free space and the range cap are not checked.
type Transfer ¶
type Transfer struct {
Space int // HashSpaces index: 0 is open-pieces, 1 is acl-pieces
StartHash []byte
EndHash []byte
From string
To string
Size int64
}
Transfer moves an absolute hash interval from one mountpoint to another within one space. Intervals are half-open (StartHash, EndHash]. From and To are StorageIDs.
Source Files