背景
在手机上用户随手拍一张衣服的照片，去找类似图片的需求比较明显，以图搜图项目目的就是满足用户的这部分需求。
该项目初步预计5个类目，每个类目500万图片用于检索。经过特征提取，每张图片可以表示为30976维空间中的一个点，即可以用30976个float值表示，为了便于处理，我们将特征值乘以100000，在不损失float值精度的情况下，用int32_t存储图片特征。
图片检索时需要计算query 图片和索引图片的欧式距离，图片之间计算欧式距离的耗时为50微秒，经过cpu指令集优化(sse)，欧式距离计算耗时减少到13微秒。
在压缩之前，所有图片的大小为 3T（ 4 30k 25000000)，每台机器30G内存用于存储图片，需要100台机器存储全量图片。
需要在计算欧式距离效率不降低的情况下，对图片进行压缩，大规模减少机器的占用。
我们的目标是压缩到500G左右，即压缩之后每张图片20k左右，欧式距离计算耗时为15微秒左右。
欧式距离计算要求耗时在微秒级别，已有的压缩方法，比如p4delta、valgrind压缩等在性能上不满足要求，需要我们根据数据特点自己定制压缩方法。
成果
- 目前的压缩方法单张图片由120k 压缩到了平均13k。
- 欧式距离计算平均耗时为9微秒。
这么靠谱的成果是如何做到的呢？
初步尝试
- bitmap的方法
观察数据特点，发现平均每张图片有7000个数为非0值，其他值都为 0。首先想到的是用bitmap表示30976个值在特定的位置是否是0。bitmap需要30976 / 8= 4k个字节。然后只存储非0值，需要7k * 4，压缩之后平均每张图片大小为32k。压缩代码大体如下：
但是在计算图片之间的欧式距离时，需要遍历30976次bitmap，并判断特定位的值知否为0，即将bitmap和掩码数组进行与操作，比较耗时，计算耗时在100微秒以上。计算两个压缩图片的欧式距离代码：
- 采用offset的压缩方式
我们只保存非0数据的off_set和value，off_set最大值30975，需要用int16_t来保存，value的范围0~100万，需要int32_t来表示，采用该方法的话，每个图片占用空间为42k （7k * (2 + 4)）。
计算两个压缩图片的欧式距离的时候，采用按照off_set归并的方法：
该方法进行欧式距离的耗时为55微秒，我们认为是if 条件比较耗时，于是尝试了用位掩码替代if的方式：
该方式消除了if 条件判断，但是耗时为70微秒，性能反而下降了，耗时的原因是cpu的指令增多了。
性能优化
场景分析
- 两个压缩图片计算 --> 一个压缩一个非压缩
目前的优化进入了一个瓶颈，如何才能提升性能到10微秒级别呢？我们回过头来重新考虑了一下应用场景，在线的场景是query图片和一系列图片计算距离，离线的场景是中心点图片和其他一系列图片计算距离也就是说都是一个图片和多个图片进行距离计算，这时一个图片不需要进行压缩，完全可以是非压缩的，即使该图片是压缩也可以先解压计算欧式距离实际上可以转化为一个非压缩图片和多个压缩图片计算欧式距离。对这样的情况，我们需要重新考虑提升效率的问题。
- 确定采用off_set压缩方式
对于计算一个压缩和一个非压缩图片欧式距离的问题，比较bitmap的压缩方式和off_set的压缩方式，off_set的压缩方式有明显的优势对于bitmap方式，最耗时的地方仍然是访问30976次bitmap，然后做与操作，来获取解压后的值，遍历30976次bitmap耗时，至少50微秒以上但是off_set的方式保存了7000个非0数据的off_set，我们只需要遍历7000次非0 数组就可以计算出欧式距离。
一个压缩一个非压缩
- 做法
首先计算好非压缩图片的累加平方和，每次查询计算多次欧式距离，只计算一次累加平方和。
遍历压缩图片数组，计算该值和另一张非压缩图片的对应off_set的差值的平方。
对于压缩图片的为0的那些值来说，欧式距离只需要加上非压缩图片那些值的平方和。
- 举例：
a.非压缩图片：[0 2 3 0 4 0 0 5 6 0 0] ，压缩图片：[0 0 0 6 6 6 0 0 ]
b.事先计算好非压缩图片的特定位之前的所有值的平方和：sqrt[0 4 13 13 29 29 29 54 90 90 90]
c.压缩的数组为 off[3 4 5]， data[6 6 6 ]
d.遍历off和data数组
- olength += (6 - 0) * (6 - 0) olength += (sqrt[2] - sqrt[0])
- olength += (6 - 4) * (6 - 4)olength += (sqrt[3] - sqrt[3])
- olength += (6 - 0) * (6 - 0) olength += (sqrt[4] - sqrt[4])
- 效率：20微秒
该方法只需要遍历7000次数组， 进行7000次相减 平方操作和 7000次访问sqrt 数组操作，大大简化了复杂度。
- 代码如下：
data1为压缩数据，data2为非压缩数据：
平方差展开
- 有没有更优化的方法呢？
欧式距离的计算公式为（a[1]-b[1]）(a[1]-b[1]) + (a[2]-b[2])(a[2]-b[2]) + ... +(a[n]-b[n])*(a[n]-b[n)。
经过展开可得a[1]a[1] + a[2]a[2] + ... +a[n]a[n]+ b[1]b[1] + b[2] b[2] + ... b[n]b[n] - 2(a[1]b[1] + a[2]b[2] + ... + a[n]b[n])。
而a[1]a[1] + ... a[n]a[n]和b[1]b[1] + ... + b[n]b[n]可以在压缩的时候先计算并保存起来，因为压缩的耗时可以多一些。所以计算欧式距离只需要计算a[1]b[1] + a[2]b[2] + ... + a[n]*b[n]即可。
- 举例，上面的例子：
a.非压缩图片：[0 2 3 0 4 0 0 5 6 0 0] ，压缩图片：[0 0 0 6 6 6 0 0 ]
b.计算压缩图片和非压缩图片的平方和。sqrt1 :90 sqrt2:108
c.每次查询 query 图片计算一次 平方和， 压缩图片的平方和在压缩的时候，计算好，并存储。
d.遍历压缩数组
- multi += 6 * 0
- multi += 6 * 4
- multi += 6 * 0
e.欧式距离 = 90 + 108 - 2 * multi - 效率 ：11微秒
该方法只计算7000次相乘，效率相对于上面的方法提高了一倍。
- 代码
for(int i=0; i
multi += (int64_t)p_data1[i] * (int64_t)p_data2[p_off1[i]]; }
olength += sqrt1 + sqrt2 - 2 * multi;
压缩比优化
基本off_set压缩
- 方法
基本的off_set压缩前面已经讲过。
- 效果
每张图片压缩到42k。
- 举例
图片 ：[ 5 5 8 0 0 ... 0 7 6 3 0 0 0 0](（8 和 7 之间500个0），其中208为平方和，6 为非0元素个数。
off_set优化
- 方法
基本的方法利用int16_t来保存非0数据的off_set，每个非0 value的off_set占用2个字节，如何减少off_set 的空间占用呢？
很自然的我们想到了保存该数据的off_set与上一个非0数据的off_set的差值，这样的话，该值就会大大减小，一般的情况下会小于255，则我们可以用uint8_t来保存off_set的差值。
但是如果off_set的差值大于255的话，该怎么办呢？
我们多存了一些0，作为非0值来保存，如果两个非0值之间的off_set大于255，则第一个非0值的off_set+255个off_set的位置存一个作为非0值的0。
如果0的off_set 与下一个非0的off_set 的差值小于255，则保存下一个非0值，否则再加一个非0值。
经过统计，每个图片平均有2个off_set差值大于255的非0值，对性能基本没有影响。
- 效果
采用该方法的话，off_set部分占用一个字节，则压缩之后，图片大小为：7k * (1+4) = 35k。
- 举例：
图片 : [5 5 8 0 0 ... 0 7 6 3 0] （8 和 7 之间500个0）。
如下图所示非0元素的个数变成了7,元素7和8之间由于off_set差值大于255，故多加了一个0，作为非0值，这样off_set的差值就小于255了，在计算欧式距离时没有影响。
value优化
- 方法
value用的是int32_t保存，经过统计，平均有6个值大于65535，则采用uint16_t来保存value的值，超过65535的值，放在压缩buff的尾部，用int32_t保存。
- 效果
压缩之后每个图片大小为7k*(2+1) = 21k。
- 举例
图片 ：[5 5 8 0 0 0 0 7 67676 66666 0 0 0]。
如下图，其中9024396695 为平方和；4 为 uint16_t的值的个数， 2为大于uint16_t的值的个数，前面的非0值采用uint16_t存储，占两个字节，后面的67676、66666由于大于65535，用int32_t类型存储，占用4个字节，平均每个图片大于65535的值的个数为6个，故大大减少了空间占用。
去掉重复值
还有没有继续压缩的可能呢？
- 方法
经过分析数据，发现了图片中的相邻的非0数值，很多都是相同的，经过统计平均每张图片有2400个相邻的值不相同，有4300个相邻值是相同的，其中700个值是相邻的两个值相同，3600个值是相邻的三个值相同。
例：0 1 1 1 0 0 3 3 3 2 2 0 0。
如果将上面的1 1 1 和 3 3 3 和 2 2 归一，只保存 1、3、2和 该值的有几个，则可以进一步压缩空间将每个值有几个存在哪里呢？存在off_set 数组中， 现在的off_set用8个bit保存，最大保存255的off_set差值，将这8个off_set拆分，6个bit保存off_set差值，最大保存差值为63,剩下的2个bit保存该值有几个相同的值，可以保存的相同值的个数为：0 （不会用到）、1 、2 、3。
经过统计，平均每条query中的off_set差值大于63的值的个数为250个，也就是需要额外保存200多个0值，对空间占用影响不是特别大。
- 效果
通过该方法将图片压缩到13k，约等于 ：2.4k 3 + （1.2+0.3）k 3 其中2.4k为 相邻不重复的值的个数，1.2k为相邻且重复值为3的值的个数， 0.3k为相邻且重复值为2 的值的个数，3 为 一字节的off_set + 2字节的value。
off_set 差值大于63的和value值大于65535的对空间影响很小。
计算欧式距离的耗时变为了35微秒，效率变慢的原因主要是int8_t字节 被拆成了6bit 和 2bit。
- 举例
图片 : [0 1 1 1 0 0 3 3 3 2 2 0 0 ]
其中38表示平方和、3表示有3个值，0表示有0个大于65535的值，(1:3)用一个uint8_t表示， 前6个bit保存1，表示off_set是1，后2个bit存3，表示相同的值有3个。(5:3) 和前面的类似，表示off_set差值是5,3个相同的值。(3:2)类似。后面的1 3 2为非0的值，与前面的方法不同的是不存重复的值。相邻相同的值，只存一个。
去掉重复值优化
上面的方法虽然压缩比高了，但是效率降低了，能不能将效率提高上来呢？
- 方法
上面的方法，效率降低是因为off_set拆成了6个bit和2个bit，在计算欧式距离时，需要做 与 操作，增大了复杂度。
能不能不拆分呢？
我们在存储的时候将没有重复的值存在一起，两个重复的值存在一起，将重复3个重复的存在一起，这样在计算欧式距离的时候，遍历到3个重复的值的时候，只需要计算三次相乘的值就可以了，就不需要保存重复值的个数了。
这样的方法off_set的差值发生了变化，不是非0值之间的off_set差值，而是没有重复值的off_set差值，和重复3个的值之间的off_set差值，这个off_set会增大，经过统计没有重复值之间的off_set差值大于255的为4个，两个重复值的off_set差值大于255的为25个,3个重复的off_set之间的差值大于255的为5个。2个重复值的之所以大于255的比较多，是因为2个重复的值比较少，300个值左右，故他们之间相隔比较远，即off_set差值比较大，所以我们将2个重复的值作为不重复的值考虑。
- 效果
该方法将图片压缩为14k左右。（2.4k + 0.7k） 3 + 1.3k 3， 其中2.4k为不重复的值的总和，0.7k为重复数为2的值的总和，1.3k为重复数为3的值的个数之和，3 为off_set字节+value 字节，其他值大小对总空间影响忽略不计。
性能：9微秒， 在11微秒的基础上减少了2微秒，因为重复数为3 的值时，不需要重复遍历数组。遍历的数组的次数不是7000，而是3000 + 1300 = 4300次。
- 举例
图片 : [0 1 1 1 0 0 3 3 3 2 2 0 0 ]。
其中38表示平方和、2表示有2不重复的值，后面的2表示有2个重复数为3 的值， 0表示有0个大于65535的值，9 和 1 表示不重复的值的off_set 差值， 2 和2 表示不重复的值，1和5表示重复数为3 的off_set差值，1 和3表示重复数为3 的值。
各个方法的效果总结：
