Moebius（莫比斯）
介绍

Moebius数据库多活集群是格瑞趋势为SQL Server数据库研发的能够同时满足可用性、数据安全、容灾、读写分离、负载均衡的一站式多活集群。
集群的名字取自
Moebius环，寓意无限扩展。

Moebius
采用
“share nothing”
架构，每个节点的
SQL Server
服务独立安装，使用每个服务器自己存储介质内的数据库文件。不基于共享存储设备，也不基于磁盘镜像等功能，通过
SQL Server
的日志同步技术实现各节点中数据的一致性。
在主节点写入数据时会产生日志，
Moebius
捕获并传输日志到其他节点，并通过
REDO
技术把日志转换成数据。因此每个节点的
SQL Server
服务都是启动的，数据都是
“
活
”
的。
Moebius
有实时和准实时两种同步方式，不同的节点可以使用不同的同步方式。

Moebius
通过
“
网络心跳
”
及
“
仲裁机制
”
实现故障监控，当侦测到某节点发生故障并经过仲裁后，将此节点剥离出集群，如果故障节点是主节点，则会进行自动故障转移，重新选择健康的节点作为主节点。节点故障恢复后会自动从主节点同步差异数据，同步完成后加入到集群中。

Moebius
的调度引擎支持连接级和
SQL
语句级两种调度方式，通过规则的配置，在不改动或者少改动应用程序的前提下，透明的实现读写分离、负载均衡。

Moebius集群的
架构


Moebius集群采用无共享磁盘架构
Moebius集群由一组数据库服务器组成，每个服务器上安装相同的数据库，集群支持无共享磁盘架构，各机器可以不连接一个共享设备，数据可以存储在每个机器自己的存储介质中。

无共享磁盘架构，使得存储不再是单点，系统可用性提高，同时还可以充分利用集群中每个机器的CPU、I/O等硬件来实现集群的高性能。
无需价格高昂的共享磁盘柜，只要使用2台服务器即可轻松构筑低成本的集群。

Moebius集群架构的分类


依据数据是否分区，Moebius集群架构分为标准架构和高级架构：
标准架构
：每个节点中具有完全相同的数据，每个节点都拥有数据全集。
高级架构
：每个节点中数据是不同的，每个节点只拥有数据全集的一部分。
Moebius For SQL Server标准架构
Moebius集群是一组相互独立的服务器，通过相互协作形成一个统一的整体。集群中多个节点相互连接，这样冗余的硬件架构不但可以避免单点故障而且提供了杰出的故障恢复能力。一旦发生系统失败，Moebius集群对用户保证最高的可用性，保障关键是业务数据不丢失。

Moebius 集群标准架构
一个集群数据库可以看作是一个被多个应用实例访问的单一数据库。在Moebius集群中，每个SQL Server实例在各自的服务器上运行。随着应用的增加，当需要添加额外的资源时，可以在不停机的情况下很容易地增加节点。
标准架构中间件工作原理
中间件驻留在每个机器的数据库中，监测数据库内数据的变化,并将变化的数据同步到其它数据库中。数据同步完成后客户端才会得到响应，同步过程是并发完成的，因此同步到多个数据库和同步到一个数据库的时间基本相等；另外同步过程是在事务环境下完成的，保证了多份数据的数据一致性。

正因为中间件宿主在数据库中，所以中间件不但能知道数据的变化，而且知道引起数据变化的SQL语句，根据SQL语句的类型智能地采取不同的数据同步策略以保证数据同步成本的最小化：
1. 数据条数很少，数据内容也不大，则直接同步数据。
2. 数据条数很少，但是里面包含大数据类型，比如文本，二进制数据等， 则先对数据进行压缩然后再
同步，从而减少网络带宽的占用和传输所用的时间。
3. 数据条数很多，此时中间件会获取造成数据变化的SQL语句， 然后对SQL语句进行解析，分析其
执行计划和执行成本，并选择是同步数据还是同步SQL语句到其他的数据库中。在对表结构进行调整
或者批量更改数据的时候，这种同步策略非常有用。
Moebius For SQL Server高级架构
在高级架构中，采用数据分区技术，依据某种规则把数据分散到多个数据库中。
数据为什么分区？
1.当数据量很大的时候，即使服务器在没有任何压力的情况下，某些复杂的查询操作都会非常缓慢，影
响最终用户的体验。
2.在大数据量下对数据库的装载与导出，备份与恢复，结构的调整，索引的调整等都会让数据库停止服
务或者高负荷运转很长时间，影响数据库的可用性和易管理性。
3.面对这样的应用环境，仅仅依靠提升服务器的硬件配置是起不到作用的，比较好的办法是通过数据分
区，把数据分成更小的部分来提高数据库的可用性和易管理性。
4.分区把各部分数据放到不同的机器中，每次查询可以由多个机器上的CPU、I/O来共同负载，通过
各节点并行处理数据来提高性能。

系统结构
Moebius For SQL Server高级架构
在结构上分访问层数据库和数据层数据库两部分。
访问层：
访问层数据库只有原来数据库的结构没有数据，处理提交上来的
SQL语句并调度执行。访问层数
据库可以由多个机器来负载均衡。
数据层：
数据层数据库就是原来的数据库，但是可以有多个冗余对查询进行负载均衡，以提高整个系统
的性能，Moebius For SQL Server保证多个数据库的一致性；数据层数据库不暴露给用户和业务程序，用户和业务程序面对的是访问层数据库。

通过访问层和数据层构建出一个网格集群来实现集群的高可用性和负载均衡，访问层和数据层的数据库是可以扩展的。(每列中各节点的数据是相同的，每行构成数据的全集；图中数据数据层设计为5×2矩阵，在实际应用中要依据业务的特点来划分)。
如何分区？
Moebius For SQL Server支持两种分区方式：Hash分区和线性分区。
Hash分区
：是将表按某一字段的值均匀地分布到若干个指定分区中的一种分区方法。
优点：
每个分区内分配的数据比较平均，承载的压力也就比较平均，机器能够得到充分的利用。
缺点：
不易扩展，如果扩展新的分区会涉及到数据的重新分配，因此在设计的时候要提前规划好。
Moebius For SQL Server支持把多个分区数据放在一个机器上然后再根据压力逐个的拆到新机器中去，这样既可以保证了分区的规划又不浪费机器，实现了线性扩展。
线性分区
：即范围分区，将表按某一字段的取值范围进行分区，如按时间，每个月的数据在一个分区中。
优点
：扩展性能比较好，因为数据的增长是有一定规律的。
缺点：
每个分区内数据的压力不是很平均，大部分业务都存在这种现象，越老的数据被访问的频率越低，从而导致各机器面临的压力也不同，因此使机器的利用率不高。
Moebius For SQL Server支持把多个分区数据放在一个机器上，所以可以通过新老分区的交替使用来提高机器的利用率。
分区操作在管理工具中很容易配置，首先设置分区，接下来给每个表选择分区并设置分区字段
.
这样中间件在解析、处理SQL语句的时候就会根据配置把数据分配到相应分区所在的机器中去或者从相应分区中读取数据。和其他一些集群不同的是Moebius For SQL Server的分区是经过抽象的，是完全透明的。

高级架构中间件工作原理
1.中间件解析到查询的SQL语句后，首先分析该语句要查找的表，根据所要查找表的分区配置和SQL语句的WHERE条件计算出要从一个分区中还是多个分区中去取数据，取完数据后在访问层合并后再返回给应用程序。这里要重点说明的是中间件通过分析SQL语句，能够对分区范围进行动态缩小或者放大。SELECT * FROM dbo.UserInfo WHERE UserID = 1，因为UserID是分区字段，所以中间件只会从一个分区中查找；SELECT * FROM dbo.UserInfo WHERE UserID IN(3, 4)则会从两个分区中查找；SELECT * FROM dbo.UserInfo WHERE Username = ‘wangzhongtao’，没有使用分区字段作为查询的条件，中间件就会从每个分区列数据库进行查找。对于多个分区列数据进行查询的操作是并行的从而保证总体响应时间的最小化。

2.中间件解析到更新的SQL语句后，首先分析要更新的表，根据要更新表的分区配置和更新语句的SQL语法来计算出要更新一个或者多个分区中的数据。例如INSERT dbo.UserInfo(UserID, Username) VALUES(1, ‘wangzhongtao’)，中间件会解析到UserID = 1，然后根据表的分区配置把数据插入到第一个分区中去。中间件解析到一个更新的SQL语句后，会同时更新同一列中的数据库。第一：更新操作是并行的，整个操作的响应时间和更新一个数据库的响应时间基本相同；第二：整个操作是在事务的环境下完成的，保证了多个数据库中数据是一致的，实现了真正的冗余。
3.中间件解析到一个更新数据库结构的DDL语句，会把该语句同步到其他访问层数据库和所有的数据层数据库中。这样用户就像在使用一个数据库去维护表、索引、存储过程等等，大大降低了用户的管理成本，也降低了出错的机率。这是Moebius For SQL Server 的亮点。

常见问题

虚拟化
\超融合平台下还有做Moebius的必要吗？

虚拟化或者超融合虽然能够保障可用性和数据安全，
但本质上提供的是一个单数据库服务器。如果有在
SQL Server层面的容灾或者读写分离、负载均衡的需求，就是有必要的。

Moebius兼容虚拟化\超融合平台吗？

兼容，
Moebius的节点可以是物理机，也可以是虚拟机，或者是两者的组合。

做了
Moebius后还有必要做存储双活吗？

如果存储设备只是为了数据库服务器提供的，那么是没有必要再做双活的，因为
Moebius的数据就是多份的，既能保障数据安全，又可以随时验证数据的一致性。可以让每个Moebius节点各接一个独立的存储设备，这样既节省了双活模块的成本，又提升了磁盘空间的利用率。

北京格瑞趋势科技有限公司是聚焦于数据服务的高新技术企业，成立于2008年，创始团队及核心技术人员来自微软和雅虎。微软数据平台高级合作伙伴，卫宁健康数据平台战略合作伙伴。通过产品+服务双轮驱动的业务模式，14年间累计服务4000+客户，覆盖互联网、市政、交通、电信、医疗、教育、电力、制造业等各个领域。

最近调研了三款国产化数据库与mysql做对比，调研主要性能指标是大数据写入速度、大数据读取速度以及是否支持分表。

一、测试结果

测试结果与预期的差别很大
1、先说oceanBase社区版这款数据库官网上描述性能非常好，感觉可以秒杀mysql，但实际测试结果单节点的情况下，和mysql数据相当，甚至还差一点点。
2、本人还挺喜欢达梦数据库，因为他仿造oracle保留了oracle的很多特性，本以为他的性能肯定比免费的oceanBase社区版和mysql社区版好很多，结果达梦数据库开始速度确实还可以但随着数据量的增加速度越来越慢有点出乎预料，到了千万级别插入速度慢了很多。
3、金仓数据库本以为和达梦不相上下，结果大跌眼镜。
4、金仓的写入速度不行，读性能比其他数据库都好很多。
5、收费的居然比不过免费的哈哈意料之外。
注：本人非常喜欢oracle可惜不是国产的,就不折腾去测试它了，要不发现他性能最好多尴尬哈哈。

声明：本次实验结果只针对本次实验，不能说明各种数据库的优劣，本次实验的数据库都是按照默认配置安装，没有对任何一种数据做过任何优化。

python针对这四种数据库的测试代码会在后续的博客中发布出来(实际的表和ip会改动)，有兴趣的伙伴可以看看使用python如何操作这四种数据库。


二、测试方法


环境说明：各种数据都是单节点

1、测试框架图

2、写性能
从同一个mysql数据库中一张表中读取14.8W的数据(大概20个字段)，读取后分别向mysql,oceanBbase,达梦,金仓四种数据库批量写入(python程序实现),千万级的数据将写入过程重复8次。

3、读性能
分别向mysql,oceanBbase,达梦,金仓四种数据库读取千万级数据（python实现）

三、国产数据库国内流行度的排名

https://www.modb.pro/dbRank

完整测试代码获取：
（1）登录-注册：http://resources.kittytiger.cn/
（2）搜索：国产数据库oceanBbase,达梦,金仓与mysql数据库的性能对比

五种常见数据类型

Redis中的数据类型指的是 value存储的数据类型，key都是以String类型存储的，value根据场景需要，可以以String、List等类型进行存储。

各数据类型介绍：

Redis数据类型对应的底层数据结构

String 类型的应用场景

常用命令

  • 存放键值：set key value [EX seconds] [PX milliseconds] [NX|XX]


    • [NX|XX] :


      • nx：如果key不存在则建立

      • xx：如果key存在则修改其值，也可以直接使用setnx/setex命令

  • 获取键值：get key

  • 值递增/递减：incr key


    • 如果字符串中的值是数字类型的，可以使用incr命令每次递增，不是数字类型则报错。
    • 一次想递增N用incrby命令，如果是浮点型数据可以用incrbyfloat命令递增。
    • 同样，递减使用decr、decrby命令。

  • 批量存放键值：mset key value [key value ...]

  • 批量获取键值：mget key [key ...]

  • 获取值长度：strlen key

  • 追加内容：append key value

  • 获取部分字符：getrange key start end

缓存对象

使用 String 来缓存对象有两种方式：

  • 直接缓存整个对象的 JSON，命令例子： SET user:1 '{"name":"seven", "age":18}'。
  • 采用将 key 进行分离为 user:ID:属性，采用 MSET 存储，用 MGET 获取各属性值，命令例子： MSET user:1:name seven1 user:1:age 18 user:2:name seven2 user:2:age 20

常规计数

比如计算访问次数、点赞、转发、库存数量等等。

# 初始化文章的阅读量
> SET aritcle:readcount:1001 0
OK
#阅读量+1
> INCR aritcle:readcount:1001
(integer) 1
#阅读量+1
> INCR aritcle:readcount:1001
(integer) 2

分布式锁

之所以采用Redis来作为分布式锁，可以有几方面理由：

  1. redis足够的快
  2. redis提供了
    setnx + expire
    的机制，完全契合分布式锁的实现要点
  3. Redisson
    客户端的流行，使得基于redis的分布式锁更加简单

SET 命令有个 NX 参数可以实现「key不存在才插入」，可以用它来实现分布式锁：

  • 如果 key 不存在，则显示插入成功，可以用来表示加锁成功；
  • 如果 key 存在，则会显示插入失败，可以用来表示加锁失败。

一般而言，还会对分布式锁加上过期时间，分布式锁的命令如下：

SET lock_key unique_value NX PX 10000
  • lock_key 就是 key 键；
  • unique_value 是客户端生成的唯一的标识；
  • NX 代表只在 lock_key 不存在时，才对 lock_key 进行设置操作；
  • PX 10000 表示设置 lock_key 的过期时间为 10s，这是为了避免应用在运行过程中发生异常而无法释放锁。

共享 session 信息

通常情况下可以使用session信息保存用户的登录（会话）状态，由于这些 Session 信息会被保存在服务器端，如果用户一的 Session 信息被存储在服务器一，但第二次访问时用户一被分配到服务器二，这个时候服务器并没有用户一的 Session 信息，就会出现需要重复登录的问题。如下：

可以借助 Redis 对这些 Session 信息进行统一的存储和管理，这样无论请求发送到那台服务器，服务器都会去同一个 Redis 获取相关的 Session 信息，这样就解决了分布式系统下 Session 存储的问题。

List 类型的应用场景

常用命令

  • 存储值：


    • 左端存值：lpush key value [value ...]
    • 右端存值：rpush key value [value ...]
    • 索引存值：lset key index value

  • 弹出元素：


    • 左端弹出：lpop key
    • 右端弹出：rpop key

  • 获取元素个数：llen key

  • 获取列表元素：


    • 两边获取：lrange key start stop
    • 索引获取：lindex key index

  • 删除元素：


    • 根据值删除：lrem key count value
    • 范围删除：ltrim key start stop

消息队列

  • 消息保序：使用 LPUSH + RPOP，对队列进行先进先出的消息处理；满足消息队列的保序性
  • 阻塞读取：使用 BRPOP；阻塞读取队列中的数据，避免消费者不停地调用 RPOP 命令带了不必要的性能损失
  • 重复消息处理：生产者实现全局唯一 ID；满足消息队列的处理重复消息的能力
  • 消息的可靠性：使用 BRPOPLPUSH让消费者程序从一个 List 中读取消息，同时，Redis 会把这个消息再插入到另一个 List（可以叫作备份 List）留存；这样一来，如果消费者程序读了消息但没能正常处理，等它重启后，就可以从备份 List 中重新读取消息并进行处理了。满足消息队列的可靠性

但是有两个问题：

  1. 生产者需要自行实现全局唯一 ID；
  2. 不能以消费组形式消费数据

Hash 类型

常用命令

  • 存放值：


    • 单个：hset key field value
    • 多个：hmset key field value [field value ...]
    • 不存在时：hsetnx key field value

  • 获取字段值：


    • 单个：hget key field
    • 多个：hmget key field [field ...]
    • 获取所有键与值：hgetall key
    • 获取所有字段：hkeys key
    • 获取所有值：hvals key

  • 判断是否存在：hexists key field

  • 获取字段数量：hlen key

  • 递增/减：hincrby key field increment

  • 删除字段：hdel key field [field ...]

缓存对象

一般对象用 String + Json 存储，对象中某些频繁变化的属性可以考虑抽出来用 Hash 类型存储。

购物车

以用户 id 为 key，商品 id 为 field，商品数量为 value，恰好构成了购物车的3个要素，如下图所示。

涉及的命令如下：

  • 添加商品：HSET cart:{用户id} {商品id} 1
  • 添加数量：HINCRBY cart:{用户id} {商品id} 1
  • 商品总数：HLEN cart:
  • 删除商品：HDEL cart:
  • 获取购物车所有商品：HGETALL cart:

Set 类型

聚合计算（并集、交集、差集）场景，比如点赞、共同关注、抽奖活动等。

常用命令

  • 存储值：sadd key member [member ...]

  • 获取所有元素：smembers key

  • 随机获取：srandmember langs count

  • 判断是否存在某member：sismember key member

  • 获取集合中元素个数：scard key

  • 删除集合元素：srem key member [member ...]

  • 弹出元素：spop key [count]

点赞

可以保证
一个用户只能点一个赞
，已经点赞过的用户不能再点赞

# uid:1 用户对文章 article:1 点赞
> SADD article:1 uid:1
(integer) 1
# uid:2 用户对文章 article:1 点赞
> SADD article:1 uid:2
(integer) 1
# uid:3 用户对文章 article:1 点赞
> SADD article:1 uid:3
(integer) 1

# uid:1 取消了对 article:1 文章点赞。
> SREM article:1 uid:1
(integer) 1

# 获取 article:1 文章所有点赞用户 :
> SMEMBERS article:1
1) "uid:3"
2) "uid:2"

# 获取 article:1 文章的点赞用户数量：
> SCARD article:1
(integer) 2

共同关注

Set 类型
支持交集运算
，所以可以用来计算共同关注的好友、公众号等。

key 可以是用户id，value 则是已关注的公众号的id。

# uid:1 用户关注公众号 id 为 5、6、7、8、9
> SADD uid:1 5 6 7 8 9
(integer) 5
# uid:2  用户关注公众号 id 为 7、8、9、10、11
> SADD uid:2 7 8 9 10 11
(integer) 5

# 获取共同关注
> SINTER uid:1 uid:2
1) "7"
2) "8"
3) "9"

# 给 uid:2 推荐 uid:1 关注的公众号：在uid:1中有但是uid:2中没有的
> SDIFF uid:1 uid:2
1) "5"
2) "6"

# 验证某个公众号是否同时被 uid:1 或 uid:2 关注:
> SISMEMBER uid:1 5
(integer) 1 # 返回0，说明关注了
> SISMEMBER uid:2 5
(integer) 0 # 返回0，说明没关注

抽奖活动

存储某活动中中奖的用户名 ，Set 类型因为有去重功能，可以
保证同一个用户不会中奖两次
。

# key为抽奖活动名，value为员工名称，把所有员工名称放入抽奖箱 ：
>SADD lucky Tom Jerry John Sean Marry Lindy Sary Mark
(integer) 5

# 如果允许重复中奖，可以使用 SRANDMEMBER 命令。
# 抽取 1 个一等奖：
> SRANDMEMBER lucky 1
1) "Tom"
# 抽取 2 个二等奖：
> SRANDMEMBER lucky 2
1) "Mark"
2) "Jerry"
# 抽取 3 个三等奖：
> SRANDMEMBER lucky 3
1) "Sary"
2) "Tom"
3) "Jerry"

# 如果不允许重复中奖，可以使用 SPOP 命令。
# 抽取一等奖1个
> SPOP lucky 1
1) "Sary"
# 抽取二等奖2个
> SPOP lucky 2
1) "Jerry"
2) "Mark"
# 抽取三等奖3个
> SPOP lucky 3
1) "John"
2) "Sean"
3) "Lindy"

Zset 类型

排序场景，比如排行榜、电话和姓名排序等。

常用命令

  • 存储值：zadd key [NX|XX] [CH] [INCR] score member [score member ...]
  • 获取元素分数：zscore key member
  • 获取排名范围：zrange key start stop [WITHSCORES]
  • 获取指定分数范围排名：zrangebyscore key min max [WITHSCORES] [LIMIT offset count]
  • 增加指定元素分数：zincrby key increment member
  • 获取集合元素个数：zcard key
  • 获取指定范围分数个数：zcount key min max
  • 删除指定元素：zrem key member [member ...]
  • 获取元素排名：zrank key member

Zset结构

typedef struct zset {
    dict *dict;//哈希表
    zskiplist *zsl;//跳表
} zset;

zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询（如 ZRANGEBYSCORE 操作，利用了跳表），也能进行高效单点查询（如 ZSCORE 操作，利用了hash表）。

排行榜

五篇博文，分别获得赞为 200、40、100、50、150。

# arcticle:1 文章获得了200个赞
> ZADD user:seven:ranking 200 arcticle:1
(integer) 1
# arcticle:2 文章获得了40个赞
> ZADD user:seven:ranking 40 arcticle:2
(integer) 1
# arcticle:3 文章获得了100个赞
> ZADD user:seven:ranking 100 arcticle:3
(integer) 1
# arcticle:4 文章获得了50个赞
> ZADD user:seven:ranking 50 arcticle:4
(integer) 1
# arcticle:5 文章获得了150个赞
> ZADD user:seven:ranking 150 arcticle:5
(integer) 1

# 获取文章赞数最多的 3 篇文章, ZREVRANGE 命令（倒序获取有序集合 key 从start下标到stop下标的元素）
# WITHSCORES 表示把 score 也显示出来
> ZREVRANGE user:seven:ranking 0 2 WITHSCORES
1) "arcticle:1"
2) "200"
3) "arcticle:5"
4) "150"
5) "arcticle:3"
6) "100"

# 获取 100 赞到 200 赞的文章，ZRANGEBYSCORE 命令（返回有序集合中指定分数区间内的成员，分数由低到高排序）
> ZRANGEBYSCORE user:xiaolin:ranking 100 200 WITHSCORES
1) "arcticle:3"
2) "100"
3) "arcticle:5"
4) "150"
5) "arcticle:1"
6) "200"

电话，姓名排序

电话排序

# 将电话号码存储到 SortSet 中，然后根据需要来获取号段：
> ZADD phone 0 13100111100 0 13110114300 0 13132110901 
(integer) 3
> ZADD phone 0 13200111100 0 13210414300 0 13252110901 
(integer) 3
> ZADD phone 0 13300111100 0 13310414300 0 13352110901 
(integer) 3

# 获取所有号码
> ZRANGEBYLEX phone - +
1) "13100111100"
2) "13110114300"
3) "13132110901"
4) "13200111100"
5) "13210414300"
6) "13252110901"
7) "13300111100"
8) "13310414300"
9) "13352110901"

# 获取 132 号段的号码：
> ZRANGEBYLEX phone [132 (133
1) "13200111100"
2) "13210414300"
3) "13252110901"

# 获取132、133号段的号码：
> ZRANGEBYLEX phone [132 (134
1) "13200111100"
2) "13210414300"
3) "13252110901"
4) "13300111100"
5) "13310414300"
6) "13352110901"

姓名排序

> zadd names 0 Toumas 0 Jake 0 Bluetuo 0 Gaodeng 0 Aimini 0 Aidehua 
(integer) 6

# 获取所有人的名字:
> ZRANGEBYLEX names - +
1) "Aidehua"
2) "Aimini"
3) "Bluetuo"
4) "Gaodeng"
5) "Jake"
6) "Toumas"

# 获取名字中大写字母A开头的所有人：
> ZRANGEBYLEX names [A (B
1) "Aidehua"
2) "Aimini"

# 获取名字中大写字母 C 到 Z 的所有人：
> ZRANGEBYLEX names [C [Z
1) "Gaodeng"
2) "Jake"
3) "Toumas"

BitMap（2.2 版新增）：

介绍

适用于二值状态统计的场景。

签到

只记录签到（1）或未签到（0）

# 记录用户 4 月 3 号已签到
SETBIT uid:sign:100:202304 2 1

# 检查该用户 6 月 3 日是否签到
> GETBIT uid:sign:100:202306 3
1

# 统计用户在 6 月份的签到次数
> BITCOUNT uid:sign:100:202206
1

# 统计这个月首次打卡时间；BITPOS key bitValue [start] [end]，start end 表示要检测的范围
BITPOS uid:sign:100:202206 1

判断用户登陆状态

key = login_status 表示存储用户登陆状态集合数据， 将用户 ID 作为 offset，在线就设置为 1，下线设置 0。通过 GETBIT判断对应的用户是否在线。 5000 万用户只需要 6 MB 的空间。

# 表示ID = 10086 的用户已登陆
SETBIT login_status 10086 1

# 检查该用户是否登陆，返回值 1 表示已登录
GETBIT login_status 10086

# 登出，将 offset 对应的 value 设置成 0。
SETBIT login_status 10086 0

连续签到用户总数

把每天的日期作为 Bitmap 的 key，userId 作为 offset，若是打卡则将 offset 位置的 bit 设置成 1。key 对应的集合的每个 bit 位的数据则是一个用户在该日期的打卡记录。

那就可以设置 7 个 Bitmap，对这 7 个 Bitmap 的对应的 bit 位做 『与』运算。那么当一个 userID 在 7 个 Bitmap 对应对应的 offset 位置的 bit = 1 就说明该用户 7 天连续打卡。结果保存到一个新 Bitmap 中，我们再通过 BITCOUNT 统计 bit = 1 的个数便得到了连续打卡 7 天的用户总数了。

HyperLogLog（2.8 版新增）

海量数据基数统计的场景，提供不精确的去重计数。但要注意，HyperLogLog 的统计规则是基于概率完成的，不是非常准确，标准误算率是 0.81%。因此适用于海量数据的场景。

HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的内存空间总是固定的、并且是很小的。在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数，和元素越多就越耗费内存的 Set 和 Hash 类型相比，HyperLogLog 就非常节省空间。

百万级网页 UV 计数

在统计 UV 时，可以用 PFADD 命令（用于向 HyperLogLog 中添加新元素）把访问页面的每个用户都添加到 HyperLogLog 中。

PFADD page1:uv user1 user2 user3 user4 user5

# 可以用 PFCOUNT 命令直接获得 page1 的 UV 值，获取统计结果
PFCOUNT page1:uv

GEO（3.2 版新增）

存储地理位置信息的场景

Redis GEO 操作方法有：

  • geoadd：添加地理位置的坐标。
  • geopos：获取地理位置的坐标。
  • geodist：计算两个位置之间的距离。
  • georadius：根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
  • georadiusbymember：根据储存在位置集合里面的某个地点获取指定范围内的地理位置集合。
  • georadius：以给定的经纬度为中心， 返回键包含的位置元素当中， 与中心的距离不超过给定最大距离的所有位置元素。

GEORADIUS方法参数：

GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

参数说明：

  • m ：米，默认单位。
  • km ：千米。
  • mi ：英里。
  • ft ：英尺。
  • WITHDIST: 在返回位置元素的同时， 将位置元素与中心之间的距离也一并返回。
  • WITHCOORD: 将位置元素的经度和维度也一并返回。
  • WITHHASH: 以 52 位有符号整数的形式， 返回位置元素经过原始 geohash 编码的有序集合分值。这个选项主要用于底层应用或者调试， 实际中的作用并不大。
  • COUNT 限定返回的记录数。
  • ASC: 查找结果根据距离从近到远排序。
  • DESC: 查找结果根据从远到近排序。

滴滴叫车

假设车辆 ID 是 33，经纬度位置是（116.034579，39.030452），可以用一个 GEO 集合保存所有车辆的经纬度，集合 key 是 cars:locations。

GEOADD cars:locations 116.034579 39.030452 33

当用户想要寻找自己附近的网约车时，LBS 应用就可以使用 GEORADIUS 命令。
例如，LBS 应用执行下面的命令时，Redis 会根据输入的用户的经纬度信息（116.054579，39.030452 ），查找以这个经纬度为中心的 5 公里内的车辆信息，并返回给 LBS 应用。

GEORADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

附近的人

nearbyPeople 是一个总的 key，user_1 和 user_2 是相当于 nearbyPeople 里面的两个元素以及他们对应的经纬度，这个例子就是把 user_1 和 user_2 的经纬度存在了 nearbyPeople 这个 key 中

redis> GEOADD nearbyPeople 13.36 38.11 "user_1" 15.08 37.50 "user_2"  
(integer) 2

获取 nearbyPeople 中的元素 user_1 和 user_2 这两个元素的经纬度，当然如果之前没有 geoadd 相对应元素的经纬度的话，会返回 nil

redis> GEOPOS nearbyPeople user_1 user_21) 1) "13.36138933897018433"   2) "38.11555639549629859"2) 1) "15.08726745843887329"   2) "37.50266842333162032"

获取 nearbyPeople 中 user_1 和 user_2 这两个节点之间的距离，距离单位可以指定，如下所示：

  • m ：米，默认单位。
  • km ：千米。
  • mi ：英里。
  • ft ：英尺。
redis> GEODIST nearbyPeople user_1 user_2"166274.1516"redis> GEODIST nearbyPeople user_1 user_2 km"166.2742"redis> GEODIST nearbyPeople user_1 user_2 mi"103.3182"

把 nearbyPeople 中的 距离经纬度(15,37)200km 以内的元素都找出来，而且带上距离：

redis>GEORADIUS nearbyPeople 15 37 200 km WITHDIST  
1) 1) "user_1"  
   2) "190.4424"  
2) 1) "user_2"  
   2) "56.4413"

Stream（5.0 版新增）

消息队列，解决了基于 List 类型实现的消息队列中存在的两个问题。
可以自动生成全局唯一消息ID，并支持以消费组形式消费数据。

面试题专栏

Java面试题专栏
已上线，欢迎访问。

  • 如果你不知道简历怎么写，简历项目不知道怎么包装；
  • 如果简历中有些内容你不知道该不该写上去；
  • 如果有些综合性问题你不知道怎么答；

那么可以私信我，我会尽我所能帮助你。

目录

简介

pgloader是一个数据同步工具，用来将数据从其它地方迁移到postgresql中，支持从如下源迁移：

  • 文件：CSV、Fixed Format、Postgres COPY text format、DBF、IXF
  • 数据库系统：SQLite、MySql、MSSQLServer、PostgreSQL、Redshift

应用场景

需要往postgresql中导入数据的时候，如数据迁移。

安装

安装概述

安装方式比较丰富，详见
https://pgloader.readthedocs.io/en/latest/install.html
。

遗憾的是未提供CentOS环境编译好的程序供下载，所以需要手动编译安装。

CentOS编译安装

去官网下载最新源码：

https://github.com/dimitri/pgloader

将源码放到 /usr/bin下，本文为例：


[root@bogon pgloader-3.6.9]# pwd
/usr/local/pgloader-3.6.9

如果下载的是源码压缩包需要使用如下命令解压：


tar -zxvf pgloader-3.6.9.tar.gz

赋予脚本执行权限：

cd /usr/local/pgloader-3.6.9


chmod -R 777 *

执行 bootstrap-centos7.sh 脚本，下载相关依赖


bootstrap-centos7.sh

执行编译：


make  pgloader

如果有提示到 ("libcrypto.so.1.1" "libcrypto.so.1.0.0" "libcrypto.so.3" "libcrypto.so") 没有找到或者相关信息
需要先安装 openssl


yum -y install openssl openssl-devel

复制编译好的程序到系统执行目录 /usr/local/bin/ 下


cp  /usr/local/pgloader-3.6.9/build/bin/pgloader        /usr/local/bin/

查看是否安装好了：


[root@bogon home]# pgloader --version
pgloader version "3.6.7~devel"
compiled with SBCL 2.2.5

使用

pgloader 有两种常见的使用方式：

  • 通过命令行
  • 通过迁移配置文件

命令行

如下命令行：

pgloader mysql://user:password@ip:3306/dbName postgresql://user:password@ip:5432/dbName
  • 将名为dbName的数据库结构和数据 从mysql迁移到postgresql
  • pgloader 为上述 /usr/local/bin/pgloader 的可执行文件
  • 后面是mysql 的连接信息 ， postgresql 的连接信息，中间使用空格分隔
  • 需要使用有写入权限的账号，建议使用root用户操作

配置文件迁移

另外一种方式就是编写迁移配置文件，然后使用 pgloader sync.load 命令执行配置文件。

如下配置文件演示了仅同步mysql的source_db库中的ramble_doc 表到 postgresql中的target_db库中，执行完毕之后将在postgresql中新建一个名为ramble_doc 的表，并新增数据。

LOAD DATABASE
     FROM     mysql://root:xxx@192.168.1.92:3306/source_db
     INTO     postgresql://postgres:xxx@192.168.1.24:5432/target_db

INCLUDING ONLY TABLE NAMES matching 'ramble_doc' ;
  • LOAD DATABASE ：表示从数据库执行迁移
  • FROM ：源数据库连接信息
  • INTO ：目标数据库连接信息
  • INCLUDING ONLY TABLE NAMES matching ：仅包含匹配的表
  • 最后那个分号不可少
  • 配置文件需要按照格式编写，如缩进

如下配置文件演示了同步mysql 的source_db库下所有表到postgresql的target_db库下面，包含表结构和数据。

LOAD DATABASE
     FROM     mysql://root:xxx@192.168.1.92:3306/source_db
     INTO     postgresql://postgres:xxx@192.168.1.24:5432/target_db
     WITH batch rows = 10000 , batch size =200MB , prefetch rows  = 5000 , workers = 4 ,concurrency = 3
;
  • WITH：with 后面可以追加一些附属参数，各个参数使用英文逗号分隔。常见的参数如：是否需要同步数据还是仅同步结构，是否在写入数据前先删除表等
  • batch rows ：在同步数据的时候分批插入postgresql的行数，默认为2.5万。
  • batch size：每批最大数据大小，设置此参数可避免出现内存溢出
  • prefetch rows：在同步数据的时候分批从mysql读取的行数，默认为1000。
  • workders： 线程数量
  • concurrency：并发线程数量

可能遇到的错误

内存溢出

报错信息为：


Heap exhausted during garbage collection: 64 bytes available, 80 requested.


垃圾回收期间堆已耗尽：可用64个字节，请求80个字节。

解决方案为调优分批数量和并发数量，需要根据源数据库数据量，硬件情况不断尝试。

更多配置参考

官网给了一个例子：


LOAD DATABASE
     FROM      mysql://root@localhost/sakila
     INTO postgresql://localhost:54393/sakila

 WITH include drop, create tables, create indexes, reset sequences,
      workers = 8, concurrency = 1,
      multiple readers per thread, rows per range = 50000

  SET PostgreSQL PARAMETERS
      maintenance_work_mem to '128MB',
      work_mem to '12MB',
      search_path to 'sakila, public, "$user"'

  SET MySQL PARAMETERS
      net_read_timeout  = '120',
      net_write_timeout = '120'

 CAST type bigint when (= precision 20) to bigserial drop typemod,
      type date drop not null drop default using zero-dates-to-null,
      -- type tinyint to boolean using tinyint-to-boolean,
      type year to integer

 MATERIALIZE VIEWS film_list, staff_list

 -- INCLUDING ONLY TABLE NAMES MATCHING ~/film/, 'actor'
 -- EXCLUDING TABLE NAMES MATCHING ~<ory>
 -- DECODING TABLE NAMES MATCHING ~/messed/, ~/encoding/ AS utf8
 -- ALTER TABLE NAMES MATCHING 'film' RENAME TO 'films'
 -- ALTER TABLE NAMES MATCHING ~/_list$/ SET SCHEMA 'mv'

 ALTER TABLE NAMES MATCHING ~/_list$/, 'sales_by_store', ~/sales_by/
  SET SCHEMA 'mv'

 ALTER TABLE NAMES MATCHING 'film' RENAME TO 'films'
 ALTER TABLE NAMES MATCHING ~/./ SET (fillfactor='40')

 ALTER SCHEMA 'sakila' RENAME TO 'pagila'

 BEFORE LOAD DO
   $$ create schema if not exists pagila; $$,
   $$ create schema if not exists mv;     $$,
   $$ alter database sakila set search_path to pagila, mv, public; $$;

https://pgloader.readthedocs.io/en/latest/ref/mysql.html

总结

pgloader是一个数据库迁移工具，花一点点时间研究一下如何使用，将在数据库迁移的时候起到事半功倍的效果，往往比自己编写迁移脚本更加完善和可靠。

引用

来源：晓飞的算法工程笔记 公众号，转载请注明出处

论文: MaskLLM: Learnable Semi-Structured Sparsity for Large Language Models

创新性

  • 提出一种可学习的
    LLM
    半结构化剪枝方法
    MaskLLM
    ，旨在充分利用大规模数据集来学习准确的
    N:M
    掩码，适用于通用剪枝和领域特定剪枝。
  • 此外，该框架促进了跨不同任务的稀疏模式迁移学习，从而实现稀疏性的高效训练。

内容概述

大型语言模型（
LLMs
）的特点是其巨大的参数数量，这通常会导致显著的冗余。论文提出一种可学习的剪枝方法
MaskLLM
，在
LLMs
中建立半结构化（或
N:M
，在
M
个连续参数中有
N
个非零值的模式）稀疏性，以减少推理过程中的计算开销。

MaskLLM
通过
Gumbel Softmax
采样将
N:M
模式稀疏化显式建模为可学习的分布，可在大规模数据集上的端到端训练，并提供了两个显著的优势：

  1. 高质量的掩码，能够有效扩展到大型数据集并学习准确的掩码。
  2. 可转移性，掩码分布的概率建模使得稀疏性在不同领域或任务之间的迁移学习成为可能。

在不同的
LLMs
上使用
2
:
4
稀疏性评估
MaskLLM
，如
LLaMA-2
、
Nemotron-4
和
GPT-3
，参数规模从
843M
到
15B
不等。实证结果显示，相较于最先进的方法有显著改进，
MaskLLM
通过冻结权重并学习掩码实现了显著更低的
6.72
困惑度。

MaskLLM

N:M
稀疏性

N:M
模式稀疏化会对
LLM
施加限制，即每一组连续的
M
个参数中最多只能有
N
个非零值。这个任务可以被转换为一个掩码选择问题，候选集的大小为
\(|\mathbf{S}|=\binom{M}{N} = \frac{M!}{N!(M-N)!}\)
，其中
\(|\mathbf{S}|\)
表示候选集的大小，
\(\binom{M}{N}\)
表示潜在
N:M
掩码的组合数。

对于
2
:
4
稀疏性，二进制掩码
\(\mathcal{M}\)
必须恰好包含两个零，从而形成一个离散的候选集
\(\mathbf{S}^{2:4}\)
，其大小为
\(|\mathbf{S}^{2:4}|=\binom{4}{2}=6\)
个候选：

\[\begin{align}
\mathbf{S}^{2:4} & = \{\mathcal{M} \in \mathbb{B}^{1\times4} | \sum \mathcal{M} = 2\} = \{\hat{\mathcal{M}}_1, \hat{\mathcal{M}}_2, \hat{\mathcal{M}}_3, \hat{\mathcal{M}}_4, \hat{\mathcal{M}}_5, \hat{\mathcal{M}}_6 \} \\
& = \{[1,1,0,0], [1,0,1,0], [1,0,0,1],[0,1,0,1],[0,1,1,0],[0,0,1,1]\}.
\end{align}
\]

对于一个
LLM
，存在大量的参数块，记为
\(\{\mathcal{W}_i\}\)
，每个参数块都需要选择相应的掩码
\(\{\mathcal{M}_i\}\)
。对于剪枝后的性能，为
N:M
稀疏性定义以下损失目标：

\[\begin{equation}
\{\mathcal{M}_i^{*}\} = \underset{\{\mathcal{M}_i | \mathcal{M}_i \in \mathbf{S}^{2:4}\} }{argmin} \mathbb{E}_{x\sim p(x)} \left[ \mathcal{L}_{LM}(x; \{\mathcal{W}_i \odot \mathcal{M}_i\}) \right], \label{eqn:objective}
\end{equation}
\]

其中
\(\mathcal{L}_{LM}\)
指的是预训练的语言建模损失。操作符
\(\odot\)
表示逐元素乘法，用于掩码部分参数以进行稀疏化。

可学习半监督稀疏性

在
LLM
的背景下，由于掩码选择的不可微分特性和庞大的参数规模，找到最佳掩码组合
\({\mathcal{M}^*}\)
可能极具挑战性。为此，论文将掩码选择转化为一个采样过程。

直接确定参数块的确切最佳掩码是不可行的，因为修剪后的
LLM
的行为还依赖于其他参数块的修剪。但可以独立地为每个块采样掩码，并在修剪后评估整体模型质量。

定义一个具有类别概率
\(p_1, p_2, \ldots p_{|\mathcal{S}|}\)
的类别分布，满足
\(\sum_{j} p_j=1\)
。在随机采样阶段，如果某个掩码在修剪过程中表现出良好的质量，那么通过增加被采样掩码的概率来调整类别分布是合理的。

通过足够的采样和更新，最终会得到一组分布，其中高概率的掩码更有可能在修剪后保持良好的质量。

从形式上讲，从随机采样的角度建模上述公式中的组合问题：

\[\begin{equation}
\{p^{*}(\mathcal{M}_i)\} = \underset{\{p(\mathcal{M}_i)\}}{argmin}\ \mathbb{E}_{x\sim p(x), \mathcal{M}_i \sim p(\mathcal{M}_i)} \left[ \mathcal{L}_{LM}(x; \{\mathcal{W}_i \odot \mathcal{M}_i\}) \right], \label{eqn:objective_sampling}
\end{equation}
\]

如果能够获得关于该分布的梯度，那么上述目标可以通过梯度下降进行优化，但从类别分布中抽取样本仍然是不可微分的。

  • 可微分掩码采样

Gumbel Max
能有效地建模采样操作，将采样的随机性解耦为一个噪声变量
\(\epsilon\)
。根据类别分布
\(p\)
抽取样本，生成用于采样的
one-hot
索引
\(y\)
：

\[\begin{equation}
y=\text{onehot}(\underset{i}{argmax} [\log(p_i) + g_i]), \; g_i=-\log(-\log \epsilon_i), \; \epsilon_i\sim U(0, 1), \label{eqn:gumbel_max}
\end{equation}
\]

其中
\(\epsilon_i\)
是遵循均匀分布的随机噪声，而
\(g_i = -\log(-\log \epsilon_i)\)
被称为
Gumbel
噪声。
Gumbel Max
将采样的随机性参数化为一个独立变量
\(g_i\)
，可微分采样的唯一问题出在
\({argmax}\)
和
one-hot
操作。

为了解决这个问题，通过
Gumbel Softmax
来近似
Softmax
索引，从而得到一个平滑且可微分的索引
\(\tilde{\mathbf{y}}=[\tilde{y}_1, \tilde{y}_2, \ldots, \tilde{y}_{|\mathbf{S}|}]\)
：

\[\begin{equation}
\tilde{y}_i = \frac{\exp((\log(p_i) + g_i) / \tau)}{\sum_j \exp( (\log(p_j) + g_j) / \tau ) }. \label{eqn:gumbel_softmax}
\end{equation}
\]

温度参数
\(\tau\)
是一个超参数，用于控制采样索引的硬度。当
\(\tau \rightarrow 0\)
时，软索引将更接近于一个
one-hot
向量，从而导致
\(\tilde{y}_i\rightarrow y_i\)
。

将软索引
\(\tilde{\mathbf{y}}\)
视为行向量，将掩码集合
\(\mathbf{S}\)
视为一个矩阵，其中每一行
\(i\)
指代第
\(i\)
个候选掩码
\(\hat{\mathcal{M}}_i\)
，通过简单的矩阵乘法很容易构造出一个可微分的掩码：

\[\begin{equation}
\tilde{\mathcal{M}} = \tilde{\mathbf{y}} \times \mathbf{S}=\sum_{i=1}^{|\mathbf{S}|} \tilde{y}_i \cdot \hat{\mathcal{M}}_i.\label{eqn:diff_mask}
\end{equation}
\]

这个操作根据软索引生成候选掩码的加权平均，所有操作（包括采样和加权平均）都是可微分的，并且相对于概率
\(p\)
的梯度可以很容易地计算，能够使用可微分掩码
\(\tilde{\mathcal{M}}\)
来优化公式
4
中的采样问题。

  • 学习
    LLMs
    的掩码

基于从基础分布
\(p\)
中采样的可微分掩码，梯度流可以轻松到达概率
\(p_i\)
，使其成为系统中的一个可优化变量。但通常并不直接学习从
logits
生成概率，而是学习带有缩放因子
\(\kappa\)
的
logits
\(\pi_i\)
，通过公式
\(p_i = \frac{\exp(\pi_i \cdot \kappa)}{\sum_j \exp( \pi_j \cdot \kappa )}\)
来产生概率。

缩放因子
\(\kappa\)
将用于平衡
logits
和
Gumbel
噪声的相对大小，从而控制采样的随机性。在训练过程中，所有参数块
\(\{\mathcal{W}_i\}\)
都与相应的分布
\(\{p_\pi(\mathcal{M}_i)\}\)
相关联，并且以端到端的方式学习到最佳分布。

但在多个大语言模型上的实验发现了一个关于可学习掩码的新问题：由于修剪操作会在网络中产生零参数，梯度可能会消失。

为了解决这个问题，引入了稀疏权重正则化，它在剩余权重中保持适当大的幅度，从而导致以下学习目标：

\[\begin{equation}
\min_{\{p_{\pi}(\mathcal{M}_i)\}} \mathbb{E}_{x, \tilde{\mathcal{M}}_i \sim p_{\pi}(\mathcal{M}_i)} \left[ \mathcal{L}_{LM}(x; \{\mathcal{W}_i \odot \tilde{\mathcal{M}}_i\}) \right] - \lambda \sum_i \|\mathcal{W}_i \odot \tilde{\mathcal{M}}_i\|^2_2.
\label{eqn:final_objective}
\end{equation}
\]

由
\(\lambda\)
加权的正则化项鼓励在修剪后保持较大的幅度。

  • 稀疏性的迁移学习

迁移学习是深度学习中最流行的范式之一，而稀疏性的迁移学习则是通过预计算的掩码来构造新的掩码。

论文提出了用于初始化分布的掩码先验（
Mask Prior
），可以大幅提升训练效率和质量。掩码先验可以通过一次性剪枝的方法获得，例如幅值剪枝、
SparseGPT
和
Wanda
。

给定一个先验掩码
\(\mathcal{M}_0\)
，计算其与所有候选掩码的相似度：

\[\begin{equation}
\text{sim}(\mathcal{M}_0, \hat{\mathcal{M}}_i) = \mathcal{M}_0 \hat{\mathcal{M}}_i^\top - \frac{1}{|\mathbf{S}|} \sum_i (\mathcal{M}_i \hat{\mathcal{M}}^\top) = \mathcal{M}_i \hat{\mathcal{M}}^\top - (N/2),
\end{equation}
\]

对于与先验掩码高度相似的候选掩码，在初始化阶段提高其概率：

\[\begin{equation}
\pi_i^{\prime} = \pi_i + \sigma(\pi)* \text{sim}(\mathcal{M}_0, \hat{\mathcal{M}}_i) * \alpha, \label{eqn:prior_mask}
\end{equation}
\]

其中，
\(\sigma(o)\)
是
logits
的标准差，
\(\alpha\)
是控制先验强度的超参数。当
\(\alpha=0\)
时，代表在没有任何先验的情况下学习可微的掩码。

  • 方法总结

从随机初始化的
logits
开始，并在可用时使用先验掩码更新它，如公式
10
所示。然后，优化
logits
以解决公式
8
中的目标。具有最大
logits
的掩码
\(\mathcal{M}_i\)
将被作为推断的最终掩码。

主要实验



如果本文对你有帮助，麻烦点个赞或在看呗～
更多内容请关注 微信公众号【晓飞的算法工程笔记】

work-life balance.

  1. 1
  2. ...
  3. 4
  4. 5
  5. 6
  6. 7
  7. 8
  8. 9
  9. 10
  10. ...
  11. 1508