1. ArrayList 保存的100万个对象,如何获取属性type=2 的子集

  1. 100W个对象使用ArrayList保存的合理性, 内存,并发
  2. 获取子集的性能要求
    多线程(cpu核心 * 2, 内存大小,swap大小 )查找, list分片搜索 -> 合并结果集
    java8 parallelStream + filter .collec(Collects.toList)
    当业务逻辑较为简单时,单线程的执行效率可能会高于 多线程(线程的创建,销毁等操作的额外开销)
  3. 当需要多次以type检索时, 构建以 type为key 的Map, type较多时 采用二次hash

2. 分布式ID生成器的解决方案

分布式系统中如何生成全局的unique ID

常见场景: 多个Mysql实例构成集群 Hbase中rowKey的设计实现
需求:

  1. ID全局唯一
  2. 数据可迁移, 即生成的ID不会受到 位置的限制
  3. 时间序列 排序 Timestamp的前缀
  4. ID的大小 不能占用过多的空间 一般小于 64bits
  5. ID生成的速度要求, QPS
  6. 本身服务的高可用

解决方案

Twitter Snowflake

41bits : timestamp + 10bits: nodeId(datacenter Id 5 bits+ work Id bits) + 12bits: sequence number

生成过程: 
1.worker启动时获取 10位机器号
2.每次生成新ID时获取当前timestamp
3.1 当当前timestamp 与前一个ID timestamp 相同 sequence num + 1 做新的 snum,当所有 ID用完,等待下一毫秒
3.2 当当前timestamp 与前一个ID timestamp 不同 随机生成一个 snum

整个过程只有在worker启动时有外部依赖
异常情况

  1. timestamp 小于前一个,持续等待
  2. 为什么使用随机的snum 会导致每一毫秒的 ID数目减半, 若使用固定snum,可能导致某些时间片数据较大时,高并发的情况下,数据倾斜,落到固定部分值上去
    变种
    simpleflake完全随机snum，发号num 减小，去中心化
    instagram 分片id， 多个shard 每个shard 对应一个shard号，每个shard内 多个snum