3 ms·
Ok, I'll try and use an example from financial services: Disclaimer: Never worked in financial tech, I have thought about this problem for 5 mins. This is unli
by yazaddaruvala 10y ago
Ok, I'll try and use an example from financial services:
Disclaimer: Never worked in financial tech, I have thought about this problem for 5 mins. This is unlikely to be an optimal solution to keeping a sorted set of distributed data. I'm just trying to show how basic knowledge of data structures helps in the field of distributed systems.
Lets say you need to keep a sorted set of sooooo much data that you cannot keep it all on one machine. I would imagine all financial services firms have some custom datastore which has "potential buy orders" and need to keep them all sorted by profitability to efficiently search/insert/remove from that datastore.
In such a situation, my instincts would be to create a distributed, redundant Heap. Now, how do you build a distributed, redundant Heap, without understanding how a Heap works? How do you even know what to look for if you don't know what a Heap is?
Now, lets say you've built it such that each node in your distributed network acted like a node in a Heap, and the left "pointer"(i.e. url to other computer) meant "less than" and the right "pointer" meant "greater than". Now you have this data store in production and all of a sudden you realize performance worsens over time... "WHY is this happening? Is there some memory leak?". You investigate and realize that all of your data isn't being distributed evenly! "Do I need to like.. shuffle the data around? How do I get it so that the data is evenly distributes?"
At this point if you do not know what a red-black tree is, what do you even google look for? Lets say you dig around for a while and find out about re-balancing trees. Now you have to implement it, and eventually you figure out that one of the best ways is to color your nodes. When a future colleague/manager asks, "What is this system, please describe it to me?" wouldn't it be nice to just say "Oh visualize it kinda like a distributed red-black tree. It holds XXX data, and ensures that it is always sorted and re-balanced for optimal performance."
- nerfhammer 10y agoFWIW finance normally uses big relational databases (because you absolutely need strong transaction support), something else off-the-shelf, or Microsoft Excel.
- fragmede 10y agoOf course there's some sort of B-tree somewhere in the stack; that's not the question. With dozens of database stacks to choose from, many companies won't have anybody actively and regularly working in the database's code, nor in the OS kernel code either. If, then, an individual can successfully contribute to the company without ever hearing of a red-black tree, what's the value in testing for it, past "this is how we've always done it"? (How long it would take someone who doesn't know CS lingo to string together "tree" and "balance" and plug that into Google, I don't know, but I suspect it's not impossible to find.)
- yazaddaruvala 10y ago> Of course there's some sort of B-tree somewhere in the stack; that's not the question. You've misunderstood me. I'm literally talking about building a distributed B-Tree or Heap. As in, a Heap which cannot fit in memory or storage of any one node. Think: S3/DynamoDB is a distributed, highly available HashTable; _____ is a distributed, highly available Heap.