Author: ZmnSCPxj 2020-05-21 05:01:36
Published on: 2020-05-21T05:01:36+00:00
The Lightning Network is a system that allows for fast and affordable transactions on the Bitcoin blockchain. To compensate for possible future increases in size and make it more practical to run a Lightning Network node on less-capable devices, reducing routemap representation size is important.This writeup proposes a routemap representation with very minimal reduction in size but allows for the implicit creation of a routefinding heuristic for pathfinding. The proposal involves using an array-based storage system where nodes and channels are stored in two large arrays, with references to channels and nodes being indices into the array rather than pointers. The memory manager needs less overhead in managing two large arrays compared to managing lots of objects of varying sizes.Deletion of channels and nodes from the routemap can be done using a freelist, but the writer proposes using Cheney 2-finger Garbage Collection instead. Cheney 2-finger Garbage Collection is a copying semispace collector that requires two pointers: a scan pointer and an allocation pointer. It involves copying live objects into a new memory space and recovering and reusing garbage and copied-from memory.The order in which objects are scanned is by "spreading" out from the root object. Breadth-first ordering is generally frowned upon in modern systems since most object accesses are deep rather than wide, and thus breadth-first tends to arrange objects in ways that are not cache-friendly if most object access is deep. However, the Cheney breadth-first ordering creates a nice heuristic for pathfinding.If A is "our" node, then in order to create a route from our node to any arbitrary payee, we simply start at the payee and head down links to nodes that have lower addresses, and inevitably, we will go towards "our" node, the special root node that is at the lowest address in the routing table.The article discusses the use of Cheney's algorithm for garbage collection in pathfinding algorithms. It explains how Cheney's algorithm can be used as a guide for which nodes to open first, but can also evaluate paths using fees and other factors.The article then discusses the issue of semispace collection, which requires twice the memory during collection. To address this issue, the author suggests writing the tospace objects into a disk file and reloading the in-memory arrays from the tospace file(s) after the Cheney run has completed.The article goes on to discuss incremental collection and the use of the tri-color abstraction to determine if a fromspace object is black, gray, or white without adding any more memory to represent those sets. The author suggests that the Cheney collector gives some very easy ways to determine the colors of fromspace objects.The article also discusses how changes to the routemap can be handled by making the collection algorithm incremental, allowing incoming changes to the routemap graph to be accepted while retaining responsiveness even while a collection is being performed.Finally, the article discusses tenuring and how it can help against losing subgraphs. The author suggests selecting some nodes with particularly long-lived channels and adding them to the root set, executing Cheney as follows: first put our own node to the root set and execute Cheney as normal; when Cheney completes (scan pointer == allocation pointer), check if any tenured nodes are still white (have no forwarding pointer) and add them to the gray set (copy them to tospace and advance the allocation pointer).
Updated on: 2023-06-03T01:38:45.403063+00:00