Comment implémenter l'algorithme Snowflake dans Golang

Snowflake est un algorithme de génération d'identifiant distribué open source par Twitter. Il utilise la méthode suivante pour générer un identifiant unique au monde :

1. ID 64 bits, dont 1 est un bit de signe, 41 sont des horodatages et 10 sont une machine de travail. ID. , 12 sont des numéros de série.
2. Pour les systèmes distribués, l'unicité globale peut généralement être garantie en combinant les horodatages, les identifiants des machines de travail et les numéros de série.

Dans cet article, nous présenterons comment implémenter Snowflake dans Golang.

1. Définir les structures et les constantes

Tout d'abord, nous devons définir une structure pour enregistrer les données dans l'algorithme Snowflake, y compris l'ID de la machine, le numéro de série et l'horodatage du dernier ID généré.

const (
    workerIdBits     = 10  // 机器ID位数
    sequenceBits     = 12  // 序列号位数
    workerIdMax      = -1 ^ (-1 << workerIdBits) // 最大机器ID
    sequenceMask     = -1 ^ (-1 << sequenceBits) // 序列号掩码
    timeShiftBits    = workerIdBits + sequenceBits // 时间戳左移位数
    workerIdShift    = sequenceBits               // 机器ID左移位数
)

type Snowflake struct {
    lastTimestamp uint64
    workerId      uint16
    sequence      uint16
}

Parmi eux, nous utilisons des constantes pour représenter le nombre de chiffres de chaque donnée, la valeur maximale, le masque et d'autres informations pour faciliter les calculs ultérieurs.

2. Implémenter la méthode de génération d'ID

Ensuite, nous devons implémenter une méthode pour générer un identifiant globalement unique. Le processus spécifique est le suivant :

1. Obtenir l'horodatage actuel S'il est inférieur à l'horodatage du dernier identifiant généré, attendez que l'horodatage soit mis à jour pour qu'il soit supérieur à l'horodatage du dernier identifiant généré.
2. Si l'horodatage actuel est égal à l'horodatage du dernier identifiant généré, augmentez le numéro de séquence. Si le numéro de séquence atteint la valeur maximale, attendez l'horodatage suivant.
3. Si l'horodatage actuel est supérieur à l'horodatage du dernier identifiant généré, réinitialisez le numéro de séquence, enregistrez l'horodatage actuel et générez un identifiant.

L'implémentation spécifique est la suivante :

func (s *Snowflake) NextId() uint64 {
    var currTimestamp = uint64(time.Now().UnixNano() / 1e6)

    if currTimestamp < s.lastTimestamp {
        panic("Invalid timestamp")
    }

    if currTimestamp == s.lastTimestamp {
        s.sequence = (s.sequence + 1) & sequenceMask
        if s.sequence == 0 {
            currTimestamp = s.waitNextMillis(currTimestamp)
        }
    } else {
        s.sequence = 0
    }

    s.lastTimestamp = currTimestamp

    return ((currTimestamp - 1483228800000) << timeShiftBits) |
            (uint64(s.workerId) << workerIdShift) |
            uint64(s.sequence)
}

func (s *Snowflake) waitNextMillis(currTimestamp uint64) uint64 {
    for currTimestamp <= s.lastTimestamp {
        currTimestamp = uint64(time.Now().UnixNano() / 1e6)
    }
    return currTimestamp
}

Dans l'implémentation, nous utilisons des horodatages UNIX pour représenter l'heure, mais depuis le moment où l'algorithme Snowflake génère des identifiants commence en 2017, nous devons soustraire une valeur de décalage fixe des horodatages (1483228800000).

3. Initialiser l'objet Snowflake

Enfin, nous devons initialiser un objet Snowflake et spécifier l'ID de la machine. L'ID de la machine doit être un entier compris entre 0 et 1023, et les ID des différentes machines sont garantis différents.

func New(workerId int) *Snowflake {
    if workerId < 0 || workerId > workerIdMax {
        panic(fmt.Sprintf("Invalid worker ID, must be in [%d, %d]", 0, workerIdMax))
    }

    return &Snowflake{
        lastTimestamp: 0,
        workerId:      uint16(workerId),
        sequence:      0,
    }
}

Dans l'implémentation ci-dessus, nous avons utilisé la fonction d'horodatage et l'opérateur binaire dans Golang pour garantir l'unicité et la continuité de l'ID, et le numéro de séquence d'ordre inférieur assure la tendance à l'augmentation de l'ID. Étant donné que les horodatages sont précis à la milliseconde près, l'algorithme Snowflake peut générer suffisamment d'identifiants pour éviter les conflits d'identifiants dans les scénarios à forte concurrence.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!