如何在大量数据中判断给定的是否在其中

发表于

1、 Bloom Filter

  • 缺点：只能增不能减，且有误判场景需要单独处理
  • 可以使用当前进程级的Bloom Filter，也可以使用Redis的Bloom Filter

2、 文件存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
import org.junit.Test;

import java.io.File;
import java.io.IOException;
import java.net.URI;
import java.nio.MappedByteBuffer;
import java.nio.channels.FileChannel;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;

public class MappedByteBufferTest {
    public static void main(String[] args) {
        System.out.println("=="+ ID_SIZE);
        System.out.println("=="+ getBufferIndex(1032387525));
        System.out.println("=="+ getBufferIndex(227081157));
        // 两个数字模结果冲突
        // 这种方案只能保存连续的一定范围的数字对应的值
    }

    private static final int ID_SIZE = 1024 * 1024 * 32 * 8;

    private static int getBufferIndex(long idx) {
        //每个id占用8个字节
        return (int) ((idx % ID_SIZE) * 8);
    }

    /**
     *
     * 写入：mappedByteBuffer.putLong(int index, long value);
     * 读取：mappedByteBuffer.getLong(int index);
     * 注：MappedByteBuffer对index的最大范围是Int.MaxValue()
     */

    // 上面的表述计算有问题
    /**
     * 2G = 2^31 字节
     * ==> 1b= 2^3 ; 1k = 2^10 b ; 1M = 2^20 b ; 1G = 2^30 b; 2G = 2^31 字节
     * long 64 位，即 2^3 字节 = 2^3
     * 2G = 2^31 字节 能存储多少个，应该是 2^31 / 2^3 = 2^28
     */

    // 31 - 3 = 28 = 10 + 10 + 5 = 1024 * 1024 * 32 * 8
    // 根据每个模之后的倍数放在不通的文件，所以不会冲突
    //如果分文件，比如10个，那么78在第8个文件的低第七个； 78%10、78/10

    /**
     * https://zhuanlan.zhihu.com/p/353988136
     * @throws IOException
     */
    @Test
    public void testMappedByteBuffer() throws IOException {
        File file = new File("/Users/kingsonwu/downloads/test.log");
        if(!file.exists()){
            file.createNewFile();
        }
        FileChannel fileChannel = FileChannel.open(Paths.get(URI.create("file:/Users/kingsonwu/downloads/test.log")),
                StandardOpenOption.WRITE, StandardOpenOption.READ);
        MappedByteBuffer mappedByteBuffer = fileChannel.map(FileChannel.MapMode.READ_WRITE, 0, Integer.MAX_VALUE);
        //fileChannel.close();
        //mappedByteBuffer.position(1024);
        //mappedByteBuffer.putLong(10000L);

        mappedByteBuffer.putLong(getBufferIndex(1032387525), 1032387528111L);
        mappedByteBuffer.putLong(getBufferIndex(1032387526), 1032387529567L);
        mappedByteBuffer.putLong((ID_SIZE - 2)*8, 4032387529569443654L);
        //mappedByteBuffer.putLong((ID_SIZE_2)*8, 1032387529569L);

        mappedByteBuffer.force();

        System.out.println(mappedByteBuffer.getLong(getBufferIndex(1032387525)));
        System.out.println(mappedByteBuffer.getLong(getBufferIndex(1032387526)));
        System.out.println(mappedByteBuffer.getLong((ID_SIZE - 2)*8));
        //System.out.println(mappedByteBuffer.getLong((ID_SIZE_2 )*8));

    }
}

3、Tendis

  • 使用tendis可以将数据存储到磁盘，避免全部数据都保存在内存，从而节约内存
  • Redis的痛点之一就是内存成本高，访问频率(QPS)没那么高, 依然占用大量机器, 维护成本很高
  • Redis vs Tendis：冷热混合存储版架构揭秘
  • 使用 rocksdb 作为存储引擎, LSM Tree