`
javafan_303
  • 浏览: 957918 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

Twitter-Snowflake 自增id实现

 
阅读更多

 

package io.github.id;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * 第一位为未使用(实际上也可作为long的符号位),接下来的41位为毫秒级时间,然后5位datacenter标识位,</br>
 * 5位机器ID(并不算标识符,实际是为线程标识),然后12位该毫秒内的当前毫秒内的计数,加起来刚好64位,为一个Long型。
 * 0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000
 * @author cailin
 *
 */
public class IdWorker {
     
    protected static final Logger LOG = LoggerFactory.getLogger(IdWorker.class);
     
    //机器id
    private long workerId;
    
    //数据中心id
    private long datacenterId;
    private long sequence = 0L;
 
    private long twepoch = 1288834974657L;
 
    //机器标识位数
    private long workerIdBits = 5L;
    //数据中心标识位数
    private long datacenterIdBits = 5L;
    //机器ID最大值
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);
    //数据中心ID最大值
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    //毫秒内自增位
    private long sequenceBits = 12L;
    //机器ID偏左移12位
    private long workerIdShift = sequenceBits;
    //数据中心ID左移17位
    private long datacenterIdShift = sequenceBits + workerIdBits;
    //时间毫秒左移22位
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    private long lastTimestamp = -1L;
 
    /**
     * @param workerId 机器id
     * @param datacenterId 数据中心id
     */
    public IdWorker(long workerId, long datacenterId) {
        // sanity check for workerId
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
        LOG.info(String.format("worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d", timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId));
    }
 
    public synchronized long nextId() {
        long timestamp = timeGen();
 
        if (timestamp < lastTimestamp) {
            LOG.error(String.format("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp));
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
 
        if (lastTimestamp == timestamp) {
        	//当前毫秒内,则+1
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
            //当前毫秒内计数满了,则等待下一秒
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0L;
        }
 
        lastTimestamp = timestamp;
        
        //ID偏移组合生成最终的ID,并返回ID   
 
        return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence;
    }
 
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    protected long timeGen() {
        return System.currentTimeMillis();
    }
    
    public static void main(String[] args) {
    	IdWorker  worker  = new IdWorker(1, 1);
    	worker.nextId();
    	
	}
}

 

 

    PHP实现

 

<?php
/* vim: set expandtab tabstop=4 shiftwidth=4: */
// +----------------------------------------------------------------------+
// | PHP version 5                                                        |
// +----------------------------------------------------------------------+
// | Copyright (c) 1997-2004 The PHP Group                                |
// +----------------------------------------------------------------------+
// | This source file is subject to version 3.0 of the PHP license,       |
// | that is bundled with this package in the file LICENSE, and is        |
// | available through the world-wide-web at the following url:           |
// | http://www.php.net/license/3_0.txt.                                  |
// | If you did not receive a copy of the PHP license and are unable to   |
// | obtain it through the world-wide-web, please send a note to          |
// | license@php.net so we can mail you a copy immediately.               |
// +----------------------------------------------------------------------+
// | Authors: Original Author <author@example.com>                        |
// |          Your Name <you@example.com>                                 |
// +----------------------------------------------------------------------+
//
// $Id:$

class Idwork {
    const debug = 1;
    static $workerId;
    static $twepoch = 1361775855078;
    static $sequence = 0;
    const workerIdBits = 4;
    static $maxWorkerId = 15;
    const sequenceBits = 10;
    static $workerIdShift = 10;
    static $timestampLeftShift = 14;
    static $sequenceMask = 1023;
    private static $lastTimestamp = - 1;
    function __construct($workId) {
        if ($workId > self::$maxWorkerId || $workId < 0) {
            throw new Exception("worker Id can't be greater than 15 or less than 0");
        }
        self::$workerId = $workId;
        echo 'logdebug->__construct()->self::$workerId:' . self::$workerId;
        echo '</br>';
    }
    function timeGen() {
        //获得当前时间戳
        $time = explode(' ', microtime());
        $time2 = substr($time[0], 2, 3);
        $timestramp = $time[1] . $time2;
        echo 'logdebug->timeGen()->$timestramp:' . $time[1] . $time2;
        echo '</br>';
        return $time[1] . $time2;
    }
    function tilNextMillis($lastTimestamp) {
        $timestamp = $this->timeGen();
        while ($timestamp <= $lastTimestamp) {
            $timestamp = $this->timeGen();
        }
        echo 'logdebug->tilNextMillis()->$timestamp:' . $timestamp;
        echo '</br>';
        return $timestamp;
    }
    function nextId() {
        $timestamp = $this->timeGen();
        echo 'logdebug->nextId()->self::$lastTimestamp1:' . self::$lastTimestamp;
        echo '</br>';
        if (self::$lastTimestamp == $timestamp) {
            self::$sequence = (self::$sequence + 1) & self::$sequenceMask;
            if (self::$sequence == 0) {
                echo "###########" . self::$sequenceMask;
                $timestamp = $this->tilNextMillis(self::$lastTimestamp);
                echo 'logdebug->nextId()->self::$lastTimestamp2:' . self::$lastTimestamp;
                echo '</br>';
            }
        } else {
            self::$sequence = 0;
            echo 'logdebug->nextId()->self::$sequence:' . self::$sequence;
            echo '</br>';
        }
        if ($timestamp < self::$lastTimestamp) {
            throw new Excwption("Clock moved backwards.  Refusing to generate id for " . (self::$lastTimestamp - $timestamp) . " milliseconds");
        }
        self::$lastTimestamp = $timestamp;
        echo 'logdebug->nextId()->self::$lastTimestamp3:' . self::$lastTimestamp;
        echo '</br>';
        echo 'logdebug->nextId()->(($timestamp - self::$twepoch << self::$timestampLeftShift )):' . ((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch)));
        echo '</br>';
        $nextId = ((sprintf('%.0f', $timestamp) - sprintf('%.0f', self::$twepoch))) | (self::$workerId << self::$workerIdShift) | self::$sequence;
        echo 'timestamp:' . $timestamp . '-----';
        echo 'twepoch:' . sprintf('%.0f', self::$twepoch) . '-----';
        echo 'timestampLeftShift =' . self::$timestampLeftShift . '-----';
        echo 'nextId:' . $nextId . '----';
        echo 'workId:' . self::$workerId . '-----';
        echo 'workerIdShift:' . self::$workerIdShift . '-----';
        return $nextId;
    }
}
$Idwork = new Idwork(1);
$a = $Idwork->nextId();
$Idwork = new Idwork(2);
$a = $Idwork->nextId();
?>      

 

 

   压力测试结果,8g内存的笔记本,10w次请求1000线程

 

time:0:00:49.145
speed:4069589.9888086272

 

   下面是压力测试的代码

package io.github.id;

import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.CountDownLatch;

import org.apache.commons.lang3.time.StopWatch;

public class Benchmark {
	public static void main(String[] args) throws InterruptedException {
		Benchmark benchmark = new Benchmark();
		benchmark.test();
	}

	public void test() throws InterruptedException {
		int threadCount = 2000;
		final int genCount = 100000;
		StopWatch watch = new StopWatch();
	    final IdWorker idWorker = new IdWorker(0, 0);
		final CountDownLatch latch = new CountDownLatch(threadCount);
		final  Set<Long> set = new HashSet();
		
		
		watch.start();
		for (int i = 0; i < threadCount; ++i) {
			Thread thread = new Thread() {
				public void run() {
					for (int j = 0; j < genCount; ++j) {
						  long id = idWorker.nextId();
			
			
					}
					latch.countDown();
				}
			};
			thread.start();
		}

		latch.await();
		watch.stop();

		System.err.println("time:" + watch);
		System.err.println("speed:" + genCount * threadCount / (watch.getTime() / 1000.0));
	}
}

 

 
分享到:
评论

相关推荐

    Laravel开发-laravel-snowflake .zip

    传统的自增ID在多节点环境下容易出现冲突,而雪花算法(Snowflake)是Twitter开源的一种解决办法。laravel-snowflake就是Laravel对这个算法的实现,它能够生成类似于Twitter Snowflake的64位ID,这些ID由时间戳、...

    Twitter的分布式自增ID算法Snowflake的PHP实现,Snowflake PHP版本,高并发唯一id,全局唯一id,不重复id

    Twitter Snowflake算法,php版代码; 请见博客: http://blog.csdn.net/envon123/article/details/52953872

    Twitter的分布式自增ID雪花算法snowflake

    综上所述,Twitter的雪花算法(Snowflake)提供了一种高效、简单的分布式ID生成方案,通过合理的结构设计,确保了全局唯一性和顺序性。在Java环境下,可以通过实现相应的类和方法轻松地引入这一机制,为分布式系统的...

    snowflake-C语言实现分布式自增有序的唯一ID生成算法

    We have retired the initial release of Snowflake and working on open sourcing the next version based on Twitter-server, in a form that can run anywhere without requiring Twitter's own infrastructure ...

    Java实现Twitter的分布式自增ID算法snowflake

    【Java实现Twitter的分布式自增ID算法snowflake】 在分布式系统设计中,生成全局唯一ID是一个常见的需求。Twitter的Snowflake算法就是为了解决这个问题而诞生的,它提供了一种高效、有序且不会冲突的ID生成策略。...

    Twitter_Snowflake

    Twitter_Snowflake,SnowFlake的优点是,整体上按照时间自增排序,并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分),并且效率较高,经测试,SnowFlake每秒能够产生26万ID左右。

    java快速ID自增器

    1. **原子类**:Java的`AtomicLong`类是线程安全的,可以用于实现自增ID。每次获取新ID时,只需要调用`incrementAndGet()`方法,该方法会原子性地增加当前值并返回新的值。 2. **数据库序列**:如果使用的是支持...

    springboot分布式自增id_javaredis_源码

    在分布式系统中,为了生成全局唯一的自增ID,可以使用Snowflake算法、Twitter的分布式ID生成服务,或者基于Redis的序列号生成方案。Spring Boot可以轻松集成这些方案,通过配置和注解简化开发流程。 2. **Redis作为...

    SnowFlake:Twitter的分布式自增ID雪花算法snowflake(Java版)

    而twitter的snowflake解决了这种需求,最初是Twitter把存储系统从MySQL迁移到Cassandra,因为Cassandra没有顺序的ID生成机制,所以开发了这样一套唯一的ID生成服务。结构雪花的结构如下(每部分用-分开): 0 - ...

    应用级自增ID的生成

    这里我们将分析标题提及的“应用级自增ID”以及其背后的实现机制,结合提供的`TableIdentityGenerator.java`和`TableIdentityVo.java`源代码文件,来解析其工作原理。 首先,自增ID通常在关系型数据库中由主键字段...

    全局自增ID设计方案

    MYCAT是一款开源的数据库中间件,它提供多种方式来实现全局自增ID的生成。 1. **本地文件实现**:这种方式简单易行,但在分布式环境下容易出现问题,例如重新发布或不同实例间无法保证全局递增性。 2. **基于...

    cpp-idgen是一个可以生成全局唯一自增id的分布式的高可用服务

    cpp-idgen是一个专门为生成全局唯一且自增ID设计的分布式高可用服务,它在C++编程语言环境下实现,适用于各种需要大量唯一标识的系统。在现代互联网应用中,尤其是在大型分布式系统中,对唯一ID的需求尤为突出,cpp-...

    donkeyid, php扩展,64位自增id生成器.zip

    1. **分布式一致性**:`donkeyid`可能采用了类似于Twitter的Snowflake算法,将64位ID分为多个部分,如时间戳、工作节点标识和序列号,确保在分布式环境中全局唯一。 2. **时间戳**:前几位用于存储当前时间戳,这样...

    Go-GolangMysql实现的分布式ID生成服务

    在设计时,可以参考Snowflake算法或采用MySQL自增ID结合分布式锁的方式,结合Go的并发特性来提高服务的可扩展性和效率。`go-id-alloc-master`项目可能是这样的实现的一个实例,它为学习和理解这一主题提供了实践素材...

    chapter-disributed-id.zip

    - **TIDB分布式ID**:TiDB提供了分布式自增ID服务,适合大数据场景,保证全局唯一性和单调递增。 3. **设计原则**: - **全局唯一性**:无论在哪个节点生成,ID必须是全局唯一的。 - **趋势递增**:便于数据的...

    sequence v1.0

    高效GUID产生算法(sequence),基于Snowflake实现64位自增ID算法。新增特性:支持自定义允许时间回拨的范围解决跨毫秒起始值每次为0开始的情况(避免末尾必定为偶数,而不便于取余使用问题)解决高并发场景中获取...

    分布式id公开课.pptx

    - 例如,基于Redis的自增操作可以实现分布式自增ID,但每次获取ID都需要网络通信,可能会成为性能瓶颈。 4. **雪花算法(Snowflake算法)**: - 雪花算法由Twitter提出,生成的ID由时间戳、工作节点ID和序列号三...

    MySQL的自增ID(主键) 用完了的解决方法

    - 使用分布式ID生成服务,如Twitter的Snowflake算法,可以生成全局唯一的64位ID,避免在单表内用尽ID。 7. **备份与恢复**: - 在进行任何更改之前,记得先备份数据库,以防止意外情况导致数据丢失。 总之,理解...

Global site tag (gtag.js) - Google Analytics