14 ms·
I almost failed to search a 37 GB text file in under 1 millisecond
- zX41ZdbW 4y agoThese days you can simply load it into a database (ClickHouse) - it will be compressed (about the same as the 7z file), and the search will take 3 ms: https://github.com/ClickHouse/ClickHouse/issues/42363 https://github.com/ClickHouse/ClickHouse/issues/42363
- intelVISA 4y agoLots of great solutions in the in-memory columnar data space, what a time to be alive.
- winrid 4y agoClickhouse is not in memory.
- gkbrk 4y agoClickHouse has a table engine for keeping data in memory. Can be accessed like this create table tableName (.....) Engine = Memory();
- zX41ZdbW 4y agoBut it's not necessary to keep data in Memory, because MergeTree works perfectly. Here is a slide deck showing why MergeTree is faster than in-memory tables: https://presentations.clickhouse.com/meetup53/optimizations/ https://presentations.clickhouse.com/meetup53/optimizations/
- 0b01 4y agoDuckDB is also great for stuff like this. You can replace a MapReduce cluster with a single SQL.
- zX41ZdbW 4y agoI checked DuckDB and your statement appears to be untrue. >>> con.execute("CREATE TABLE passwords (hash TEXT, count INT)") <duckdb.DuckDBPyConnection object at 0x7fc7bceb55f0> >>> con.execute("CREATE INDEX ix_hash ON passwords (hash)") <duckdb.DuckDBPyConnection object at 0x7fc7bceb55f0> >>> con.execute("COPY passwords FROM 'pwned-passwords-sha1-ordered-by-hash-v8.txt' (SEPARATOR ':')") 100% 100% It froze in an attempt to load the data. Nothing happens after it displays 100%.
- zX41ZdbW 4y agoI cannot even ssh into the server after trying to use DuckDB. It is completely dead (with all the ducks, what a misery). The reason is probably that it's using a full index, in contrast with the sparse index in ClickHouse, and maybe it's trying to build it in memory, going to swap (the server has 32 GB memory).
- zX41ZdbW 4y agoInteresting - the database file looks ok, but the data is lost (the table is empty): ubuntu@ip-172-31-3-138:~$ ls -l total 69561648 -rw-rw-r-- 1 ubuntu ubuntu 17631031296 Dec 16 23:57 my-db.duckdb -rw-rw-r-- 1 ubuntu ubuntu 326 Dec 16 23:53 my-db.duckdb.wal -rw-rw-r-- 1 ubuntu ubuntu 16257755606 Jan 21 2022 pwned-passwords-sha1-ordered-by-hash-v8.7z -rw-rw-r-- 1 ubuntu ubuntu 37342268646 Dec 2 2021 pwned-passwords-sha1-ordered-by-hash-v8.txt ubuntu@ip-172-31-3-138:~$ python3 Python 3.10.6 (main, Nov 14 2022, 16:10:14) [GCC 11.3.0] on linux Type "help", "copyright", "credits" or "license" for more information. >>> import duckdb >>> con = duckdb.connect(database='my-db.duckdb') >>> con.execute("SELECT count(*) FROM passwords").fetchall() [(0,)]
- ignoramous 4y ago
- hedora 4y ago“These days”? A 32 bit intel running mysql back in 2000 would probably have laughed at this query. Granted, I’d expect one or two disk seeks, at ~ 10 ms each. I imagine on modern hardware, it would be in the 100’s of usec range. (Assuming you limited it to 2-4 GB of ram).
- Aeolun 4y agoBut the point was to make it take less than 1ms. How would 3ms help?
- danielvf 4y agoIf we are really going all out for performance optimization... In theory, hashes are going to be very evenly distributed. With a file of that size you could probably land within 1% of the correct location just by seeking to byte offset percentage given by the first bytes of the hash... (It's a fun article)
- jffry 4y agoIndeed that's discussed in the article, under "Position heuristic" - https://death.andgravity.com/pwned#position-heuristic https://death.andgravity.com/pwned#position-heuristic
- Mogzol 4y agoThey did mention they tried that, and got similar results to the binary search they were already doing: https://death.andgravity.com/pwned#position-heuristic https://death.andgravity.com/pwned#position-heuristic
- remus 4y agoI assume this doesn't improve perf much because you pretty quickly zoom in on a slice of hashes that are not evenly distributed. 37GB feels like a lot of hashes but it's pretty small compared to the space of all hashes, I suspect this approach would be more effective if we were searching over a much bigger chunk of data.
- throwaway14356 4y agocould one insert empty bytes to make it evenly distributed?
- leni536 4y ago> We can do this once, and then binary search a safety interval around that position. Alas, this only gets rid of the fast jumps at the beginning of the binary search, and for some reason, it ends up being slightly slower than binary search alone. I don't get why you can't do this at each step.
- danbruc 4y agoYou could compute the expected position of the hash in the file as hash / 2^160 * filesize and then just look around in the vicinity of that. Would be interesting to know what the maximum deviation for any hash from its expected position is, then you could maybe just load a single block of that size and search it in memory if the maximum deviation is sufficiently small.
- foota 4y agoThey actually discuss that: https://death.andgravity.com/pwned#position-heuristic https://death.andgravity.com/pwned#position-heuristic
- puffoflogic 4y agoNot very well unfortunately. The author's confusion about how binary search works is preventing progress toward this solution. The idea is to do an "unbalanced" binary search, with the pivot chosen as offset (range size * big-endian value of hash / (maximum possible big-endian value of hash + 1)). Correctness is exactly the same as correctness of binary search, because the correctness of binary search does not depend on the offset of the pivot (so long as it's not zero or past the end). At some heuristic range length, fall back to linear search of the range. (Possibly, at some larger length, fall back to balanced binary search... But with efficient linear search of no more than a couple disk pages, I doubt this would help.)
- bagels 4y agoThis exactly. The author is not describing their approach very well, so I stopped reading because it was frustrating to try to figure out if they tried this solution. The simple statement of the approach is: Use binary search, but instead of using the middle as the pivot, use the estimated position heuristic as the pivot for each iteration.
- matheusmoreira 4y ago> You could compute the expected position of the hash in the file as hash / 2^160 * filesize and then just look around in the vicinity of that. > The idea is to do an "unbalanced" binary search, with the pivot chosen as offset (range size * big-endian value of hash / (maximum possible big-endian value of hash + 1)). Thanks. I thought something along these lines but didn't know how to express or formalize it. Now I must study unbalanced binary search algorithms.
- foota 4y agoI wonder if they could improve this by queueing multiple positions to read at once. Presumably the disk will be able to do some of them more efficiently.
- genericlemon24 4y ago(author here) Hey, that's actually a great idea. I remember reading about a fast grep or wc implementation that did parallel reads. Off the top of my head, I don't really know how to do that (aside from the naive way of using threads), I'm guessing readv[1] might be be useful? Will definitely look into it. [1]: https://linux.die.net/man/2/readv https://linux.die.net/man/2/readv
- mberning 4y agoI am curious how fast you could query this data if it were inserted into a sqlite table with an index on hash.
- genericlemon24 4y agoI actually did try this, but I got impatient and stopped it after 30 minutes or so, and a ~20G database file. For some reason, after that, `ls` in that directory (or even shell completion) would freeze the shell entirely, even after reboot. I eventually managed to delete the file with `rm db.sqlite` (no completion allowed), but even that took like 2 minutes. I might try again with WAL enabled (based on my shell history, I also deleted a -journal file).
- 0b01 4y agoHave you tried DuckDB? It’s the columnar version of SQLite.
- genericlemon24 4y agoNot yet, I might give it a try.
- thewisenerd 4y agoimporting was sooo slow (something I likely messed up trying to make it go faster, was only chugging along at ~100MB/s) SQLite version 3.37.0 2021-12-09 01:34:53 here's the results tho sqlite> create table hashes (hash text, count text); sqlite> pragma cache_size=1000; sqlite> pragma synchronous=off; sqlite> .mode csv sqlite> .separator : sqlite> .timer on sqlite> .import pwned-passwords-sha1-ordered-by-hash-v8.txt hashes sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; ^CRun Time: real 14.841 user 9.370057 sys 2.363629 Error: stepping, interrupted (9) sqlite> create unique index hash_uniq on hashes(hash); Run Time: real 530.029 user 262.952507 sys 213.305437 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.004 user 0.000303 sys 0.000936 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.001 user 0.000310 sys 0.000306 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.000 user 0.000295 sys 0.000305 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.000 user 0.000320 sys 0.000279 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.001 user 0.000322 sys 0.000317 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.001 user 0.000128 sys 0.000155 sqlite> select * from hashes where hash = 'F2B14F68EB995FACB3A1C35287B778D5BD785511'; F2B14F68EB995FACB3A1C35287B778D5BD785511:26437 Run Time: real 0.001 user 0.000145 sys 0.000158
- ohbtvz 4y agoLet me get this straight. OP searched for an entry in a sorted list using dichotomic search. Okay... Any CS undergrad can do that. Is there something that I'm missing?
- dang 4y agoSome important site guidelines, including: "Don't be snarky." "Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something." https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
- civopsec 4y agoIt is famously difficult to implement binary search correctly.
- karmakaze 4y agoHow so, integer overflow? Not so famous that I'm aware.
- mason55 4y ago> Not so famous that I'm aware https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about...
- kragen 4y agoit took about ten years from the time of the first purported publication of a binary search algorithm for a correct algorithm to be published it's an algorithm where it's easy to have off-by-one errors that lead to nontermination or incorrect results for certain inputs integer overflow is also a problem on some platforms, especially java
- ilyt 4y agoI doubt someone spent 10 years trying to implement a binary search. I suspect it is as usual, someone made theoretical invention, then someone else looked at it years later and wrote implementation in evening or two
- divbzero 4y agoOP attempted this using Python. What would be the fastest way using *nix commands? A naive solution would be something like: echo -n password | sha1sum | cut -d ' ' -f 1 | xargs -I hash grep hash pwned.txt
- AceJohnny2 4y agoPerhaps there's a way to insert GNU Parallel in there to do parallel search of different chunks? Or just use ripgrep, which integrates multi-core.
- chkhd 4y agoThat is already doable with xargs itself xargs -P maxprocs Parallel mode: run at most maxprocs invocations of utility at once. If maxprocs is set to 0, xargs will run as many processes as possible.
- giantrobot 4y agoGNU parallel gives you some extra features like a runtime log and resumable operation.
- deleted 4y ago[deleted]
- throwaway14356 4y agoif have 10 computers put every 10th line in its own file, if each file is 1000 lines put line 500 at the start, then line 250, then line 750, then line 125, 375 etc
- saalweachter 4y agoMake sure you put a space at the beginning of your command, so you don't leave your password sitting plaintext in your bash history.
- geniium 4y ago
- kragen 4y agoto not qualify as clickbait the title needs to include the word 'sorted'
- puffoflogic 4y ago> we skip ahead by half the file size, then back, then ahead two times by a quarter. This is not how one does binary search.
- twawaaay 4y agoCan't you just use something like a bloom filter? There is a bit over 1B passwords in there (based on the size of the file and the length of the line). You would need a binary file around 3GB in size that would have to either load into memory or do about 17 accesses to read specific bytes ( no searching) to figure out if the password is in the filter.
- genericlemon24 4y agoYou can, Scott Helme wrote some articles about this (I mention them at the end of my article): * https://scotthelme.co.uk/when-pwned-passwords-bloom/ https://scotthelme.co.uk/when-pwned-passwords-bloom/ * https://scotthelme.co.uk/sketchy-pwned-passwords/ https://scotthelme.co.uk/sketchy-pwned-passwords/ – here he uses a count-min sketch to also store the frequency
- deleted 4y ago[deleted]
- UncleEntity 4y ago> Can't you just use something like a bloom filter? If I had the ability to download a massive file I’d try it out on a hextree I toy around with occasionally. If you’re making an index file may as well just throw it into a tree structure where a lookup is anywhere from 1 to 20 pointer dereferences (assuming the checksum is 20 hex digits) as it optimizes storage so tree depth is variable. Plus it can retain the counts as well. Now I really want to try this out, the last article I read along these lines I used it as a comparison and it was equally as efficient as their conclusion.
- seritools 4y agoSee the bonus chapter in the post (CTRL+F + "bloom" to find it)
- lern_too_spel 4y agoIt doesn't solve the same problem. They want to know if the password is in the file, not if the password could be in the file.
- didip 4y agoIn Unix just split the input text into a smaller chunk and fork a few processes to speed up the processing. If the input file is even larger and you have a lot of RAM, use your favorite programming language and call mmap() syscall.
- deleted 4y ago[deleted]
- orf 4y agoI wonder how long `rg "^000085013a02852372159cb94101b99ccaec59e1" --max-count=1` would take on this?
- mro_name 4y agocreate cdbs https://news.ycombinator.com/item?id=32648589 https://news.ycombinator.com/item?id=32648589
- genericlemon24 4y ago(replying with more details, because I think it's pretty cool, and I'll definitely try this out) The linked item is to https://blog.mro.name/2022/08/pwned-diy/ https://blog.mro.name/2022/08/pwned-diy/, where the author converts the passwords list to a CDB (Constant DataBase) file, a simple, fast lookup database format created by D. J. Bernstein. https://cr.yp.to/cdb.html https://cr.yp.to/cdb.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html https://manpages.ubuntu.com/manpages/bionic/man1/cdb.1.html
- wolfgang42 4y agoHaving recently been digging into the CDB format[1], this was exactly my first thought as well. `tinycdb` is extremely fast at creating an index, and most successful lookups take only two disk seeks (failed lookups need only one), very close to the optimal possible lookup performance on this problem. [1]: https://search.feep.dev/blog/post/2022-12-03-cdb-file-format https://search.feep.dev/blog/post/2022-12-03-cdb-file-format
- ciupicri 4y ago> Positions, lengths, and hash values are 32-bit quantities, stored in little-endian form in 4 bytes. Thus a cdb must fit into 4 gigabytes. Source: https://cr.yp.to/cdb/cdb.txt https://cr.yp.to/cdb/cdb.txt
- mro_name 4y agoYou're a bit hasty, young padawan. Do you insinuate this has never been tried while you don't even take a glimpse at it and see how it's done? What use is it linking the cdb docs? The article has it all in context if you bother reading. The dataset is turned to 16 cdbs to be precise in case you wonder how 37GB fit into the 4GB cdb size limit.
- mhuffman 4y ago
- jiggawatts 4y agoThis problem came up before on Reddit. After a bit of code-golfing style optimisation the general consensus was that for searching for passwords in a file the optimal exact solution (which excludes Bloom filters) was: Compute the SHA1 of each password. Sort. Store in a binary file, so for 'n' passwords the file is '20n' bytes in length exactly. Compute the SHA1 of the candidate password, and use the prefix to guess at the location in the file. Read a block of +/- a few kilobytes around that guessed location. This will have a "hit" about 99% of the time, and at this guess will have to be refined at most 2-3 times. It's possible to precompute the maximum +/- error bounds, and also to produce a tiny (~100KB) second level index that can guarantee a hit in one I/O operation for a lookup. For a file that's bigger than memory, this is absolutely optimal and cannot be improved upon (without sacrificing the exact answers).
- colejohnson66 4y ago> Compute the SHA1 of the candidate password, and use the prefix to guess at the location in the file. Read a block of +/- a few kilobytes around that guessed location. This will have a "hit" about 99% of the time, and at this guess will have to be refined at most 2-3 times. Basically, a binary search?
- contravariant 4y agoMore like the secant method I suppose.
- dellamonica 4y agoI think the basic idea is that the hash has a fairly uniform probability distribution, so knowing the prefix means you can estimate its location in a sorted list. For instance if we were talking about n random sequences of digits then if you want to look for a number starting with 42 then you can start looking at the the 0.42n element and it is likely already very close to a match.
- piyh 4y agoIs a uniform hash the same thing as a consistent hash?
- gigatexal 4y agoThis could be a game changing blog post for self taught devs like me who are just getting into profiling code for improving it and such. I’m still reading it but I’ve already bookmarked it for further study.
- genericlemon24 4y agoGlad to hear that :D One of my main goals was to show the entire progression of how I approached the problem, instead of just saying "here's the final result". I have another article that covers profiling in more detail, you might find it useful: https://death.andgravity.com/fast-conway-cubes#intro-to-profiling https://death.andgravity.com/fast-conway-cubes#intro-to-prof... Note that besides the cProfile text output, there are better, graphical tools for profiling; I've personally used pyflame+flamegraph.pl, and tuna.
- SleepyMyroslav 4y agoI wish that community would put a warning sign or something. The article is a collection of things that should never be done. People who want to learn software performance work need to start from a solid foundation. Mentioning that algorithms exist at the end is not good enough.
- alexiaa 4y agoit's generally a good idea to do echo 3 | sudo tee /proc/sys/vm/drop_caches for benchmarks to avoid disk cache speeding things up, i'm surprised it wasn't mentioned
- arcastroe 4y agoA strategy I haven't seen mentioned is to use the filesystem itself as an index. Directory structure can be used to implement a trie or prefix tree. For example, if you want to look up the existence of a sample hash: `2aae6c35c94fcfb415dbe95f408b9ce91ee846ed` Then simply check for existence of directory <data-root>/2a/ae/6c/35/etc... I was looking at the directory structure of Gitea's Docker Container Registry and this is how they stored container images.
- Dylan16807 4y agoI'm pretty skeptical of the performance of a billion files. I'm sure it will go at okay speed once you actually construct it, since it's basically a tree, but with so many entries I'd expect it to be much less pleasant than a database in many ways. The "preprocessing" is going to be especially awful.
- arcastroe 4y agoThere's probably a large overhead in storage used. It would probably result in much larger overall storage than 37GB. And I agree preprocessing would be painful. But I'm curious on how lookup speeds would compare to the author's 1ms. I'm also curious on how addition of a new hash would compare against adding a new hash to the single sorted file used by the author. Leveraging any database is probably better in any case :)
- Dylan16807 4y agoIf we're running on a SATA SSD, we can probably chain 5 or fewer accesses to the drive before we go over a millisecond. And each directory of depth likely requires 2 accesses. > I'm also curious on how addition of a new hash would compare against adding a new hash to the single sorted file used by the author. In a fair fight with that requirement, the sorted file would be allowed to add a few percent of extra blank entries and then it could insert in a millisecond too.
- Too 4y agoSame strategy as git uses for objects, .git/objects/d6/70460b4b4aetc https://git-scm.com/book/en/v2/Git-Internals-Git-Objects https://git-scm.com/book/en/v2/Git-Internals-Git-Objects
- matheusmoreira 4y ago> Notice we land on the same 7F... prefix twice; this makes sense – we skip ahead by half the file size, then back, then ahead two times by a quarter. How would one fix that?
- arghwhat 4y agoAlmost failing in under 1 millisecond sure is taking fail fast to the extreme...
- fullstackchris 4y agoI wonder what the performance would be if the whole thing was thrown into a postgres instance with a full text index...
- johnklos 4y agoI'm always amazed about how well naive Unix solutions measure up compared to contemporary solutions. For instance, the non-indexed python solution here takes a little more time than the Unix look command (Pi 4): time pwned.sh password 5BAA61E4C9B93F3F0682250B6CF8331B7EE68FD8:9545824 0.053u 0.035s 0:00.40 20.0% 83+22k 35+0io 21pf+0w time python3.10 02-binary-search.py pwned-passwords-sha1-ordered-by-hash-v8.txt password looking for 5baa61e4c9b93f3f0682250b6cf8331b7ee68fd8 pwned! seen 9,545,824 times before in 0.090021 seconds 0.105u 0.013s 0:00.44 25.0% 0+3k 32+0io 4pf+0w Obviously, if you're doing millions of lookups you'll want indexing, but otherwise using built-in tools that have been optimized and refined for decades does very well.
- deleted 4y ago[deleted]
- thdc 4y agoGenerating a trie might be a useful idea here in the allowing preprocessing approach
- segmondy 4y agoHow fast is grep or fastgrep?