Fashionable things
Today, I’m determined to talk about technologies that were very fashionable and spawned a shaft of publications, but over the years did not lead to any significant practical results, or their niche was so narrow that its comparison with the original expectations creates a satirical effect. As a rule, such technologies create an impression of “magic” for newbies at the first acquaintance, something that solves all problems in an incredibly tricky way, but sober professional evaluation in Big-O , real numbers and circumstances ends with a diagnosis: “dummy”.
Experience shows that such fashionable things have four qualities in a more or less vivid way: "magic" (admires complexity), unnaturalness (going against wool, natural order of things), complexity (it is always bad) and inapplicability (only in specific circumstances, but whatever circumstances you take - it does not apply).
So, proceed to the autopsy.
In terms of magic, the undisputed leader is Blum filters . Let me remind you that the Blum filter is a probabilistic data structure that allows you to encode a certain set of values so as to eliminate false negatives (if the value belongs to a set, the filter will respond positively), and make false positives unlikely (sometimes the filter will allow outliers, alas). From a practical point of view, the filter allows you to reduce the memory cost of storing the set by a factor of ten, with the cost that determinism is lost, probability appears. So The gain is a coefficient, and in terms of Big-O there is none at all. However, Blum filters are often perceived by a typical graduate student as a “silver bullet”, especially when he adjusts with a degree of difficulty and tries to heal the problem by optimizing coefficients. In practice, Blum filters are applied, but rarely and in special circumstances, as additional optimization.
A unique fusion of magic and unnatural - digital fountains . In simple terms, this is something like RAID-5, but over the network. The data is divided into series of p pieces, but p + q recombined pieces are sent to the network — so that, having received any p recombined pieces, you can recover the originals. The only difficulty is that recombination algorithms with good properties are very difficult to implement algorithmically. In conventional computer networks, if a packet is lost, it is easier to re-request it (it rarely takes more than 0.1 second) than to muddle with recombinations. But there are special niches where digital fountains tried to adapt - as a rule, into one-way communication systems. Mitzenmaher tried to save multicast fountains, for example. I personally spoke with a Russian German who is moving a digital radio standard based on digital fountains. Perhaps, when the spacecraft will begin to surf the spaces, the digital fountains will massively go into production, but for now this is an exotic toy.
')
Favorably combines all four main qualities of another technology - DHT , distributed hash tables. It would seem that in a distributed network, you can divide the key space between multiple nodes and route requests between them - so that each node will be responsible only for a certain segment of the hash table, and its total capacity will reach astronomical values. Alas, a number of questions arose. For example, different segments may have different popularity, and while some nodes are idle, others will be buried under a shaft of requests. Also, the nodes have no motivation to work honestly - in the processing of other people's requests, you can also shaltur. But the most important and incurable is that DHT needs a logarithmic number of round-trips to find the node responsible for the desired part of the table. RTT (round trip time, package travel time on the Internet) is fundamentally unimprovable, since it is determined by the speed of light. While the capacity of memory and disks grows exponentially, allowing you to store more and more data in data centers, RTT remains in place. Alas, at least “logarithmic” is not enough, but still it is a multiple of more than one round-trip required to request a data center. It turned out that the technology optimizes a resource that is already growing exponentially (memory), but losing on a resource that cannot be improved in principle (round-trip). DHT is now, with half the sin, used for tracking peers in bit-torrent systems, but, as one of DHT founding fathers Paul Francis wrote,
Behind the leaders in all qualities except inapplicability, another once-fashionable technology - feast-to-feast (in the sense of BitTorrent, and not in the sense of Skype). The idea of raising traffic from user machines promised solid dividends - because unlike centralized systems, in a feast-and-feast system available resources grow in proportion to the number of participants, which means flash crowds and the Sleshdot effect will not kill the system, but only make it stronger. It would seem that with big-O everything is in order. Alas, computers and end-user Internet connections are not such convenient objects for operation. Forwarding the connection to the end user is fieldwork, consuming 90% of the budget when building networks. Compact, under sterile conditions, upgrade the data center is much easier and more profitable. Economy of scale in action - trunk channels and data centers developed much faster than user connections, and server traffic became immeasurably cheaper and more reliable than the last mile. Today, the feast is interesting only as a legal loophole for the distribution of pirated content by technically savvy students. Economically, the topic is not absolutely interesting, the scientific interest is fading away.
Here you can also add a multicast , but it was fashionable, even when I asked my mother for fifteen kopecks for ice cream.
What conclusions can be drawn from this? It's simple. You should not get involved in the beauty and fashionability of technology, you only need to pragmatically assess its capabilities and costs. Common sense is enough.
Experience shows that such fashionable things have four qualities in a more or less vivid way: "magic" (admires complexity), unnaturalness (going against wool, natural order of things), complexity (it is always bad) and inapplicability (only in specific circumstances, but whatever circumstances you take - it does not apply).
So, proceed to the autopsy.
In terms of magic, the undisputed leader is Blum filters . Let me remind you that the Blum filter is a probabilistic data structure that allows you to encode a certain set of values so as to eliminate false negatives (if the value belongs to a set, the filter will respond positively), and make false positives unlikely (sometimes the filter will allow outliers, alas). From a practical point of view, the filter allows you to reduce the memory cost of storing the set by a factor of ten, with the cost that determinism is lost, probability appears. So The gain is a coefficient, and in terms of Big-O there is none at all. However, Blum filters are often perceived by a typical graduate student as a “silver bullet”, especially when he adjusts with a degree of difficulty and tries to heal the problem by optimizing coefficients. In practice, Blum filters are applied, but rarely and in special circumstances, as additional optimization.
A unique fusion of magic and unnatural - digital fountains . In simple terms, this is something like RAID-5, but over the network. The data is divided into series of p pieces, but p + q recombined pieces are sent to the network — so that, having received any p recombined pieces, you can recover the originals. The only difficulty is that recombination algorithms with good properties are very difficult to implement algorithmically. In conventional computer networks, if a packet is lost, it is easier to re-request it (it rarely takes more than 0.1 second) than to muddle with recombinations. But there are special niches where digital fountains tried to adapt - as a rule, into one-way communication systems. Mitzenmaher tried to save multicast fountains, for example. I personally spoke with a Russian German who is moving a digital radio standard based on digital fountains. Perhaps, when the spacecraft will begin to surf the spaces, the digital fountains will massively go into production, but for now this is an exotic toy.
')
Favorably combines all four main qualities of another technology - DHT , distributed hash tables. It would seem that in a distributed network, you can divide the key space between multiple nodes and route requests between them - so that each node will be responsible only for a certain segment of the hash table, and its total capacity will reach astronomical values. Alas, a number of questions arose. For example, different segments may have different popularity, and while some nodes are idle, others will be buried under a shaft of requests. Also, the nodes have no motivation to work honestly - in the processing of other people's requests, you can also shaltur. But the most important and incurable is that DHT needs a logarithmic number of round-trips to find the node responsible for the desired part of the table. RTT (round trip time, package travel time on the Internet) is fundamentally unimprovable, since it is determined by the speed of light. While the capacity of memory and disks grows exponentially, allowing you to store more and more data in data centers, RTT remains in place. Alas, at least “logarithmic” is not enough, but still it is a multiple of more than one round-trip required to request a data center. It turned out that the technology optimizes a resource that is already growing exponentially (memory), but losing on a resource that cannot be improved in principle (round-trip). DHT is now, with half the sin, used for tracking peers in bit-torrent systems, but, as one of DHT founding fathers Paul Francis wrote,
DHT papers published all around the same time (along with Chord and Pastry). It’s been a little bit different, though it’s not a problem. It’s appropriate to gossip-style approach doesn’t work ...).
Behind the leaders in all qualities except inapplicability, another once-fashionable technology - feast-to-feast (in the sense of BitTorrent, and not in the sense of Skype). The idea of raising traffic from user machines promised solid dividends - because unlike centralized systems, in a feast-and-feast system available resources grow in proportion to the number of participants, which means flash crowds and the Sleshdot effect will not kill the system, but only make it stronger. It would seem that with big-O everything is in order. Alas, computers and end-user Internet connections are not such convenient objects for operation. Forwarding the connection to the end user is fieldwork, consuming 90% of the budget when building networks. Compact, under sterile conditions, upgrade the data center is much easier and more profitable. Economy of scale in action - trunk channels and data centers developed much faster than user connections, and server traffic became immeasurably cheaper and more reliable than the last mile. Today, the feast is interesting only as a legal loophole for the distribution of pirated content by technically savvy students. Economically, the topic is not absolutely interesting, the scientific interest is fading away.
Here you can also add a multicast , but it was fashionable, even when I asked my mother for fifteen kopecks for ice cream.
What conclusions can be drawn from this? It's simple. You should not get involved in the beauty and fashionability of technology, you only need to pragmatically assess its capabilities and costs. Common sense is enough.
Source: https://habr.com/ru/post/108597/
All Articles