README
¶
XDS - eXtensible Data Structure Sets
(第三方可扩展的 Golang 高性能数据结构和数据类型合集)
A third-party extensible collection of high-performance data structures and data types in Go
- XDS - eXtensible Data Structure
（第三方可扩展的 Go 语言中高性能数据结构和数据类型合集） - XDS 介绍：（什么是 Xds）
- XDS - XMap 概要介绍
- 如何使用 XMap？
- XMap 内部是如何实现的？
- XDS 项目开发者
- XDS 技术交流
XDS 介绍：（什么是 Xds）
XDS - eXtensible Data Structure（第三方可扩展的 Go 语言中高性能数据结构和数据类型合集）
XDS 主要是为了解决现有 Go 语言官方内置的各类数据结构性能在高并发场景中不尽如人意的情况而开发，核心主要是依赖于 XMM 内存管理库基础之上开发，保证了高性能和内存可控。
XDS 集合目前主要包含：
- XMap - 高性能的类似 map/sync.map 的 Map 型数据结构类型（已开源）
- XSlice - 高性能类似 slice 的数组型数据结构类型（开发中）
- XChannel - 高性能的 channel 管道类型结构（调研中）
- 更多...
XDS - XMap 概要介绍
XMap 是属于高性能开源 Go 数据结构 Xds 中的 map 数据结构类型的实现，主要是基于高性能内存管理库 XMM 基础之上进行的开发，主要弥补了 Go 内置 map 的无法并发读写，并且总体读写性能比较差的问题而开发。
为什么要设计 XMap？
现有 Golang 中的 map 数据结构无法解决并发读写问题，Sync.map 并发性能偏差，针对这个情况，各种高性能底层服务需要一个高性能、大容量、高并发、无 GC 的 Map，所以开发实现 XMap。 针对我们需求调研了市场上主要的 hashmap 结构，不能满足我们性能和功能要求。
XMap 设计目标是什么？
要求设计一个可以并发读写不会出现 panic，要求并发读写 200w+ OPS/s 的并发 map 结构。 （写 20%，读 80% 场景；说明：go 自带 map 读写性能在 80w ops/s，大量并发读写下可能 panic；sync.map 写入性能在 100w OPS/s）
XMap 的技术特点
- 绝对高性能的 map 数据结构（map 的 3 倍，sync.map 的 2 倍并发性能）
- 内部实现机制对比 Go 原生 map/sync.map 技术设计上要更细致，更考虑性能，使用包括开地址法，红黑树等等结构提升性能；
- 为了节约内存，初始的值比较低，但是依赖于 XMM 高性能内存扩容方式，能够快速进行内存扩容，保证并发写入性能
- 底层采用 XMM 内存管理，不会受到 Go 系统本身 GC 机制的卡顿影响，保证高性能；
- 提供 API 更具备扩展性，在一些高性能场景提供更多调用定制设置，并且能够同时支持 map 类型操作和底层 hash 表类型操作，适用场景更多；
- 其他特性
XMap 性能数据和实现对比
XMap 目前并发读写场景下性能可以达到 200 万 op/s，对比原生 map 单机性能 80 万 op/s，提升了 3 倍 +，对比 Go 官方扩展库 sync.Map 性能有 2 倍的提升。
XMap 与 Go 官方数据结构特点对比：(20% 写入，80% 读场景)
| map 模块 | 性能数据 |
加锁机制 | 底层数据结构 | 内存机制 |
|---|---|---|---|---|
| map | 80w+ read/s 并发读写会 panic |
无 | Hashtable + Array | Go gc |
| sync.Map | 100w+ op/s | RWMutex | map | Go gc |
| Xds.XMap | 200w+ op/s | CAS + RWMutex | Hashtable + Array + RBTree | XMM |
如何使用 XMap？
快速使用：
- 下载对应包
go get -u github.com/heiyeluren/xds
go get -u github.com/heiyeluren/xmm
- 快速包含调用库：
//注意：本代码只是伪代码，大家最好看这个使用测试案例更充分一些
//详细使用案例：https://github.com/heiyeluren/xds/blob/main/example/xmap_test0.go
//快速使用入门：https://github.com/heiyeluren/xds/blob/main/example/xmap_test1.go
import (
xmm "github.com/heiyeluren/xmm"
xds "github.com/heiyeluren/xds"
xmap "github.com/heiyeluren/xds/xmap"
)
// 创建一个 XMM 内存块
f := &xmm.Factory{}
mm, err := f.CreateMemory(0.75)
// 构建一个 map[string]string 的 xmap
m, err := xmap.NewMap(mm, xds.String, xds.String)
// 写入、读取、删除一个元素
err = m.Set("name", "heiyeluren")
ret, key_exists, err := m.Get("name")
err = m.Remove("name")
// 遍历整个map
m.Each(func(key, val interface{}) error {
fmt.Printf("For each XMap all key:[%s] value:[%s] \n", key, val)
return nil
})
//...
- 执行对应代码
go run map-test.go
XMap 各类 API 使用案例
- Xmap 快速使用入门
- XMap 详细使用示例 -
- 更多案例（期待）
以上代码案例执行输出：
XMap 内部是如何实现的？
- 《Xds-XMap技术设计与实现》 -
XDS 项目开发者
| 项目角色 | 项目成员 |
|---|---|
| 项目发起人/负责人 | 黑夜路人 ( @heiyeluren ) 老张 ( @Zhang-Jun-tao ) |
| 项目开发者 | 老张 ( @Zhang-Jun-tao ) 黑夜路人 ( @heiyeluren ) Viktor ( @guojun1992 ) |
XDS 技术交流
XDS 还在早期，当然也少不了一些问题和 bug，欢迎大家一起共创，或者直接提交 PR 等等。
欢迎加入 XDS 技术交流微信群，要加群，可以先添加如下微信让对方拉入群：
（如无法看到图片，请手工添加微信： heiyeluren2017 ）
Documentation
¶
Index ¶
- Variables
- func ByteToRaw(kind Kind, data []byte) (content interface{}, err error)
- func Marshal(kind Kind, content interface{}) (data []byte, err error)
- func RawToByte(kind Kind, content interface{}) (data []byte, err error)
- func UnMarshal(kind Kind, data []byte) (content interface{}, err error)
- type Kind
Constants ¶
This section is empty.
Variables ¶
var InvalidType = errors.New("Kind type Error")
类型错误 type error
Functions ¶
Types ¶
Source Files
Directories
¶
| Path | Synopsis |
|---|---|
|
entry
Package entry Package redblacktree provides a pure Golang implementation of a red-black tree as described by Thomas H. Cormen's et al.
|
Package entry Package redblacktree provides a pure Golang implementation of a red-black tree as described by Thomas H. Cormen's et al. |