# Intro This is my personal wiki with some notes, thoughts, etc. that I felt like sharing. Find me on [Github](https://github.com/ainzzorl), [Linkedin](https://www.linkedin.com/in/anton-emelyanov-75337b68/). # Pet Projects # Good Code A curated collection of annotated code examples from prominent open-source projects. Home page: I think I'm rather good at understanding other people's code bases and extracting interesting bits from them. Let's try to make some use of it. # LangFlipFlop Home page: [https://langflipflop.com/](https://langflipflop.com/landing) **LangFlipFlop** - practice languages by translating short phrases. Spent ***a lot*** of time and effort on it, but so far very little payout. # Soccer Adjectives Home page: Parse Reddit's /r/soccer to associate adjectives with soccer teams. Given an archive of comments, find out what adjectives best describe teams. It was a lot of fun, and it got a lot more attention than I expected! # Word Highlighter Home page: Firefox: Chrome: A browser extension to highlight words from a list. I use it to help me memorize new words. # News Digest Home page: Self-hosted minimalistic tool to generate personal digests from news websites, reddit and Hacker News. Can run locally or on AWS. I use it to spend less time in these rabbit holes. # Algorithms in Kotlin Home page: Learning some algorithms plus learning Kotlin. So far implemented only a few: * Finonacci heaps. * Seam carving. # rustorcli Home page: A simple BitTorrent client in Rust. It was developed as an exercise for learning Rust. A lot of time spent, a lot of fun had, a lot of things learned. # Tech # Tech Articles Notes on tech articles I'm reading. * [The mythical 10x programmer](http://antirez.com/news/112) (read: 10/10/2021) \* * [Caches, Modes, and Unstable Systems](https://brooker.co.za/blog/2021/08/27/caches.html) (read: 10/2/2021) * Very cool. * * "Most real systems like this have a *congestive collapse* mode, where they can't get rid of requests as fast as they arrive, concurrency builds up, and the goodput drops, making the issue worse. You can use tools like [Little's law](https://brooker.co.za/blog/2018/06/20/littles-law.html) to think about those situations." * "So our system has two stable loops. One's a happy loop where the cache is full:"... "The other is a sad loop, where the cache is empty, and stays empty:". * "Load testing typically isn't enough to kick a system in the *good* loop into the *bad* loop, and so may not show that the bad loop exists. This is for a couple of reasons. One is that caches love load, and typically behave better under high, predictable, well-behaved load than under normal circumstances. The other is that load tests typically test *lots of load*, instead of testing the bad pattern for caches, which is load with a different (and heavier-tailed) key frequency distribution from the typical one." * * [How Bash completion works](https://tuzz.tech/blog/how-bash-completion-works) (read: 9/26/2021) * [Part 2](https://tuzz.tech/blog/adding-bash-completion) * [HN](https://news.ycombinator.com/item?id=21172097) * Interface: a function that "accepts" env variables, "returns" another. * This was good to know! * [Metastability and Distributed Systems](https://brooker.co.za/blog/2021/05/24/metastable.html) (read: 9/11/2021) * "There's no more time-honored way to get things working again, from toasters to global-scale distributed systems, than turning them off and on again." * "Metastable failures occur in open systems with an uncontrolled source of load where a trigger causes the system to enter a bad state that persists even when the trigger is removed." * "We consider the root cause of a metastable failure to be the sustaining feedback loop, rather than the trigger. There are many triggers that can lead to the same failure state, so addressing the sustaining effect is much more likely to prevent future outages." * Retries: "If you're only looking at your day-to-day error rate metric, you can be lead to believe that adding more retries makes systems better because it makes the error rate go down. However, the same change can make systems more vulnerable, by converting small outages into sudden (and metastable) periods of internal retry storms. Your weekly loop where you look at your metrics and think about how to improve things may be making things worse." * [Gateway](https://martinfowler.com/articles/gateway-pattern.html) (read: 9/5/2021) * Very common thing. * Reminds me of SAOs at Amazon (Service Access Object). * "I use a gateway whenever I access some external software and there is any awkwardness in that external element. Rather than let the awkwardness spread through my code, I contain to a single place in the gateway." * I love how Fowler writes. * "At that time I struggled whether to coin a new pattern name as opposed to referring to the existing Gang of Four patterns: Facade, Adapter, and Mediator. In the end I decided that there was enough of a difference that it was worth a new name." * "While Facade simplifies a more complex API, it's usually done by the writer of the service for general use. A gateway is written by the client for its particular use." * "Adapter is the closest GoF pattern to the gateway as it alters an class's interface to match another. But the adapter is defined in the context of both interfaces already being present, while with a gateway I'm defining the gateway's interface as I wrap the foreign element. That distinction led me to treat gateway as a separate pattern. Over time people have used "adapter" much more loosely, so it's not unusual to see gateways called adapters." * [Eclipse - AOSA book](http://aosabook.org/en/eclipse.html) (read: 9/2/2021) * [Redundant against what?](https://brooker.co.za/blog/2021/04/14/redundancy.html) (read: 8/28/2021) * Okay. * [Cost-Efficient Open Source Big Data Platform at Uber](https://eng.uber.com/cost-efficient-big-data-platform/) (read: 8/22/2021) * Better compression. * Delete unnecessary columns. * "Row order can dramatically affect the size of compressed Parquet files. This is due to both the Run-Length Encoding feature inside Parquet format, as well as the compression algorithm’s capability to take advantage of local repeats. We examined a list of the largest Hive tables at Uber, and performed manually-tuned ordering that reduces the table sizes by more than 50%. A common pattern that we found is simply to order the rows by user ID, and then timestamp for the log tables. Most log tables have user ID and timestamp columns. This allows us to compress many denormalized columns associated with the user ID extremely well." * Whoa. * The rest is rather hard to follow. * [Challenges and Opportunities to Dramatically Reduce the Cost of Uber’s Big Data](https://eng.uber.com/challenges-opportunities-to-reduce-cost-ubers-big-data/) (read: 8/14/2021) * Ok. * [Zero-Overhead Tree Processing with the Visitor Pattern](https://www.lihaoyi.com/post/ZeroOverheadTreeProcessingwiththeVisitorPattern.html) (read: 8/7/2021) * HN: * "The Visitor Pattern gives you flexible, streaming, zero-overhead processing of complex data structures." * Wow this is a really awesome article. * [Hybrid Clock](https://martinfowler.com/articles/patterns-of-distributed-systems/hybrid-clock.html) (read: 8/1/2021) * "[Hybrid Logical Clock](https://cse.buffalo.edu/tech-reports/2014-04.pdf) provides a way to have a version which is monotonically increasing just like a simple integer, but also has relation with the actual date time. Hybrid clocks are used in practice by databases like [mongodb](https://www.mongodb.com/blog/post/transactions-background-part-4-the-global-logical-clock) or [cockroachdb](https://www.cockroachlabs.com/docs/stable/architecture/transaction-layer.html)." * Fancy. * [namedtuple in a post-dataclasses world](https://death.andgravity.com/namedtuples) (read: 8/1/2021) * HN: * I knew neither about data classes nor about named tuples lol. Shame. * Well-written. * [A Deep Dive into Airbnb’s Server-Driven UI System](https://medium.com/airbnb-engineering/a-deep-dive-into-airbnbs-server-driven-ui-system-842244c5f5) (read: 7/24/2021) * HN: * Problems of client-driven UI: * "there’s listing-specific logic built on each client to transform and render the listing data. This logic becomes complicated quickly and is inflexible if we make changes to how listings are displayed down the road." Don't quite get it. * "Second, each client has to maintain parity with each other. As mentioned, the logic for this screen gets complicated quickly and each client has their own intricacies and specific implementations for handling state, displaying UI, etc. It’s easy for clients to quickly diverge from one another." Fair. * "Finally, mobile has a versioning problem. Each time we need to add new features to our listing page, we need to release a new version of our mobile apps for users to get the latest experience. Until users update, we have few ways to determine if users are using or responding well to these new features." Mkay. * Interesting stuff. * Why not just use web apps then? * [Write a time-series database engine from scratch](https://nakabonne.dev/posts/write-tsdb-from-scratch/) (read: 7/17/2021) * Very insightful. * I should implement something like this some day. * The whole API is `InsertRows` and `Select`? * HN: * [Versioned Value](https://martinfowler.com/articles/patterns-of-distributed-systems/versioned-value.html) (read: 7/11/2021) * Skip lists! It's the first time I see them being used anywhere. * Mvcc = Multiversion concurrency control. * Nice article. * [Handling Flaky Unit Tests in Java](https://eng.uber.com/handling-flaky-tests-java/) (read: 7/11/2021) * The oldest topics there is :-) * Test Analyzer tool - I've seen this before :-) * "Therefore, to enable any developer to triage flaky failures, we built dynamic reproducer tools which can be used to reproduce the failure locally." - how? * Ok found it: 1. Run just the input test 2. Run all the tests in the input test class 3. Run all the tests in the test target 4. Run the test under port collision detection mode. 5. Repeat steps 1 – 3 while increasing the resource load on the system * [Supercharging Application Delivery](https://www.allthingsdistributed.com/2021/06/supercharging-application-delivery.html) (read: 7/7/2021) * "customers should be able to adopt, customize and evolve best practices and technologies for delivering their modern applications to the cloud, and not worry about how they roll this out – potentially to thousands of developers – across their organization." * Does not sound very amazonian. People there do care very much about how things are rolled out. * Next gen of infrastructure-as-code? * I still don't quite understand what exactly it does. Umbrella thingie for CloudFormation + CodeDeploy + CodePipelines? * [It’s Officially Startup Season in Space](https://www.allthingsdistributed.com/2021/06/aws-accelerates-startups-in-space.html) (read: 7/7/2021) * Space is cool. I wonder if I can do something in this *space*. * The article is meh. * [On the Diverse And Fantastical Shapes of Testing](https://martinfowler.com/articles/2021-test-shapes.html) (read: 6/27/2021) * The definition of "unit" is vague. Can be "social" (can use other units) or "solitary" (everything is mocked out). * I for one like integration tests. * "The take-away here is when anyone starts talking about various testing categories, dig deeper on what they mean by their words, as they probably don't use them the same way as the last person you read did." * [Why (and how) GitHub is adopting OpenTelemetry](https://github.blog/2021-05-26-why-and-how-github-is-adopting-opentelemetry/) (read: 6/27/2021) * * Common tracing is good, naturally. * I wish they explained the format a little. * Where/how are they stored? * Optimizing a code intelligence commit graph [Part 1](https://about.sourcegraph.com/blog/optimizing-a-code-intel-commit-graph/), [Part 2](https://about.sourcegraph.com/blog/optimizing-a-code-intel-commit-graph-part-2/) (read: 6/19/2021) * [It's probably time to stop recommending Clean Code](https://qntm.org/clean) (read: 6/19/2021) * * Makes sense for the most part. * Indeed some Uncle Bob's code is questionable. * The maxima of tiny functions with no params always seemed bad to me. * But Clean Code still contains a ton of solid advice. * There must be some common reference. Everyone doing it their own way won't work. * [Diving Deep on S3 Consistency](https://www.allthingsdistributed.com/2021/04/s3-strong-consistency.html) (read: 6/13/2021) * * He starts with describing analytical workflows, etc, but surely no one cares about strong consistency there. * If customers had to build their own solutions with Dynamo, etc. to track S3 consistency, it's really sad. * Hard to follow the actual design part. * I don't think it can be called "deep dive". * [A new era of DevOps, powered by machine learning](https://www.allthingsdistributed.com/2021/05/devops-powered-by-machine-learning.html) (read: 6/13/2021) * "Although DevOps technology has evolved dramatically over the last 5 years, it is still challenging. Issues related to concurrency, security or handling of sensitive information require expert evaluation and often slip through existing mechanisms like peer code reviews and unit testing." * What does this have to do with DevOps? * I wonder what Werner actually thinks of CodeGuru, not the sales pitch. * I'm not sure about DevOps Guru. Can you really "trust" it to monitor for you? I would be very scared to use it in place of some hand-picked thresholds, etc. * [Easily build real-time apps with WebSockets and Azure Web PubSub—now in preview](https://azure.microsoft.com/en-us/blog/easily-build-realtime-apps-with-websockets-and-azure-web-pubsub-now-in-preview/) (read: 6/6/2021) * Seems pretty cool. If I was building a realtime app, I would seriously consider using it. * [A brief history of Rust at Facebook](https://engineering.fb.com/2021/04/29/developer-tools/rust/) (read: 6/6/2021) * * A lot of discussion if there are/will be good jobs in Rust. * "When corruption or downtime can potentially bring services to a halt, reliability is a top priority. That’s why the team chose to go with Rust over C++." * It's always strange to hear the expectation of strong influence of the language on reliability. Testing, monitoring, all that - that seems to matter so much more. * [Chilling Tales from Reddit Engineering](https://redditblog.com/2020/10/28/chilling-tales-from-reddit-engineering/) (read: 5/29/2021) * Don't deploy stuff on Fridays and before holidays. * “It works on my machine!” she declared, shipping the code to production." Then "With haste, the young engineer rolled back the Firebase update." * MCM anyone? * "Only little did he know, a button that read ‘Save Policy,’ hid below the fold and his termination policy made no impact." * Who's updating prod infrastructure through the AWS UI? CloudFormation/Terraform FTW. Or at very least use the CLI. * [Scaling Reporting at Reddit](https://redditblog.com/2021/02/26/scaling-reporting-at-reddit/) (read: 5/29/2021) * Old system: pre-aggregate things offline, one row per advertiser/day. * Need to code more complex queries. * "This system also had issues with memory usage. Queries that had to fetch many keys from Redis would cause our reporting service to deserialize large quantities of Thrift data. Deserializing all of this Thrift data was slow and required a lot of memory. We had to over-provision the reporting service to anticipate large queries. This system resulted in a degraded experience as our advertisers got larger." * "Another issue with the system was that it wasn’t flexible. Adding new breakdown capabilities usually meant adding new pre-aggregates before inserting the data into Redis. We would then have to implement corresponding querying logic in the reporting service. Adding new fields also required a lot of work to wire them through the entire pipeline. It was clear that our data store was not nearly as flexible as the products that we needed to support." * Sounds familiar! * Offloaded aggregation to Druid. * "A Spark job validates incoming events and places them into Amazon S3 as parquet files. Another Spark job performs minor transformations on these parquet files to make them appropriate for Druid to ingest." * Why not just one job then? What's the point of these intermediate files in S3? * "The largest benefits of this migration can be seen in our availability and latency graphs. As you can see below, the new reporting service (blue) is consistently more available than the legacy system (green). Our legacy system struggled to maintain 99.5% availability at times while our new service is generally able to maintain 99.9% availability." * Huh, they use some different definition of availability then. Just success/all, rather than minutes of unavailability, etc. * [In Slack, no one can hear your scream!](https://8thlight.com/blog/ian-carroll/2021/04/20/in-slack-no-one-can-hear-you-scream.html) (read: 5/23/2021) * Okay. Not sure why I read it. * [Git hash function transition](https://github.com/git/git/blob/master/Documentation/technical/hash-function-transition.txt) (read: 5/15/2021) * HN: * I wish I knew git internals better to understand what's going on. * The consinceness of the language, the clarity and level of detail are amazing. * Discussion of candidates: * Kind of personal rant by Linus: * Facebook - [How Facebook encodes your videos](https://engineering.fb.com/2021/04/05/video-engineering/how-facebook-encodes-your-videos/) (read: 5/9/2021) * "From a pure computing perspective, applying the most advanced codecs to every video uploaded to Facebook would be prohibitively inefficient. Which means there needs to be a way to prioritize which videos need to be encoded using more advanced codecs." * ML to predict which videos are going to be highly watched. * "But this task isn’t as straightforward as allowing content from the most popular uploaders or those with the most friends or followers to jump to the front of the line. There are several factors that have to be taken into consideration so that we can provide the best video experience for people on Facebook while also ensuring that content creators still have their content encoded fairly on the platform." * ``` Benefit = (relative compression efficiency of the encoding family at fixed quality) \* (effective predicted watch time) ``` ``` Cost = normalized compute cost of the missing encodings in the family Priority = Benefit/Cost ``` * Not every device can play every codec. * "The best indicator of next-hour watch time is its previous watch time trajectory." * Duh. * "Improvements in ML metrics do not necessarily correlate directly to product improvements. Traditional regression loss functions, such as RMSE, MAPE, and Huber Loss, are great for optimizing offline models. But the reduction in modeling error does not always translate directly to product improvement, such as improved user experience, more watch time coverage, or better compute utilization." * Huh. * "we decided to build two models, one for handling upload-time requests and other for view-time requests" * Martin Fowler - [Bitemporal History](https://martinfowler.com/articles/bitemporal-history.html) (read: 5/9/2021) * There's a property that can change, and we want to track its history. But sometimes we receive updates about the past. * So we keep a table with "record" dates and "actual" dates. * We read it as "on \, we thought that on \ the value was \". * "In programming terms, If I want to know Sally's salary, and I have no history, then I can get it with something like sally.salary. To add support for (actual) history I need to use sally.salaryAt('2021-02-25'). In a bitemporal world I need another parameter sally.salaryAt('2021-02-25', '2021-03-25')" * "One way to avoid it is to not support retroactive changes. If your insurance company says any changes become in force when they receive your letter - then that's a way of forcing actual time to match record time." * "One of the hardest parts of this is educating users on how bitemporal history works. Most people don't think of a historical record as something that changes, let alone of the two dimensions of record and actual history." * "Bitemporal history is a way of coming to terms that communication is neither perfect nor instantaneous. Actual history is no longer append-only, we go back and make retroactive changes. However record history itself is append only." * [Our Journey Towards Cloud Efficiency](https://medium.com/airbnb-engineering/our-journey-towards-cloud-efficiency-9c02ba04ade8) * Too much corporate speak. * Utilize spot. * Eliminate waste. * S3 - use data retention policies. * S3 - use more cost effective tiers. * Be careful when storing small files in Glacier. * Compute - use K8s for auto scaling. * I wonder if stuff like AWS Config or Trusted Advisor recommend these? * Track usage. * Attribute usage. * Use reserved instances for RDS and ElastiCache. * "Culture of Cost Awareness". * "The changes stemmed from better contract management and utilization of our third-party cloud services." Wat? * HN: * [How we sped up Dropbox Android app startup by 30%](https://dropbox.tech/mobile/how-we-sped-up-dropbox-android-app-startup-by-30-) * Load time seems sort of constant on 2-week interval. Need to look at bigger intervals. * Need to measure more granularly, for each step of the startup. Identify biggest offenders with this. * "The major app startup offenders included Firebase Performance library initialization, feature flag migration, and initial user loading." * "In our debugging, we discovered that Firebase suite initialization was seven times longer when Firebase Performance tool was enabled. To fix the performance issue, we chose to remove the Firebase Performance tool from the Android Dropbox application." * Hmm, can't they load it in background or something, without blocking users? And start using it when it's ready? * "In the legacy part of our application, we store Dropbox user contacts metadata on the device as JSON blobs. In an ideal world, those JSON blobs should be read and converted into Java objects only once. Unfortunately, the code to extract users was getting called multiple times from different legacy features of the app, and each time, the code would perform expensive JSON parsing to convert user JSON blobs into Java objects." * How slow can it possibly be? How big are these blobs? * [Detecting memory leaks in Android applications](https://dropbox.tech/mobile/detecting-memory-leaks-in-android-applications) * They describe Android-specific memory leak patterns. * Android-specific memory leak finding lib: . Can upload found leaks. * Can hook LeakCanary to integ tests. * [Packaging award-winning shows with award-winning technology](https://netflixtechblog.com/packaging-award-winning-shows-with-award-winning-technology-c1010594ba39) * 4/25/2021 * So there's a codec-agnostic open packaging format for tranferring videos. Ok. * [The Netflix Cosmos Platform](https://netflixtechblog.com/the-netflix-cosmos-platform-35c14d9351ad) * 4/19/2021 * "Orchestrated Functions as a Microservice" lol. * It's interesting that these video encoding flows take days to complete. I wonder what SLO they need to provide for stuff like this. On one hand, availability should not be that big of a deal because it's async and not directly customer facing, but retries can be very costly. Can it, say, delay a release of a title? * But do they actually ever need to retry the entire thing? * It takes a confident person to call something internal Optimus. * So many details about internal systems, all with creative names. No way I will (or want to) follow what they are all doing. * Oh wait, some of these video processing flows are user-facing apparently. And latency matters. * [A Day in the Life of an Experimentation and Causal Inference Scientist @ Netflix](https://netflixtechblog.com/a-day-in-the-life-of-an-experimentation-and-causal-inference-scientist-netflix-388edfb77d21) * 4/19/2021 * No takeways. # Algorithms # Distributed Hash Table (DHT) * * * * * ## DHT in BitTorrent * * Problem: how do I find peers for a torrent I'm trying to download? Trackers are not in the spirit of P2P and are SPOFs. Solution: distribute the knowledge about peers for torrents across all participating nodes. Nodes and torrent infohashes are mapped to the same space. Nodes closer to the torrent are expected to store peers for it. Each node maintains a routing table of known nodes, and a map of peers for some torrents. It traverses the nodes until it finds one that knows the peers. Then it announces itself. **RPCs**: * ping * announce\_peer * Announce that the peer, controlling the querying node, is downloading a torrent on a port. announce\_peer has four arguments: "id" containing the node ID of the querying node, "info\_hash" containing the infohash of the torrent, "port" containing the port as an integer, and the "token" received in response to a previous get\_peers query. The queried node must verify that the token was previously sent to the same IP address as the querying node. Then the queried node should store the IP address of the querying node and the supplied port number under the infohash in its store of peer contact information. * get\_peers * Get peers associated with a torrent infohash. "q" = "get\_peers" A get\_peers query has two arguments, "id" containing the node ID of the querying node, and "info\_hash" containing the infohash of the torrent. If the queried node has peers for the infohash, they are returned in a key "values" as a list of strings. Each string containing "compact" format peer information for a single peer. If the queried node has no peers for the infohash, a key "nodes" is returned containing the K nodes in the queried nodes routing table closest to the infohash supplied in the query. In either case a "token" key is also included in the return value. The token value is a required argument for a future announce\_peer query. The token value should be a short binary string. * find\_nodes * Find node is used to find the contact information for a node given its ID. "q" == "find\_node" A find\_node query has two arguments, "id" containing the node ID of the querying node, and "target" containing the ID of the node sought by the queryer. When a node receives a find\_node query, it should respond with a key "nodes" and value of a string containing the compact node info for the target node or the K (8) closest good nodes in its own routing table. **Protocol**: * Bootstrap. * find\_nodes(self) * Refresh buckets. * find\_nodes(target bucket) * Announce. * get\_peers(infohash) + announce\_peer(infohash) A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. A trackerless torrent dictionary does not have an "announce" key. Instead, a trackerless torrent has a "nodes" key. This key should be set to the K closest nodes in the torrent generating client's routing table. Alternatively, the key could be set to a known good node such as one operated by the person generating the torrent. Please do not automatically add "router.bittorrent.com" to torrent files or automatically add this node to clients routing tables. **Spoof protection**: Before we add someone to the peer-list, we verify that that ip is really requesting it. * get\_peers responds with a write-token. * Write token is typically a MAC of: * source(ip, port) * target info-hash * local\_secrets (experes in tens of minutes) * announce\_peer requires a valid write token to insert the node into the peer list. **Topology.** Describes how nodes can repond to recursive lookup queries like this, with nodes closer and closer to the target. The DHT is made up by all bittorrent peers, across all swarms. Each npde has a self-assigned address, or node id. Id space - \[0, 2^160). All nodes appear uniformly distributed. Same space as infohash space. Nodes whose ID is close to an info-hash are responsible for storing information about it. **Routing.** It's impractical for every node to know about every other node. There are millions of nodes, they come and go constantly. Every node specializes in knowing about all nodes close to itself. The routing table orders nodes based on their distance from oneself. XOR distance metric: d(a, b) = a xor b. The distance space is divided into buckets, each no more than 8 nodes. Each bucket is half as the previous. Fartherst 1/2 nodes: 1 bucket. You know more about nodes closer to you. For every hop in a recursive lookup, the nodes distance is cut in half. Lookup complexity: O(log n). **Routing table.** The XOR distance metric applied to the routing table just counts the length of the common bit-prefix. Max of 160 buckets. Most buckets will be empty (too few nodes!), so an array of 160 buckets is not efficient. A typical routing table starts with only bucket 0. When 9th bucket is added, the bucket is split into bucket 0 and bucket 1, with the nodes moved into the respective buckets. Only the highest number bucket is ever split. **Traversal algorithm.** You join the swarm - you need ips for the infohash + announce yourself. Sort nodes in your routing table by distance to the target. Pick, say, 3 nodes. Send get\_peers requests to these nodes at the same time. Keep 3 outstanding requests. They come back with nodes, we insert them into the routing table. Hopefully closer to the info-hash. Mark stale nodes (don't remove, to save time when it's reinserted). When we have 8 nodes on top, all queried successfully and no closer nodes, we stop. We announce ourselves to these 8 nodes. Re-announce every 15 minutes. # RSA * [The original paper.](http://people.csail.mit.edu/rivest/Rsapaper.pdf) * ### Method * Choose random semi-prime n = p \* q * Choose random e: gcd(e, (p-1)(q-1)) = 1 * d: ed = 1 mod (p-1)(q-1) Public key: (e, n) Private key: (d, n) Encrypt: E(M) = M^e mod n Decrypt: D(C) = C^d mod n ### Math D(E(M)) = M is proved based on Fermat's little theorem or Euler's theorem. (p-1)(q-1) is the Euler's totient number for n (number of integers less than n co-prime with it). Knowing p and q, it's trivial to compute d from e. Not knowing: supposedly hard. ### Attacks and Stuff * There are many ways to choose weak keys. * * * Needs strong random number generator, otherwise can be factorized. * Needs good padding. * * ### RSA Problem * ["If we consider the problem of finding the private exponent 𝑑 then it is proven by Miller to be computationally equivalent to factoring 𝑛;"](https://crypto.stackexchange.com/questions/89883/is-it-proven-that-breaking-rsa-is-equivalent-to-factoring-as-of-2021) * [Breaking RSA Generically is Equivalent to Factoring.](https://eprint.iacr.org/2008/260.pdf) * Decrypting a single cyphertext: not necessarily as difficult as factoring. It probably isn't. ### Format DER: binary format; modulo concatenated with exponent. PEM: base64-encoded DER. # Seam Carving * * * * My (ugly, incomplete and horribly inefficient) implementation: # Fibonacci Heaps [My implementation.](https://github.com/ainzzorl/algorithms-kotlin/blob/main/src/com/ainzzorl/algorithms/heaps/FibonacciHeap.kt) # Suffix trees, suffix arrays, etc. From MIT 6.851: * Video: * * Given text upfront, preprocess text T and query pattern P. Goal - query in O(P). O(T) space. **Trie** - rooted tree with child branches labeled with letters in Σ. **Task: find predecessor.** Solved with tries, but the problem is how to represent the node in the trie. Array: too much memory. BST - too slow. Hash - doesn't preserve order, so doesn't solve the predecessor. There are tricks how to do it in O(P + logΣ). Can use to sort strings: O(T + klgΣ). **Compressed trie** - contract non-branching path into single edge. O(k) nodes. **Suffix trees** (or suffix tries) - compressed trie of all |T| suffixes. T\[i:] of T with $ appended. Applications of suffix trees: * Search for P gives subtree whose leaves correspond to all occurrences of P in T. * Which node representation to use? * Hashing => O(P) time. But not in order. * Trays => O(P + lgΣ) time. * LCP (T\[i:], T\[j:]) = LCA * All occurrences of T\[i:j] = weighted level ancestor j-i of T\[i:] leaf. O(lglgT). * Document retrieval: O(p + #docs) - all documents matching the pattern. With RMQ. **Suffix array** - sort suffixes of T (just store their indexes) in O(T) space. LCP - largest common prefix or neighbour prefixes. You can build suffix tree using suffix array and LCPs. O(T + sort(Σ)) construction: 1. Sort Σ. 2. Replace each letter by its rank in Σ. 3. Form T0=<(T\[3i], T\[3i+1], T\[3i+2])> for i =0,1,... T1=<(T\[3i+1], T\[3i+2], T\[3i+3])>. T2=... 4. Recurse on \ 5. Radix sort of T2's suffixes. T2\[i:] = T\[3i+2] = \ 6. Merge suffixes of T0 and T1 with suffixes of T2. Exercises: * Build suffix tree. * Find substring. * Find longest repeated substring. Try wikipedia! # Technologies # Threads vs Events * * * * Events are great for IO parallelism without CPU parallelism. # TLS Handshake: * The handshake begins when a client connects to a TLS-enabled server requesting a secure connection and the client presents a list of supported [cipher suites](https://en.wikipedia.org/wiki/Cipher_suite) ([ciphers](https://en.wikipedia.org/wiki/Encryption) and [hash functions](https://en.wikipedia.org/wiki/Cryptographic_hash_function)). * From this list, the server picks a cipher and hash function that it also supports and notifies the client of the decision. * The server usually then provides identification in the form of a [digital certificate](https://en.wikipedia.org/wiki/Public_key_certificate). The certificate contains the [server name](https://en.wikipedia.org/wiki/Hostname), the trusted [certificate authority](https://en.wikipedia.org/wiki/Certificate_authority) (CA) that vouches for the authenticity of the certificate, and the server's public encryption key. * The client confirms the validity of the certificate before proceeding. * To generate the session keys used for the secure connection, the client either: * encrypts a [random number](https://en.wikipedia.org/wiki/Random_number_generation) (PreMasterSecret) with the server's public key and sends the result to the server (which only the server should be able to decrypt with its private key); both parties then use the random number to generate a unique session key for subsequent encryption and decryption of data during the session * uses [Diffie–Hellman key exchange](https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange) to securely generate a random and unique session key for encryption and decryption that has the additional property of forward secrecy: if the server's private key is disclosed in future, it cannot be used to decrypt the current session, even if the session is intercepted and recorded by a third party. Certificate: * "A digital certificate certifies the ownership of a public key by the named subject of the certificate, and indicates certain expected usages of that key. This allows others (relying parties) to rely upon signatures or on assertions made by the private key that corresponds to the certified public key." [What is a TLS/SSL certificate, and how does it work?](https://protonmail.com/blog/tls-ssl-certificate/) # GPU * [Graphics Processing Unit](https://en.wikipedia.org/wiki/Graphics_processing_unit) * * GPUs offer many cores, but narrow instruction set and lower clock speed * VS video card: Video Card generated feed of output images; has a GPU in its core. Also usually has dedicated RAM (unlike integrated video cards that share RAM with the rest of the system). * GPUs offer many cores, but narrow instruction set and lower clock speed * Major brands: NVIDIA (GeeForce), AMD Radeon, Intel. ### CUDA * CUDA - NVIDIA's platform and API for accessing their GPU's instruction sets. CUDA-powered GPUs also support open standards like OpenMP or OpenCL. * Natively supports C, C++, Fortran. Third-party wrappers exist for Python, Ruby and many other languages. * Parallelize functions by making a function doing only a part of the job depending on its thread id. * Threads are grouped into blocks; blocks form a grid. * Lower-level [Driver API](https://docs.nvidia.com/cuda/cuda-driver-api/index.html) and higher-level [Runtime API.](https://docs.nvidia.com/cuda/cuda-runtime-api/index.html) * ### DL Thinks like convolution or even matrix multiplication can easily be parallelized to run much faster on GPU. # Web Sockets * * * Allows low-latency bi-directional communication. Low-latency server-to-client can be accomplished with long-held connections, but client-to-server require establishing new connections each time. The connection must be kept alive on the server somehow. # OSI Model * * # Open Source # Homebrew Summarizing my attempts to understand Homebrew codebase * * * * [**Terms**](https://docs.brew.sh/Formula-Cookbook#homebrew-terminology)**:** * Formula - package definition. * Keg - installation prefix of a formula. * Cellar - where all kegs are located. * Tap - git repo of formulae and/or commands. * Bottle - pre-built keg. * Cask - extension of Homebrew to install native MacOS apps. **General notes:** * I like how formulae come with tests. * Formula dev guide is pretty great. * Ruby seems like a great choice for DLSs like this. * Overall code structure seems moderately simple, e.g. there are not too many layers of redirection for the most part. * Implementation details are often rather convoluted, with not too many comments. * A lot of long methods. **Tracing:** * Entry point shell script: * Then * Setting env variables for OS, cache location, etc. * Checks that it's not sudo, not installing on temp, etc. * Check dependencies: curl, git, ... * Then route to one of * Some are .sh, some are .rb * I expected a single ruby entry point, but there's none! * Install path: * * Test: Seems rather... superficial. But I kind of like their test DSL. * Command parser: * Check if to install: * Install: * Accepts formula and a ton of params. * I would probably extract the params into some class. * Then it creates [FormulaInstaller](https://github.com/Homebrew/brew/blob/aa14e48f4e73d2f4c7d178d7b8a2f528b74995d7/Library/Homebrew/formula_installer.rb#L29) and calls its methods one by one: prelude, fetch, install, finish. * FormulaInstaller seems... rather convoluted. **Interesting:** * Did you mean? * Not too interesting. It just delegates. * Locking. * Github access With pagination and what not. Spec: * Search: * Download strategy switch: * Unpack strategy. * Cache store: * Curl & workarounds: # Standard Notes Summarizing my attempts to understand StandardNotes codebase. * How does it sync? * How does it encrypt? * How does it deal with conflicts? * Overall front-end code structure? * How does it store on user disk? * How does it store on the server? ## Code * Web client (also core for desktop): * Desktop client: * JS/TS: * Angular. * Syncing server: * Core js logic: ## Thoughts & Observations * Web * I love how easy it is to start it locally. `yarn install && yarn start`. Done. * What is the rails server doing inside the client app? * Are there any tests? * Sync server * DI with inversify. * Specs are located right next to the code under test. * Bindings are helpful to understand where everything is * What is extensions server? * I thought all extensions were client-side? If so, why do anything about them when syncing items? * Are notes just rows in MySQL? * * I expected them to be blobs in some blobstore or something. * Is there a limit on the item size then? * S3, SNS, SQS - what are they doing here? * ItemService - seems to actually handle persistence * What exactly does "projection" mean? * Conversion between persistent-data and some transfer format? * S3 backup * # LiChess Summarizing my attempts to understand LiChess. ### Arch * The main diagram is not very clear, or helpful. * Where's Redis? Or does the diagram predate it? ### API * They stream board events with ndjson . It's long polling I suppose? * Can't find API to actually make moves. I suppose it's done via websockets? * Can't find API to actually do puzzles. Only see API to get daily puzzle. Perhaps it's also done with web sockets. * There's an API to send a message, but I see no API to view messages. ### Code {% embed url="" %} ### Lila * Doesn't seem to have many tests. * Board literals in tests whoa ### WS * WS deploy command whoa Just like that. * **Very** magic numbers are all over the place * Few comments, very hard to follow which class is doing what. * No tests apparently. * WFH is anaMove? * Actually receive move from Lila * Send the move to watching clients ## UI * Arguments: t, d, o. How is anyone supposed to understand what it means? Tracking how a move is sent to the server: * * ### Puzzler {% embed url="" %} Overall, seems very basic stuff. It feels like it's possible to do a lot better. * Main script (?) * Generator * Extracting puzzle from a game ### Cheat detection # Bash * To get pids by name, use `pgrep` instead of `ps | grep` * E.g. `pgrep -i expressvpn` * It will exclude your own grep process. # Raft Raft is a consensus algorithm for managing a replicated log. * Strong leader. Raft uses a stronger form of leader-ship than other consensus algorithms. For example,log entries only flow from the leader to other servers.This simplifies the management of the replicated log and makes Raft easier to understand. * Leader election: Raft uses randomized timers to elect leaders. This adds only a small amount of mechanism to the heartbeats already required for any consensus algorithm, while resolving conflicts simply and rapidly. * Membership changes: Raft’s mechanism for changing the set of servers in the cluster uses a new joint consensus approach where the majorities of two different configurations overlap during transitions. This allows the cluster to continue operating normally during configuration changes. Consensus algorithms for practical systems typically have the following properties: * They ensure safety(never returning an incorrect result) under all non-Byzantine conditions, including network delays, partitions, and packet loss, duplication, and reordering. * They are fully functional (available) as long as any majority of the servers are operational and can communicate with each other and with clients. Thus, a typical cluster of five servers can tolerate the failure of any two servers. Servers are assumed to fail by stopping; they may later recover from state on stable storage and rejoin the cluster. * They do not depend on timing to ensure the consistency of the logs: faulty clocks and extreme message delays can, at worst, cause availability problems. * In the common case, a command can complete as soon as a majority of the cluster has responded to a single round of remote procedure calls; a minority of slow servers need not impact overall system performance. Sub-problems: * Leader election: a new leader must be chosen when an existing leader fails. * Log replication: the leader must accept log entries from clients and replicate them across the cluster, forcing the other logs to agree with its own. * Safety: the key safety property for Raft is the State Machine Safety Property: if any server has applied a particular log entry to its state machine, then no other server may apply a different command for the same log index. * Any two majorities always overlap. * The leader can commit after hearing back from the half of other servers. * Then the leader tells the replicas to commit too. It's piggy-backed inside the next AppendEntries. * Why is the system focused on logs in the first place? Because it needs to apply operations in the same order. And it can reply the log after the crash. Leader election: * Possible to build a system like this without a leader. But it's more efficient (while servers don't fail). * Each term has at most one leader. * There's an election timer on each server. If it expires, it assumes the current leader is dead, becomes a candidate, tries to become a leader. * Increment term. * Vote for itself. * Request votes. * Election timer is randomized, to reduce the probability of split votes. Choose random timeout every time, not just once! * New leader sorts out possibly divergent replicas. Compaction: * Must avoid indefinitely growing logs. * Take state machine snapshots. * With "last included index" and "last included term". These are needed for checks in AppendEntry. * Generally servers take snapshots independently. Server sends snapshots to peers falling behind. * Use copy-on-write. Fast Backup (when leader needs to find out where to append to the follower): on AppendEntries rejection, the follower also sends the term and the index of the conflicting entry, and the length of the log. Then the leader will know how to update the nextIndex. * They say I have to do this to pass the lab, but I didn't and it still passed :-| * Maybe I'll need it after I add persistence. Persistent properties vs volatile. It only matters if it restarts. It is likely to be the performance bottleneck. Persist: * Log. * CurrentTerm. * VotedFor. This and CurrentTerm are needed to ensure there's only one leader. # Quantum Computing * * * "Shut up and calculate". * All metaphors will lead you astray. It can only be understood with the language of math. * Quantum computers only use reversible operations. Moreover, only operations that are their own reverses. # GFS * [Paper](http://nil.csail.mit.edu/6.824/2020/papers/gfs.pdf) Amazing stuff overall. And the paper is written so well. I found reading it very inspiring. * "most files are mutated by appending new data rather than overwriting existing data. Random writes within a file are practically non-existent. Once written, the files are only read, and often only sequentially" * "We have also introduced anatomic append operation so that multiple clients can append concurrently to a file without extra synchronization between them." * Multiple clients writing the same file concurrently seems strange. * Ah, I see. "Our files are often used as producer-consumer queues or for many-way merging. Hundreds of producers, running one per machine, will concurrently append to a file. Atomicity with minimal synchronization overhead is essential". * "Multi-GB files are the common case and should be managed efficiently. Small files must be supported, but we need not optimize for them." * "High sustained bandwidth is more important than low latency. Most of our target applications place a premium on processing data in bulk at a high rate, while few have stringent response time requirements for an individual read or write." * How do you build PD on top of this then? * Single master (SPOF?), for metadata and management. Clients read/write directly to chunkservers. * Reading/writing is done in the client lib, interesting. * If you decide to change the chunk size, then what happens? It seems like the client lib and the master must use the same "version". * Chunk size is 64mb. That's a lot! Especially in 2003. * "Lazy space allocation avoids wasting space due to internal fragmentation, perhaps the greatest objection against such a large chunk size" * Do they do something for data integrity? * 32-bit checksums. * Nice that it's so short. Why bother with something cryprographically strong? * But for 64kb blocks, not the entire chunk. * Master keeps operation log, builds checkpoints in the background. * They are minimizing master's involvement in anything. * Leases. * There seems to be a lot of trust into the client code. * "We decouple the flow of data from the flow of control to use the network efficiently." * "Our network topology is simple enough that “distances” can be accurately estimated from IP addresses." Lol * "Finally, we minimize latency by pipelining the data transfer over TCP connections. Once a chunk server receives some data, it starts forwarding immediately." Sounds familiar (e.g CDNs and random trees). * Fancy control flow to guarantee atomicity. * "GFS does not guarantee that all replicas are bytewise identical. It only guarantees that the data is written at least once as an atomic unit" Hmm * "we use standard copy-on-write techniques to implement snapshots" Very standard indeed :-) * "Unlike many traditional file systems, GFS does not have a per-directory data structure that lists all the files in that directory. Nor does it support aliases for the same file or directory (i.e, hard or symbolic links in Unix terms)." * No POSIX for you. * Master - "When it fails, it can restart almost instantly. If its machine or disk fails, monitoring infrastructure outside GFS starts anew master process elsewhere with the replicated operation log. Clients use only the canonical name of the master (e.g.gfs-test), which is a DNS alias that can be changed if the master is relocated to another machine." * "Initially, GFS was conceived as the backend file system for our production systems. Over time, the usage evolved to include research and development tasks. It started with little support for things like permissions and quotas but now includes rudimentary forms of these. While production systems are well disciplined and controlled, users some times are not. More infrastructure is required to keep users from interfering with one another" * Clients read directly from chunkservers - no surprise permissions are hard to manage. * [MIT 6.824 notes.](http://nil.csail.mit.edu/6.824/2020/notes/l-gfs.txt) ``` Overall structure clients (library, RPC -- but not visible as a UNIX FS) each file split into independent 64 MB chunks chunk servers, each chunk replicated on 3 every file's chunks are spread over the chunk servers for parallel read/write (e.g. MapReduce), and to allow huge files single master (!), and master replicas division of work: master deals w/ naming, chunkservers w/ data ``` ``` Master state in RAM (for speed, must be smallish): file name -> array of chunk handles (nv) chunk handle -> version # (nv) list of chunkservers (v) primary (v) lease time (v) on disk: log checkpointMaster state in RAM (for speed, must be smallish): file name -> array of chunk handles (nv) chunk handle -> version # (nv) list of chunkservers (v) primary (v) lease time (v) on disk: log checkpoint ``` [FAQ](http://nil.csail.mit.edu/6.824/2020/papers/gfs-faq.txt) # MapReduce The original article: [MIT 6.824: Distributed Systems Lecture 1](https://www.youtube.com/watch?v=cQP8WApzIQQ) * Somehow I used to think that functional languages borrowed the terms ("map" and "reduce") from them, not the other way around. * The brilliance is hiding the complexity of parallelism, massive scale, fault tolerance, etc. behind very simple interface. * "After successful completion, the output of the map-reduce execution is available in the output files (one per reduce task, with file names as specified by the user). Typically, users do not need to combine these output files into one file – they often pass these files as input to another MapReduce call, or use them from another distributed application that is able to deal with input that is partitioned into multiple files." * Huh. Somehow I'm used to a single output file. * Or at least that one key belongs to only one output file. * "Completed map tasks are re-executed on a failure be-cause their output is stored on the local disk(s) of the failed machine and is therefore inaccessible. Completed reduce tasks do not need to be re-executed since their output is stored in a global file system." * How is work distributed across Reduce tasks? With Map it's clear. * Is there a "global" master, or per-job masters? I guess the latter. * I like the discussion of the failure semantics. * "We conserve network band-width by taking advantage of the fact that the input data(managed by GFS \[8]) is stored on the local disks of the machines that make up our cluster." * It's interesting just how everything runs on the same machines... Needs some thinking. * It allows tricks like input locality then. * "One of the common causes that lengthens the total time taken for a MapReduce operation is a “straggler”: a ma-chine that takes an unusually long time to complete one of the last few map or reduce tasks in the computation." * Oh I've seen that at Microsoft. * "We have a general mechanism to alleviate the problem of stragglers. When a MapReduce operation is close to completion, the master schedules backup executions of the remaining in-progress tasks." * Clever. * Combiner - does it really need framework support? The user can just use the reducer code at the end of their Map. * So, each Reduce reads *all* Map outputs, and just filters by the key that belongs to it? Isn't it too many reads? And then read locality for inputs - does it even make much difference in comparison? * I suppose if the intermediate output is sorted on the Map worker, it's not that bad. And then the filtering is done on the Map side too. * Also it's network-constrained. If the sorting is done on the Map side, then the network transfer does not explode. * "This includes about a minute of startup over-head. The overhead is due to the propagation of the pro-gram to all worker machines, and delays interacting with GFS to open the set of 1000 input files and to get the information needed for the locality optimization." * The whole crawled web was 20TB around that time! It's just nothing! # ZooKeeper Paper: To summarize, in this paper our main contributions are: * Coordination kernel: We propose a wait-free coordination service with relaxed consistency guarantees for use in distributed systems. In particular, we describe our design and implementation of a coordination kernel, which we have used in many critical applications to implement various coordination techniques. * Coordination recipes: We show how ZooKeeper can be used to build higher level coordination primitives, even blocking and strongly consistent primitives, that are often used in distributed applications. * Experience with Coordination: We share some of the ways that we use ZooKeeper and evaluate its performance. Clients submit requests to ZooKeeper through a client API using a ZooKeeper client library. In addition to exposing the ZooKeeper service interface through the client API, the client library also manages the network connections between the client and ZooKeeper servers. In this paper, we use client to denote a user of the ZooKeeper service, server to denote a process providing the ZooKeeper service, and znode to denote an in-memory data node in the ZooKeeper data, which is organized in a hierarchical namespace referred to as the data tree. We also use the terms update and write to refer to any operation that modifies the state of the data tree. Clients establish a session when they connect to ZooKeeper and obtain a session handle through which they issue requests. ZooKeeper provides to its clients the abstraction of a set of data nodes (znodes), organized according to a hierarchical name space. The znodes in this hierarchy are data objects that clients manipulate through the ZooKeeper API. There are two types of znodes that a client can create: * Regular: Clients manipulate regular znodes by creating and deleting them explicitly * Ephemeral: Clients create such znodes, and they either delete them explicitly, or let the system remove them automatically when the session that creates them terminates (deliberately or due to a failure). Data model.The data model of ZooKeeper is essentially a file system with a simplified API and only full data reads and writes, or a key/value table with hierarchical keys. Client API: * create(path, data, flags): Creates a znode with path namepath, stores data\[] in it, and returns the name of the new znode. flags enables a client to select the type of znode: regular, ephemeral, and set the sequential flag; * delete(path, version): Deletes the znode path if that znode is at the expected version; * exists(path, watch): Returns true if the znodewith path name path exists, and returns false otherwise. The watch flag enables a client to set a watch on the znode; * getData(path, watch): Returns the data and metadata, such as version information, associated with the znode. The watchflag works in the same way as it does for exists(), except that Zoo-Keeper does not set the watch if the znode does not exist; * setData(path, data, version):Writes data\[] to znode path if the version number is the current version of the znode; * getChildren(path, watch): Returns the set of names of the children of a znode; * sync(path): Waits for all updates pending at the start of the operation to propagate to the server that the client is connected to. The path is currently ignored. Guarantees: * Linearizable writes: all requests that update the state of ZooKeeper are serializable and respect precedence; * FIFO client order: all requests from a given client are executed in the order that they were sent by the client. Can easily build primitives on top of it: * Locks. * Dynamic configuration. * Group membership. **Linearizability**. A history is linearizable, if exists a total order of ops, matches real time, reads see preceping writes in order. Why ZooKeeper? (MIT 6.824) * API for general-purpose coordination service. * Nx many servers - can it yield Nx performance? Takeway: in consesus-based systems like Raft, you can't scale write performance by adding more replicas - it can only get slower. You can scale read throughput by adding replicas and serving reads by replicas, but you have to relax some consistency guarantees. **Scalable lock** - implement locking without herd effect with seq noded. # Courses Many universities make their course materials available online. I prefer actual university courses to resources such as Coursera. ## Courses I studied in my spare time * [MIT 6.824: Distributed Systems](/tech/algorithms/distributed-hash-table-dht) * [MIT 6.854/18.415: Advanced Algorithms + Stanford CS168: The Modern Algorithmic Toolbox](/courses/mit-6.854-18.415-advanced-algorithms-+-stanford-cs168-the-modern-algorithmic-toolbox) * [Stanford CS234: Reinforcement Learning](http://web.stanford.edu/class/cs234/) * [Stanford CS243: Program Analysis and Optimization](https://suif.stanford.edu/~courses/cs243/) * [Stanford CS246: Mining Massive Data Sets](http://web.stanford.edu/class/cs246/) * [My homework solutions.](https://github.com/ainzzorl/stanford-246-mining-massive-datasets) ## Courses I consider doing * ## How to choose a course It goes without saying that the topic and the syllabus must be interesting and useful (whatever it means) to you. Beside that, an important factor is availability of study materials: * Lecture notes. * Textbooks. * lecture videos. * Homeworks. * When it comes to CS-related courses, I greatly prefer exercises that involve coding something. * Solutions to homeworks. If I don't know what I want to study, I skim the lists: * [Stanford CS](https://cs.stanford.edu/academics/courses) * [MIT CS](https://courses.csail.mit.edu/) * Harvard: TODO ## How I study After watching/listening/reading a lecture, I try to briefly explain the gist in my own words. If I can't, it means I didn't understand it. I also try to summarize the biggest takeways from it. Homeworks are extremely important. I neglected them when I was a student, but now when I study something in my spare time I take homeworks very seriously. # MIT 6.824: Distributed Systems [Course page](http://nil.csail.mit.edu/6.824/2020/) {% embed url="" %} [Hacker News discussions](https://news.ycombinator.com/item?id=23723513) [My homeworks.](https://github.com/ainzzorl/mit-6.824) ## Lectures 1. [MapReduce](/tech/mapreduce) [Video](https://www.youtube.com/watch?v=cQP8WApzIQQ) 2. RPC and Threads [Video](https://www.youtube.com/watch?v=gA4YXUJX7t8) 1. Didn't learn anything particularly new, but I loved it how they discussed the code on the screen. 3. [GFS](/tech/gfs) [Video](https://www.youtube.com/watch?v=EpIgvowZr00) 1. Consistency -> Poor performance. 4. [Primary-Backup Replication](/courses/mit-6.824-distributed-systems/primary-backup-replication) [Video](https://www.youtube.com/watch?v=M_teob23ZzY) 5. Go, Threads, and Raft [Video](https://www.youtube.com/watch?v=UzzcUS2OHqo) 1. 6. Fault Tolerance: [Raft](/tech/raft) (1) [Video](https://www.youtube.com/watch?v=64Zp3tzNbpE) 7. Fault Tolerance: Raft (2) [Video](https://www.youtube.com/watch?v=4r8Mz3MMivY) 8. [ZooKeeper](/tech/zookeeper) [Video](https://www.youtube.com/watch?v=pbmyrNjzdDk) 9. [Object Storage on CRAQ](http://nil.csail.mit.edu/6.824/2020/papers/craq.pdf) 10. [Aurora](/courses/mit-6.824-distributed-systems/aurora) 11. [Cache Consistency: Frangipani](/courses/mit-6.824-distributed-systems/cache-consistency-frangipani) 12. [Distributed Transactions](/courses/mit-6.824-distributed-systems/distributed-transactions) 13. [Spanner](/courses/mit-6.824-distributed-systems/spanner) 14. [Optimistic Concurrency Control](/courses/mit-6.824-distributed-systems/farm) 15. [Big Data: Spark](/courses/mit-6.824-distributed-systems/spark) # Primary-Backup Replication The Design of a Practical System for Fault-Tolerant Virtual Machines Very cool stuff overall. And I bet the implementation is super challenging. * "typically reduces performance of real applications by less than 10%" * Doesn't sound like nothing to me! * State-machine approach. * Crash-consistent or app-consistent? App consistent I guess? Or neither? * Do they assume no network calls, etc? Or is it another thing that the hypervisor intercepts and adjusts? * "Deterministic replay". * Fail-stop failures - detected before incorrect externally-visible action. * What sort of VMs are usually replicated like this? Must be something stateful. DB servers? * Ok, network and all inputs go only to the primary. * Secondary outputs are dropped. * Split brain - must ensure that only one VM takes over the execution. * Challenges: * Capture all inputs and non-determinism. * Apply them to the backup. * Do it without degrading performance. * Also instructions with undefined behavior. * Inputs and non-determinism are written to a log, then read. * Log is not written to disk - sent straight to the backup. * They can have any number of secondaries this way I suppose? If they fan out the log stream. * If the backup takes over, must function consistently with outputs of the primary. * Delay external outputs until the event has been applied to the secondary. * Received and acked. * This prevents duplicate outputs at failover. * We assume some failure on the hardware/infra level? Otherwise, if the primary failed, why wouldn't the secondary fail too? * Can't guarantee that all outputs are produced exactly once! * The logic is baked into the hypervisor? * Split-brain is avoided - before going live, a VM acquires a lock on the shared storage. If it can't - it kills itself. * To start replication (not necessarily when the VM is starting), they have a tech to clone a running VM. * If the primary produces logs faster than the secondary can consume, it will result in slowing down the primary. * Operations like shutting down should be directed only to the primary machine. * Parallel non-blocking disk reads can lead to non-determinism. * Solution: detect such races, force to execute sequentially. * Alternative design: no shared storage. * Secondary writes to its own disk. * Can do long distance. * Need to sync disks when it's failing over. * Harder to deal with split-brain situations. * Alternative design: instead of sending disks inputs through the logging channel, the secondary could actually read from the disk. * It would reduce the logging traffic significantly. * But there are too many subtleties. Like dealing with failed disk operations. * Only implemented for uni-processor VMs. Mkay. * Is there a way to extend it I wonder? * How do the clients cut-over? How do they know to communicate with the new machine? I suppose it has different IP? Or the same? I'm missing something major here. * They say the backup claims the primary's ethernet id. Lecture () notes: * Replication: only deal with fail-stop faults. Not bugs, etc. * Assume failures are independent. If dependent - replication won't help. * Is it worth to pay for 2 machines? It depends. An economic question, not tech. * State transfer vs Replicated State Machine. * Operations are usually much smaller than the entire state. * But state replication is more complex. * To implement replicated state machine we need to decide: * What state? * How to synchronize? How close? * Scheme for switching over. * Anomalies in cut-over. How to cope with them. * New replicas. * What state? All state. Memory, etc. * It's rare. Usually replication only does what's important for the application. But here it's very general-purpose. * Application-level replication requires the application to participate in it. * Disk Server is not much, or at all, different than any other network dependency. * Non-determinism: * Inputs - data + interrupt. * Weird instructions like random numbers, time, ... * Multi-core. Not dealing with it here. * Log entry: * Instruction number/index. * Type (network input, weird inst...) * Data * Any replication system would have possibility of either duplicate outputs, or missing output (during cutover). Duplicate output is usually better. If it's TCP, it will be deduped on TCP level, transparently to client apps. # Object Storage on CRAQ Video: * Chain replication. The basic approach organizes all nodes storing an object in a chain, where the chain tail handles all read requests, and the chain head handles all write requests. Writes propagate down the chain before the client is acknowledged, thus providing a simple ordering of all object operations—and hence strong consistency—at the tail. The lack of any complex or multi-round protocols yields simplicity, good throughput, and easy recovery. * Apportioned queries: that is, dividing read operations over all nodes in a chain, as opposed to requiring that they all be handled by a single primary node. * Eventual Consistency in our system implies that writes to an object are still applied in a sequential order on all nodes, but eventually-consistent reads to different nodes can return stale data for some period of inconsistency (i.e., before writes are applied on all nodes). * Each node can store multiple versions on an object. When it receives a write, it's marked as "dirty". When it receives an ack from below it markes it as "clean". When handling a read, if the value is clean - return it. If it's dirty - check with the tail, return its version. * Read-heavy - load distributed mostly uniformly across all nodes in the chain. Life is good. * Write heavy - will need to check with the tail a lot. Not great, but tolerable. # Aurora * "We believe the central constraint in high throughput data processing has moved from compute and storage to the network." * "Aurora brings a novel architecture to the relational database to address this constraint, most notably by pushing redo processing to a multi-tenant scale- out storage service, purpose-built for Aurora." * "Instance lifetime does not correlate well with storage lifetime. Instances fail. Customers shut them down. They resize them up and down based on load. For these reasons, it helps to decouple the storage tier from the compute tier." * "In Aurora, we have chosen a design point of tolerating (a) losing an entire AZ and one additional node (AZ+1) without losing data, and (b) losing an entire AZ without impacting the ability to write data. We achieve this by replicating each data item 6 ways across 3 AZs with 2 copies of each item in each AZ." Not very easy to follow. The [FAQ](http://nil.csail.mit.edu/6.824/2020/papers/aurora-faq.txt) explains it greatly though. ``` Mirrored MySQL involves an ordinary MySQL database server that thinks it is writing to a local disk. Each transaction involves a bunch of large writes to update B-Tree pages; even if a transaction only modifies a few bytes of data, the resulting disk writes are entire file system blocks, perhaps 8192 bytes. The mirroring arrangement sends those 8192-byte blocks over the network to four different EBS storage servers, and waits for them all to write the data to their disks. Aurora, in contrast, only sends little log records over the network to its storage servers -- the log records aren't much bigger than the actual bytes modified. So Aurora sends dramatically less data over the network, and is correspondingly faster. ``` FT Goals: * Write with one dead AZ. * Read with one dead AZ + 1. * Resilient to transient slowness. * Fast re-replication. Quorum replication: * N replicas. * W for writes. * R for reads. * R + W = N + 1 # Cache Consistency: Frangipani {% embed url="" %} * I like they don't shy away from saying they didn't explore something or they haven't got enough experience with something. * Small data blocks and large data blocks separately. Clever. * Very decentralized. All the file system logic is on the clients. * Challenges with consistency then. Challenges: * Cache coherence. * Atomicity. * Crash recovery. Coherence is solved with locks. Atomic multi-step operations: * Distributed transactions. * First acquire all the locks I need. Then do all updates. Then release all the locks. * But can crash in the middle of doing the updates. With locks. * Can't just release its locks. * So do write-ahead logging (WAL). * Separate per-workstation logs, in the shared storage. * Logs contain only metadata-changes, not file contents. * Log initially is in-memory; written to Petal only when it has to be. * In revoke: * Write log to Petal. * Write modified blocks for locks. * Send release. * If a workstation crashes while holding a lock, another workstation will replay its log! And only then the lock will he released. # Takeways 1. [MapReduce](/tech/mapreduce) 1. Simple interface to hide the complexity of mass parallelism, fault tolerance, scale, etc. 2. Data and computation are on the same cluster. You try to run jobs on the same machines where you have the data. 2. [GFS](/tech/gfs) 1. Filesystem-like interface but not exactly. 2. Purpose-built for their use cases. They can afford a lot of weirdness (e.g. non-idential replicas) because of this. 3. Replicate data. 4. Consistency -> Poor performance. 3. [Primary-Backup Replication](/courses/mit-6.824-distributed-systems/primary-backup-replication) 1. Represent a VM as a state machine. 2. Make it fully deterministic. 3. Apply actions to the replica and the backup. 4. Raft 1. Replicate the log across peers. 2. Elect leader. 3. Consistency guarantees through a clever scheme. 4. Requires a majority for anything. Two different majorities always overlap, so can't overwrite something. 5. Reply to the client only when committed. 6. Any application, like KV server, is built on top. 7. 5. [Object Storage on CRAQ](http://nil.csail.mit.edu/6.824/2020/papers/craq.pdf) 1. Can do chain replication. 2. Leader handles writes. 3. The last node in the chain handles reads. 6. [Aurora](/courses/mit-6.824-distributed-systems/aurora) 1. Decouple storage from the rest. 2. Only replicate the log. This way, drastically reduce the network traffic. 7. [Cache Consistency: Frangipani](/courses/mit-6.824-distributed-systems/cache-consistency-frangipani) 1. Can cache local operations. 2. Achieve cache coherence with clever locking. 3. Only write when releasing a lock. # Distributed Transactions * Concurrency control. * Atomic commit. ACID: Atomic, Consistent, Isolated (serializable), Durable. Serializable: exists serial order of execution of the transactions that yields same result. Concurrency control: 1. Pessimistic. 2. Optimistic, OCC. If conflicts are frequent - pessimistic is good. If they are rare - optimistic is good. Two-phase locking: 1. Acquire lock before using record. 2. Hold lock until after it commits or aborts. It's bad for concurrency, but required for performance. Distributed transactions: * Transaction participants. * Transaction coordinator (TC). * Each message is tagged with transaction id. * First send prepare message to participants. Make sure participants can do it. * If they all reply yes, send Commit message. Participants reply. * Participants unlock when they see either Commit or Abort. What if a participant crashed after replying to PREPARE but crashed? When recovering, it must still be prepared to commit. So the participant must make state and locks durable on disk before replying to Prepare. What if a participant crashed after making change but before returning to COMMIT? What if TC crashes? Before sending COMMIT messages, it must write it to its durable log. If it doesn't receive replies from any Prepare's, it must abort. If a participant is waiting for Commit but hasn't received it for some time, it's not entitled to abort the transaction unilaterally. It must keep waiting. Blocking and locking is a fundamental property of 2-phase commits. But it's not a good property. It makes it slow. The decision is made by a single entity - TC. Sort of looks similar to Raft, but it's entirely different. It solves very different problem. Raft: High availability by replicating data. Can operate even though some servers are unreachable. In 2PC, you need to wait for all participants. Raft - everyone is doing the same, 2PC - everyone doing different. Raft is all about availability, 2PC - not highly available at all. 2PC is correct with failures, but not available with failures. You can use Raft to replicate each part, coordinate cross-shard communication with 2PC. This can be highly available and correct. # Midterm Questions: Answers: ### MapReduce A. Briefly describe the advantage of allowing reduce workers to start reading intermediate files early The entire job will finish faster. The job will finish when the last reduce task is finished, so the sooner the reduce jobs will start the sooner the entire thing will finish. The started reduce job might need to wait for the map, but it is at least not slower than waiting for the map to finish before starting the reduce. B. Describe how you would modify your lab implementation to allow reading of intermediate files early, as Google's MapReduce library does, while maintaining correctness. (You don't have to write code, but sketch out a design in words. Keep your answer brief.) Modifications to the master: * Start assigning Reduce tasks before all Map tasks are done. It should still assign Map tasks before Reduce tasks. Modifications to reduce workers: * We now cannot sort the input by key. Instead, we should maintain a map key->state. * Find the first unprocessed Map output. Iterate the values, update the state for the corresponding key. Repeat until all map outputs are processed. * `reducef` must support streaming, e.g. support `reducef(key, state, values): updatedState`. Hmm, in the answers they just suggest to copy files over, but not actually start computations on Reduce... It makes sense I guess. ### MapReduce (Lab) When testing their implementation, Zara notices that a job with map tasks numbered 0, 1, and 2 often fails. A. In some scenarios, some reduce workers cannot open intermediate file mr-1-x (where x is the Reduce task number). Explain a scenario that could cause this to occur. I see two problems: * The loop over map tasks starts from `numCompletedMapTasks`. This seems to assume that tasks are completed in the same order as they are assigned, which is not guaranteed to be true. * `numCompletedMapTasks` can be counted twice if one worker times out but later still reports the job as done, and then another worker also completes the task. Scenario where this output can happen: * Task 0 is assigned to worker 0, task 1 is assigned to worker 1. * Worker 0 dies. * Worker 1 completes successfully, `numCompletedMapTasks` is set to 1. * Then task 0 will never get finished. Any reduce worker trying to read its output will fail. B. Briefly describe what Zara should do to fix this problem. * Start the first loop from 0. * Maintain "completed" flag for each task. Increment `numCompletedMapTasks` only if this task is completed for the first time. ### GFS A. The GFS file system doesn't guarantee linearizability. Give an example of how the lack of linearizability complicates writing programs with GFS. That is, describe a feature that one must implement when using GFS that one wouldn't have to implement if GFS would have provided linearizability. Briefly explain your answers. Users need to implement checksums to verify data consistency, and/or use appends with deduplication where they would otherwise use writes. B. Briefly explain why append operations are not allowed to span chunk boundaries. Can't dedup if something is written twice. (???) Wrong: to make appends atomic. ### VMware FT In VM-FT (as described by in the paper "Fault-Tolerant Virtual Machines" by Scales et al.), the backup lags behind the primary to ensure, for example, that network interrupts are delivered at exactly the same instruction at the backup as on the primary. Briefly explain what could go wrong if the backup delivered interrupts at a different instruction than the primary? Interrupt handles on two replicas will trigger in different replica states and will produce different results. The replicas will deviate forever. ### Raft Consider figure 7 of the Raft paper "In search of Understandable Consensus Algorithms (Extended Version)". The last follower (at the bottom of the figure) has term 3 in its last index 11. Could there have been a scenario under which that follower's log had entries in indexes 12, 13, and 14 in figure 7? What terms could those entries have? (Briefly explain your answer.) It could have more entries with term 3, it it received more entries from the client in that term before committing them. It could only be 3; it could not be a leader of any other term, and it it received more entries as a follower, terms 2 and 3 would've been overwritten. ### Raft (Lab) A. No failures of any kind 5 (eventually). Once for each server. B. Network partitions possible (but no crashes) 0 or 3-5. 0 if it never commits. 3 or higher if it commits and is replicated to the majority. C. Crashes possible (but no network partitions) 0 is possible. It is still not guaranteed to replicate everywhere - the leader can crash, another leader will be elected, and this message will get lost forever. If it does replicate, it will replicate everywhere eventually. So, 5. Can it be greater than 5? Yes. It can be any number greater than 5 if it restarts. ### Raft (Persistence) While implementing Raft, Connie Consensus decided that instead of persisting the entire log, she would persist only committed entries. Connie claims that uncommitted entries could have been lost because of crashes or network issues so it's safe to ignore them until they've been committed. Does this change affect Raft's correctness? If so, provide a sequence of events that would lead to unsafe behavior. You can assume that the rest of Connie's implementation is correct. When a leader sends an entry to the follower and it replies with success, the leader assumes it will be durable. Otherwise the correction breaks. * 3 servers. * S1 is elected the leader. * S3 is partitioned away. * S1 sends and entry to S2, S2 replies success. * S1 commits the entry and replies to the client with success. * S2 crashes and "looses" the entry. * S3 wakes up, S2 wakes up, S1 is partitioned. * S3 becomes the leader. * S2 and S3 keep committing new entries. The previously committed entry is lost. ### Zookeeper A. Zookeeper's read throughput scales with the number of servers (e.g., see the red line in Figure 5). The Raft paper describes an optimization for read-only operations. Would that optimization allow Raft to scale read throughput with the number of peers as in Zookeeper? (Briefly explain your answer.) Yes, but only at expense of weaker consistency guarantees. It would allow stale reads. B. For this example, briefly explain what could go wrong if ZooKeeper didn't guarantee FIFO client order. In particular, what values could the read of f by client 2 return? 0, or 1. # Spanner [Paper](http://nil.csail.mit.edu/6.824/2020/papers/spanner.pdf). At the highest level of abstraction, it is a database that shards data across many sets of Paxos \[21] state machines in datacenters spread all over the world. Replication is used for global availability and geographic locality; clients automatically failover between replicas. Spanner automatically reshards data across machines as the amount of data or the number of servers changes, and it automatically migrates data across machines (even across datacenters) to balance load and in response to failures. Spanner is designed to scale up to millions of machines across hundreds of datacenters and trillions of database rows. "We believe it is better to have application programmers deal with per- formance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions. Running two-phase commit over Paxos mitigates the availability problems." My understanding: * Global database. * Sharded, each shard is replicated, possibly across data centers and even continents. * Writes are standard two-phase commits. Can be rather slow because of the whole cross-continent thing. * Reads are fast because we don't use locks and can read from the nearest replica. * The tricks are: * Versioned storage. Associate each update with a timestamp. When a read starts, capture the timestamp, and get latest before it. * It increases storage, but it's ok-ish. We can garbage collect. * Call this snapshot isolation. * We can know if the replica is guaranteed to have all updates up to the time. If it doesn't - wait. * For times, we need good clock. TrueTime to the rescue. It offers a confidence interval. * Time sync is important for RO. RW - they use 2PC, they don't care. # FaRM [Article](http://nil.csail.mit.edu/6.824/2020/papers/farm-2015.pdf). * Super fast with DRAM. * All within one data center. Doesn't solve geo replication anyhow. * Bottleneck - CPU. * Sharded by key between primary/backup pairs. * All replicas are updated if there's change. You always read from primary. If one replica is available you are good. * All must fit in the (combined) RAM. * Tolerate power failures - non-volatile RAM scheme (NVRAM). * RDMA - network interface cards that can read/write memory directly. * Kernel Bypass - app code can access network cards directly, without kernel help. * When the battery system detects main power failure - stop all processes, write all RAM to SSD. Then die. * RDMA - remote direct memory access. Access memory remotely without involving destination CPU at all. Append messages to a queue. * API: * txCreate() * o = txRead(oid) * o.f += 1 * txWrite(oid, o) * ok = txCommit() # Spark [Paper](http://nil.csail.mit.edu/6.824/2020/papers/zaharia-spark.pdf) "Generalized MapReduce". # Cache Consistency: Memcached at Facebook [Paper](http://nil.csail.mit.edu/6.824/2020/papers/memcache-fb.pdf) * We provision hundreds of memcached servers in a cluster to reduce load on databases and other services. Items are distributed across the memcached servers through consistent hashing * Front-end servers, database, pool of memcache servers. * Multiple regions, full DB primary-secondary DB replication. * Multiple clusters within a region. Cluster: only FE + DB. * Regional memcache pool for non-popular keys. * DB is sharded. * MC is also sharded, with consistent hashing. * Starting a new cluster is a problem because it temporarily increases the DB load. They "cold start" new clusters by making them read from other cluster's cache first before the new cache is warm. * One cluster can't be too big, will overload popular keys within the cluster. * "Thundering heard". Very popular key in MC, many FEs are reading it. Someone deletes the key, and the cache is invalidated. Now everyone tries to read the DB at the same time, not good. * They use "Leases". When you miss a cache, it gives you a "lease". Other callers are asked to wait. * The owner of the lease will be allowed to put. * If MC instance fails, the DB is exposed. The MC can be auto replaced, but it takes a while. * There's a small set of GUTTER servers, idle unless a MC server fails. * If a MC fails, the request is sent to a GUTTER instead. * Consistency problem - there are many copies of the same data. Master DB, each DB replica, many MCs... When a write comes in, something must happen on all these copies. * There can be races, ending up writing stale data to cache. It stays there indefinitely. Also solved with leases. When you read, you get a lease to write. When someone deletes, it invalidates the lease. * Caching is not so much about reducing latency, but about hiding a relatively slow DB from the very high load, # Page 2 # MIT 6.854/18.415: Advanced Algorithms + Stanford CS168: The Modern Algorithmic Toolbox These two courses, [MIT 6.854/18.415: Advanced Algorithms](http://people.csail.mit.edu/moitra/854.html) and [Stanford CS168: The Modern Algorithmic Toolbox,](http://web.stanford.edu/class/cs168/index.html) overlap a lot, and I studies them together. Where they overlap, they sort of augment each other in terms of materials: the MIT course has video recording of lectures, but the Stanford course has more interesting (IMO) homeworks. [Videos](https://www.youtube.com/playlist?list=PL6ogFv-ieghdoGKGg2Bik3Gl1glBTEu8c). [My homeworks](https://github.com/ainzzorl/stanford-cs168-modern-algorithmic-toolbox) (just the coding questions). I was familiar with some of the topics in the courses; I skipped the lectures where I thought I already knew the topic sufficiently well. ## Hashing, Load Balancing * * * * * * * [Akamai Paper](https://www.akamai.com/uk/en/multimedia/documents/technical-publication/consistent-hashing-and-random-trees-distributed-caching-protocols-for-relieving-hot-spots-on-the-world-wide-web-technical-publication.pdf) * Recipe for "universal" HF. Family of \[ha, b(x) = (ax+b mod p) mod n, a != 0] works just as good as completely random universal HFs. A family of hash functions H is 2-universal if, for any pair x!=y,Pr\[h∈H | h(x) =h(y)] ≤ 1/n * Power of 2 choices: if we distribute N tasks to N servers randomly, the max load on one will be Θ(lognlog logn). If we pick 2 and assign to smallest, it's Θ(log logn) which is a lot better. * Consistent caching: assign machines randomly to points at \[0, 1] interval. Then each request is randomly assigned to a point too, and routed to the machine on the right, with wrapping. The idea is that when we add or remove machines, we don't need to redistribute things too much. * Caches and pages are mapped to the same space. There are no "indexes" for caches or anything. * To answer queries on big data (streams) or get some statistics, we can sacrifice some accuracy for big gains in memory. It's lossy compression. * E.g. Bloom filters, count-min sketch (estimate frequency of element in a stream), algs to estimate number of distinct elements. * Count-min sketch - estimate frequency of any element in a steam. Choose l HFs, b values each. Hash each element with each hash and increment corresponding counters. Estimate frequency by checking min value for all hashes. * Huge practical improvement can be achieved by conservative updates - if we don't increment the counter if it is already the max in corresponding buckets. Does not miss anything (still guaranteed to overestimate the frequency), but makes the guess a lot closer to the truth. At least this is what happened in the homework. ## Data with Distances (Similarity Search, Nearest Neighbor, Dimension Reduction, LSH) * * * * * * * High data dimensionality is bad - even calculating distance between rows is too expensive. But it can be reduced/embedded to lower dimentionality rather easily (Johnson-Lindenstrauss). Basically, we "hash" (estimate) each point and use the result as a proxy for comparison. Repeat X times to boost confidence. JL works only for preserving Euclidian distances! If you have other metrics - not so much. * Dimentionality reduction is kind of lossy compression. Like count-min sketch. * Every precise algorithm to find nearest neighbour is exponential in dimensions, either runtime or space, or both. Higher dimentional spaces sort of lack geometry. * kd-trees - partition space into binary tree to find nearest neighbour. Kinda like Voronoi diagram in arbitrary dimensions. Exponential of dimentions because we can't always discard one branch. * LSH - can quickly find nearest neighbor (not precisely, though) by using hashes that are likely to collide for similar elements and unlikely for distant. * Use k different hashes, each being locality sensitive. In preprocessing, hash each point with each hash and put to corresponding bucket (different hashes use different buckets). * Query: hash, compare to all elements in all buckets. * Can tune characteristics by changing the cardinality of each hash (bigger - fewer FPs) and number of hashes (bigger - fewer FNs). * Each hash is usually a combination of hashes, this allows us to boost size of each hash and reduce FPs. * Min-hash: estimate Jaccard similarity by using random permutations. Use random pertumation, then MinHash(A) = min(perm(A)). Probability of two sets having the same hash is their Jaccard similarity exactly. Repeat N times (that's why we need permutations - so we can hash the same thing many times differently) to boost. * What does "min" mean? We just assign some values to points. Some random hash to ints. The idea is that this "min" gives us Jaccard similarity - it is the same in 2 sets iff it belongs to their intersection. ## Max Flow, Min Cost * * * (Max flow) Any flow can be decomposed into s-t paths and cycles. Cycles can be ignored for the purpose of finding the max. * Max flow is equal to the min cut. * Ford-Fulkerson - iterate in the "residual" graph (arcs that can be added, including reversing). Find path increasing the flow and add it. * This is not guaranteed to converge if capacities are real numbers! If they are ints/rationals, it will finish, but can be very slow and depends on exact arc capacities. Unless we are smart about how we pick the paths (shortest, adding max increment, ...) * Capacity Scaling: like FF, but only look for edges in the residual graph with capacity >= D until there's no path. Then divide D by 2, and repeat while it's >= 1. Will finish in O(m2(1 + lgU)) * Min-cost flow - each edge has a capacity, we are looking for max flow minimizing ∑(a,b)∈Ef(a, b)c(a, b). * Can use max flow to find max matching in a bipartite graph. * Can use idea similar to FF to find min-cost perfect matching. Construct a different type of residual graph, look for cycles of negative weight, improve. It's called Klein's Cycle Cancelling Algorithm. * Goldberd-Tarjan: apply negative cycles to find min-cost max-flow by choosing the negative cost cycle that minimizes cH(C)/|C| (mean cost in the cycle). ## Linear-Algebraic Techniques: Understanding Principal Components Analysis * [http://web.stanford.edu/class/cs168/l/l7.pdf]() * [http://web.stanford.edu/class/cs168/l/l8.pdf]() * PCA (Principal Component Analysis): express m n-dimensional vectors as a linear combination of k n-dimensional vectors. Choose "best" such vectors maximizing the variance. Helps visualizing, interpreting the data. * PCA components are eigenvectors with biggest eigenvalues of the covariance matrix multiplied on the left by itself transposed. These are the directions of the biggest stretch, geometrically. * Each principal component best "fits" the data (minimize avg squared distance to the line) while orthogonal to previous components. * PCA is a dimensionality reduction technique that helps visualizing/interpreting/compressing the data. ## Sampling and Estimation * * * Reservoir sampling - sample k elements uniformly from a stream of unknown size. In one pass. * Markov - "at most 10% of the population can have an income that is more than 10× the average income of the population" * Chebyshev - "the probability that a random variable is more than c standard deviations from its expectation, is at most 1/c2" * In general, to estimate the expectation of a 0/1 random variable to error ±ε, one needs roughly O(1/ε2) independent samples * Importance sampling - oversample "important" subset (eg heavy tail), adjust weights to keep the estimator unbiased. Keeps the expectation, but reduces the variance * Good-Turing frequency estimation - "An estimate of the probability that the next word you read is a new word that you haven’t seen before, is the number of words that you have seen exactly once, divided by the total number of words that you have seen." * Markov process - initial state, set of states, transition probability. Markov property - the transition depends only on the current state; no memory. * Estimate probability of being in certain state after certain number of steps either directly (multiply some matrices) or by random sampling - Markov Chain Monte Carlo (MCMC). * Example - PageRank's random walk. * Fundamental Theorem of Markov Chain - if there's path from any state to any other, and it's aperiodic, then the probabilities will converge to some distribution, independent of time and initial state. Called the stationary distribution. ### The Fourier Transform and Convolution * [Fourier Transform](/math-1/fourier-transform) # Math # Fourier Transform * [Modern Algorithmic Toolbox](http://web.stanford.edu/class/cs168/l/l15.pdf) * [An Interactive Introduction to Fourier Transforms](http://www.jezzamon.com/fourier/index.html) * Great explanation. * * # Probabilities & Statistics ## Probability vs Likelihood Probabilities attach to results; likelihoods attach to hypotheses. E.g. probability of certain result given distribution; likelihood that the distribution is this given an observed result. We usually consider ratios of likelihoods to compare hypotheses. # Places # Moscow ## Restaurants * [Зеленый Лис/Zeleny Lis](https://www.zelenylis.ru/) * Vegan. * Nice atmosphere. * Nice breakfasts and lunches. * The menu for business lunch doesn't change (often). * No alcohol. * [Джаганнат/Jagannath - Prospect Mira](https://www.jagannath.ru/jagannath-mira/) * Vegetarian. * "Stolovaya"/over the counter. * Pretty delicious. * They won't warm up your food unless you ask. Strange. * [Falafel Bro](http://falafelbro.ru/) * "Vegan street food". Not on the street, though. ¯\_(ツ)\_/¯ * Tasty. * In the basement; there's place to eat there, but I had no desire to stay. * [Flora no Fauna](https://www.instagram.com/floranofaunacafe/?hl=en) * Vegan. * Meh. * [Raw to go](http://rawtogo.ru/) * Vegan. * Raw :-) * I never tried the delivery. * The cafe (Большой Патриарший пер., д. 12, стр 1) is great. * [Avocado/Авокадо](https://avocadocafe.ru/#about) * Vegetarian. * Delicious. * [Центральный Рынок/Central Market](https://moscowcentralmarket.ru/) * Huge and awesome food court. * [Депо/Depo](https://depomoscow.ru/) * Huge and awesome food court. ## Parks # Books ## Rubric * 1\* - worse than garbage. Actively horrible. * 2\* - bad. * 3\* - meh. Somewhat enjoyed, though. * 4\* - enjoyed, would recommend. * 5\* - among all-time favorites, would recommend to anyone. # Page 1 # Page 1 # Page 1 # Page 1 # Page 1 # Tobol Mnogo Zvannyh - Ivanov # The Twelve Chairs/12 стульев - Ilf, Petrov Finished: 9/19/2021 Rating: 5 Would recommend: yes. Hilarious! I had no idea how many common jokes are rooted from there. # Beauty is a Wound - Eka Kurniawan Finished: 9/9/2021 Rating: 4- Would recommend: maybe. This was strange AF. Really really weird. Occasionally in a good sense. Too much rape-driven narration, though. # The Queen of Spades/Пиковая Дама - Pushkin Finished: 8/24/2021 Can't rate. Pushkin is Pushkin, but it's hard to take this mystical stuff any seriously. # The Sirens of Titan - Kurt Vonnegut Finished: 8/21/2021 Rating: 3\* Would recommend: no. Very strange. Funny at places. Not funny at most other places. It's enough Vonnegut for me. # Обитель - Захар Прилепин Finished: 8/12/2021 Rating: 5\* Would recommend: yes. Wow this was strong. Loved it. Yuzefovich: # The Faithful Executioner - Joel Harrington Finished: 7/31/2021 Rating: 3+\* Would recommend: maybe. Interesting topic; mostly not very interesting narration. A lot of guesswork. # City of Lies: Love, Sex, Death, and the Search for Truth in Tehran - Ramita Navai Finished: 7/22/2021 Rating: 3-\* Would recommend: no. [Goodreads](https://www.goodreads.com/book/show/21535308-city-of-lies). Meh. Feels very repetitive, very... made up. # June/Июль - Dmitry Bykov/Дмитрий Быков Finished: 7/11/2021 Rating: 4-\* Would recommend: maybe [Goodreads](https://www.goodreads.com/book/show/4406.East_of_Eden). [Yuzefovich](https://meduza.io/feature/2017/09/02/luchshiy-roman-dmitriya-bykova-iyun). * I liked the first part most. I could relate. A bit too pornographic to my liking, though. * Very anti-soviet. * Did he actually follow the pattern described in the part 3? # East of Eden - John Steinbeck Finished: 6/29/2021 Rating: 4-\* Would recommend: maybe [Goodreads](https://www.goodreads.com/book/show/4406.East_of_Eden) * Interesting to read. * I expected more from it. It's supposed to be a masterpiece, but it didn't feel like it. * I'm a bit sick of family sagas by now; it somehow happened that I read only them recently. * The villain, Cathy, is too simple. She's revealed to be pure evil right away. It's silly how she reveals all her secrets immediately when she drinks. But I guess it's the biblical devil or something. * It's the story of Cain and Abel, repeated. I get it. # Como Agua Para Chocolate/Like Water for Chocolate - Laura Esquivel Valdés Finished: 6/29/2021 Rating: 2\* Would recommend: no [Goodreads - Spanish](https://www.goodreads.com/book/show/73716.Como_agua_para_chocolate?ac=1\&from_search=true\&qid=7L0c2nBDzz\&rank=1), [Goodreads - English](https://www.goodreads.com/book/show/6952.Like_Water_for_Chocolate?ac=1\&from_search=true\&qid=Rqo0odCXNM\&rank=1) I read it only for the sake of practicing my Spanish - I chose it because it's written by a Mexican writer, it's rather short and is available in my public library. I found it very silly and not in my taste at all. What I hated in particular is just how quickly major events (like deaths of major characters) are described, compared to the emotions and thoughts, etc. The whole magical realism is not for me, either. # The Kukotski Enigma/Казус Кукоцкого - Lyudmila Ulitskaya/Людмила Улицкая Finished: 6/9/2021 Rating: 4\* Would recommend: yes Reminds me of every other family saga I ever read: Middlesex, Тихий Дон (And Quiet Flows the Don), even "100 years of solitude". But it was quite interesting to read overall. I hated the dream section, though. The critics complain that it lacks structure or actual storylines, and it's true. But it was fun nevertheless. # Ancillary Justice - Ann Leckie Finished: 6/6/2021 (didn't actually finish). Rating: 2\* Would recommend: no I gave up after \~50 pages. I found it outright impossible to make myself read it. It's strange given all the awards it won. # Career of Evil - JK Rowling Finished: 6/2/2021 Rating: 5-\* Would recommend: yes **Spoilers below!** * Very exciting to read. Loved it. * Not a typical mystery though. * It's not at all clear how the reader was supposed to solve it on their own. * Flowers out of season? Surely not. * Arthritis meds? * Suspect Ray? Possible. We were supposed to look for a Kelsey connection. # The Signal and the Noise - Nate Silver Finished: 5/26/2021 Rating: 4-\* Well-put, interesting to read. I didn't learn much new though, but I'm rather familiar with the topic. Bayesian thinking FTW! # Don't Sleep, There are Snakes - Daniel Everett Finished: 5/26/2021 Rating: 5\* Goodreads: * It's crazy to think that the whole mission to learn their language, etc. was done by missionaries to teach the Bible to Indians. * It's so strange that he didn't just go along, but brought his entire family. * The story of him rushing with his family to the hospital is terrifying. And exciting. * I wonder how children learn the intricacies of the language, e.g. what an article really means and when to use it. * I wonder if his wife/daughter were ok with him putting the details of their diarrhea into writing and sharing with the world. It's nothing to be ashamed of or anything, but I would not have liked it. * Living in the moment, not thinking about the future - nice. * Not treating children much differently - nice. * No numbers, no quantifiers. Wow. * To orient themselves in a town, they need to know where the river is. Amazing. * Cognition-> Grammar (Chomsky) vs Grammar->Cognition (Linguistic relativity, Sapir–Whorf hypothesis). * Can only work in a single file, even in a city - nice. * The "debate" against Chomsky was a bit too much for the book, IMO. * The ending, about his missionary work and religion, was wonderful. * I wonder what happened to his family. * It must be very unpleasant to read if you are religious. * "'The women are afraid of Jesus. We do not want him.' 'Why not?' I asked, wondering what triggered this declaration. 'Because last night he came to our village and tried to have sex with our women. He chased them around the village, trying to stick his large penis into them.' Kaaxaooi proceeded to show me with his two hands held far apart how long Jesus's penis was - a good three feet." * Goodreads reviewers claim he constantly contradicts himself. Well, maybe. # Оправдание Острова - Eugene Vodolazkin Finished: 5/15/2021 Rating: 4\* A "pritcha" about history. Would recommend. * It was quite enjoyable to read overall. * The chapters about making the movie and life in Paris seemed boring. * Maybe a bit too long. Why did they need a chapter about a horse-obsessed leader after a bee-obsessed leader? * It seems to mock the entire world history, not just the Russian. But nothing is too precise. * It makes one look at the history of the world "from the above". * The mystical element (ancient princes, yelling "knife" across the island, people generally hearing things from too far) are... interesting. * The mocking of the revolution was hilarious. * The narrator is unreliable, is he? For some parts of the story, he's very explicitly unreliable (when there are two tales of the same event), but for the rest? I wonder if the story of the revolution and of the abdication is told honestly. Are the ancient prince and princess really this holy? * I just love his style. * A lot of kindness and wisdom in there. * I loved the "discoveries" of evidence of their ancestry from August. I will read more of Vodolazkin for sure. Yuzefovich review: # A Place Called Winter - Patrick Gale Finished: 5/5/2021 Rating: 3+\* Gay romance set in the early days of farming in Canada. Not bad, but would not recommend. * The first part, before he moved to Canada, seemed too long and uninteresting. * The Bethel part was not interesting. * Rather interesting to read overall, however. * The settings (Canadian farms) were nice. * The villain is a bit dumb. * I hate rape-driven plots (Kite Runner is the worst offender IMO). It's the cheapest way to make someone sympathize the character. * I'm not too interested in gay soul searching. * Not too clear what it's all about really. What was the point of it. # 1491: New Revelations of the Americas Before Columbus - Charles C. Mann Finished: 4/26/2021. Rating: 3\* Listened an audiobook. * Indians were very numerous. * Killed off by germs. * Older and more advanced than previously thought. * Freedom-loving. * Controlled the environment. I'm generally very interested in the topic, but this book I found a bit hard to focus on. Perhaps I should've read it instead of listened. # Трудно Отпускает Антарктида - Vladimir Sanin Finished: 4/13/2021 Rating: 3\* A novel about Antarctic explorers getting stuck on the continent unable to leave. I love books about Antarctic, explorations, etc. but this was not exactly about it. It's mostly about the people. But it was fun to read this very Soviet style of writing. I wonder if people actually were like that back then? # Klara and the Sun - Kazuo Ishiguro Finished: 4/15/2021 Rating: 4\* ## Overall (No Spoilers) Loved it overall. Ishiguro in his finest. It reminded me greatly of Never Let Me Go, which is one of my favorite books. But it may be even *too* similar in a way. Very touching, atmospheric. Intricate world building, very thought-provoking, filled with infinite kindness. ## Plot Summary (Spoilers) The story is told from the point of view of Klara, an "AF" robot. It's soon explained that AF stands for Artificial Friend. She "lives" in a store, has a friend AF called Rosa, and the store is operated by human Manager with whom they seem to have very good relationship. Klara loves looking through the window and admires the Sun, which powers her. Once she sees a homeless man and his dog lie motionless for over a day (dead?), but then the Sun sends them "special nutrition" that brings them back to life. While standing near the window, Klara meets a girl, Josie. Josie promises to come back for Klara. Klara likes her very much and wants it to happen. The girl then comes again in a few days, but again she promises to come back next day. She doesn't come for some time, though, but Klara keeps waiting. She even avoids getting picked by some other teenager, and it makes the manager upset. The manager reminds Klara that it's up to the teenager to pick an AF, not the other way around, and that children make all sorts of promises, but more often than not they don't keep them. Nevertheless, the girl comes back with her mother and picks Klara. Before they leave, the mother tests Klara's ability to notice things about Josie and imitate her. It's mentioned that Klara's exceptionally perceptive. Josie promises Klara a view from her window to the sunset and taking care of her, but warns her that sometimes she's not herself. Klara doesn't mind, and they leave. Klara now lives with Josie, Mother and housekeeper Melania. She goes outside for the first time and meets Josie's friend, Rick, who's a teenager around her age, who likes playing with his drones. Rick lives in the only neighboring house with his mother. It is mentioned that Rick, unlike many (most?) other teenagers is not "lifted". The meaning of it is not explained, but it's implied that it makes Rick somewhat inferior. Otherwise, Rick seems to be an intelligent teenager. Rick and Josie have some "plan" for their future, which probably implies building their lives together somehow. A meeting is setup by Josie's mother to socialize with some teenagers. Rick is invited too, but it is generally considered strange because he is not lifted. Klara attends too, and other teenagers are being somewhat mean to her due to Klara's reluctance to interact with them without explicit approval by Josie. Josie meanwhile acts distant and is being mean to Klara too, saying that perhaps she should've gotten a different AF model. Rick doesn't like her tendency to act differently in presence of some people. Josie turns out to be sick and she's getting weaker. It's mentioned that she had a sister who died, but Josie says it was different. The family was arranging a trip to waterfalls, but it doesn't happen due to Josie's weakness. Instead, Mother goes together with Klara, and opens up about her fears for Josie, and asks Klara to pretend to be Josie, which Klara supposedly does very well. While Josie's getting worse and everyone is afraid for her, Klara decides to act by asking Sun's help. With Rick's help, she goes to a barn where she expects the Sun to go down, and makes a "pact" with it that it will send that special nutrition to Josie as it did for the homeless man and his dog, and it return Klara will destroy a machine that pollutes the air in the city. Rick wants to attend a university, but it is very hard to do because he is not "lifted" - there are very few universities that would even accept his application. Rick doesn't even want to try, but his mother asks Klara to help him. Klara, Josie, Mother, Father, Rick and Rick's mother go to a city. Rick's family's agenda is to meet his mother's old lover and ask him a favor in helping Rick to get into a university. He's impressed with Rick, but angry with Rick's mother. Rick eventually declines any help from him. It is revealed that "lifting" means genetically enhancing. Josie, Klara, Mother and Father meet someone who makes a "portrait" of Josie. It is revealed to Klara that the portrait is an AF looking like Josie, and Josie is supposed to "fill" it and act like Josie if she dies. They tried doing the same in the past for Josie's sister, but it didn't work out. They expect it to work out better this time because Klara imitates Josie perfectly. Father confronts the "artist" - the artist believes there's nothing in human beings that can't be copied, but Father believes that there is. He later confesses that he's not so sure anymore. With Father's help, Klara destroys the pollution machine, sacrificing some liquid she needs to function. It's mentioned that Father lost his job due to being displaced by someone (lifted? robots?) but he's trying to find his peace with it. Josie only gets worse, and Klara makes another attempt to beg Sun for help. She promises the Sun that Klara and Rick love each other and are destined to be together. Eventually, the Sun sends the "special nutrition", and Josie gets better. Not only she gets better, but she also grows up almost immediately. She soon leaves to university leaving Klara behind. Soon Klara ends up in some graveyard for AFs loosing her conscience. There she meets Manager and reckons about her life. ## More Thoughts (Spoilers) Main topics: * Loyalty. * Being left behind. * Not finding one's place in the world. * Loneliness. After learning about the "portrait", I thought "lifting" meant "being transferred to a robot". Still not quite sure about "special nourishment". "Maybe". The structure of the world is revealed gradually and never completely; the same as for all other fantasy-ish works of Ishiguro. But unlike, say, Never Let Me Go, things are revealed somehow more directly and less shockingly. It's funny how robots don't seem very scientifically literate and are religious in their own way. Some readers on Goodreads complain about absence of a plot twist, but it would be a bit strange if there was. I don't think Ishiguro really tried to write Never Let Me Go all over again. Well, at least not exactly. ## Quotes from reviews [As with *Never Let Me Go*, one of the enormous pleasures of *Klara and the Sun* is the way Ishiguro only drip-feeds to the reader hints and suggestions about the shape of this futuristic world, the reasons for its strangeness. We are left to do much of the imagining ourselves, and this makes the novel a satisfyingly collaborative read.](https://www.theguardian.com/books/2021/mar/01/klara-and-the-sun-by-kazuo-ishiguro-review-another-masterpiece) [Most of Ishiguro’s slender books are more complicated than they seem; Klara and the Sun is by contrast more simple than it seems.](https://newrepublic.com/article/161899/kazuo-ishiguro-klara-sun-review-deceptively-simple-story-ai) # The History of My Contemporary/История Моего Современника - Vladimir Korolenko Listened an audio book (in Russian). Finished: 4/7/2021 Rating: 3\* I read it because Yuzefovich (Юзефович) was recommending it all over the place. It's a memoir of his childhood years. It was fun to read at first (I think I liked pretty much every book of this sort), but I got bored near the middle. So, ok overall. Not particularly memorable. # Life at the Speed of Light - Craig Venter Finished: 3/27/2021 Rating: 3-\* Interesting topic, very cool author, but hard to read, hard to make sense. I took away pretty much nothing I think. Ok DNA is the basis of all life, but I knew that already. I should not read any more biology pop-science books, completely useless. # Misery - Stephen King Listed to an audio book. Finished: 3/25/2021. Rating: 4\* Scary and exciting! Overall, I loved it. 5 stars would maybe be too much, but at very least 4. I didn't quite get the ending, but whatever. Deep inside hoped that he would keep her prisoner at the end, but didn't happen unfortunately. It reminded me of The Collector by Fowles. It was great too. The villain was terrifying. So much more interesting than the hero. # And Then There Were None - Agatha Christie Finished: 3/28/2021 Rating: 5\* Awesome! Loved it! Spoilers below. I was thinking, throughout the book: * The Rogers (servants) because I thought the murderer had to arrive early to prepare. * Dr Armstrong because it would be convenient for him, and there was nothing written from his point of view. * I figured that someone "dead" was not really dead somehow, but couldn't think of how. The only one I thought of was Mrs Rogers. * I figured the judge's death was strange: not only he was killed when everyone but him rushed away from the room, but someone also bothered to put a wig and stuff on him - I didn't think it made sense. But it did not occur that he could be conspiring with the doctor. Next time I read a mystery novel like this, I should do it very slowly, and actually try to solve it myself. All and all, as good as of a mystery as it gets. # A Kim Jong-Il Production - Paul Fischer Listed an audio book. Finished: 3/20/2021 Rating: 5\* Fascinating reading. The story is exciting, the topic is interesting, the delivery is great. I don't know how precise everything is and how much is fictionalized, but supposedly it's rather accurate. It's terrifying how Shim could just die in prison and no one would even know what happened to him. I wonder if I should've read the original story published by Shim and Choi instead. Learned: * Kim Jong Il went by Yura for a long time! I knew he way Yuri in his birth certificate, but not this. * Kim Jong Il wasn't supposed to be the leader from the beginning. It's unfortunate that Kim Jong Il lived happily ever after. # Cooking Favorite sites: * * (in Russian) General advice: * Fry tomatoes longer to extract more juice from them. * Use mustard to fake "smokiness". * Don't attempt to parallelize recipes you've never cooked before. Spices: * Turmeric (Russian - Kurkuma) * Makes things yellow. * Some aroma. * Cumin (Russian - Zira). * Makes things taste "Indian". * Black pepper. * Adds some spiciness. * Paprica. * Adds some spiciness. * Looks nice. Red. # Marinated Mushrooms * 1 box of cremini/white mushrooms * 1/4 cup oil * 1/3 cup white vinegar * \~ 1/6 big red onion, cut in rings * salt * oregano * black pepper No need to cook mushrooms or onions. Just mix it all in a bowl and refrigerate for 12+ hours before serving. Notes: * It's all about the vinegar. * Any onion tastes the same in this recipe, but red onions just look better. * With this vinegar/oil proportion, it'll taste exactly the same no matter what mushrooms/vegetables/whatever you put there. To make the mushroom/whatever taste more distinct, substitute some of the vinegar with water. * You can add minced garlic. You need a lot of it for it to make difference (7+ cloves). # Pea Soup Based on * Peas: 500g * Water: 1,8 l * Potatoes: 3 medium * Carrot: 1/2 big * Onion: 1 small * Garlic: 3 cloves * Mustard: 2 tsp * Salt, pepper... * Serve with scallion. Cook onion and carrot a little. Boil peas for 45 minutes, then added everything, cook for 20 more minutes. Mustard brings it to life. # Fried Potato Ingredients: * Potatoes - 4-5. * Onion - 1 small. * Preheat oil. * Add chopped potatoes. * Mix every 4-5 minutes. * After \~10 minutes add chopped onion and salt. * Cook for \~10 more minutes. Tips: * Don't put the lid on. With the lid on you are boiling it, not frying. * Put a lot of oil! * High heat! * Don't mix too often! Every 4-5 minutes at most. * Don't put too much on the skillet. Only enough to cover it + a bit more. * Need to dice potatoes as uniformly as possible. * Goes great with [Chimichurri](/cooking/chimichurri)! * Goes great with the [Komendantsy Sauce](/cooking/mayo-based-sauce). # Chimichurri Based on * 1/2 bunch of cilantro * 1/2 bunch of parsley * 1 tbsp sugar * 1 Avocado * 1 Lime * 2 small Serrano peppers * 5 cloves garlic * Salt * Water Mix all this in food processor. * Best when chunky. * It's essential to dissolve the sugar in water before adding it. # Komendantsky Sauce * Mayo (TODO: amount) * Pickle: 1 small, finely diced * Garlic: 2 cloves, finely diced * Dill: 1 stem with branches, with one branch removed, finely diced * Lemon: 1/4, juiced And mix it all together. I love it. Turns out, it's basically tar-tar. Who knew. # Spicy mushroom marinara Strong stuff. * 1 small onion * 4 garlic cloves * 1/2 box white mushrooms * tomato paste, 150g * \~8 slices of jalapeno, chopped * dry oregano * dry basil * dry black pepper * olives - \~10 * penne, \~300g. * 1/2 lemon, juiced * water: 1/3 cup * Boil penne separately. * For the sauce: * Fry onions until golden. * Add everything else. * Cook a little. Tips: * Don't salt the sauce. It will be salty already. # Bruschetta Based on For the tomatoes * 4 tbsp. extra-virgin olive oil * 2 cloves garlic, thinly sliced * 4 large tomatoes, diced * dried basil, a lot * would've used fresh if I had it * 2 tbsp. balsamic vinegar * 1 tsp. salt * black pepper, some For the bread * 1 small baguette, thinly sliced * Extra-virgin olive oil, for brushing * 2 cloves garlic, halved Cook garlic a little on oil. Then mix everything in a bowl (including the oil!), let it stand for 30 minutes. "Brushed" bread with olive oil. Baked on 200 deg for 12 minutes, flipping in the middle. Then brushed with garlic. Serve on the bread. # Solyanka with Mushrooms Based on * White mushrooms - 400g box * Onion - 1 * Carrot - 1 (?) * Tomato paste - 2 tbsp * Flour - 1 tbsp * Pickles - 4 small * Olives - \~200g * Salt * Black pepper * Water - \~2l * Green onion * Parsley * Lemon, a little Mushrooms: * Cut * Cook for \~6 minutes * Set aside Main: * Cook onion \~2 min * Add carrot, cook for \~3 more minutes * Add mushrooms, cook for \~6 minutes * Add tomato paste, flour, a bit of water, cook \~2 minutes * Add pickles, cook 5 minutes * Add olives, boiling water, salt, pepper. Cook \~10 minutes. * Done! Serve with onion, parsley, slice of lemon. # Tofu Scramble * Spicy tofu - 1 box * Turmeric (kurkuma) - 1/4 tsp * Tomato - 2 big * Onion - 1 small * Salt * Green onion, 2 big stems. Fry onions, then add tomatoes, then break and add tofu. Tips: * Fry tomatoes for some time to extract the juice. * It's easier to break tofu with hands than with fork or something. * Salt the tomatoes before frying. It makes them juicier. # Bean Spaghetti * Spaghetti - 1/2 pack * Black beans - 220g can * Onion - 1 small * Garlic - 4 cloves * Fresh tomato - 1 big * Jalapeno - 3 slices * Salt * Olive - 4 Onion and garlic, then tomatoes, olives and jalapeno for 5-10 minutes, then beans and salt. # Salsa * 4 medium tomatoes * 1 big clove garlic * 1/2 small onion - I put 1 * cilantro - small bunch, \~10 stems * \~4 slices of jalapeno * 1/2 big lemon - juiced * some salt # Baked Mushrooms Baked mushrooms * White mushrooms - 400g box. 10 very big mushrooms * Soy sauce - 3 tbsp * Vinegar - 1 tbsp Marinated the mushrooms for 10-something minutes, then baked for 15 minutes at 200c. 10 more minutes to pre-heat the oven. Not bad! Juicy, salty. # Lentil Soup Lentil soup * 1 medium onion * 2/3 med carrot (ate the rest) * 1 tablespoon tomato paste * 1 teaspoon ground cumin/zira * 1.5l water * 2/3 450g pack of red lentil - a little less than 300ml * 1 small potato * salt * fresh lemon, for serving Fry onion and carrot a little, then add cumin/zira and tomato paste and cook a little more. Then add lentil and potato and simmer for 15 minutes. Salt. Blend. Serve with lemon. # Веганство в Москве ## Не дома ### Веганские и вегетарианские Стоит завести [вегкарту](https://vegcard.com/). Принимается примерно в половине нижеперечисленных. Однозначно рекомендую: * Авокадо (чистые пруды). Самое цивильное из перечисленных. Мое любимое блюдо - борщ с черносливом, но в целом вкусно все. Говорят там лучшие веганские сырники в галактике, но сам не проверял. * Зеленый лис (сухаревская). Сытно, вкусно, дружелюбно. Любимое блюдо - тост с "тунцом". Раньше было доступное обеденное меню, но сейчас отменили и стало дороговато, но все равно хорошо. Вкусные завтраки. * Фалафель Бро (маяковская). В стиле шаурмы. Внутри места почти нет и вообще задерживаться там атмосфера не располагает, но на вынос самое то. Любимое блюдо - итальянский фалафель-ролл. * Джаганнат (я лично был только на проспекте мира, но вообще их много). В стиле столовой. Любимое блюдо - том-ям. Тоже неплохо: * Брокколи (таганская). Там целый фуд-корт, много всего интересного. * Raw to go kitchen (у патриарших). Не путать с депо. * Веганутые (новослободская, фудкорт депо). Довольно вкусно, но неоправдано дорого. Мне не зашло: * Прасад (менделеевская (?)). Не то чтобы плохо, но и не хорошо. * Raw to go (новослободская, фудкорт депо). Не путать с Raw to go kitchen. * Flora no fauna (кузнецкий мост). ### Прочие Во многих чебуречных, вареничных и хинкальных есть соответствующие блюда с грибами или картошкой. При церквях есть лавки с постной выпечной. Во время великого поста почти во всех кафе есть постное меню. ## Дома Я покупаю продукты в вкусвиле и перекрестке. ### Завтрак Купить: * Хумус, идеально с тостом. Хумусы продаются в ассортименте во вкусвиле. * Паштеты, идеально с тостом. Много паштетов в перекрестке. Лучшие - от Casa Kubana. * Фасоль в томатном соусе. Их много разных. Очень сытно. * Фасоль + кукуруза в мексиканском соусе, перекресток. * Арахисовая паста. Приготовить: * [Тофу скрэмбл.](/cooking/tofu-scramble) Обязательно с куркумой. ### Супы * [Гороховый](/cooking/pea-soup). Хозяйке на заметку - пара чайных ложек горчицы на кастрюлю добавят эффект копчености. * [Солянка](/cooking/solyanka-with-mushrooms). * Окрошка. * [Чечевичный](/cooking/lentil-soup). ### Основные блюда Постный майонез слобода - дар божий. Продается в перекрестке. Делает все более вкусным и сытным. Купить: * Вареники во вкусвиле. Приготовить: * [Маринара](/cooking/spicy-mushroom-marinara) * Лапша * Масала * [Жареная картошка](/cooking/fried-potato) ### Прочее * [Маринованые грибы](/cooking/marinated-mushrooms). * [Грибы в духовке](/cooking/baked-mushrooms) * [Брускетта](/cooking/bruschetta) * [Сальса](/cooking/salsa) --- [Next Page](/llms-full.txt/1)