Categories
程式開發

我们是如何为算法交易系统进行数据库选型的?


所有软件系统中都必须包含一项关键组件,那就是用于存储、检索和分析数据的数据库。本文中,我们将和大家一起探讨适用于算法交易平台的数据库都会有哪些特性?有哪些可选择的数据库?

从广义层面来看,数据库提供了记录和管理数据(OLTP)和分析数据(OLAP)的能力。大多数数据库会擅长其中一种能力,同时在某些指标具备优势,而在另一些方面则有所欠缺。举例来说,擅长一致和持久事务的关系型数据库可能在性能方面表现不是很好,因为它需要锁定其数据结构并刷新所有磁盘写入。相反,优先考虑性能的数据库可能需要使用宽松的一致性模型。

根据特定功能和特性的优先级划分,不同种类的数据库适用于不同的场景。

算法交易系统的数据存储

如果我们想追求完美,即持久、一致地存储大量数据并快速进行实时分析,这能做到吗?尽管计算机科学理论警告我们不要太贪心,但是有一些工程思想值得参考。

主要设计目标包括:

  • 快速将大量事件提取到持久存储中(每天工作数小时,约250K-1M个事件/秒;我们预期每个事件约为100-200字节,并具有10-30个字段)

  • 实时分析,包括汇总

  • 能够处理大量模式和趋势历史数据

基于以上的设计目标,我们可以构建几种解决方案,不过基本上都需要对数据存储进行分层,以提供多种附加能力。

其中的一种解决方案为:

  1. 将交易系统中的所有事件存储到一个快速数据存储中,例如仅附加文件日志(可能在高可用性系统的多个节点上复制或重新创建)。该文件提供持久存储,但没有真正的查询功能。

  2. 将该日志文件的内容顺序提取到一个内存数据库/缓存中。这个步骤可以很快,甚至是实时的,因为在这一层没有一致性检查、复制或持久性要求。该层应提供实时聚合和分析。

  3. 定期将内存数据库的内容持久存储到磁盘(每小时或一天结束时等)。这里使用可以对磁盘上存储的大量数据进行操作的数据库。本质而言,对存储的这些数据进行的操作被视为脱机或批处理模式,并且不期望瞬时响应时间。

  4. (可选)仅将日志文件的相关部分提取到一个关系型数据库中,以提交每日/每月报告。例如,只有订单和执行会被加载到关系型数据库中,而市场报价会被跳过。

另外,这个解决方案也是可以简化的,例如可以将步骤2、3和4组合起来,使用一个提供多种存储和分析数据模式的工具。

接下来,我们就来一起讨论一下细分需求下的数据库工作。

我们对数据库的要求

我们对数据库的要求可分为非技术需求和技术需求两部分。

非技术需求列表:

  1. 成本:作为一家注重成本的初创企业,我们正在寻找免费或相对便宜的产品。鉴于当今有许多FOSS方案,我们认为这不是什么疯狂的要求。这也意味着Oracle和MS SQL Server等标准付费数据库被排除在外了。

  2. 良好的文档和社区支持:如果我们不支付许可和支持费用,就需要良好的文档和另一种解答问题的途径。可行途径可以是邮件列表、活跃的在线社区,也可能只需StackOverflow即可。

  3. 运营工具:我们更喜欢相对成熟的产品,自带用于设置、管理和监视部署(包括可能的多节点集群)的工具。

技术需求:

  1. 快速提取:我们需要数据库能够以每秒250K次插入的速度提取,越高越好。如果我们需要批量插入,那是可以接受的;如果我们需要使用多个线程或连接也可以。

  2. 快速聚合:我们打算在系统中使用事件源模式。按照这一架构模式的规定,我们会将系统中的所有状态更改记录为离散的不可变事件。为了从这些事件中重新创建系统的最新状态,我们需要对内存中快速聚合的支持,包括窗口函数、upsert和其他可能的横截面聚合。

  3. 时间序列操作:支持诸如时间段、移动窗口聚合和as-of joins之类的操作。

  4. 表达力强的查询语言:SQL可以,但对于高级分析来说表达能力还是不够。理想情况下,数据库将使用带有矢量化操作的函数语言支持数据访问和处理。创建用户定义函数或服务端脚本的能力也很有用。

  5. 内存中的表:用于快速分析工作数据集。

  6. 磁盘中的表:我们预期这一类别中的多数数据库使用面向列的存储。

  7. 数据库应支持优化的磁盘数据布局,这会显著提高性能。

  • 数据按日期划分并分段存储,以便数据管理

  • 对于每个分区,数据由Symbol(交易代码)跨多个节点分片,以实现并行性和冗余

  • 在每个分区和分片中,数据记录按(Symbol + Exchange,代码+交易所)进行聚类,以方便顺序读取磁盘

  • 最后,在每个聚簇键的记录中,按时间戳对数据排序,以实现更快的时序操作

  • 此外,可以将数据压缩在磁盘上,以减少从磁盘读取的数据总量

  • 分层数据存储:数据库还可以支持分层存储策略,将较旧的数据移动到速度较慢的存储上,从而降低存储成本。

下面是我们评估的数据规模估算:

  1. 每日数据增长:50–100 GB(未压缩)〜1B条记录

  2. 历史数据(最终):100 TB(未压缩)〜1T条记录

如何进行测试?

我们所有的测试都是在单个或两个AWS专用实例(m5n-2xlarge)上进行的。这些实例运行Amazon Linux 2 AMI,包括8个vCPU、32GB RAM和100–200GB SSD卷。

我们知道,对于某些参与测试的数据库来说,这些实例不算很大,尤其是在内存指标方面。但我们这样选择也有我们的考量,首先,我们认为这些资源足以进行我们想要的测试,其次,我们想了解在资源不足时,这些工具将如何降级或失败。

在我们的时间限制内,我们尽了最大的努力来配置各个工具以使其发挥最佳性能,但是我们可能并没有一直使用推荐的配置、硬件或节点数。我们也尝试了遵循文档并以最佳方式设置数据布局(例如分片方案)。

我们执行的实际测试包括:

  • 加载一天的NYSE TAQ数据(20180730的文件)。这会将3500万笔交易加载到一个表中,并将7.19亿个报价加载到另一个表中。我们不打算将此数据库用于报价数据分析,但这肯定会成为一个很好的示例数据集。

  • 对于每笔交易,在该交易所在的交易所中找到当前的报价。我们希望对单个繁忙的代码(例如SPY)的查询将花费不到一分钟的时间,对于所有代码,我们希望查询在30分钟内完成。这是对查询语言表示复杂联接的能力,以及数据库在合理时间内执行联接能力的测试。

  • 对于每个交易代码,计算交易日每分钟的交易数量、平均大小和交易量加权平均成交价。我们希望在整个交易表上花费的时间不超过10秒。

  • 在交易日的每一分钟计算每个交易代码的OHLC条形。

  • 计算交易日每个交易品种的时间加权平均价差。这是一个有趣的测试,其原因有两个:1)确定报价的持续时间需要使用诸如LEAD或next之类的窗口函数;2)必须处理每个报价,因此这是对原始扫描速度的测试。

备选方案

要说明一下,我们在kdb+上拥有丰富的经验,因此,我们对响应时间的预期大部分来自于这部分经验。在原始单核速度方面,我们还没有发现比kdb +更快的工具。但因为价格、陡峭的学习曲线和缺乏可操作工作等原因,我们没有把kdb+列在备选名单中。

平面文件(Flat File)

虽然数据库是最常见的数据存储,但是直接处理平面文件是真正关键的竞争优势,因为它提供了存储数据的最大灵活性。如今,有多种工具可以有效操作存储在本地磁盘或S3存储桶上的平面文件,例如:Python(带有Jupyter的Pandas)、Apache Spark、Amazon Redshift Spectrum甚至clickhouse-local。

我们在AWS上使用Apache Spark尝试了EMR(Elastic Map Reduce)集群,虽然设置起来相对容易,但我们仍旧花了一些时间才弄清楚如何从文件和JDBC源加载数据,以及如何使用Spark数据集和PySpark数据帧。我们的结论是,这可以用于具有适当扩展能力的批处理分析,但不能用作主数据库。不过,我们对Hadoop和Spark的了解有限,因此对于结论判断也会有所影响。

不过,我们仍然认为这是一个精心设计的系统,该系统以正确方式组织文件和目录,还带有相应的工具和规划好的作业,对于能够分配适当资源的高级用户而言,这可能是一个可行的选择。但是对于我们来说,我们认为它可能太脆弱且缺乏组织性,我们还需要其他一些花哨的功能。

MySQL

我们只把MySQL视为一个起点,主要是为了确认传统的RDBMS对我们而言并不是真正的正确答案。MySQL不是时间序列数据库,也不是面向列的,并且不支持我们正在寻找的高级分析特性或性能指标。

它的优点是免费,还有庞大的社区。它的支持者会声称,只要你知道方法,它就可以做任何事情。在我们的测试中,MySQL(InnoDB引擎)无法跟上连接池中250K/秒的快速批量插入,并且随着表增加到几百万条记录,插入速率也下降了。磁盘上的数据大小看起来非常大,查询几百万条记录时的响应时间以秒为单位。即使可以添加索引,具有数百万条记录的联接表也无法在可接受的时间内完成。

在校对本文的草稿时,一位前同事向我们推荐了MariaDB列存储。由于时间限制,我们无法对其进行全面评估,但是这个链接将它与ClickHouse做了很好的对比,后面将对后者进行讨论。

PostgreSQL和TimescaleDB

在我们的负载测试中,PostgreSQL比MySQL更好,尤其是在插入速率和表大小增加时响应时间的退化水平方面,但对于实际需求而言还不够好。

TimescaleDB似乎很有竞争力——它是一个PostgreSQL扩展,使用大量常规PostgreSQL表创建一个称为超表的虚拟表。在超表上的所有查询和操作都向下传递到适当的块表。这里的主要目的是提高插入速率,并在处理大量数据时提供可预测的查询时间。TimescaleDB还提供了一些与时间序列相关的功能,以帮助分析。

宣传的效果很好,但实际跑起来就不行了。最初的插入速率很不错(250K /秒),但我们无法提取3500万笔交易记录——它莫名其妙地耗尽了内存。我们还注意到,文本文件加载器无法利用服务器上所有可用的内核。提取数据时,我们发现服务器上的IOWait时间比其他数据库长得多,这可能是由于缺少磁盘压缩所致。磁盘空间使用率也很高——存储的数据比完全未压缩的文本数据占用的空间还要多,这是很奇怪的(也许是因为预分配?)。我们知道最近的版本支持原生压缩了,但是我们无法将其自动用于新提取的数据。

ClickHouse

ClickHouse基本可以算是一个新玩家,几乎拥有我们梦寐以求的所有特性:

  • 它是FOSS、速度超快、水平可伸缩、容错、硬件支持良好,并且具有磁盘(包括分层存储)上的高级数据管理;

  • 开发过程非常透明,在Github上有活跃的社区,并且每2至3周发布一次更新,其中包含新功能、改进和修复;

  • 文档很好,很容易从维护者那里得到问题的答案。

ClickHouse主要是一个OLAP引擎,没有真正的事务支持可言——例如,它不支持插入数据的更新和删除,除非通过笨拙的异步ALTER TABLE命令。它还不支持窗口函数(neighbor和runningAccumulate这类特殊情况除外),这让人有些惊讶,毕竟它主要针对的是时间序列。

我们在未启用任何复制功能的单个节点上测试了ClickHouse。ClickHouse能够以超过1M/sec的速度加载3500万笔交易和7.19亿笔报价。它使用特殊的磁盘数据结构(MergeTree)将数据尽快写入临时文件,然后在后台合并,从而达到很高的速度。它永远不会用完内存(只有一个例外),并且使用压缩过的源文件节省了将近一半磁盘空间,效率极高。

遗憾的是,我们无法克服一些关键障碍:

  • 发出查询的唯一方法是使用类似SQL的查询语言,但有一些严格的限制:每个请求只能发出一个选择语句,并且不支持用户定义函数(UDF)或存储过程(Stored Procedure)。

  • 他们的哲学可以概括为”只能听我的”。维护人员对一些合理的用户请求(例如支持日期时间数据类型中的亚秒级精度)给出了无法令人满意的答复。公平地说,有些回应也有正当的理由,但是看到这些交流仍然有些令人不安。

总而言之,我们还是认为ClickHouse具有很大的潜力,将密切关注其发展,甚至我们会在系统中的非关键部分部署ClickHouse。

DolphinDB

DolphinDB是一种奇特的专用产品,在这次评估之前我们完全没注意过它。这是一个快速的分布式时间序列分析数据库,是kdb+的可行替代方案。来自kdb+的背景激发了我们的兴趣,即便它是付费产品,也足以让我们试用一下。

我们对它的总体印象是积极的。它比ClickHouse更快,甚至可能比kdb+更快。它拥有对多节点集群的原生支持、功能丰富的函数式编程语言以及优化的内存上以及磁盘上的数据结构。它仅用6秒钟就将我们的3500万笔交易载入了一张表!它仅在358毫秒内就执行了所有SPY交易及其主要报价之间的as-of join,在25秒钟内对所有代码执行了同样的联接,而在kdb+上一次查询大约需要5分钟。另外,存储数据的磁盘用量还不到压缩后的源文件的一半。

它还有一些高级功能(我们未测试)包括:支持流和发布/订阅、实时聚合/窗口引擎、实时异常检测引擎、高级统计分析函数和机器学习函数

尽管它表现极佳,但仍有一些我们无法克服的负面因素:

  • 成本:虽然它看起来比kdb+便宜,但对我们来说仍然太贵了;

  • 需要学习非标准语言(尽管比kdb+容易得多),不过,好在它的文档完整出色;

  • 对于关键业务组件,我们真的可以考虑为(对我们而言)未经验证且尚无法判断其局限性的闭源产品付费吗?让人犹豫不决的是,它出现了几次崩溃和莫名其妙的内存不足情况,这都是扣分点。

不过,看来我们可能已经发现了比kdb+更快、功能更丰富的产品,这一点得分很高。我们将密切注意这款产品,如果对具有这些能力的产品(例如tick数据研究环境)有强烈的需求,我们一定会考虑它的。

MemSQL

现在要讲的是,我们最终的选择——MemSQL了。MemSQL是一种付费产品,但它也为初始集群提供了免费的商业许可证,其最多可包含4个节点、128 GB内存和无限的磁盘数据。我们认为这足以满足我们在考虑付费产品之前的初始需求了。

MemSQL将自己定义为名为HTAP(混合事务/分析处理)的新数据库种类。MemSQL的主要卖点有:它提供快速的分析功能,同时具有丰富的事务支持并充分兼容SQL。它甚至可以与MySQL兼容,因此你可以使用所有MySQL工具和驱动程序。与庞大的工具生态系统集成是很棒的,但也存在一些障碍,因为它很难使用纯SQL表示某些高级分析。由于它以UDF和存储过程提供了对过程语言的全面支持,我们接受了这一特殊缺点[注意:过程方法比通常的矢量化操作至少慢一个数量级]。

MemSQL支持内存上行存储表以及磁盘上列存储表,带有分片、排序和压缩功能(它们最近还发布了混合单存储格式)。我们仅使用Columnstore进行了测试,特别是考虑到我们的测试实例只有32GB内存。就部署、管理、监视、集群设置甚至数据的加载和查询而言,MemSQL是最容易使用的工具之一。

我们能够以超过50万条记录/秒的速度加载交易和报价。我们注意到,服务器上的加载过程能够使用多个内核并行化提取。加载的数据占用的空间与压缩后的源文件大致相同。我们还观察到,使用JDBC接口时,外部工具能够以超过1Gbps的速度从MemSQL读取数据,这特别令人印象深刻。

大多数单表查询以及多表联接查询的整体性能都很好。它在as-of joins中表现不佳,但毕竟它根本不是针对该用例设计的。我们花了很多时间试图以最佳方式在SQL中表示一个as-of join,最后我们强迫引擎执行(相对)快速的MergeJoin。可以预期,厂商将来可以作为自定义操作添加对as-of-join的专门支持。

总而言之,MemSQL是我们在调查中可以找到的最平衡解决方案。它很成熟、易于使用、免费(暂时)、快速、高效且可与我们想要的所有标准工具互操作。

成绩统计

针对以上测试,我们做了一个详细的数据统计和对比:

我们是如何为算法交易系统进行数据库选型的? 1

如果想要更详细查看我们的测试结果,可以查看这里:https://github.com/prerak-proof/dbtests

总结

我们知道还有其他许多工具可以评估,尤其是各种NoSQL数据库。我们的总体感受是,尽管这些选项也可能处理我们的数据规模,但它们大概无法满足我们的性能期望。至少到现在,我们认为MemSQL是最适合我们的产品,既能满足我们的需求,也符合我们的约束条件。

原文链接

https://medium.com/prooftrading/selecting-a-database-for-an-algorithmic-trading-system-2d25f9648d02