103 lines
2.4 KiB
Markdown
103 lines
2.4 KiB
Markdown
|
# lseq
|
||
|
|
|
||
|
|
Go implementation of the L-SEQ algorithm for fractional indexing and list CRDTs.
|
||
|
|
|
||
|
|
The library handles edge cases that break other more naive implementations of
|
||
|
|
fractional indexing. With this library you can always insert before the first
|
||
|
|
item or after the last item, indefinitely.
|
||
|
|
|
||
|
|
This is exactly what you need to build realtime collaborative apps with
|
||
|
|
ordering for lists or trees of items. Users can reorder or insert at arbitrary
|
||
|
|
positions but in practice people really like moving items to the top or end of
|
||
|
|
a list.
|
||
|
|
|
||
|
|
## Installation
|
||
|
|
|
||
|
|
```bash
|
||
|
|
go get peoplesgrocers.com/code/oss/lseq/golang
|
||
|
|
```
|
||
|
|
|
||
|
|
## Usage
|
||
|
|
|
||
|
|
```go
|
||
|
|
package main
|
||
|
|
|
||
|
|
import (
|
||
|
|
"fmt"
|
||
|
|
"math/rand"
|
||
|
|
"sort"
|
||
|
|
|
||
|
|
"peoplesgrocers.com/code/oss/lseq/golang"
|
||
|
|
)
|
||
|
|
|
||
|
|
func main() {
|
||
|
|
l := lseq.NewLSEQ(rand.Float64)
|
||
|
|
|
||
|
|
first := l.Alloc(nil, nil)
|
||
|
|
second := l.Alloc(&first, nil)
|
||
|
|
between := l.Alloc(&first, &second)
|
||
|
|
|
||
|
|
// String comparison gives correct order
|
||
|
|
keys := []string{second, first, between}
|
||
|
|
sort.Strings(keys)
|
||
|
|
fmt.Println(keys) // [first, between, second]
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
## API
|
||
|
|
|
||
|
|
### `NewLSEQ(random func() float64) *LSEQ`
|
||
|
|
|
||
|
|
Create an allocator. Requires a random function returning values in [0, 1).
|
||
|
|
|
||
|
|
### `lseq.Alloc(before, after *string) string`
|
||
|
|
|
||
|
|
Allocate a key between `before` and `after`.
|
||
|
|
|
||
|
|
- `lseq.Alloc(nil, nil)` — first key in an empty list
|
||
|
|
- `lseq.Alloc(nil, &first)` — insert at head
|
||
|
|
- `lseq.Alloc(&last, nil)` — insert at tail
|
||
|
|
- `lseq.Alloc(&a, &b)` — insert between a and b
|
||
|
|
|
||
|
|
### `CompareLSEQ(a, b string) int`
|
||
|
|
|
||
|
|
Compare two keys. Returns -1, 0, or 1.
|
||
|
|
|
||
|
|
### `EvenSpacingIterator`
|
||
|
|
|
||
|
|
Generate evenly-spaced keys for bulk initialization:
|
||
|
|
|
||
|
|
```go
|
||
|
|
k, iter, err := lseq.NewEvenSpacingIterator(1000)
|
||
|
|
if err != nil {
|
||
|
|
panic(err)
|
||
|
|
}
|
||
|
|
|
||
|
|
var keys []string
|
||
|
|
for {
|
||
|
|
pos, ok := iter.Next()
|
||
|
|
if !ok {
|
||
|
|
break
|
||
|
|
}
|
||
|
|
keys = append(keys, lseq.PositionToKey(k, pos))
|
||
|
|
}
|
||
|
|
```
|
||
|
|
|
||
|
|
## Design
|
||
|
|
|
||
|
|
Keys are base-64 encoded strings using the alphabet `-0-9A-Z_a-z`. Standard
|
||
|
|
string comparison produces correct ordering. Keys work in SQL `ORDER BY`,
|
||
|
|
database indexes, and any language with string sorting.
|
||
|
|
|
||
|
|
## Cross-language support
|
||
|
|
|
||
|
|
Matching implementations exist for Rust, TypeScript, and Python; validated
|
||
|
|
against a shared conformance test suite.
|
||
|
|
|
||
|
|
## References
|
||
|
|
|
||
|
|
- [LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing](https://hal.science/hal-00921633/document) (Nédelec et al., 2013)
|
||
|
|
|
||
|
|
## License
|
||
|
|
|
||
|
|
AGPL-3.0
|