要讨论的问题

读《消息顺序性为何这么难？》发现，聊天软件的顺序问题其实可以用multicast算法的理论来分析。

问题1 单聊消息投递，保证发送方发送顺序与接收方展现顺序一致？

unicast问题。可以理解为：如何实现FIFO Ordering。
方案：发送方给每个消息加上递增id，接收方使用滑动窗口，或者先到先展示，后到的消息插入到已展示的消息中。

image.png

问题2 群聊消息投递，保证所有接收方展现顺序一致?

即如何实现Total Ordering。按业务需要可能是要实现FIFO-Total Ordering甚至Causal-Total Ordering
方案1:sequencer-based Total Ordering

image.png

方案2：还是sequencer-based，用黏性策略做负载均衡，解单点瓶颈。

image.png

注：可以在service维护一个滑动窗口，做FIFO Ordering

方案3：放弃中心化的sequencer，用近似算法模拟分布式的sequencer。可能存在乱序。

• sharding squencer
  Leaf——美团点评分布式ID生成系统
  https://gitee.com/keets/snowflake-id-generator
  

  image.png
  缺点：
  1.个人理解，强依赖load balance，如果负载不均，乱序情况比较严重

• 使用分布式id生成算法snowflake

  
  image.png

注：这种方案没法保证FIFO Ordering，客户端发送消息msg1,msg2，服务端收到msg2,msg1，msg2的id会比msg1小

注2：snowflake的讲解可以参考:

架构 细聊分布式ID生成方法
snowflake升级版全局id生成
https://www.reddit.com/r/programming/comments/cajap/twitter_announces_snowflake_a_distributed_unique/
https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html
理解分布式id生成算法SnowFlake
从一次 Snowflake 异常说起

follow up:
snowflake是单独部署为一个服务好，还是作为库放在每个业务service里好？

个人理解，这取决于每个进程能否获取机房内唯一workerId。如果基础设施保证能取得唯一workerId就没必要中心化的发号器、没必要单独部署，例如每个业务服务的hostname有唯一后缀；否则就要用etcd/zk等协调服务发号，考虑机器多了后心跳压力大、且有网络partition风险，就要部署到单独服务了。

snowflake方案的缺点：
1.强依赖时钟，怕回拨。可以通过持久化存储+校验的策略，或者把NTP关了来解决。
2.但是不允许回拨的话，集群间机器又会有Clock skew问题

问题3 充值支付消息，保证同一个用户发起的请求在服务端执行序列一致？

即如何实现FIFO ordering。方案同问题1.