README
¶
Go Range Store
Range store provides a simple datastructure providing efficient storage of a single value to many (consecutive) keys. Inspired by wanting to write:
store := make(map[uint64]interface{})
store[10:20] = "hello"
greet := store[15]
// Greet is "hello"
Contact: developer@tenta.io
Installation
go get github.com/tenta-browser/go-range-store
Usage
The range store provides a compact and efficient tree based method of storing a single value associated with a range of keys. You may
either use the provided DefaultRangedValue to store data. In addition, a Ranged interface is provided allowing for storage of
arbitrary types. For example, using US zip codes (postal codes), to map zip codes to a regional office:
items := make([]Ranged,0)
items = append(items, DefaultRangedValue{0, 25505, "New York"})
items = append(items, DefaultRangedValue(25506, 67890, "Chicago"})
items = append(items, DefaultRangedValue(67891, 89000, "Phoenix"})
items = append(items, DefaultRangedValue(89001, 99999, "Los Angeles"})
n, err := NewRangeStoreFromSorted(items)
// Check error
city := n.RangeSearch(85716)
// City is "Phoenix"
The range store must be constructed with a continuously inscreasing set of non-negative integers which don't overlap and contain
no discontinuities. To simplify operation when using values where only weights matter, and not explicit ranges, a Weighted interface
and DefaultWeightedValue are provided. For example, so select fairly among servers with different weights:
items := make([]Weighted, 0)
items = append(items, DefaultWeightedValue{10, "a.example.com"})
items = append(items, DefaultWeightedValue(10, "b.example.com")}
items = append(items, DefaultWeightedValue(20, "c.example.com")}
n, err := NewRangeStoreFromWeighted(items)
// Check error
p := rand.Intn(40)
server := n.RangeSearch(uint64(p))
// Server has a 25% chance of being a or b and a 50% chance of being c
Performance
We wrote it to be fast and we use it in production. The tests include a totally arbitrary benchmark against a very naive implementation using a raw map with an entry for every value in the range. Unsurprisingly, for large ranges, the range store massively outperforms the map. However, even for small ranges, the range store still outperforms the map, as indexing requires only fast integer operations. In addition, the range store always outperforms the map on construction:
Benchmark_NewNodeSorted_Small-4 10000000 219 ns/op
Benchmark_NewMapSorted_Small-4 300000 5389 ns/op
Benchmark_NewNodeSorted_Large-4 10000000 224 ns/op
Benchmark_NewMapSorted_Large-4 5 203757320 ns/op
Benchmark_RangeSearch_Node-4 20000000 63 ns/op
Benchmark_RangeSearch_Map-4 10000000 186 ns/op
License
Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.
For any questions, please contact developer@tenta.io
Contributing
We welcome contributions, feedback and plain old complaining. Feel free to open an issue or shoot us a message to developer@tenta.io. If you'd like to contribute, please open a pull request and send us an email to sign a contributor agreement.
About Tenta
This range store library is brought to you by Team Tenta. Tenta is your private, encrypted browser that protects your data instead of selling. We're building a next-generation browser that combines all the privacy tools you need, including built-in OpenVPN. Everything is encrypted by default. That means your bookmarks, saved tabs, web history, web traffic, downloaded files, IP address and DNS. A truly incognito browser that's fast and easy.
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type DefaultRangedValue ¶
type DefaultRangedValue struct {
// contains filtered or unexported fields
}
func (DefaultRangedValue) GetMax ¶
func (r DefaultRangedValue) GetMax() uint64
func (DefaultRangedValue) GetMin ¶
func (r DefaultRangedValue) GetMin() uint64
func (DefaultRangedValue) GetValue ¶
func (r DefaultRangedValue) GetValue() interface{}
type DefaultWeightedValue ¶
type DefaultWeightedValue struct {
Weight uint64
Value interface{}
}
func (DefaultWeightedValue) GetValue ¶
func (w DefaultWeightedValue) GetValue() interface{}
func (DefaultWeightedValue) GetWeight ¶
func (w DefaultWeightedValue) GetWeight() uint64
type ErrDiscontinuity ¶
type ErrDiscontinuity struct {
// contains filtered or unexported fields
}
func (ErrDiscontinuity) Error ¶
func (ex ErrDiscontinuity) Error() string
type ErrEmptyInput ¶
type ErrEmptyInput struct{}
func (ErrEmptyInput) Error ¶
func (ex ErrEmptyInput) Error() string
type ErrOutOfRange ¶
type ErrOutOfRange struct {
// contains filtered or unexported fields
}
func (ErrOutOfRange) Error ¶
func (ex ErrOutOfRange) Error() string
type ErrOverlap ¶
type ErrOverlap struct {
// contains filtered or unexported fields
}
func (ErrOverlap) Error ¶
func (ex ErrOverlap) Error() string
type ErrUnsignedIntegerOverflow ¶
type ErrUnsignedIntegerOverflow struct {
// contains filtered or unexported fields
}
func (ErrUnsignedIntegerOverflow) Error ¶
func (ex ErrUnsignedIntegerOverflow) Error() string
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
func NewRangeStoreFromSorted ¶
Builds a optimal(ish) tree containing the range values as node values. For the computation of optimality, we assume that every value in the aggregate ranges is equally likely to be looked up. We then choose pivots so that roughly equal amounts of range are in each subtree.
That is, with a set of values like: * A [0,1] * B [1,2] * C [2,3] The tree produced will look like
B [2] ___|___ | | A C
[1] [3]
However with non-equal weights, such as * A [0,1] * B [1,2] * C [2,100] The tree produced will look more like
C
[100]
___|
|
A
[1]
|___
|
B
[2]
Although this tree is degenerate based on a counting of *nodes* it is optimal based on lookup frequency, since ~98% of lookups will terminate at the root node and only very infrequently will recursion down the tree occur.
_Note_: The items passed to RangeStoreFRomSorted must contain a monotonically increasing and continuous sequence of min and max values
_Note_: Construction of the tree is done using Mehlhorn's approximation for balancing the tree and uses an effective floor (unsigned integer division) when computing pivots. As a result, the produced data structure approaches, but may not always be exactly, optimal.
func (*Node) RangeSearch ¶
Searches for the range which contains the specified key and returns the associated value, or an error if the value is out of range
Source Files