partition

Documentation

Overview

Package partition encapsulates partitioning and querying large keyspace which can't be expressed even as uint64.

All to/from string functions use hex encoding.

Index

• type Partition
  • func FromInts(low, high int64) *Partition
  • func FromString(s string) (*Partition, error)
  • func SpanInclusive(low, highInclusive string) (*Partition, error)
  • func Universe(keySpaceBytes int) *Partition
  • func (p Partition) Copy() *Partition
  • func (p Partition) EducatedSplitAfter(exclusive string, beforeItems, targetItems, maxShards int) SortedPartitions
  • func (p Partition) MarshalJSON() ([]byte, error)
  • func (p Partition) QueryBounds(keySpaceBytes int) (low, high string)
  • func (p Partition) Split(shards int) SortedPartitions
  • func (p Partition) String() string
  • func (p *Partition) UnmarshalJSON(bs []byte) error
• type SortedPartitions
  • func (ps SortedPartitions) OnlyIn(n int, key func(i int) string, use func(l, h int), keySpaceBytes int)
• type SortedPartitionsBuilder
  • func NewSortedPartitionsBuilder(p *Partition) SortedPartitionsBuilder
  • func (b *SortedPartitionsBuilder) Exclude(exclude *Partition)
  • func (b *SortedPartitionsBuilder) IsEmpty() bool
  • func (b *SortedPartitionsBuilder) Result() SortedPartitions

Types

type Partition

type Partition struct {
	Low  big.Int // inclusive
	High big.Int // exclusive. May be equal to max SHA2 hash value + 1.
}

Partition represents a range [Low..High).

func FromInts

func FromInts(low, high int64) *Partition

func FromString

func FromString(s string) (*Partition, error)

func SpanInclusive

func SpanInclusive(low, highInclusive string) (*Partition, error)

func Universe

func Universe(keySpaceBytes int) *Partition

func (Partition) Copy

func (p Partition) Copy() *Partition

func (Partition) EducatedSplitAfter

func (p Partition) EducatedSplitAfter(exclusive string, beforeItems, targetItems, maxShards int) SortedPartitions

EducatedSplitAfter splits partition after a given boundary assuming constant density s.t. each shard has approximately targetItems.

Caps the number of resulting partitions to at most maxShards. panics if called on invalid data.

func (Partition) MarshalJSON

func (p Partition) MarshalJSON() ([]byte, error)

func (Partition) QueryBounds

func (p Partition) QueryBounds(keySpaceBytes int) (low, high string)

func (Partition) Split

func (p Partition) Split(shards int) SortedPartitions

func (Partition) String

func (p Partition) String() string

func (*Partition) UnmarshalJSON

func (p *Partition) UnmarshalJSON(bs []byte) error

type SortedPartitions

type SortedPartitions []*Partition

SortedPartitions are disjoint partitions sorted by ascending .Low field.

func (SortedPartitions) OnlyIn

func (ps SortedPartitions) OnlyIn(n int, key func(i int) string, use func(l, h int), keySpaceBytes int)

OnlyIn efficiently returns a subsequence of the `n` sorted by key objects whose key belongs to one of the partitions.

Calls use(i,j) for each objects[i:j] which belong to the range.

type SortedPartitionsBuilder

type SortedPartitionsBuilder struct {
	// contains filtered or unexported fields
}

SortedPartitionsBuilder constructs a sequence of partitions by excluding chunks from a starting partion.

Not intended to scale to large number of exclusion operations.

func NewSortedPartitionsBuilder

func NewSortedPartitionsBuilder(p *Partition) SortedPartitionsBuilder

func (*SortedPartitionsBuilder) Exclude

func (b *SortedPartitionsBuilder) Exclude(exclude *Partition)

func (*SortedPartitionsBuilder) IsEmpty

func (b *SortedPartitionsBuilder) IsEmpty() bool

func (*SortedPartitionsBuilder) Result

func (b *SortedPartitionsBuilder) Result() SortedPartitions