Multi-hop path finding

Abstract

Systems and techniques are provided for multi-hop path finding. Order data describing an order may be received. The order data may include a currency pair, a price level, and a volume. A one-hop path structure may be generated based on the order data describing the order. The one-hop path structure may include one-hop paths for the currency pair. The one-hop path structure may be written to a first ring buffer. The one-hop path structure may be read from the first ring buffer. Two-hop path structures may be generated by joining the one-hop path structure with other one-hop path structures. A value for the relative importance of the two-hop path structures may be determined to be greater than a threshold. Combined two-hop path structures may be written to a second ring buffer when the value for the relative importance of the two-hop path structures is greater than the threshold.

1 . A computer-implemented method comprising:
 executing a first thread, the first thread repeating operations comprising:
 receiving order data comprising a currency pair, a price level, and a volume, 
 generating a one-hop path structure based on the order data, the one-hop path structure comprising one or more one-hop paths for the currency pair, and 
 writing the generated one-hop path structure to a first ring buffer; and 
   executing a second thread, the second thread repeating operations comprising:
 reading, from the first ring buffer, one of the at least one one-hop path structures written to the first ring buffer by the first thread, 
 generating one or more two-hop path structures by joining the one-hop path structure read from the first ring buffer with one or more other one-hop path structures, 
 writing one or more combined two-hop path structure based on the generated two-hop path structure to a second ring buffer. 
   
     
     
         2 . The computer-implemented method of  claim 1 , wherein the first thread further repeats operations comprising determining that a relative importance value of the generated one-hop path structure is greater than a first threshold before writing the generated one-hop path structure to the first ring buffer. 
     
     
         3 . The computer-implemented method of  claim 1 , wherein the second thread further repeats operations comprising checking the first ring buffer until at least one generated one-hop path structure is available in the first ring buffer after being written to the first ring buffer by the first thread. 
     
     
         4 . The computer-implemented method of  claim 1 , wherein the second thread further repeats operations comprising determining that one or more of the generated one or more two-hop path structures have relative importance value greater than a second threshold before writing one or more combined two-hop path structure based on the generated two-hop path structure to a second ring buffer. 
     
     
         5 . The computer-implemented method of  claim 1 , wherein the first thread and second thread operate concurrently and asynchronously on a computing device comprising a memory, and wherein the memory comprises the first ring buffer and the second ring buffer. 
     
     
         6 . The computer-implemented method of  claim 1 , wherein the first thread further writes generated one-hop path structures to a persistent data structure for one-hop path structures in a memory of a computing device and the second thread writes combined two-hop path structures to a persistent data structure for two-hop path structures in the memory of the computing device. 
     
     
         7 . The computer-implemented method of  claim 1 , wherein a threshold used by a thread is based on a set point and number of hops in the paths of the path structures generated by the thread, and wherein the set point is based on an amount of time between the receiving of the order data by the first thread and determining the relative importance value for the one-hop path structure by the first thread. 
     
     
         8 . The computer-implemented method of  claim 1 , further comprising executing one or more additional threads, each of the one or more additional threads responsible for paths with a different number of hops, each additional thread of the one or more additional threads performing operations comprising:
 checking a ring buffer for the additional thread until at least one combined path structure is available after being written to the ring buffer for the additional thread by a thread responsible for paths with one fewer hop than a number of hops in paths the additional thread is responsible for,   reading, from the ring buffer for the additional thread, one of the at least one combined path structures written to the ring buffer for the additional thread, and   generating one or more path structures comprising paths with the number of hops the additional thread is responsible for by joining the combined path structure read from the ring buffer for the additional thread with one or more one-hop path structures.   
     
     
         9 . The computer-implemented method of  claim 8 , executing the one or more additional threads, each of the one or more additional threads responsible for paths with a different number of hops, further comprises each additional thread of the one or more additional threads further performing operations comprising:
 determining a relative importance value for at least one of the generated one or more path structures, and   writing, for any of the generated path structures with a relative importance value greater than a threshold associated with the additional thread, a combined generated path structure based on the generated path structure to a ring buffer for another additional thread.   
     
     
         10 . A computer-implemented system comprising:
 one or more storage devices;   a communications device that receives order data comprising a currency pair, a price level, and a volume from exchange computing devices; and   one or more processors that execute one or more threads, the one or more threads comprising:
 a first thread that receives order data comprising a currency pair, a price level, and a volume, generates a one-hop path structure based on the order data, the one-hop path structure comprising one or more one-hop paths for the currency pair, and writes the generated one-hop path structure to a first ring buffer, and 
 a second thread that reads, from the first ring buffer, one of the at least one one-hop path structures written to the first ring buffer by the first thread, generates one or more two-hop path structures by joining the one-hop path structure read from the first ring buffer with one or more other one-hop path structures, and writes one or more combined two-hop path structure based on the generated two-hop path structure to a second ring buffer. 
   
     
     
         11 . The computer-implemented system of  claim 10 , wherein the first thread further determines that a relative importance value of the generated one-hop path structure is greater than a first threshold before writing the generated one-hop path structure to the first ring buffer. 
     
     
         12 . The computer-implemented system of  claim 10 , wherein the second thread further checks the first ring buffer until at least one generated one-hop path structure is available in the first ring buffer after being written to the first ring buffer by the first thread 
     
     
         13 . The computer-implemented system of  claim 10 , wherein the second thread further determines that one or more of the generated one or more two-hop path structures have relative importance value greater than a second threshold before writing one or more combined two-hop path structure based on the generated two-hop path structure to a second ring buffer. 
     
     
         14 . The computer-implemented system of  claim 10 , wherein the first thread further writes generated one-hop path structures to a persistent data structure for one-hop path structures stored in the one or more storage devices and the second thread writes combined two-hop path structures to a persistent data structure for two-hop path structures stored in the one or more storage devices. 
     
     
         15 . The computer-implemented system of  claim 10 , wherein the one or more processors execute the first thread and second thread concurrently and asynchronously. 
     
     
         16 . The computer-implemented system of  claim 10 , wherein a threshold used by a thread is based on a set point and number of hops in the paths of the path structures generated by the thread, and wherein the set point is based on an amount of time between when the first thread receives the order data and the first thread determines the relative importance value for the one-hop path structure. 
     
     
         17 . The computer-implemented system of  claim 10 , wherein the one or more processors further execute one or more additional threads, each of the one or more additional threads responsible for paths with a different number of hops, wherein each additional thread of the one or more additional threads checks a ring buffer for the additional thread until at least one combined path structure is available after being written to the ring buffer for the additional thread by a thread responsible for paths with one fewer hop than a number of hops in paths the additional thread is responsible for, reads, from the ring buffer for the additional thread, one of the at least one combined path structures written to the ring buffer for the additional thread, and generates one or more path structures comprising paths with the number of hops the additional thread is responsible for by joining the combined path structure read from the ring buffer for the additional thread with one or more one-hop path structures. 
     
     
         18 . The computer-implemented system of  claim 17 , wherein each of the one or more additional threads further determines a relative importance value for at least one of the generated one or more path structures and writes, for any of the generated path structures with a relative importance value greater than a threshold associated with the additional thread, a combined generated path structure based on the generated path structure to a ring buffer for another additional thread. 
     
     
         19 . A system comprising: one or more computers and one or more storage devices storing instructions which are operable, when executed by the one or more computers, to cause the one or more computers to perform operations comprising:
 executing a first thread, the first thread repeating operations comprising:
 receiving order data comprising a currency pair, a price level, and a volume, 
 generating a one-hop path structure based on the order data, the one-hop path structure comprising one or more one-hop paths for the currency pair, and 
 writing the generated one-hop path structure to a first ring buffer; and 
   executing a second thread, the second thread repeating operations comprising:
 reading, from the first ring buffer, one of the at least one one-hop path structures written to the first ring buffer by the first thread, 
 generating one or more two-hop path structures by joining the one-hop path structure read from the first ring buffer with one or more other one-hop path structures, 
 writing one or more combined two-hop path structure based on the generated two-hop path structure to a second ring buffer. 
   
     
     
         20 . The system of  claim 19 , wherein the instructions are operable, when executed by the one or more computers, to cause the one or more computers to further perform operations comprising executing one or more additional threads, each of the one or more additional threads responsible for paths with a different number of hops, each additional thread of the one or more additional threads performing operations comprising:
 checking a ring buffer for the additional thread until at least one combined path structure is available after being written to the ring buffer for the additional thread by a thread responsible for paths with one fewer hop than a number of hops in paths the additional thread is responsible for,   reading, from the ring buffer for the additional thread, one of the at least one combined path structures written to the ring buffer for the additional thread, and   generating one or more path structures comprising paths with the number of hops the additional thread is responsible for by joining the combined path structure read from the ring buffer for the additional thread with one or more one-hop path structures.