Add Clawflake ID number generation

7 files changed, 188 insertions, 15 deletions

diff --git a/README.md b/README.md
index c9d1b82..51d8182 100644
--- a/README.md
+++ b/README.md
@@ -1,27 +1,36 @@
 # Clawflake
 
-Clawflake is a Rust application which implements [Twitter Snowflakes](https://github.com/twitter-archive/snowflake/tree/snowflake-2010) and communicates using [gRPC](https://grpc.io/).
+Clawflake is a distributed ID number generation system inspired from Twitter 
+[Snowflake](https://github.com/twitter-archive/snowflake/tree/snowflake-2010).
 
-Snowflake ID numbers are 63 bits integers stored as `i64`.
+The goal of Clawflake is to be hosted as a distributed system with all workers
+being isolated from each others apart from the machine ID.
 
-An ID number is composed of:
+## Format
 
-- a timestamp (which is the difference between the current time and the epoch) [`41 bits`]
-- a configured machine ID (Data center ID and Worker ID) [`10 bits`]
-- a sequence number which rolls over every 4096 per machine (with protection to avoid rollover in the same ms) [`12 bits`]
+Unlike Snowflake, the composition of a Clawflake uses all 64 bits.
 
-## Usage
+- `time` (45 bits): The number of milliseconds passed from a configured epoch.
+- `sequence` (12 bits): A sequence number rolling out whenever required.
+- `machine` (7 bits): An identifier for the worker.
+
+Therefore, Clawflake ID numbers gives **2^45 - 1 = 1115.7 years of safety**
+from the configured epoch.  
+Thanks to the sequence number, a worker can handle **2^12 = 4069 generations**
+per milliseconds at peak.
+The system can accept a maximum of **2^7 = 128 machines** for a given epoch.
 
-> You need to use the nightly toolchain!
+> Since Clawflake uses the most significant bit, converting a Clawflake ID from
+> `uint64` to `int64` is not safe.
 
-Run the container
+## Usage
 
-```sh
-docker run -e CLAWFLAKE_EPOCH=<epoch> -e CLAWFLAKE_WORKER_ID=<worker_id> -e CLAWFLAKE_DATACENTER_ID=<datacenter_id> -p <host port>:50051 docker pull n1c00o/clawflake
-```
+TODO(nc0): Usage information, with or without containers.
 
-(or you can build from source)
+## License
 
-You can then create your client using [clawflake.rs](clawflake.rs) and start communicate with the service.
+Clawflake is governed by a BSD-style license that can be found in the 
+[LICENSE](LICENSE) file.
 
-An example client can be found [here](src/client.rs)!
+Older codebase was licensed by the Apache License, Version 2.0, however none of
+the old code still exists.
diff --git a/cmd/generator/generator b/cmd/generator/generator
new file mode 100755
index 0000000..4182f4b
--- /dev/null
+++ b/cmd/generator/generator
diff --git a/cmd/generator/generator.go b/cmd/generator/generator.go
new file mode 100644
index 0000000..0a8f961
--- /dev/null
+++ b/cmd/generator/generator.go
@@ -0,0 +1,18 @@
+package main
+
+import (
+	"context"
+
+	generatorpb "go.nc0.fr/clawflake/api/nc0/clawflake/generator/v3"
+)
+
+// GeneratorServiceServer is an implementation of the gRPC GeneratorService
+// service.
+type GeneratorServiceServer struct {
+	generatorpb.UnimplementedGeneratorServiceServer
+}
+
+// Generate allows generating a set of Clawflake ID numbers.
+func (g *GeneratorServiceServer) Generate(context.Context, *generatorpb.GenerateRequest) (*generatorpb.GenerateResponse, error) {
+	return nil, nil
+}
diff --git a/cmd/generator/id.go b/cmd/generator/id.go
new file mode 100644
index 0000000..052b353
--- /dev/null
+++ b/cmd/generator/id.go
@@ -0,0 +1,88 @@
+// Clawflake ID number generation.
+
+package main
+
+import (
+	"errors"
+	"flag"
+	"sync"
+	"time"
+
+	"go.uber.org/zap"
+)
+
+var (
+	epoch     *uint = flag.Uint("epoch", 0, "The epoch to use to generate ID numbers.")
+	machineId *uint = flag.Uint("machine_id", 255, "The ID of the current machine worker. Should be between 0 and 127.")
+)
+
+// IdGenerator generates Clawflake ID numbers
+type IdGenerator struct {
+	// Sequence number, varies between 0 and 4096
+	seq       uint16
+	last_time int64
+	mu        sync.Mutex
+	logger    *zap.Logger
+}
+
+// GetTime returns the current time based on the configured epoch
+func (i *IdGenerator) GetTime() int64 {
+	return time.Now().UTC().UnixMilli() - int64(*epoch)
+}
+
+// NextId generates a Clawflake ID number.
+func (i *IdGenerator) NextId() (uint64, error) {
+	if !flag.Parsed() {
+		return 0, errors.New("unparsed flags")
+	}
+
+	// Generation:
+
+	var id uint64
+	i.mu.Lock()
+	defer i.mu.Unlock()
+
+	t := i.GetTime()
+	l := i.logger.With(zap.Int64("last_time", i.last_time),
+		zap.Uint16("seq", i.seq), zap.Uint("epoch", *epoch))
+
+	if t < i.last_time {
+		// Time went backward.
+		l.Warn("time went backward, sleeping 10ms", zap.Int64("current_time", t))
+		time.Sleep(10 * time.Millisecond)
+
+		t = i.GetTime()
+	}
+
+	if t == i.last_time {
+		// If the generation is in the same millisecond, increment the sequence
+		// number if it is possible.
+		if i.seq == 4096 {
+			i.seq = 0
+			l.Debug("rolling over sequence number", zap.Uint16("seq", 0))
+		} else {
+			i.seq += 1
+			l.Debug("incrementing sequence number", zap.Uint16("seq", i.seq))
+		}
+	} else {
+		// Reset the sequence number each millisecond.
+		i.seq = 0
+		l.Debug("resetting sequence number", zap.Uint16("seq", 0))
+	}
+
+	i.last_time = t
+	id = uint64(t)<<19 | uint64(*machineId)<<7 | uint64(i.seq)
+	l.Info("generated id number", zap.Uint64("generated_id", id))
+
+	return id, nil
+}
+
+// NewIdGenerator creates a new IdGenerator
+func NewIdGenerator(l *zap.Logger) *IdGenerator {
+	return &IdGenerator{
+		seq:       0,
+		last_time: 0,
+		mu:        sync.Mutex{},
+		logger:    l,
+	}
+}
diff --git a/cmd/generator/main.go b/cmd/generator/main.go
new file mode 100644
index 0000000..7ed230b
--- /dev/null
+++ b/cmd/generator/main.go
@@ -0,0 +1,49 @@
+// Package main implements the generator service, a server that can creates
+// Clawflake ID numbers.
+package main
+
+// TODO(nc0): Configure CI inside //.github/workflows.
+
+import (
+	"flag"
+
+	"go.uber.org/zap"
+)
+
+var (
+	grpcHost *string = flag.String("grpc_host", "localhost:5000", "The host the gRPC server should listen to. Default to localhost:5000.")
+	devMode  *bool   = flag.Bool("dev", false, "Enables development mode, with more debug logs.")
+)
+
+func main() {
+	flag.Parse()
+
+	var logger *zap.Logger
+	if *devMode {
+		logger, _ = zap.NewDevelopment()
+	} else {
+		logger, _ = zap.NewProduction()
+	}
+	defer logger.Sync()
+
+	l := logger.Named("generator").With(zap.Bool("dev", *devMode),
+		zap.String("grpc_host", *grpcHost), zap.Uint("epoch", *epoch),
+		zap.Uint("machine_id", *machineId))
+
+	// Verify 0 <= machineId < 128
+	if *machineId > 128 {
+		l.Fatal("Invalid machine_id given, the value should be between 0 and 127 (included).")
+		return
+	}
+
+	i := NewIdGenerator(l)
+	l.Info("i time", zap.Int64("time", i.GetTime()))
+
+	id, err := i.NextId()
+	if err != nil {
+		l.Error("failed to generate id", zap.Error(err))
+		return
+	}
+	l.Info("i id", zap.Uint64("id", id))
+
+}
diff --git a/go.mod b/go.mod
index 38550fe..6fd2fa2 100644
--- a/go.mod
+++ b/go.mod
@@ -18,6 +18,9 @@ require (
 	github.com/googleapis/enterprise-certificate-proxy v0.2.1 // indirect
 	github.com/googleapis/gax-go/v2 v2.7.0 // indirect
 	go.opencensus.io v0.24.0 // indirect
+	go.uber.org/atomic v1.10.0 // indirect
+	go.uber.org/multierr v1.9.0 // indirect
+	go.uber.org/zap v1.24.0 // indirect
 	golang.org/x/net v0.4.0 // indirect
 	golang.org/x/oauth2 v0.0.0-20221014153046-6fdb5e3db783 // indirect
 	golang.org/x/sys v0.3.0 // indirect
diff --git a/go.sum b/go.sum
index 33c897a..e6c22e1 100644
--- a/go.sum
+++ b/go.sum
@@ -57,6 +57,12 @@ github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO
 github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
 go.opencensus.io v0.24.0 h1:y73uSU6J157QMP2kn2r30vwW1A2W2WFwSCGnAVxeaD0=
 go.opencensus.io v0.24.0/go.mod h1:vNK8G9p7aAivkbmorf4v+7Hgx+Zs0yY+0fOtgBfjQKo=
+go.uber.org/atomic v1.10.0 h1:9qC72Qh0+3MqyJbAn8YU5xVq1frD8bn3JtD2oXtafVQ=
+go.uber.org/atomic v1.10.0/go.mod h1:LUxbIzbOniOlMKjJjyPfpl4v+PKK2cNJn91OQbhoJI0=
+go.uber.org/multierr v1.9.0 h1:7fIwc/ZtS0q++VgcfqFDxSBZVv/Xo49/SYnDFupUwlI=
+go.uber.org/multierr v1.9.0/go.mod h1:X2jQV1h+kxSjClGpnseKVIxpmcjrj7MNnI0bnlfKTVQ=
+go.uber.org/zap v1.24.0 h1:FiJd5l1UOLj0wCgbSE0rwwXHzEdAZS6hiiSnxJN/D60=
+go.uber.org/zap v1.24.0/go.mod h1:2kMP+WWQ8aoFoedH3T2sq6iJ2yDWpHbP0f6MQbS9Gkg=
 golang.org/x/crypto v0.0.0-20190308221718-c2843e01d9a2/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
 golang.org/x/crypto v0.0.0-20200622213623-75b288015ac9/go.mod h1:LzIPMQfyMNhhGPhUkYOs5KpL4U8rLKemX1yGLhDgUto=
 golang.org/x/exp v0.0.0-20190121172915-509febef88a4/go.mod h1:CJ0aWSM057203Lf6IL+f9T1iT9GByDxfZKAQTCR3kQA=