目录
- 音频指纹是什么
- 音频指纹使用场景
- 音频指纹检索主流程
- 指纹检索原理
- 索引检索方案选型
- 机器成本
- 性能考虑
- 如何增量DUMP
- 指纹HASH冲突问题
- HASH冲突解决方案
音频指纹是什么
音频指纹技术是指通过特定的算法将一段音频中独一无二的数字特征以标识符的形式提取出来，用于识别海量的声音样本或跟踪定位样本在数据库中的位置；
音频指纹使用场景
听歌识曲：Y
哼唱识曲：N
翻唱改编检测：N
版权检测：Y
音频指纹检索主流程
A: STFT

下图是一首歌曲的一段时间的波形图，它只能反映出来时域以及能量值两个维度的数据，分析价值低
所以我们需要挖掘出这段旋律背后的更多信息，所以下图STFT来了，STFT简单说就是把各个频率段混合的信号拆分开,还原原始频率信息，物理课有简单讲过。
B: 求landmark
Landmark是频谱图中的一系列能量极大值点。根据shazam（全球著名歌曲识别应用）论文，能量极大值点的抗噪能力很强。求法多种多样，目的就是在二维平面中寻找峰值。通过调节参数可以控制每秒选取的landmark个数。一般情况下每秒保留20~30个点即可
C: 构造指纹
指纹的构造方法和shazam算法一样。首先针对每一个landmark都有一个targetzone。事实上，这个target zone就是一个landmark构造指纹的范围，这个也是人为指定的。然后，将landmark和target zone中的所有landmark两两组合，构成一个指纹。指纹由三部分构成：两个landmark的频率和时间差。同时每个指纹都有一个对应的时间，也即landmark的时间，表示这个指纹出现的时刻
D: 提取指纹
|f1-f2| + (t2-t1)：t1 = hash1：time1
一首歌曲含有 N个指纹，如 hash1：time1，hash2：time2，，，，hashN：timeN
存储格式是二进制，hash 用32位，time 用32位

指纹检索原理
上面这张图是我找了好久找到的自认为很适合形象表达指纹检索原理的图片 。
不同的在于指纹检索的难点在于要从海量数据里边去匹配，而且是含有时间属性的随机片段匹配。
和普通倒排索性文本搜索不同的是，一首歌的指纹并不是一个单独的数字或者字符串，而是一个附属有时间属性的数字集合。
Shazam算法依据这样一个假设选择结果：要检索的片段肯定来自于某一首完整音乐从某个时刻开始的片段，而它们的生成的指纹应该相同，则对应的时间差也应该相同。所以排序完了之后就寻找含有最多相同时间差的音乐id即可
匹配原理
H: 指纹hash T: 时间点 S：歌曲ID
1：将客户端传递的音频提取指纹，每个指纹H伴随有一个时间属性T；
2: 对每一个提取的指纹都查找倒排索引表，获得该指纹对应的倒排 id；
3: 将倒排列表中每一个歌曲s对应的时间t和提取的指纹对应的时间T进行相减，如果时间差大于零，则放到一个map中<SID,DT>；
4：将SID-DT 作为一个key，做count(1)聚合计算，最终取count 最高的那个SID-DT作为结果，SID即是命中歌曲ID；
索引检索方案选型
选型原则：
1：单机建hash表的方案不做考虑，此方案较难做容灾、热更新以及高性能
2: 分布式存储
3：分布式计算
如果只用分布式DB的存储功能，把分布式数据召回后放到中心化的机器运算会有一个大问题就是数据的网络传输瓶颈，很容易把中心化机器网卡打满
3：可热更新某一首歌曲
4：高性能
数据特点：
数据结构：KV结构
数据大小：
1：_id 32位,可表达约21.47亿行数据；
2：stv 字段 为字符串数组
每行均2.7k（1511024/333)10000000/2147000000;
3：最大约21.47亿行数据
期望读写性能：
主要是读，支撑200以上QPS，增量写；写不求实时生效
请求特点：
每次请求都包含有约1000-5000个id的查询，查询到的条目做聚合(逻辑见下)计算，最终返回TOP1
存储选型
Mysql : 读写时不能进行一些复杂运算。分布式不灵活
Hbase : 读写时复杂的脚本运算要对集群做定制开发
RDS ：读写时无法做复杂运算
Opensearch : 虽然有成熟分布式方案，但不适合自定义复杂脚本MR运算
ES(elasticsearch) : 天然的分布式优势，且可在分布式单机上编写自定义的map combine reduce 运算脚本
得益于ES以上在分布式以及自定义运算脚本的优势，本方案选型了ES
ES 分布式架构简介
replica（副本）作用：可用性；稳定性；横向拓展性能
master节点：普通服务器即可(CPU 内存 消耗一般)
data节点：主要消耗磁盘，内存
client节点：普通服务器即可(如果要进行分组聚合操作的话，建议这个节点内存也分配多一点)
Cluster：集群，一个ES集群由一个或多个节点（Node）组成，每个集群都有一个cluster name作为标识
node：节点，一个ES实例就是一个node，一个机器可以有多个实例
index：索引，即一系列documents的集合
shard：分片，每个索引有一个或多个分片，索引的数据被分配到各个分片上，相当于一桶水用了N个杯子装
注：本方案采用架构上图左
本方案一次query 流程
如何降低机器成本
333首歌的指纹数据评估
ES 磁盘占用公式(参考阿里云ES)
精简ES 数据
本方案不需要ES的分词功能，所以禁用掉一些属性，可以减少很多数据
压缩算法：
使用best_compression压缩算法可以使数据大小减少很多，具体多少忘记记录了。但是读写时会带来额外的CPU开销，尤其时影响读的性能
精简源数据
ES已经精简的没有什么油水了，数据还是大，那么还可以对源数据进行经验，我采用的数据归并
{"index":{"_id":1}}
{"stv": ["1:10,20", "1:15", "2:10", "3:10"]}
{"index":{"_id":2}}
{"stv": ["1:20,30", "1:15", "2:10", "3:10,33"]}
数据实际占用预估（实际入库后ES有做优化，会小很多，话说ES这点优势很低调，放很多系统里可以大吹特吹了）
333首歌产生了2837439行DOC，共150M(不含副本)
1000W首的话1000W*(150/333)/1024/1024= 4.3T
ES总磁盘最小 =源数据*3.3=14.2T
机器费用
机器规格：16c-64g
14.2T数据需要 50台 ：5shard(60g/shard) *50
价格： 50(3000+560)*12=198W;
线上 磁盘2240GB 内存256GB CPU 64核, 13*20W=260W；
性能优化
批量：
整个批量请求需要被加载到接受我们请求节点的内存里，所以请求越大，给其它请求可用的内存就越小。有一个最佳的bulk请求大小。超过这个大小，性能不再提升而且可能降低。
- 在加载大量数据时候可以暂时不用refresh和repliccas
- 使用SSD；
- 设置好mapping;
- 适时force merge;
- 避免scripts；
- 不需要排序使用filter 查询；
- 避免无意义索引字段和source；
- 压缩算法best_compression；
- 使用最小的足够用的数值类型；
……
JVM性能之堆内堆外
刚开始在本地JVM测试，采用的堆内策略，很快就FGC了，所以又尝试了各种堆外方案

- 堆内缓存：使用java堆内存来存储对象，好处是不需要序列化/反序列化，速度快，缺点是受GC影响。可以使用Guava Cache、Ehcache 3.x、MapDB实现。
- 堆外缓存：缓存数据存储在堆外，突破了JVM的枷锁，读取数据时需要序列化/反序列化，比对堆内缓存慢很多。可以使用Ehcache 3.x、MapDB实现。
- 磁盘缓存：在JVM重启时数据还在，而堆缓存/堆外缓存数据会丢失，需要重新加载。可以使用Ehcache 3.x、MapDB实现。
- 分布式缓存：没啥好说的了，Redis
经过多次试验，即使是用堆外缓存部分数据，但是仍旧跑不了拿到堆内计算，仍旧躲不开吓人的FGC，
更可气的是即使机器可以用256G内存的物理机，但JVM堆超过32G，会采用内存对象指针压缩技术，不但会占用更多内存，还会占用更多的带宽。不得已放弃JAVA，改用python，充分利用机器内存。
- python 处理：
python虽然不用担心FGC问题，但是为了高效处理，尝试了各种多进程多线程方案，最后使用了多进程和多线程结合的方式，即一个进程启动多个线程。中间也踩了一些坑，这个过程省略一万字....
如何增量dump
上文为了最大程度精简ES数据，把一个source属性禁用了，但是后面发现ES做更新的时候必须启用这个字段，看了各种文档问了很多人，还是躲不开，不得已又打开了这个属性，当然，数据也大了很多。
ES强大可不是吹的，更新方案用到的复杂运算用简单的几句脚本就可以实现了。这里需要提一嘴的是这个脚本的语言是ES官方为了性能和安全综合考量自己搞了一套类groovy 语言，有些语法和坑，需要踩到才知道。
指纹hash 冲突问题
本来故事基本上要完美结束了，但是当dump了大量真实数据时发现当歌曲数据量过高时，会有很严重的指纹hash冲突问题。
根据上文描述的指纹算法（ |f1-f2| + (t2-t1) = HASH），当歌曲数量过高时，极易放大hash冲突的概率，导致同一段指纹可能命中大量疑似结果数据，这就需要大量的计算对比，消耗大量的CPU 、内存。

优化方案
1：当歌曲数量在百万级别的时候，尽可能改进指纹算法，是指纹数据足够散列；
2：索引分组，并发查询。
当方案1不能很好的实施时，只能退而求其次，使用2来缓解这个问题。
最后
整个过程对音频指纹知识从大致了解到弄懂一些算法细节，非常感谢@屠零 博士 的答疑和帮忙，学习到很多。
另外，ES里有很多架构和哲学思想，很值得学习。
