2020-06-26 dedef8f327eaab92b5c2e2bea7c33f66 99+ 10 分钟 1.6 k 0次访问

Golang游戏服务器知识点散记

Golang游戏服务器知识点零散记录

一、使用Go语言开发大型MMORPG游戏服务器

语言、库、第三方库

1、Golang 语言特性和 C 语言很像。
2、Golang 用组合+接口，C++ 则更多是继承。
3、Golang 服务器如何保证解决游戏服务器存盘一致性问题？stop the world 是需要的，但是 Golang 可以从语言层并发序列化玩家数据，再通过后台存盘。
4、channel 和 goroutine 虽然是 Golang 的语言特性。但是在编写服务器时，其实只有底层用的比较多。
5、Golang 的第三方库很多。
6、Golang 用 interface{}/反射做泛型。

运行期 runtime

1、Go1.6 版后的 GC 优化的已经很好了，如果不是高性能、高并发Web应用，只用 Golang 写游戏服务器，GC 损耗可以忽略不计。
2、崩溃捕捉是标配功能。
3、热更新：官方已经有 plugin 系统，plugin 跨平台。可以告别手动 cgo 做 so 热更新。

开发、部署、调试、优化

1、Jetbrains 的 Goland 是一把利器。
2、Golang 自带性能调优工具，从内存、CPU、阻塞点等几个方面直接出图进行分析，非常直观。
3、Golang 支持交叉编译、跨平台部署，在 windows 上编译输出一个 elf，到 Linux 服务器上直接开跑。

二、Goroutine

1、goroutine 的目的是描述并发编程模型。并发与并行不同，它并不需要多核的硬件支持，它不是一种物理运行状态，而是一种程序逻辑流程。它的主要目的不是利用多核提高运行效率，而是提供一种更容易理解、不容易出错的语言来描述问题。
2、实际上 golang 默认就是运行在单 OS 进程上面的，通过指定环境变量 GOMAXPROCS 才能转身跑在多 OS 进程上面。
3、coroutine 本质上是语言开发者自己实现的、处于 user space 内的线程，无论是 erlang、还是 golang 都是这样。需要解决没有时钟中断，碰着阻塞式 IO，整个进程都会被操作系统主动挂起，需要自己拥有调度控制能力（放在并行环境下面还是挺麻烦的一件事）等等问题。
4、把线程放到 user space 的可以避免陷入 system call 进行上下文切换以及高速缓冲更新，线程本身以及切换等操作可以做得非常的轻量。这也就是 golang 这类语言反复提及的超高并发能力，分分钟给你开上几千个线程不费力。
5、golang 的并发调度在 IO 等易发阻塞的时候才会发生，一般是内封在库函数内；erlang 则更夸张，对每个 coroutine 维持一个计数器，常用语句都会导致这个计数器进行 reduction，一旦到点，立即切换调度函数。
6、中断介入程度的不同，导致 erlang 看上去拥有了 preemptive scheduling(抢先调度) 的能力，而 golang 则是 cooperative scheduling 的。golang 一旦写出纯计算死循环，进程内所有会话必死无疑；要有计算量大，少 IO 的函数还得自己主动叫 runtime.Sched() 来进行调度切换。

三、架构

3.1、一种 bigworld 手游架构设计

进程划分

Gate
首先要有一个 Gate（网关）服务器，负责客户端连接及消息转发到 Game（游戏服），保持客户端到服务端的连接。没有任何逻辑，只做消息加密和解密，以及客户端和服务器消息的转发（相当于两者之间的桥梁）。
GameServer
GameServer 是游戏进程，提供游戏逻辑功能（采用单进程（或者单线程）模型，游戏服务器的瓶颈从来不在 CPU，所以只做逻辑功能的话单线程足够了，在这里没必要用多线程或多进程）。
DBManager
实现数据库的读写，方便 Game 服务器异步读写数据库的数据（有些把数据库读写放在游戏服，没有单独的服务器，那恐怕游戏服单进程就不够用了）。
GameManager
负责管理所有的 GameServer，GameServer 之间消息转发，提供广播到所有 Game 的功能。

协议

客户端与服务器之间协议通信，可以用 tcp 或者 http。主要看游戏模型，如果是那种弱联网单机玩法，用 http 足够了，像天天酷跑之类，只在需要的时候处理一条 http 请求响应。

不过 tcp 用的比较还是比较多的。现在的网络游戏大多数都是 tcp，像 MMORPG 类游戏。我们现在的游戏就是同时用了 http 和 tcp，客户端和游戏服采用 http 协议。只有多人战斗转向战斗服才采用 tcp 长链接。

其实游戏是有 udp 的，在一些高效率的场景下比如 pvp 即时战斗，tcp 的拥塞控制和超时重传并不适合，有些就用的 udp，然后自己做丢包重发，拿网络公平性换游戏局部的效率。

存盘

有数据库就肯定有数据库读写操作，最主要的还是存盘（save），周期存盘还是即时存盘。

即时存盘就是每一次操作数据都存到数据库，当然这样会导致对数据库的操作过于频繁，这是效率的瓶颈之一。

周期存盘也叫固定存盘，就是每隔固定时间存盘一次，比如 10 秒或者 15 秒，这样数据库的压力就会小很多，当然自己就要在内存中做好数据操作，防止数据污染或者存盘不上导致回档。

开源技术

protobuf
全称 Google Protocol Buffers，是 google 开发的的一套用于数据存储，网络通信时用于协议编解码的工具库。它和 XML 或者 JSON 差不多，也就是把某种数据结构的信息，以某种格式（XML、JSON）保存起来。protobuf 与 XML 和 JSON 不同在于，protobuf 是基于二进制的，主要用于数据存储、传输协议格式等场合。
zeromq
消息队列，一个稳健、简洁的多进程通讯方案的基础。ZeroMQ 并不是一个对 socket 的封装，不能用它去实现已有的网络协议。它有自己的模式，不同于更底层的点对点通讯模式。它有比 tcp 协议更高一级的协议。（当然 ZeroMQ 不一定基于 TCP 协议，它也可以用于进程间和进程内通讯。）它改变了通讯都基于一对一的连接这个假设。在这里它更适合服务器与服务器之间的通信，比如逻辑服和战斗服之间进行通信。
memcached
一个高性能的分布式内存对象缓存系统，用于动态 Web 应用以减轻数据库负载。它通过在内存中缓存数据和对象来减少读取数据库的次数，从而提高动态、数据库驱动网站的速度。可以用来做缓存，比如客户端本来每次操作都需要操作数据库，会严重影响效率，这时在中间加一层缓存系统，就提升了性能。基于 http 协议的通信用 memcached 是一个不错的选择，如果是 tcp 长链接，直接维护一个在线的内存对象就可以了。类似的技术还有 redis 等。
tcmalloc
内存性能分析
distcc
分布式编译工具，之前每次修改代码都要 make 半个小时，用 distcc 多台电脑同时帮你编译，速度快很多。

3.2、为什么像王者荣耀这样的游戏 Server 不愿意使用微服务？

1、回答一

比如 moba 类游戏/王者荣耀/LOL，就看王者荣耀的客户端吧，想象一下。

账号系统，符文系统，英雄系统，皮肤系统，好友系统，好友之间 messaging，这些都是常规操作，如果流量足够大，当然可以用微服务的架构去做。

不过这不是这个游戏的核心，核心是 MOBA：Multiplayer online battle arena。特性是什么？

10 个人之间各种游戏事件的高速多向通讯 streaming/broadcast/multicast/pubsub 各种通讯模式。

所以游戏的核心在于小规模群体之间的高速网络通信。就是对方说的 realtime。多了一个 10ms 的延迟玩家就接受不了了。

微服务为了把业务完美拆解，把原来的同一个进程里的模块拆分成不同的服务，显著增加额外的网络开销。更别说什么 service mesh，各种 gateway，proxy，sidecar，简直就是担心延迟太低。
微服务基本只有 request/response 的模式。做不了 streaming？微服务通常要求应用是无状态的才能做到水平扩展。streaming 本身就是加入了状态。
我可以想像，为了提高通讯的性能，一场英雄联盟游戏很可能会使用同一个服务器负责这 10 个玩家之间的通讯，这样就使得数据可以在本地交换，性能最大化。这对客户端或者说服务端统一网关的要求是必须支持 sticky routing。假设客户端连接断了，接下来的必须重连之前的同一个服务器。微服务的 stateless，水平扩展要求本身就是反 sticky routing 的，因为 sticky routing 本身就是状态。
对服务端集群来说，同时有无数个王者荣耀的比赛在进行，每个都可以看成一个沙盒，每个沙盒都处于一个不同的状态：塔被推了几个了，你被杀了几次了，对面几个超神了，20 分钟到了没。这些都是长时间存在的状态，直到游戏结束，服务端才可以清理一场游戏的状态。所以虽然不用把这些状态写进持久性存储，但是必然会在内存中存在很长时间，都是状态，反正有状态，就别想用微服务。除非你说把这些状态都移到 redis 里去，那么在服务器在信息流传输到一半还要做一个 remote request，一来一回，延迟就上升了，总之怎样都不好。（比如想象对方在 A 你的水晶，每一次 A 的操作都是一个 event，被 streaming 到服务端的沙盒中，沙盒中有一个流处理器，每次接收到一个你水晶被 A 的 event 都会计算一下你水晶爆了没。这个计算需要极快，你是不可能把你水晶生命值的数据存在远端的。）

像这类游戏，都是对网络，内存，CPU 的优化需求很高，整个游戏进行过程中，几乎不存在什么 RPC call，真的需要 remote data，也应该是prefetch，就是在游戏刚开始的时候加载好。

微服务不是什么银弹，也就是方便拆解一下原来的 CRUD 应用罢了而已，一没触及高级的交互方式，二没触及分布式系统真正的难点：状态，其实没有大家想的那么有用。之所以感觉上好像微服务改变了互联网，只不过 90% 的互联网应用都只是简单小规模的 CRUD 而已。

对方没有听说过微服务完全没有问题，因为这本身就不是什么高深的概念，反而对方听你说一下就知道微服务不适合游戏，说明对方理解能力很强，对游戏系统设计也了解足够深。

2、回答二

微服务本身是为了应对业务逻辑的复杂，需要新的组织接口的方式。游戏本身逻辑其实没有这么复杂，比如大厅就是一些基本功能，修改帐号，登录等。游戏本身就是游戏本身的逻辑。
游戏逻辑服务器本身（比如斗地主等棋牌）因为网络响应性能要求问题（玩家对每个操作的反馈时长敏感度远高于业务系统），所以游戏服务器都是有状态的，状态就存在内存，偶尔会接受 redis，mysql 等是绝对不可以的接受的，关系型数据库仅用来定时异步持久化数据，仅游戏服务器而言持久化在 redis 即可。
游戏服务器一般需要主动推送，所以第一代微服务网关就没办法满足需求，tcp 的没有网关用，spring cloud gateway 的 web socket 也许可以用（但是从防攻击角度讲端游用 TCP 绝对比 web socket 合理）。
服务间通信 rpc 首先 ribbon、feign 等并不是合适，因为都是基于 http 的，用 http 存在一个消息乱序问题，比如玩家出牌两次，在http 就可能出现次序不一致。游戏服务器集群一般使用长连接互联。
游戏逻辑服务器（比如斗地主服务器），一般是不能用 spring mvc 做的，因为线程模型完全不同。多线程模型处理游戏性能差还非常复杂，一般都是使用单进程/线程驱动固定数量房间的方式（这也是为何服务器一定有状态，一定不能直接读写 mysql）。一般就直接 netty 了。
自动扩容在游戏这边叫做开服，早就有固定流程和工具和限流方式了。
游戏很多操作不存在服务降级熔断，不行就要直接报错给用户。
大厅服务器登录注册等的确可以做微服务，但是其实也不是做微服务，就是几个接口有自动水平扩容的方案即可。服务注册发现用处不大，开服都是确定的事情，还有一系列运营手段配合，关服也是绝对不能随便关的。
游戏处理的流量真的不算多，你在线 1 万的棋牌游戏已经很赚钱了，10W 就是个特别厉害的产品了。
一些独立的服务器比如充值之类的需要微服务化么？只能说这种服务器都需要微服务处理了，项目组做梦都能笑醒。

虽然上面说了很多点，但是其实也是可以考虑用 spring cloud 改造的，因为游戏集群一样有注册中心，需要服务发现，需要编排启动顺序，只是spring cloud 没有为了游戏设计而已，比如至少要完全支持 webflux吧，需要一个单线程的长连接最好支持 protobuf rpc 框架吧（集成服务发现相关功能与接口），网关支持 tcp 或者至少封装或者暴露一些 netty 的 decoder encoder（或者允许注入）等等。

3.3、游戏中排行榜的实现

游戏开发中排行榜经常出现，接触过的排行榜有两种。一种是由玩家挑战排名比自己靠前的其他玩家，胜利后交换位置；另一种是根据玩家的某特性对所有玩家进行排序。第一种只涉及到两个玩家数据的变化，实现起来比较简单，因此只记录第二种情况。

1、需求

排行榜内容是有序的所有玩家信息（以等级为例）
玩家等级变化后，更新排行榜
根据玩家 id 获取在排行榜中的排名
获取排行榜中特定排名的玩家

2、思路

思路一
如果用关系型数据库的话，实现排行版比较简单，一条 SQL 即可。由于游戏服务器并发量大、排行榜数据变化频繁，用 SQL 显然不合适。
思路二
用数组作为排行榜存放玩家信息并对其进行排序。有新玩家加入或玩家等级变化时，重新排序。这样的好处是获取特定排名的玩家时很快，时间复杂度仅仅是 O(1)。但是获取某玩家的排名时需要遍历整个数组，时间复杂度是 O(n)。有新玩家加入或玩家信息有变化时，需要重新排序，以归并排序为例，其平均时间复杂度为 O(nlogn)。每次更新排行榜都需要排序，不断地排序似乎并不优雅。于是考虑定期排序，如每分钟排一次序。
思路三
思路二的情况下，如果某玩家的排名上升了 1000 名，操作数组就要把被他超越的 1000 个玩家数据都向后移动。于是考虑了使用链表替代数组。但是这就带来了新的问题，通过排名获取玩家时，就要遍历链表，思路二中这个操作的时间复杂度为 O(1)，现在就变成了 O(n)。故不能使用链表，或者说不能直接使用普通的链表。
思路四
借助 Redis。用 Redis 的 zset 来处理排行榜。
思路五
用 ssdb，是兼容 Redis 的 api。

3、zset 的 golang 实现

package zset

import (
	"math/rand"
)

const zSkiplistMaxlevel = 32

type (
	skipListLevel struct {
		forward *skipListNode
		span    uint64
	}

	skipListNode struct {
		objID    int64
		score    float64
		backward *skipListNode
		level    []*skipListLevel
	}
	obj struct {
		key        int64
		attachment interface{}
		score      float64
	}

	skipList struct {
		header *skipListNode
		tail   *skipListNode
		length int64
		level  int16
	}
	// SortedSet is the final exported sorted set we can use
	SortedSet struct {
		dict map[int64]*obj
		zsl  *skipList
	}
	zrangespec struct {
		min   float64
		max   float64
		minex int32
		maxex int32
	}
	zlexrangespec struct {
		minKey int64
		maxKey int64
		minex  int
		maxex  int
	}
)

func zslCreateNode(level int16, score float64, id int64) *skipListNode {
	n := &skipListNode{
		score: score,
		objID: id,
		level: make([]*skipListLevel, level),
	}
	for i := range n.level {
		n.level[i] = new(skipListLevel)
	}
	return n
}

func zslCreate() *skipList {
	return &skipList{
		level:  1,
		header: zslCreateNode(zSkiplistMaxlevel, 0, 0),
	}
}

const zSkiplistP = 0.25 /* Skiplist P = 1/4 */

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and _ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
func randomLevel() int16 {
	level := int16(1)
	for float32(rand.Int31()&0xFFFF) < (zSkiplistP * 0xFFFF) {
		level++
	}
	if level < zSkiplistMaxlevel {
		return level
	}
	return zSkiplistMaxlevel
}

/* zslInsert a new node in the skiplist. Assumes the element does not already
 * exist (up to the caller to enforce that). The skiplist takes ownership
 * of the passed SDS string 'obj'. */
func (zsl *skipList) zslInsert(score float64, id int64) *skipListNode {
	update := make([]*skipListNode, zSkiplistMaxlevel)
	rank := make([]uint64, zSkiplistMaxlevel)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		/* store rank that is crossed to reach the insert position */
		if i == zsl.level-1 {
			rank[i] = 0
		} else {
			rank[i] = rank[i+1]
		}
		if x.level[i] != nil {
			for x.level[i].forward != nil &&
				(x.level[i].forward.score < score ||
					(x.level[i].forward.score == score && x.level[i].forward.objID < id)) {
				rank[i] += x.level[i].span
				x = x.level[i].forward
			}
		}
		update[i] = x
	}
	/* we assume the element is not already inside, since we allow duplicated
	 * scores, reinserting the same element should never happen since the
	 * caller of zslInsert() should test in the hash table if the element is
	 * already inside or not. */
	level := randomLevel()
	if level > zsl.level {
		for i := zsl.level; i < level; i++ {
			rank[i] = 0
			update[i] = zsl.header
			update[i].level[i].span = uint64(zsl.length)
		}
		zsl.level = level
	}
	x = zslCreateNode(level, score, id)
	for i := int16(0); i < level; i++ {
		x.level[i].forward = update[i].level[i].forward
		update[i].level[i].forward = x

		/* update span covered by update[i] as x is inserted here */
		x.level[i].span = update[i].level[i].span - (rank[0] - rank[i])
		update[i].level[i].span = (rank[0] - rank[i]) + 1
	}

	/* increment span for untouched levels */
	for i := level; i < zsl.level; i++ {
		update[i].level[i].span++
	}

	if update[0] == zsl.header {
		x.backward = nil
	} else {
		x.backward = update[0]

	}
	if x.level[0].forward != nil {
		x.level[0].forward.backward = x
	} else {
		zsl.tail = x
	}
	zsl.length++
	return x
}

/* Internal function used by zslDelete, zslDeleteByScore and zslDeleteByRank */
func (zsl *skipList) zslDeleteNode(x *skipListNode, update []*skipListNode) {
	for i := int16(0); i < zsl.level; i++ {
		if update[i].level[i].forward == x {
			update[i].level[i].span += x.level[i].span - 1
			update[i].level[i].forward = x.level[i].forward
		} else {
			update[i].level[i].span--
		}
	}
	if x.level[0].forward != nil {
		x.level[0].forward.backward = x.backward
	} else {
		zsl.tail = x.backward
	}
	for zsl.level > 1 && zsl.header.level[zsl.level-1].forward == nil {
		zsl.level--
	}
	zsl.length--
}

/* Delete an element with matching score/element from the skiplist.
 * The function returns 1 if the node was found and deleted, otherwise
 * 0 is returned.
 *
 * If 'node' is NULL the deleted node is freed by zslFreeNode(), otherwise
 * it is not freed (but just unlinked) and *node is set to the node pointer,
 * so that it is possible for the caller to reuse the node (including the
 * referenced SDS string at node->obj). */
func (zsl *skipList) zslDelete(score float64, id int64) int {
	update := make([]*skipListNode, zSkiplistMaxlevel)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil &&
			(x.level[i].forward.score < score ||
				(x.level[i].forward.score == score &&
					x.level[i].forward.objID < id)) {
			x = x.level[i].forward
		}
		update[i] = x
	}
	/* We may have multiple elements with the same score, what we need
	 * is to find the element with both the right score and object. */
	x = x.level[0].forward
	if x != nil && score == x.score && x.objID == id {
		zsl.zslDeleteNode(x, update)
		return 1
	}
	return 0 /* not found */
}

func zslValueGteMin(value float64, spec *zrangespec) bool {
	if spec.minex != 0 {
		return value > spec.min
	}
	return value >= spec.min
}

func zslValueLteMax(value float64, spec *zrangespec) bool {
	if spec.maxex != 0 {
		return value < spec.max
	}
	return value <= spec.max
}

/* Returns if there is a part of the zset is in range. */
func (zsl *skipList) zslIsInRange(ran *zrangespec) bool {
	/* Test for ranges that will always be empty. */
	if ran.min > ran.max ||
		(ran.min == ran.max && (ran.minex != 0 || ran.maxex != 0)) {
		return false
	}
	x := zsl.tail
	if x == nil || !zslValueGteMin(x.score, ran) {
		return false
	}
	x = zsl.header.level[0].forward
	if x == nil || !zslValueLteMax(x.score, ran) {
		return false
	}
	return true
}

/* Find the first node that is contained in the specified range.
 * Returns NULL when no element is contained in the range. */
func (zsl *skipList) zslFirstInRange(ran *zrangespec) *skipListNode {
	/* If everything is out of range, return early. */
	if !zsl.zslIsInRange(ran) {
		return nil
	}

	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		/* Go forward while *OUT* of range. */
		for x.level[i].forward != nil &&
			!zslValueGteMin(x.level[i].forward.score, ran) {
			x = x.level[i].forward
		}
	}
	/* This is an inner range, so the next node cannot be NULL. */
	x = x.level[0].forward
	//serverAssert(x != NULL);

	/* Check if score <= max. */
	if !zslValueLteMax(x.score, ran) {
		return nil
	}
	return x
}

/* Find the last node that is contained in the specified range.
 * Returns NULL when no element is contained in the range. */
func (zsl *skipList) zslLastInRange(ran *zrangespec) *skipListNode {

	/* If everything is out of range, return early. */
	if !zsl.zslIsInRange(ran) {
		return nil
	}
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		/* Go forward while *IN* range. */
		for x.level[i].forward != nil &&
			zslValueLteMax(x.level[i].forward.score, ran) {
			x = x.level[i].forward
		}
	}
	/* This is an inner range, so this node cannot be NULL. */
	//serverAssert(x != NULL);

	/* Check if score >= min. */
	if !zslValueGteMin(x.score, ran) {
		return nil
	}
	return x
}

/* Delete all the elements with score between min and max from the skiplist.
 * Min and max are inclusive, so a score >= min || score <= max is deleted.
 * Note that this function takes the reference to the hash table view of the
 * sorted set, in order to remove the elements from the hash table too. */
func (zsl *skipList) zslDeleteRangeByScore(ran *zrangespec, dict map[int64]*obj) uint64 {
	removed := uint64(0)
	update := make([]*skipListNode, zSkiplistMaxlevel)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil {
			var condition bool
			if ran.minex != 0 {
				condition = x.level[i].forward.score <= ran.min
			} else {
				condition = x.level[i].forward.score < ran.min
			}
			if !condition {
				break
			}
			x = x.level[i].forward
		}
		update[i] = x
	}

	/* Current node is the last with score < or <= min. */
	x = x.level[0].forward

	/* Delete nodes while in range. */
	for x != nil {
		var condition bool
		if ran.maxex != 0 {
			condition = x.score < ran.max
		} else {
			condition = x.score <= ran.max
		}
		if !condition {
			break
		}
		next := x.level[0].forward
		zsl.zslDeleteNode(x, update)
		delete(dict, x.objID)
		// Here is where x->obj is actually released.
		// And golang has GC, don't need to free manually anymore
		//zslFreeNode(x)
		removed++
		x = next
	}
	return removed
}

func (zsl *skipList) zslDeleteRangeByLex(ran *zlexrangespec, dict map[int64]*obj) uint64 {
	removed := uint64(0)

	update := make([]*skipListNode, zSkiplistMaxlevel)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil && !zslLexValueGteMin(x.level[i].forward.objID, ran) {
			x = x.level[i].forward
		}
		update[i] = x
	}

	/* Current node is the last with score < or <= min. */
	x = x.level[0].forward

	/* Delete nodes while in range. */
	for x != nil && zslLexValueLteMax(x.objID, ran) {
		next := x.level[0].forward
		zsl.zslDeleteNode(x, update)
		delete(dict, x.objID)
		removed++
		x = next
	}
	return removed
}

func zslLexValueGteMin(id int64, spec *zlexrangespec) bool {
	if spec.minex != 0 {
		return compareKey(id, spec.minKey) > 0
	}
	return compareKey(id, spec.minKey) >= 0
}

func compareKey(a, b int64) int8 {
	if a == b {
		return 0
	} else if a > b {
		return 1
	}
	return -1
}

func zslLexValueLteMax(id int64, spec *zlexrangespec) bool {
	if spec.maxex != 0 {
		return compareKey(id, spec.maxKey) < 0
	}
	return compareKey(id, spec.maxKey) <= 0
}

/* Delete all the elements with rank between start and end from the skiplist.
 * Start and end are inclusive. Note that start and end need to be 1-based */
func (zsl *skipList) zslDeleteRangeByRank(start, end uint64, dict map[int64]*obj) uint64 {
	update := make([]*skipListNode, zSkiplistMaxlevel)
	var traversed, removed uint64

	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil && (traversed+x.level[i].span) < start {
			traversed += x.level[i].span
			x = x.level[i].forward
		}
		update[i] = x
	}

	traversed++
	x = x.level[0].forward
	for x != nil && traversed <= end {
		next := x.level[0].forward
		zsl.zslDeleteNode(x, update)
		delete(dict, x.objID)
		removed++
		traversed++
		x = next
	}
	return removed
}

/* Find the rank for an element by both score and obj.
 * Returns 0 when the element cannot be found, rank otherwise.
 * Note that the rank is 1-based due to the span of zsl->header to the
 * first element. */
func (zsl *skipList) zslGetRank(score float64, key int64) int64 {
	rank := uint64(0)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil &&
			(x.level[i].forward.score < score ||
				(x.level[i].forward.score == score &&
					x.level[i].forward.objID <= key)) {
			rank += x.level[i].span
			x = x.level[i].forward
		}

		/* x might be equal to zsl->header, so test if obj is non-NULL */
		if x.objID == key {
			return int64(rank)
		}
	}
	return 0
}

/* Finds an element by its rank. The rank argument needs to be 1-based. */
func (zsl *skipList) zslGetElementByRank(rank uint64) *skipListNode {
	traversed := uint64(0)
	x := zsl.header
	for i := zsl.level - 1; i >= 0; i-- {
		for x.level[i].forward != nil && (traversed+x.level[i].span) <= rank {
			traversed += x.level[i].span
			x = x.level[i].forward
		}
		if traversed == rank {
			return x
		}
	}
	return nil
}

/*-----------------------------------------------------------------------------
 * Common sorted set API
 *----------------------------------------------------------------------------*/

// New creates a new SortedSet and return its pointer
func New() *SortedSet {
	s := &SortedSet{
		dict: make(map[int64]*obj),
		zsl:  zslCreate(),
	}
	return s
}

// Length returns counts of elements
func (z *SortedSet) Length() int64 {
	return z.zsl.length
}

// Set is used to add or update an element
func (z *SortedSet) Set(score float64, key int64, dat interface{}) {
	v, ok := z.dict[key]
	z.dict[key] = &obj{attachment: dat, key: key, score: score}
	if ok {
		/* Remove and re-insert when score changes. */
		if score != v.score {
			z.zsl.zslDelete(v.score, key)
			z.zsl.zslInsert(score, key)
		}
	} else {
		z.zsl.zslInsert(score, key)
	}
}

// IncrBy ..
func (z *SortedSet) IncrBy(score float64, key int64) (float64, interface{}) {
	v, ok := z.dict[key]
	if !ok {
		// use negative infinity ?
		return 0, nil
	}
	if score != 0 {
		z.zsl.zslDelete(v.score, key)
		v.score += score
		z.zsl.zslInsert(v.score, key)
	}
	return v.score, v.attachment
}

// Delete removes an element from the SortedSet
// by its key.
func (z *SortedSet) Delete(key int64) (ok bool) {
	v, ok := z.dict[key]
	if ok {
		z.zsl.zslDelete(v.score, key)
		delete(z.dict, key)
		return true
	}
	return false
}

// GetRank returns position,score and extra data of an element which
// found by the parameter key.
// The parameter reverse determines the rank is descent or ascend，
// true means descend and false means ascend.
func (z *SortedSet) GetRank(key int64, reverse bool) (rank int64, score float64, data interface{}) {
	v, ok := z.dict[key]
	if !ok {
		return -1, 0, nil
	}
	r := z.zsl.zslGetRank(v.score, key)
	if reverse {
		r = z.zsl.length - r
	} else {
		r--
	}
	return int64(r), v.score, v.attachment

}

// GetData returns data stored in the map by its key
func (z *SortedSet) GetData(key int64) (data interface{}, ok bool) {
	o, ok := z.dict[key]
	if !ok {
		return nil, false
	}
	return o.attachment, true
}

// GetDataByRank returns the id,score and extra data of an element which
// found by position in the rank.
// The parameter rank is the position, reverse says if in the descend rank.
func (z *SortedSet) GetDataByRank(rank int64, reverse bool) (key int64, score float64, data interface{}) {
	if rank < 0 || rank > z.zsl.length {
		return 0, 0, nil
	}
	if reverse {
		rank = z.zsl.length - rank
	} else {
		rank++
	}
	n := z.zsl.zslGetElementByRank(uint64(rank))
	if n == nil {
		return 0, 0, nil
	}
	dat, _ := z.dict[n.objID]
	if dat == nil {
		return 0, 0, nil
	}
	return dat.key, dat.score, dat.attachment
}

// Range implements ZRANGE
func (z *SortedSet) Range(start, end int64, f func(float64, int64, interface{})) {
	z.commonRange(start, end, false, f)
}

// RevRange implements ZREVRANGE
func (z *SortedSet) RevRange(start, end int64, f func(float64, int64, interface{})) {
	z.commonRange(start, end, true, f)
}

func (z *SortedSet) commonRange(start, end int64, reverse bool, f func(float64, int64, interface{})) {
	l := z.zsl.length
	if start < 0 {
		start += l
		if start < 0 {
			start = 0
		}
	}
	if end < 0 {
		end += l
	}

	if start > end || start >= l {
		return
	}
	if end >= l {
		end = l - 1
	}
	span := (end - start) + 1

	var node *skipListNode
	if reverse {
		node = z.zsl.tail
		if start > 0 {
			node = z.zsl.zslGetElementByRank(uint64(l - start))
		}
	} else {
		node = z.zsl.header.level[0].forward
		if start > 0 {
			node = z.zsl.zslGetElementByRank(uint64(start + 1))
		}
	}
	for span > 0 {
		span--
		k := node.objID
		s := node.score
		f(s, k, z.dict[k].attachment)
		if reverse {
			node = node.backward
		} else {
			node = node.level[0].forward
		}
	}
}