Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Log2Fixed ¶
Log2Fixed is a fixed point approximation of log2 with a lookup table for deterministic math. 16 bits of precision represents the fractional value. Calculates the logarithm as the sum of three pieces:
1. The integer value, which is calculated by counting number of bits.
2. A value calculated by a lookup table of lutEntryBits
3. The linearly interpolated value between the lookup table and the next value.
Since log2(x) = N+log2(x/2^N) we can easily remove the integer part of the logarithm. We calculate that exactly by counting the number of bits in the number. log(x/2^N) will then be a number between 0 and 1 for which we can use a lookup table to get precomputed values.
In contrast with mathematical logarithm, this function is defined for x=0 removing the need for conditionals the maximum value this function produces is 64 << 16 - 1.
func NewShardingBlobAccess ¶
func NewShardingBlobAccess(backends []ShardBackend, shardSelector ShardSelector) blobstore.BlobAccess
NewShardingBlobAccess is an adapter for BlobAccess that partitions requests across backends by hashing the digest. A ShardSelector is used to map hashes to backends.
Types ¶
type Shard ¶
Shard is a description of a shard. The shard selector will resolve to the same shard independent of the order of shards, but the returned index will correspond to the index sent to the ShardSelectors constructor.
type ShardBackend ¶
type ShardBackend struct {
Backend blobstore.BlobAccess
Key string
}
ShardBackend is the Backend together with its key, the key is used for error messages.
type ShardSelector ¶
ShardSelector is an algorithm that for a hash resolves into an index which corresponds to the specific backend for that shard.
The algorithm must be stable, the removal of an unavailable backend should not result in the reshuffling of any other blobs. It must also be numerically stable so that it produces the same result no matter the architecture.
func NewRendezvousShardSelector ¶
func NewRendezvousShardSelector(shards []Shard) (ShardSelector, error)
NewRendezvousShardSelector performs shard selection using the Rendezvous Hashing algorithm. The algorithm distributes blobs over the shard proportional to the shards weight, it fulfills all required properties of the ShardSelector interface:
- Reordering the shards will not affect the chosen shard.
- Removing a shard is guaranteed to only affect blobs that would have resolved to the removed shard.
- Adding a shard will only affect that blobs resolve to the new shard.
Source Files
Directories