Documentation
¶
Overview ¶
Package ec erasure-codes flushed-part backend objects for shared-nothing durability at sub-replica storage cost: an object split into Data shards plus Parity parity shards (systematic Reed-Solomon) survives the loss of any Parity shards while storing only (Data+Parity)/Data of the logical bytes — e.g. {4,2} tolerates 2 losses at 1.5x versus 3x for RF=3 full copies. Each of Data+Parity cluster nodes holds one shard slot; any Data shards reconstruct the object.
This package is the codec and framing layer only (issue 108, phase 2 milestone 1): shard encode/reconstruct/join over github.com/klauspost/reedsolomon (kept behind this package's small surface so the codec is swappable), plus the per-part Meta sidecar that records the scheme, each object's size, and per-shard checksums for fetch-time verification. Placement, the reconstructing read path, and repair live in later milestones.
Index ¶
- Constants
- Variables
- func ChecksumShard(shard []byte) uint64
- func Encode(s Scheme, data []byte) ([][]byte, error)
- func Join(s Scheme, shards [][]byte, size int64) ([]byte, error)
- func MetaKey(partPrefix string) string
- func Reconstruct(s Scheme, shards [][]byte) error
- func ShardKey(partPrefix string, slot int, object string) string
- func ShardSlotOf(key string) (slot int, ok bool)
- func ShardSlotPrefix(partPrefix string, slot int) string
- func ShouldShard(size int64) bool
- func SplitKey(key string) (partPrefix, object string, ok bool)
- type Meta
- type ObjectMeta
- type PeerFetch
- type Reader
- type Scheme
Constants ¶
const FullCopyFloor = 4 << 10
FullCopyFloor is the object size (bytes) below which an object in an EC part stays full-copy on every owner instead of being sharded: k+m shards of a tiny object cost more (framing, per-object round-trips) than the bytes they save.
const MetaObject = "ecmeta"
MetaObject is the object name of the per-part Meta sidecar, relative to the part prefix.
Variables ¶
var ErrCorrupt = errors.New("ec: corrupt meta")
ErrCorrupt reports a Meta payload that fails structural or checksum validation.
Functions ¶
func ChecksumShard ¶
ChecksumShard returns the xxh3 checksum of one shard as stored in ObjectMeta.Checksums.
func Encode ¶
Encode splits data into scheme.Data equal-size shards (zero-padded systematically: the original bytes are the concatenation of the data shards, truncated to len(data)) and computes scheme.Parity parity shards. The returned slice has scheme.Shards() entries. Empty data is valid (all shards empty).
func Join ¶
Join reassembles the original object of size bytes from a complete shard set (all data slots present — run Reconstruct first if any are missing).
func Reconstruct ¶
Reconstruct fills the missing (nil) entries of shards in place. At least scheme.Data entries must be present; shards must have exactly scheme.Shards() entries in slot order.
func ShardKey ¶
ShardKey returns the backend key under which shard slot holds object (a part-relative name like "c/0") for the part at partPrefix.
func ShardSlotOf ¶
ShardSlotOf reports whether key is an EC shard object and, if so, its slot index. It is how the mirror path filters a peer's listing down to the shards a node should hold (its own slot), leaving every non-shard object — full copies, the ecmeta sidecar, the bucket index — kept (ok=false).
func ShardSlotPrefix ¶
ShardSlotPrefix is the backend key prefix under which shard slot's objects live for the part at partPrefix — a List of it enumerates exactly that slot's shards (used to confirm a peer holds its slot before the owner prunes its staged copy).
func ShouldShard ¶
ShouldShard reports whether an object of the given size is worth erasure-coding: objects under FullCopyFloor stay full-copy on every owner (see the layout comment).
func SplitKey ¶
SplitKey splits a backend key into its part prefix and part-relative object name, keyed off the engine's fixed-width numeric part-sequence segment ("{enginePrefix}/{seq:010d}/{object}"). It reports ok=false for keys not under a part (e.g. the engine's bucket index or identity objects).
Types ¶
type Meta ¶
type Meta struct {
Scheme Scheme
Objects []ObjectMeta
}
Meta is the per-part erasure-coding sidecar: the scheme and every coded object. It is written (like a manifest) after the part's shards, and read before any reconstruction.
func Convert ¶
func Convert(ctx context.Context, be backend.Backend, partPrefix string, scheme Scheme) (*Meta, error)
Convert erasure-codes a full-copy part in be to scheme, in place: it shards every part object at or above FullCopyFloor, writes the Meta sidecar, and deletes the full copies it replaced. It is the compaction owner's cold-part re-encode step (issue 108 phase 2). Objects below the floor and the part's other non-object keys are left untouched; the returned Meta lists exactly the sharded objects.
All Data+Parity shards are written into be — the owner's backend is the staging area from which the shards are distributed to peers and pruned to the owner's own slot (a later milestone). Reads work throughout via Reader, which serves a surviving full copy or reconstructs from the shards.
Crash-safety mirrors the flush commit discipline: shards are new keys that leave the full copies intact, the sidecar is written next as the commit point, and only then are the full copies deleted. A crash before the sidecar leaves a readable full-copy part (the orphan shards are overwritten on retry); a crash mid-delete leaves a still-readable part (full copy or reconstruction). Convert is idempotent: a part that already has a valid sidecar is not re-read (its full copies may be gone) — only any leftover full copies are swept.
func Converted ¶
Converted reports whether the part at partPrefix has been erasure-coded (has a valid sidecar), returning the decoded sidecar when so.
func DecodeMeta ¶
DecodeMeta parses an AppendBinary payload, defensively against truncation and corruption (trailing whole-payload checksum, bounded lengths).
func (*Meta) AppendBinary ¶
AppendBinary appends the framed sidecar to dst and returns the extended slice.
type ObjectMeta ¶
type ObjectMeta struct {
// Name is the object's key relative to the part prefix (e.g. "c/0", "manifest").
Name string
// Size is the original object's byte size.
Size int64
// Checksums holds one xxh3 hash per shard slot.
Checksums []uint64
}
ObjectMeta describes one erasure-coded backend object within a part: its original size (Join needs it — shards are zero-padded) and the xxh3 checksum of each shard for fetch-time verification (a corrupt shard is detected before it poisons a reconstruction).
func EncodeObject ¶
EncodeObject shards one part object for the converter/repair paths: it encodes data into Scheme.Shards() shards and returns them with the object's sidecar entry (size + per-shard checksums) for Meta.Objects. The caller stores shard i under ShardKey on owner i and appends the entry to the part's sidecar.
type PeerFetch ¶
PeerFetch fetches one backend object from the node holding shard slot. The read path uses it to gather remote shards; the caller maps a slot to a peer (ring owner order) and its transport (the partsync object endpoint). A slot whose node is down returns an error; the gatherer just moves on — any Data shards suffice.
type Reader ¶
type Reader struct {
// Local is the node's private backend.
Local backend.Backend
// Slot is this node's shard slot for the engine's shard key (its index in the ring's
// owner list at rf = Data+Parity), or -1 when this node is not an owner (every shard is
// fetched from peers).
Slot int
// Fetch gathers a remote slot's objects; nil disables remote gathering (only local
// full copies and this node's own shards are usable — enough for unit tests and
// single-node repair tooling).
Fetch PeerFetch
}
Reader is the reconstructing read path over a node's private backend (issue 108 phase 2, milestone: `ecread`): Read serves a key from the local backend when the full object is present (hot full-copy parts, sub-floor objects, this node's own materialized copies) and otherwise reassembles it from erasure-coded shards — its own slot locally, the rest from peers — verifying every shard against the sidecar checksums before it participates in a reconstruction. The engine stays unaware: wrap the engine's backend and EC parts read like any others (cache with backend.Cached outside this wrapper, so a reconstructed object is decoded once).
type Scheme ¶
Scheme is a Reed-Solomon layout: Data data shards + Parity parity shards.
func (Scheme) MinZones ¶
MinZones is the number of distinct failure domains (racks/zones) needed to place the shards so that losing any one zone costs at most Parity shards — i.e. the placement stays recoverable through a whole-rack failure. It is `ceil(Shards / Parity)`: with that many zones a balanced placement holds at most Parity shards per zone. Fewer zones cannot be made rack-safe for this scheme (a zone must then hold more than Parity shards).
Source Files