hanahmily commented on code in PR #999: URL: https://github.com/apache/skywalking-banyandb/pull/999#discussion_r2918268677
########## pkg/idgen/snowflake.go: ########## @@ -0,0 +1,90 @@ +// Licensed to Apache Software Foundation (ASF) under one or more contributor +// license agreements. See the NOTICE file distributed with +// this work for additional information regarding copyright +// ownership. Apache Software Foundation (ASF) licenses this file to you 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. + +package idgen + +import ( + "sync" + "time" + + "github.com/apache/skywalking-banyandb/pkg/logger" + "github.com/apache/skywalking-banyandb/pkg/convert" +) + +const ( + epoch int64 = 1609459200000 + + nodebits = 7 + sequenceBits = 10 + + nodeShift = sequenceBits + timeStampShift = nodebits + sequenceBits + + maxNodeID = (1 << nodebits) - 1 + maxSequence = (1 << sequenceBits) - 1 +) + +// [1-bit sign=0] [46-bit ms timestamp] [7-bit node ID] [10-bit sequence] +type Generator struct { + l *logger.Logger + mu sync.Mutex Review Comment: using a lock-free approach via sync/atomic is an elegant way to solve both the mutex deadlock and the clock regression problem in one go. To make this lock-free, the trick is to pack both the lastTime and the sequence into a single 64-bit integer. Since your timestamp uses 46 bits and your sequence uses 10 bits, they combined take up 56 bits—which fits perfectly inside a uint64. ########## pkg/idgen/snowflake.go: ########## @@ -0,0 +1,90 @@ +// Licensed to Apache Software Foundation (ASF) under one or more contributor +// license agreements. See the NOTICE file distributed with +// this work for additional information regarding copyright +// ownership. Apache Software Foundation (ASF) licenses this file to you 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. + +package idgen + +import ( + "sync" + "time" + + "github.com/apache/skywalking-banyandb/pkg/logger" + "github.com/apache/skywalking-banyandb/pkg/convert" +) + +const ( + epoch int64 = 1609459200000 + + nodebits = 7 + sequenceBits = 10 + + nodeShift = sequenceBits + timeStampShift = nodebits + sequenceBits + + maxNodeID = (1 << nodebits) - 1 + maxSequence = (1 << sequenceBits) - 1 +) + +// [1-bit sign=0] [46-bit ms timestamp] [7-bit node ID] [10-bit sequence] +type Generator struct { + l *logger.Logger + mu sync.Mutex + nodeID int64 + sequence int64 + lastTime int64 +} + +// NewGenerator creates a Generator whose 7-bit node component is derived by hashing the given nodeID string. +func NewGenerator(nodeID string, l *logger.Logger) *Generator { + nid := int64(convert.HashStr(nodeID)) & maxNodeID + return &Generator{ + nodeID: nid, + l: l, + } +} + +// NextID returns the next unique 64-bit ID. +func (g *Generator) NextID() uint64 { + g.mu.Lock() + defer g.mu.Unlock() + + now := time.Now().UnixMilli() - epoch + + if now < g.lastTime { Review Comment: By making this combined state atomic, we can use a CAS loop. If the clock goes backward, we simply ignore the OS clock, rely on the atomic state, and push our "logical clock" forward. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
