Wiki
纠删码（Error Correcting Code, ECC）是一种用于数据存储和传输的技术，它通过添加冗余信息来保证即使部分数据丢失或损坏，也能恢复原始数据。在分布式数据库或存储系统中，纠删码用于增强 数据容错性 。例如，数据会被分成多个部分，并通过纠删码生成冗余信息，即使某些数据丢失，依然可以通过这些冗余数据恢复原始信息。与传统的副本机制相比，纠删码能更高效地使用存储空间，同时提供更强的数据恢复能力。在分布式数据库中常用的有Reed-Solomon 码，XOR 码等。 Reed-Solomon 码基于有限域的数学原理，属于块编码的一种。它将数据分割成多个块，并通过冗余数据块（校验符号）来增强容错能力。通过数学算法，它能够纠正数据丢失或损坏。对于每个数据块，Reed-Solomon 码使用冗余信息使得丢失的多达 t 个数据块可以通过其他存活的 n-t 个块恢复。典型的配置是 (n, k) 形式，其中 n 是总的数据块数，k 是数据块的数量，n-k 就是冗余块数。 它具有较高的容错性，能够容忍多个数据块丢失。（例如 n = 10, k = 6 可以容忍 4 块丢失)但同时由于数学运算的复杂性，复杂度较高。 XOR 码是通过按位异或操作生成冗余数据。其基本思想是将多个数据块通过 XOR 运算生成冗余块，丢失一个数据块时可以通过 XOR 恢复。XOR 码的特点是冗余数据是通过简单的异或操作得到的。若丢失一个数据块，可以通过其他数据块和冗余块进行恢复。 由于 XOR 码仅依赖于按位异或运算，计算复杂度低，恢复速度快，适合于快速恢复场景。但XOR 码通常适用于单一容错场景，即容忍最多一个数据块丢失，容错能力较低。
Academic Push
Optimizing Collections of Bloom Filters within a Space Budget作者：Gabriel Mersy, Zhuo Wang, Stavros Sintos, Sanjay Krishnan链接：https://dl.acm.org/doi/pdf/10.14778/3681954.3682020代码：https://github.com/gmersy/truncated-bloom-filter本文探讨了在有限的内存占用下，如何优化多个布隆过滤器的空间分配问题。布隆过滤器是一种用于集合成员查询的近似数据结构，在空间受限的情况下能够高效运行。虽然单个布隆过滤器的空间与精度之间的权衡已经有较多研究，但本文着眼于实际应用中多个布隆过滤器的优化问题，例如在数据跳过（data skipping）、横向信息传递和网络过滤等场景中使用。作者提出了一个关键问题：如何在已知每个布隆过滤器被查询的可能性（即查询的热度）的前提下，分配有限的空间以最小化预期的假阳率（false positive rate）。为此，作者引入了“截断布隆过滤器”的概念，允许在构建完过滤器后进行截断操作以节省空间，并基于此提出了一个优化问题模型。该模型通过分配更多的空间给频繁被查询的“热”过滤器，减少了其误报率，而对不常被查询的“冷”过滤器则减少空间分配。具体来说，论文首先分析了截断布隆过滤器的理论误报率，并证明该优化问题是凸优化问题，可以通过快速算法求解。通过应用于数据跳过和全文搜索等实际场景，作者展示了他们的方法在不同空间预算下相对于当前技术的有效性。最终的结果表明，他们的方法在保证较高精度的同时，能够更好地利用空间，尤其是在面对查询分布明显倾斜的场景时表现突出。Question
在时间序列数据库中，时间序列数据的核心特性之一就是记录的顺序必须与时间顺序一致。时间戳（Timestamp） 是最合适的字段，因为它精确标识了每个记录的时间点，能够确保数据按时间顺序进行存储和检索。A) 随机生成的UUID：UUID 是唯一标识符，用于标识记录，但它不包含时间信息，因此不适合确保数据的时间顺序。B) 自动递增的整数ID：自动递增的整数 ID 适合用于标识唯一的记录，但它并不依赖于时间顺序，无法直接确保记录按时间顺序排列。C) 时间戳（Timestamp）字段：时间戳字段显然是最合适的选项，因为它能够明确记录数据的时间顺序，便于按时间顺序存储和查询。D) 外键引用另一个表的ID：外键用于建立表之间的关系，通常与时间序列数据的顺序无关，无法确保记录按时间顺序排列。数据库与数据挖掘协会（DataBase & DataMining Association，简称DBDMA）一个致力于促进重庆大学数据库和数据挖掘领域发展的学生社团，我们的目标是让世界了解重大数据库，让重大数据库走向世界！
