```
# PartitionMap
*WORK IN PROGRESS*
PartitionMap maps arbitrary terms to a set of contiguous and dynamic (but deterministic) partitions. It's intended as a hash table for distributed systems.
The general goal is to assign every possible term to a set of known buckets, without the O(N) size requirement of a Map.
You can think of PartitionMap like [Consistent Hashing](https://en.wikipedia.org/wiki/Consistent_hashing) but with a couple of key advantages:
- dynamic number of partitions
- dynamically sized partitions
- pluggable slicing strategies for application-specific optimizations
- doesn't conflate partition assignment with replication policies
There's a great article by @slfritchie on the topic: [A Critique of Resizable Hash Tables: Riak Core & Random Slicing](https://www.infoq.com/articles/dynamo-riak-random-slicing)
PartitionMap takes heavy inspiration and uses the "CutShift" algorithm from ["Random slicing: Efficient and scalable data placement for large-scale storage systems."](docs/miranda-tos14.pdf)
## Internals
PartitionMap works by hashing the given term into a fixed-size range of integer keys, the hash lands inside one of many contiguous intervals of integers (partitions).
Each partition belongs to an "owner", each owner owns a configurable proportion of the total hash space.
A graphical example:
```
owner1 o2 o1 o1 o2 o1 o2
v v v v v v v
<- p1 ->|<- p2 ->|<----- p3 ----->|<- p4 ->|<- p5 ->|<-- p6 -->|<------ p7 ------>|
|-------|--------|----------------|--------|--------|----------|------------------|
^ ^ ^ ^ ^ ^ ^ ^
0 | | | | | | 2**32 (phash2)
| | | | | |
"abcd" <<1,2>> "z" %{a: 123} 500 {:ok, [1, 2, 3]}
```
So, the terms `"z"` and `%{a: 123}` are both mapped to the same partition.
## Installation
The package can be installed by adding `partition_map` to your list of dependencies in `mix.exs`:
```elixir
def deps do
[
{:partition_map, "~> 0.1.0"}
]
end
```
The docs can be found at [https://hexdocs.pm/partition_map](https://hexdocs.pm/partition_map).
```