我抛一个公司最近的技术难点,各位帮忙想想。 两个队列,一个队列100万数据左右,一个队列10万数据左右,这两个队列都在动态补充和消耗。 第一个队列需要多维排序,取出最优的与第二个队列的数据一起处理, 处理完成后如果没有用光,还会回到第一个队列。 希望能够尽可能取出更优的和速度较快。[北京-阴空]
北京-阴空(-) 15:51:14
这是个投标的场景。 如果标的资产是1万,但是第一个队列里有100万,就会用1万,还生99万继续回到队列。
深圳-平凡(-) 15:51:42
你们是做优先匹配吗?
北京-阴空(-) 15:51:49
我本来想到用多维树来解决,但是,因为队列一直变化, 用树就不合适了。我们根据这个队列去向存管银行发请求。
北京-哇咔咔(-) 15:53:52
似乎 应该从队列2拿出数据,从队列1取头数据,算完了,再把队列1的数据放回去;重复这个过程
深圳-平凡(-) 15:54:43
问题就在第一个队列的动态多维排序里
北京-哇咔咔(-) 15:54:55
从队列1拿出数据,再从队列2遍历数据并计算,就不对了。因为计算完一条队列2的数据以后,这时候从队列1拿到的数据可能就不是最优值了
北京-哇咔咔(-) 15:55:24
不过为什么要有队列2
北京-阴空(-) 15:55:27
会导致匹配速度过慢吧。 每次都要等处理完了重新排序是吧。
北京-阴空(-) 15:55:43
相当于队列一是钱,二是资产。
成都-梅小西(-) 15:56:16
队列1是资金,队列2是标,对不对
深圳-平凡(-) 15:56:20
第一个队列是用户买你们的产品,第二个队列是产品资金对接到真实债权?
北京-阴空(-) 15:56:20
对的
成都-梅小西(-) 15:56:28
就是队列1的资金去投队列2
成都-梅小西(-) 15:56:36
还要最优组合
成都-梅小西(-) 15:56:47
这个东西涉及并发啊,要注意安全, 钱要是出问题了就麻烦
北京-阴空(-) 15:56:47
恩,多维排序。现在的解决方案是。 都放到数据库里。。。order by多个字段。。
深圳-平凡(-) 15:57:54
多维排序是P2P的匹配规则,比如监管要求的不能期限错配,公司的利率差最优值这些
北京-阴空(-) 15:58:30
比如,a.b 两个用户来公司投资。 这两个人投资的产品分别是预期8,9的利率,(第一个维度),然后每个人投资的钱只有一部分投到了标的上(第二个维度),每个人的钱到期的时间不同(第三个维度),现在希望根据上面几个维度,把这些钱投到,资产端过来的标的上。就是两个队列出来的数据match下。 然后做出来。 第一个队列的数据,如果还有钱剩下来还要回去。
北京-Easy哥(-) 15:59:53
a b就是那2个队列? 一个是决策 一个资产转移
北京-阴空(-) 16:00:01
我想到用多维树做。 但是每次回来修改都需要锁住树。。。还是 队列是 <源 利率 投的钱 到期时间> 另一个队列是 <标>, 决策 的部分你加个时窗就好了,不要是实时的, 这个意思? 比如每5s排一次序,排完之后,转移一次资产, 然后 产出 2个的结合?
北京-哇咔咔(-) 16:00:18
ignite、disruptor、hazelcast可以研究一下
北京-阴空(-) 16:01:04
基本喜神的意思吧, 对的
北京-Easy哥(-) 16:01:57
标有自己的属性么?比如 钱 到期时间 利率?
北京-阴空(-) 16:02:20
标的问题不用考虑。
北京-阴空(-) 16:02:46
恩,easy个说的大概就是那样。 就是这个队列里都是对象,排序根据这个对象的多个属性。
成都-梅小西(-) 16:02:53
他的意思是,按照各种维度排序后去投标。比如按照钱多钱少排序,然后投标,还有剩下的,就按到期时间排序,再去投标
北京-Easy哥(-) 16:03:01
感觉 根据这个几个纬度做倒排索引 然后 做个交集就出来了
北京-阴空(-) 16:03:19
@成都-梅小西
是根据多个维度排好序了。。投标。
北京-Easy哥(-) 16:03:33
反过来做就好做很多
成都-梅小西(-) 16:03:53
哦,你是说排序都搞好了?
成都-梅小西(-) 16:04:04
每个维度排序都搞好了?
北京-阴空(-) 16:04:08
没有。。排序是个麻烦的地方。主要是不能等太久
北京-阴空(-) 16:05:01
因为这个排序涉及到了用户的投资是否能够接近预期年利率。
北京-Easy哥(-) 16:05:02
用标的特性去过滤投标的队列
北京-阴空(-) 16:06:04
@深圳-平凡 现在这个内存的方案还没有可以执行的。 因为用户一直在投资。 匹配玩后的资产还可能回来。锁的话频率太高了
北京-喜(-) 16:06:06
锁的这个事情,改成定期排期吧,不然你根本没法处理,没有快照现场,一直是动态的
北京-阴空(-) 16:06:40
定期排期,按照次优处理是吧, 定期排期是不是也得锁一下。
成都-梅小西(-) 16:07:55
你打算作为job定期运行么?
北京-阴空(-) 16:07:56
@北京-Easy哥 我猜测是担心如果这么做。 导致某些用户的收益率够了,有些用户的不够。
北京-喜(-) 16:08:20
还有个点是:你是想把钱都投出去,还是想把标的都卖出去( 不太懂业务,用词不太准)
北京-阴空(-) 16:09:06
标的都卖出去,因为一般钱都比标的多。(目前来说)然后,还要让用户的预期收益率尽可能达标。
北京-喜(-) 16:09:06
改决策模型, 也就是说, 你的排序权重里,其实还有一列, 根据用户的已投和回报率,来计算下一次该如何投的, 这一次给他比如2万10%汇报的,用户期望9%。下一次可能可以给他一个8.5%的, 历史投的情况,也是决策因子
天津-coffee(-) 16:09:11
我们匹配就没这么多维度
深圳-平凡(-) 16:09:15
完全实时是做不到的,受影响的数据时刻在变化。换成三个队列可以吗?
一个排序
一个排序后的数据
一个处理排序后的数据
北京-阴空(-) 16:10:50
北京-喜(332069183) 16:10:53
当然, C端看到的和B端资产 不是一个维度的
北京-阴空(799036779) 16:11:19
北京-阴空(-) 16:11:48
第一幅图左侧的利率是不一定的。 所有的标的都会优先给资产去匹配, 之后才考虑是否展示到前台。
北京-喜(-) 16:11:51
用户维度是按笔算的?每一笔里的历史投递情况,需要作为下一次的决策依据的。 你看下决策树
北京-阴空(-) 16:12:14
一个产品一个用户。 是一条数据
广州-小护士<-> 16:12:56
没懂业务背景, 主要是业务背景没介绍清楚,突然来一段动态匹配问题,不好搞
北京-喜(-) 16:14:01
广州-小护士<-> 16:14:21
感觉这个不是决策树问题, 决策树只是做用户分群
北京-喜(-) 16:14:30
比如相亲相了很多之后,后来决策可能变,比如去他妈的,长相不看了
北京-阴空(-) 16:14:59
@北京-喜 我也是你这个想法,打算把所有的数据压倒这个树里, 然后从中取数据去匹配。
北京-喜(-) 16:15:00
算法我是渣渣, 我只是告诉他 历史因子是要加进来的
北京-阴空(-) 16:15:22
可是。 就是修改太频繁。。每次修改涉及到了树结构的变化。。
北京-喜(-) 16:15:34
改成定期的, 只要最后能达标即可, 实时是需要计算能力的
北京-阴空(-) 16:16:08
定期的也去给树上锁吗
北京-喜(-) 16:16:29
需要优化你的投递窗口, 排一次序,并行投。 投完之后,在排下一次,新排序,使用以前的投递结果, 即便用户不改,你的模型也是变化的
北京-阴空(-) 16:18:30
定期的时候是要上锁是吧。 你说的优化投递窗口有什么办法吗
北京-喜(-) 16:18:44
排和投 都需要改成并行的, 并行计算、逐级归并, 提高效率 这不是锁的问题
成都-梅小西(-) 16:20:04
让你跑定期跑job,不需要锁, 要实时的话,难度大
北京-喜(-) 16:21:22
排的时候不投,或者分批次投, 这个看你是并行之后,100W数据归并完毕,再投. 还是说分段,比如分成128段并行排序,排到比如4段 就停止, 然后依次投, 第一段投完之后, 第1段如果有剩余,继续排。 期间并行投第2端
北京-阴空(-) 16:22:44
广州-小护士<-> 16:23:22
用户投的钱,然后呢, 这个东西对应用户每一笔钱还是多笔钱?
北京-阴空(-) 16:24:23
@北京-喜 这里没懂,没有排序的情况下就分成128段了吗
北京-喜(-) 16:24:50
对
北京-阴空(-) 16:24:54
我们也是担心并行的话算错了。。
北京-喜(-) 16:25:07
你要看你的目标是什么
北京-阴空(-) 16:25:09
不是排好序了再分堆吗。。
北京-喜(-) 16:25:16
这个目标是多次达成的 还是 单次达成的
北京-阴空(-) 16:25:23
多次
北京-喜(-) 16:25:34
那就是最终是对的就可以了
北京-阴空(-) 16:25:48
恩,最终尽可能优
北京-喜(-) 16:25:50
你可以加一个风险区间控制, 不断优化这个流程
北京-阴空(-) 16:27:40
有个地方没懂, 数据一开始分成128段。 那么都不能随便从某一段取吧。都不知道哪段的是更优的。
北京-喜(-) 16:27:51
单次没有最优解, 比如也可以按照排序 把钱分几个档,依据档分标的, 我的意思是,比如有100W用户, 50W一个批次投,50W一个批次投, 第一个50W整体 比如执行6个周期搞定, 这个你得提前排好序吧。第二个50W比如执行10个周期搞定
北京-阴空(-) 16:30:59
我懂了你的意思了。 在这五十万内, 追求最优是吧。
北京-喜(-) 16:31:09
对的, 但是你要有风控
北京-阴空(-) 16:31:23
我靠。 牛逼啊
北京-喜(-) 16:31:30
就是标的端能不能满足 用户端的诉求
北京-阴空(-) 16:31:35
明白
北京-喜(-) 16:31:36
这个你们应该是有的吧 是题外的
北京-阴空(-) 16:31:49
别到最后。。就这五十万的人投了最好的了。。相当于把原本资产端的排序扩展到了标的端
北京-喜(-) 16:32:16
如果你嫌排序慢, 可以并行排, 如果你嫌投递慢 可以并行投, 单机搞不定,就分布式排,分布式投。 分布式排 就是大数据计算.
北京-阴空(-) 16:35:19
有两个问题。 第一个是投完的数据,是不是直接放到最后的队位,接着排就好。第二个问题是,这样还需要定时吗
北京-喜(-) 16:35:53
段位是你定的, 段不足的话,可以补位, 也可以不补, 比如新用户的数据,补到第一个段, 假如段都满了,可以加段, 第3个段产生了, 后面再优化,让每个段内的数据分布,尽可能均匀, 比如你的排序,其实是计算 以及 权重累计的过程, 后续让每个段内的权重分布趋势 基本一致就可以了, 然后在把标的 也分成3段, 第一段钱,用第一段标的,或者标的的1/3. 你也可以把用户的每笔投,切成几段,比如用户投的5W,8%回报:你切成1W6%,1W7%,1W8%,1W9%,1W10%
北京-阴空(-) 16:42:48
我感觉这个就太复杂了。 我们公司不一定能承受这个方法了
北京-喜(-) 16:43:30
这个是逐渐的,后面为了最求利润,可能要切, 早期的话,是先满足业务
北京-阴空(-) 16:43:54
假定已经按照预料的段位分好了。 用户资产的队列有10段。 第一段第一个去投,还有剩余这个时候要回到队列。这个时候要重排序吗
北京-喜(-) 16:44:40
要的
北京-阴空(-) 16:44:53
就是每一个重拍一次是吧。
北京-喜(-) 16:44:54
因为投递结果,是下一次计算/排序的因子, 会影响对标的的选择
北京-阴空(-) 16:45:53
北京-喜(-) 16:46:18
因为你把用户的钱拆了嘛
北京-阴空(-) 16:46:20
我一开始的想法是这样。 把队列的数据压倒这个树里面。
北京-喜(-) 16:47:01
不用, 每个计算项, 你给个权重, 最后加权出来 整体按权重排即可
北京-阴空(-) 16:47:38
这个权重给不了好像
北京-喜(-) 16:47:49
权重值早期粗,后续不断优化, 比如过期
北京-阴空(-) 16:48:10
这个好像公司给不出来这个东西,缺少对应的数据支持
北京-喜(-) 16:48:21
早期一刀切, 后期可能差几天 都要算进去, 你的if else ,也是一刀切,也不是精细的。 本质上还不如权重
北京-阴空(-) 16:49:57
我记得之前我提过一个思路,就是算个分出来。 然后将多维度变成单维度排序。应该是类似你说的权重了
北京-喜(-) 16:50:49
对的, 你代码写出来的 和权重一样的, 比如一个分支走if +1, 走else+0
北京-阴空(-) 16:51:20
对, 你模拟下你最简单的场景, 就是这个. 但是在往后,权重能做的事情,可不是if else能搞定的
北京-阴空(-) 16:52:06
上次说分的情况。 没有推动。。不知道是我人微言轻还是思路上不好。 我说下我理解的你的方法哈。两边队列都分割成同样的比例。 然后可以并行排序和并行投递。 有新增的数据或者可以继续使用的数据,先考虑回到原有的段,超额的话,新增段。不能新增吧。。新增的话两边不匹配了。。
北京-喜(-) 16:54:19
这个看标的 质量和配比了
北京-阴空(-) 16:54:39
不是打算两边切割成同样数量吗
北京-喜(-) 16:54:44
会不会导致 资金饥饿,不达标, 做的越细,结果越好. 我原来的思路是 ,假如资金是3段, 那么针对具体的标的,每个段投标的时候,只允许它最多投到1/3。 剩下的2/3预留给另外2个段.
北京-阴空(-) 16:57:05
北京-喜(-) 16:59:28
这个和你整体当做一段 问题是一样的, 分段是提高程序效率,不是质量
, 所以,会希望把整体排序来保证优先投递质量,需要额外细化对标的做权重, 对钱做权重2个之间如果匹配,做个规则
北京-阴空(-) 17:00:30
满足规则成交是吧
北京-喜(-) 17:00:32
各自的权重模型和匹配规则,未来都是不断优化的
北京-阴空(-) 17:01:54
那有可能b投了一个后,因为不满足规则。 只有a段在一直投标了是吧。如果每个段都没有满足。
北京-阴空(-) 17:01:58
在降低标准。。
北京-喜(-) 17:02:17
这个就是饥饿的情况, 要么给每个段都留点饼, 这个是指的,对于一个标的,不允许1个段吃完, 要么就是把标的分一分段,每个段内的质量基本差不多, 然后段对段去投, 段内的质量,你需要量化的,某个回报率明显缺失(被投完),是需要补的,或者重排
北京-阴空(-) 17:06:19
两个队列分段都尽量保持质量均匀吗
北京-阴空(-) 17:08:53
有个地方我觉得是有问题的。 分词a,b,c三段,三段分别投递。 然后a段普遍其实优先级都大于b如果每个段投递的都是相当数量的,肯定是不行。 所以要有规则。b段不满足的话,就只允许a段投递,之后再降低规则。 但是假如你降低规则后,有新的满足高级规则的进来了。 这个就有可能一直沉着了。
北京-喜(-) 17:09:57
北京-阴空(-) 17:15:44
好多了。 喜神的字和我风格好像啊。。
北京-喜(-) 17:16:16
新数据来,是计算,然后加入资源池, 段区对接业务,资源不足,跟中间的管理区申请
北京-阴空(-) 17:17:06
两个队列都这么处理。 然后分值一样的区间进行撮合交易是吧。
北京-喜(-) 17:17:33
分值这个 按照业务了, 不一定是一对一, 同一个标的 基本是什么分值是固定的, 钱不是,因为钱被拆了, 当然标的也可以变啊, 比如同比下,标的可以是2个分值,
北京-阴空(-) 17:19:09
恩,因为我担心段二整体都比段一差, 结果段二查的部分给投光了,所以考虑分值相近的部分去撮合。
北京-喜(-) 17:19:27
所以优化, 不断优化
北京-阴空(-) 17:20:24
优化即指打分的模型,也指两个队列的撮合规则是吧。
北京-喜(-) 17:21:32
对, 新资源是不是可以入段,取决于段内现状, 出现空缺,去向资源层申请,或者资源层监控, 有资源就补位
北京-阴空(-) 17:22:29
喜神非常感谢。 感觉有了一个整体思路。 以我对公司的了解。。这么复杂的方式公司肯定不会采用的。。。。我自己尝试练习下.
北京-喜(-) 17:22:34
资源没有。质量断层之后,可能需要重新分, 只有重新分的时候,才需要锁资源。单纯的增量入队入段,是不需要的
北京-阴空(-) 17:23:35
资源层监控是指起个job去监控每个段位数据的减少是吗
北京-喜(-) 17:23:47
是的
北京-阴空(-) 17:24:49
北京-喜(-) 17:25:06
是的, 钱端,计算过程多, 没被投一次 肯定要重新计算一次
北京-阴空(-) 17:25:38
我自己抽空写一下,写成功了的话,拿数据跑一下,如果真的性能比数据库好,领导应该会采用。
北京-喜(-) 17:25:49
数据库是另外一个事
北京-阴空(-) 17:25:55
是的,放回去需要重算。重新放回是放回资源层,还是放回哪里
北京-喜(-) 17:27:40
这个看你的入队策略, 允不允许插队、还是天维度做完即可, 这里也是可以细化的
北京-阴空(-) 17:30:10
感觉每个段里面不同分值区间和另一个队列里的进行匹配好麻烦。。既要考虑尽可能让高分去投高分。。又要避免高分的一直停着没有投出去。。
北京-喜(-) 17:30:54
可以只投一部分, 下一次他的分值就变了, 这个是前面提到的 是不是预拆:6% 7% 8% 各来1W, 这样是参差不齐都有
北京-阴空(-) 17:32:13
你这个方案把钱也拆了是吧。
北京-喜(-) 17:32:21
我没拆钱, 这个是分层 和 匹配, 整体还比较粗 实现不了细粒度的投递质量
北京-喜(-) 17:33:26
这个重分配的那个,假如这个是钱, 回来的时候,你可以让他重新排队,就是4那个线。 也可以插队,就是5那个线, 对于钱,假如现在得分是80, 你可以拆成 70 80 90。 假如是70 ,你可以拆成60 70 80。 假如是90,你可以拆成80 90 100, 80的话,就是好坏都有,70的话就是2个坏的1个中的。 90的话就是1个中的2个好的
北京-阴空(-) 17:36:59
北京-喜(-) 17:37:22
会的, 这个时候标的端 要补标的, 没有可用标的,就要重新分配, 重新分配还不行,那你只能接受了
北京-阴空(-) 17:38:06
整体重排吗
北京-喜(-) 17:38:11
这个情况就是资产端与标的端 对不齐. 不用, 改分段规则即可, 从中间往右侧去的时候,你可以理解成有个shard方式
北京-阴空(-) 17:39:11
原本段一匹配段一改成 段二匹配段一这种是吗
北京-喜(-) 17:39:24
这个不好, 最好是自治
北京-喜(-) 17:39:59
在这里解决, 以这个框为例, 右侧段内的标的,都是左侧资源内的,是关联的, 所以你可以清空右侧段, 重新分段, 按照分值 和 分值内的标的数目,决定如何分.
北京-阴空(-) 17:41:23
懂了应该均匀分布。 如果是正好匹配剩余几个的情况呢? 比如,资产端段1 100分的有10个, 标的的段1有9个。
北京-喜(-) 17:43:00
理论是看你的积分规则,你怎么积分的,基本决定标的能不能被投, 这个不是啊, 是钱数啊, 不是这个数量
北京-阴空(-) 17:43:34
我是说最后撮合的时候。
北京-喜(-) 17:43:35
是钱的total值, 你也可以作为积分的计算因子加进来, 积分 -> 分值, 名词对齐下, 你也可以引入批次的概念。 一个批次投完之后(段内完成一次),重新计算标的分值,来解决标的和资产的对齐关系
北京-阴空(-) 17:49:07
每个分数段的标的是一定会小于资产的。
北京-喜(-) 17:50:03
那你们不是负债了么, 还是有资产端的一部分优势产品,内部投,没开放给用户
北京-阴空(-) 17:51:19
资产就是用户投资来的钱。 资产是债权。债权一般是少于资金的。
北京-喜(-) 17:52:01
那你需要拿到一个数值, 这个负债会影响 资产和标的如何对接, 所以需要有个量化的数字 ,然后整体的计算和分配模型,一直保持在负债区间内,那么就是个好策略
广州-小护士<-> 18:25:03
今天没看懂喜神的分享
北京-喜(-) 18:34:52
简单说:源数据 -> 预计算 -> 实际用 ,分了这三层(每一层都有自己的资源池,资源不足,跟上一级要), 这样资源就是隔离的了, 极端最坏情况下,场景会回退到不分层,只有1个层的情况下的效率. 可以拿多级缓存来比对。每层缓存放的是不同维度的数据,上一级缓存没有数据的时候,跟下一级要,都没有,最后从DB拿。
最坏情况是,缓存全失效,需要重新从DB向各个缓存预热(计算、处理、刷存储)。除了这个情况,其他都算健康的。
所以比只有一个数据源(DB)效率要好很多(分层隔离、独立计算、独立逻辑)
北京-阴空(-) 18:53:31
喜神。。你这样解读感觉太震撼了。。。刚才拿外卖的时候有个想法。能不能,从计算层拿固定数额的到使用层。 先从头部取。 然后从标的队列去对应的数量。 这样可以减少撮合时候的不匹配。
北京-喜(-) 18:56:31
可以的。流量、流速都可以控制, 质量、匹配规则 也可以, 无非是哪里做厚哪里做薄的事
北京-阴空(-) 18:58:37
再问个low的问题。这样比数据库order by, 好在哪里呢
北京-喜(-) 19:00:40
资源隔离的, 资源不隔离,就有竞争问题,你的这个场景
北京-阴空(-) 19:03:31
公司打算单线程做。 所以,可能没有考虑竞争问题
北京-喜(-) 19:04:04
因为元数据不是元数据, 源数据不是元数据, 无法直接用, 要排序 计算 分配
北京-阴空(-) 19:04:54
我们现在的模型是可以的。 我理解排序计算分配是为了更加高效。 我懂了你的意思了, 源数据是不能直接使用。没有排序。 所以,他们加入到数据库 , 通过数据库orderby了
北京-喜(-) 19:05:36
是的, 所以你需要保护他
北京-阴空(-) 19:06:08
所以,直接用数据库缺点是什么?
北京-喜(-) 19:06:44
慢是一方面, 取决于排序复杂度和存量数据大小, 另外还有个问题是风险, DB挂了的话,上层其实可以有次优解, 把自己的资源池耗空 能抗一会业务, 不从DB补位标的而已, 另外架构上 建议读写分离,这个有空再说.
北京-喜(-) 19:10:50
你的排序和计算 都是读逻辑, 但是放在源库上了, 源库做写业务比较好,比如实际的投的结果和新标的入库
北京-阴空(-) 19:10:43
明白
北京-喜(-) 19:13:53
大数据计算 好像有个模型并行和数据并行?
北京-阴空(-) 19:13:59
是的。
北京-喜(-) 19:14:15
模型并行那个适合你的场景好像. 思路是类似, 三层模型. 并行 隔离.