DEV Community: Micah Kepe

I Made an Extended Version of vimtutor - Introducing Vimtutor Sequel

Micah Kepe — Sat, 03 Aug 2024 14:12:48 +0000

Hey DEV community,

I'm excited to share something I've been working on - Vimtutor Sequel! 🎉

After going through the original vimtutor, I felt there was a need for an extended tutorial for some more advanced topics not covered in the original tutor program.

What's Vimtutor Sequel?

Vimtutor Sequel picks up where the original vimtutor left off. It’s designed for those who already know the basics and are ready to dive into more advanced Vim features and commands.

Key Features

Advanced Topics: Dive into splits, spellcheck, advanced search and replace, macros, Vim scripting, plugins, sessions, and registers.
Step-by-Step Tutorials: Hands-on lessons that encourage you to practice commands as you learn.
Custom Vim Configuration: Comes with a custom vimrc to ensure a consistent learning experience and mimic the original vimtutor.

How to Install

For Mac

To get started, install Vimtutor Sequel using Homebrew:

brew install vimtutor-sequel

How to Use

To start the Vimtutor Sequel lessons, just run:

vimtutor-sequel

For Windows/Linux

Clone the repository:

git clone https://github.com/micahkepe/vimtutor-sequel.git

Navigate to the repository:

cd vimtutor-sequel

Make a Copy of the Tutorial:

cp vimtutor-sequel.txt vimtutor-sequel-copy.txt

Run Vim with the Custom Configuration:

vim -u vimtutor-sequel.vimrc vimtutor-sequel-copy.txt

Looking for Feedback!

I'd love to hear what you think! Whether you spot any bugs, have suggestions for new lessons, or just want to share your thoughts, your feedback is really appreciated. Feel free to contribute or open issues on the GitHub repo.

Links

Thanks for checking it out, and I hope you find it useful in your Vim journey. Happy Vimming! 🚀

Bloom Filters: Space-Efficient Probabilistic Data Structures

Micah Kepe — Sat, 03 Aug 2024 14:11:19 +0000

In the realm of computer science, efficiency is often the key to solving complex problems. One elegant solution that stands out for its efficiency is the Bloom filter. Despite being relatively lesser-known, Bloom filters offer a powerful method for determining set membership while using minimal space. This post explores what Bloom filters are, how they work, their applications in various fields, and compares them with other data structures.

(Note: this article was originally published in its entirety with the code snippets for the experiments on my blog: check it out here)

What is a Bloom Filter?

A Bloom filter is a probabilistic data structure designed to efficiently test whether an element is a member of a set. It can tell you if an element is definitely not in the set or that it might be in the set. This probabilistic nature makes Bloom filters incredibly space-efficient, but it also means they come with a small chance of false positives.

A Bloom filter consists of:

A bit array of size m (initially all bits are set to 0).
k independent hash functions, each of which maps an element to one of the $m$ array positions.

How Bloom Filters Work

Insertion

To add an element to the Bloom filter, the element is passed through each of the k hash functions, resulting in k array positions. The bits at these positions in the bit array are set to 1. If any of these bits are already set to 1, they remain unchanged.

Querying

To check if an element is in the Bloom filter, the element is hashed using the same k hash functions to find the $k$ array positions. If all the corresponding bits in the bit array are 1, the Bloom filter reports that the element might be in the set. If any of the bits are 0, the element is definitely not in the set.

False Positives

Bloom filters do not store the actual elements, so they can never have false negatives (i.e., reporting an element is not in the set when it actually is). However, they can have false positives (i.e., reporting an element is in the set when it is not). The probability of false positives depends on the size of the bit array m, the number of hash functions $k$, and the number of elements inserted n.

Mathematical Insight

The false positive probability $p$ can be approximated by:

\approx \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k

For practical use, choosing the optimal number of hash functions $k$ and the bit array size $m$ is crucial to minimize the false positive rate.

Comparing a Bloom Filter with a Hash Set in Python

To demonstrate the practical use of Bloom filters, let's consider a mock scenario where a Bloom filter is used to check if a URL is malicious. We will compare Bloom filters and hash sets in terms of space efficiency and the ability to quickly determine if a URL is in the blacklist.

Mock Scenario: Checking Malicious URLs

In this scenario, we simulate a web browser that checks if a URL is malicious using a locally stored Bloom filter or list. The Bloom filter offers a space-efficient solution, reducing the need for frequent network calls.

Bloom Filter: Efficient in terms of space, but can have false positives.
Hash Set: No false positives, but can be memory-intensive.

Setup and Explanation

We will simulate a scenario where we have 1 million URLs in a blacklist and check a large number of URLs to see if they are malicious. This will highlight the space efficiency of Bloom filters compared to hash sets.

Bloom Filter

Here's the results I got when running the Bloom filter simulation:

Bloom Filter Insertion Time: 3.457702159881592 seconds
Bloom Filter Query Time: 0.10877871513366699 seconds
False Positives: 121
Memory Usage: 1.14 MB

Hash Set

Here's the results I got when running the hash set simulation:

Hash Set Insertion Time: 0.6073956489562988 seconds
Hash Set Query Time: 0.03299856185913086 seconds
False Positives: 0
Memory Usage: 30.15 MB

As you can see, the hash set is significantly more memory-intensive compared to the Bloom filter (30.15 MB vs. 1.14 MB). However, it does not have any false positives and is faster in terms of insertion and querying times. But, imagine a scenario where the blacklist is much larger, and the memory usage becomes a critical factor. This is where Bloom filters shine:

Memory Efficiency: Bloom filters use a fixed amount of space regardless of the number of items inserted, making them ideal for applications with limited memory resources.
Scalability: As the size of the data set grows, the memory usage of a hash set grows linearly, whereas a Bloom filter's memory usage remains constant. This makes Bloom filters suitable for very large data sets.
Network Latency: By storing the Bloom filter locally, we can quickly determine if a URL might be malicious without frequent network calls, reducing latency and improving user experience.

Pros and Cons of Bloom Filters

Pros

Space Efficiency: Bloom filters use minimal space compared to other data structures.
Fast Set Membership Tests: Bloom filters offer constant-time set membership tests.
Scalability: The memory usage of a Bloom filter remains constant regardless of the number of elements inserted.
Reduced I/O Operations: Bloom filters can reduce disk reads and network calls by quickly filtering out non-existent elements.

Cons

False Positives: Bloom filters can produce false positives, which may not be acceptable in certain applications.
Optimal Parameters: Choosing the optimal number of hash functions and bit array size is crucial for minimizing false positives.
Limited Applications: Bloom filters are best suited for scenarios where false positives are acceptable and space efficiency is critical.

Real-World Case Studies

Case Study: Using Bloom Filters in Google Bigtable

Google Bigtable, a distributed storage system for managing structured data, uses Bloom filters to reduce disk lookups for non-existent rows or columns. By using Bloom filters, Bigtable can quickly determine if a row or column is absent without accessing the disk, thereby improving read performance significantly. This application of Bloom filters showcases their efficiency in handling large-scale data storage and retrieval systems.

Case Study: Akamai's Content Delivery Network (CDN)

Akamai, one of the largest CDNs in the world, uses Bloom filters to quickly determine if content is cached on their edge servers. By using Bloom filters, Akamai can minimize the number of cache misses and reduce the latency of serving content to users. This helps in delivering content more efficiently and improves the overall performance of the CDN.

Case Study: Medium Duplicate Story Detection

Medium, a popular online publishing platform, uses Bloom filters to detect duplicate stories. When a user submits a new story, Medium checks if the story is a duplicate by querying a Bloom filter that stores the hashes of previously submitted stories. This helps in identifying and preventing the publication of duplicate content, ensuring a better user experience for readers.

Case Study: Bitcoin's SPV Nodes

In Bitcoin, Simplified Payment Verification (SPV) nodes use Bloom filters to track transactions relevant to them without downloading the entire blockchain. By using Bloom filters, SPV nodes can operate more efficiently with limited resources, making it feasible for lightweight clients to participate in the Bitcoin network.

Conclusion

Bloom filters are a prime example of how probabilistic data structures can offer powerful solutions to space and time efficiency challenges. By understanding and implementing Bloom filters, you can enhance the performance of your applications in scenarios where quick set membership tests are critical. Despite their simplicity, Bloom filters have found their way into various sophisticated systems and continue to be a valuable tool in a programmer's toolkit.

References

- Bloom Filters and SPV nodes within the bitcoin blockchain
- Bloom Filter Wikipedia Page
- Cloud Bigtable under the hood: How we improved single-row read throughput by 20-50%
- University of Washington Lecture Slides on Bloom Filter Applications
- Bloom Filters – Introduction and Implementation
- System Design: Bloom Filter
- Bloom Filter Data Structure: Implementation and Application

The Rewarding (Sometimes Painful) Process of Creating a Portfolio Website

Micah Kepe — Tue, 14 May 2024 03:12:44 +0000

Hello, DEV Community! 👋

Nearly a year ago on June 8th, 2023, I made the first commit for the source code for my website. Starting this project was kind of an accident— setting up a GitHub Pages site was exercise that was mentioned in passing in an online course I was taking so I did it without giving much thought to it. I'd never done web development before that point, but as soon as I saw that first extremely basic website go live I was hooked on seeing how far I could take the project.

Getting Started

I did some searching online at other portfolio sites to gain inspiration, taking note of features I loved and those I thought were unnecessary, jotting down notes and ideas for my own site.

Here you can see one of my earliest drafts of the site that I drew roughly in OneNote just to put all my thoughts together of the site I wanted to create:

Being as this was my first real web development project, a large majority of the early work in the project was actually research instead of coding. I familiarized myself with popular frameworks and explored various design patterns and best practices. I eventually settled on using React and NodeJS because the vast amount of online content on these would mean that I would have plenty of resources to utilize if I ever got stuck.

As I delved deeper into the world of web development, I realized that creating a portfolio website was not just about showcasing my projects but also about demonstrating my ability to learn and adapt to new technologies. Each line of code I wrote was a testament to my growing skills and understanding of web development concepts.

Headaches and Successes

The journey of building my portfolio website was not without its challenges. There were moments of frustration when things didn't work as expected, and I found myself stuck debugging for hours on end.

The website felt like a hydra sometimes- I'd cut off the head of one problem only for two more problems to spring up elsewhere:

However, with each challenge I overcame, I grew more confident in my abilities. I learned the importance of breaking down complex problems into smaller, manageable tasks and tackling them one at a time. I also discovered the power of community and reached out for help when needed, whether it was through online forums, developer communities, or seeking guidance from more experienced developers.

One of the recent milestones in my journey was integrating a blog into my portfolio website. I wanted a platform to share my experiences, insights, and tutorials with the developer community. To achieve this, I delved into the world of static site generators, exploring options like Jekyll, Hugo, and Gatsby. After weighing the pros and cons, I ultimately chose to use Zola, a fast and flexible static site generator written in Rust. Integrating Zola into my existing website architecture posed its own set of challenges, but the learning experience was invaluable, and the satisfaction of publishing my first blog post made it all worthwhile.

Lessons Learned

Throughout this journey, I picked up countless valuable lessons- the importance of version control and learning to set up GitHub workflows to streamline my development process to name just a few. I gained a newfound appreciation for the challenges of web development and the hard work that goes into creating seamless user experiences. I also adopted best practices for writing clean, modular, and maintainable code.

Perhaps the most significant lesson was the importance of just diving in and starting. It's easy to get caught up in the planning phase, striving for perfection before writing a single line of code. But the truth is, the best way to learn and grow as a developer is by building projects, making mistakes, and iterating along the way.

Closing Thoughts

Looking back on this journey, I am amazed at how far I have come. What started as an accidental exercise has turned into a passion for web development and a valuable learning experience. Building my portfolio website has not only allowed me to showcase my projects and skills but has also taught me the importance of perseverance, continuous learning, and embracing challenges as opportunities for growth.

I invite you to explore my website and provide your feedback. I would love to hear your thoughts on the design, functionality, and overall user experience:

🌐 Personal Website: https://micahkepe.com
📝 Blog: https://micahkepe.com/blog
💻 GitHub: https://github.com/micahkepe/micahkepe.github.io

To anyone considering building a personal website, my advice is simple: just start. Don't worry about having everything figured out from the beginning. Embrace the journey, learn as you go, and enjoy the rewarding experience of creating something that showcases your skills and growth as a developer.

Best,
Micah Kepe