markpapadakis

Trinity - depending on the execution mode - is over 100% faster for certain queries compared to Lucene, and Lucene is already very fast. It all comes down to the postings ling codecs, and the iterators design/impl anyway.

1.65ms for what kind of queries? Also, is that 1M blog posts, all weighting 500mb in total size(characters)?

See links about Algolia arch (and other related material) here: https://github.com/phaistos-networks/Trinity/wiki/IR-Search-...

Supporting faced search and other functionality requiring access to per document field-values is just an extension over the core IR functionality.

Tracking (document, field) values can be used for query by range or by geolocation primitives (that's what Lucene does, where it will index that data into a special tree-like structure, and for each query, it will build a custom 'iterator' and use it along with other iterators to match documents), and for static ranking of matched documents.

BTW, Lucene and Algolia are vastly different in terms of the underlying architecture.

I 've watched most of his talks - the ones I could find - and its really such a pleasure to listen to him; he just shows up and rants about all kinds of subjects, without breaking a beat, and rarely if ever following a script or notes he compiled earlier.

I am not sold on the premise of VR myself; nowadays it comes down to novelty byte-sized demos or "games", with the occasional random mainstream game offering "VR support" (whatever that means, which usually doesn't mean much).

There's also the practical issue of strapping yourself to gadgets and wires, and on top of that, this is still expensive. That said though, I trust Carmack, Abrash and other smart folks elsewhere will solve those problems, and wind up building better alternatives and "next gen" killer apps that do justice to the term(VR) will be developed and we 'll all eventually experience it.

Thanks Jonathan. Why did Google chose to build its own proprietary web server? Was there a specific requirement or need that Apache or other alternatives couldn't support? I suspect around that time the first event-based (async I/O /w connection multiplexing) web server was Zeus, which was commercial and likely not worth looking into it and soon thereafter there was Lighting HTTPD or whatever it's called. Did you want to, perhaps, implement your own similar design, optimised for your use cases, without having to say, pay, for Zeus?

It depends on the size and what you are trying to do. For example, lately I 've spent maybe a week studying Lucene, and kept going back to it every other day, because I needed to understand pretty much everything about it, to get ideas for improving Trinity ( https://github.com/phaistos-networks/Trinity ).

Some other codebases are so vast it takes a lot, lot longer to understand them enough to feel 'comfortable' navigating them (e.g the Unreal Engine codebase).

Most codebases however are quite small, and within 1 hour, or a few, you 'll be able to understand where to go to find what you need, which are the primary data structures and functions, etc.

Exactly. This isolation ( though obviously they all make use of many core APIs ) makes it easier to focus on one component at a time. I didn’t like the VFS layer that much ;)

I sleep at around midnight and I wake up at 06:00 every day with no exceptions (e.g weekends or vacations ). I average about 6 hours of sleep. If I sleep for 7 hours I definitely feel better and think “faster” the following day. Sleep is good for you.

I never implied that I studied the Linux kernel codebase insight out -- specifically, I was interested in the networking stack and the VFS layer, and from there I looked into the memory subsystem and certain drivers implementation. I did map the codebase to the extent that I can more less find my way around easily.

Same is true for Chrome. I was interested in the code for the various UI components, but I looked into other bits here and there.

I 've studied most of Postgres, LLVM and Tensorflow codebases - as in, I went through pretty much most if not all files looking for interesting bits (and finding plenty). I guess there's no way to "prove" anything to anyone, but I don't really care or want to do that either -- it's not about bragging rights, if that's what you implied; I just thought I 'd share a list of codebases I came across that I thought were interesting and worth of other people times.

As for my job, and my work, you may want to check out my Github profile (https://github.com/markpapadakis) -- though there's only public stuff there. I guess I like to spend my free time learning instead of say, watching tv or waste time elsewhere:)

For what it’s worth, this is how I usually go about exploring codebases ( I am the author of that blog post ).

I either have something specific in mind that I want to understand, e.g in the case of Seastar, I wanted to understand their reactor design and implementation, so I locate the respective file(s) that implement them and I start from there, and then I just branch out to other files -- I usually keep multiple vim windows open, and I take notes.

When I am not looking for a specific answer, I choose a directory, and then I sort its files by size (e.g ls -lShr *.{h,cpp,hh,cc,java} ). I usually sort by file size in descending order(smallest first), but some times it makes more sense to sort by largest file first, and I start from there. I still map my way around, and if something stands out, I open the respective file in another vim window/tab, and look it up, and then continue with the previous file.

I thought their proprietary Web Server was an Apache for (and maybe still is)?

It's true that different index codecs are being designed with different tradeoffs (index size vs postings lists access time and cost), but the work is very incremental IMHO, no huge advances to speak of. Also, can you talk about the top-k challenges you mentioned? Priority queues are not optimal enough ?

I have some experience in developing IR/search software ( https://github.com/phaistos-networks/Trinity ) and, the way I see it, it all comes down to accepting the following premises:

- It’s all about the relevance models. Specifically, BM25 and TF-IDF which are widely used by e.g Lucene and variants just won’t do. Specifically, they only word for large enough documents anyway.

- Indexing and Search algorithms and practices haven’t changed much in decades (though some novel ideas have been introduced not long ago). Lucene’s index encoding is compact and facilitates fast access, but even compared to the one made available by Google which is arguable simpler in design, doesn’t result in more than around 5% reduction in index size and postings list access time (according to my measurements that is). Posting lists intersections, unions and other such operations implementations are pretty much common across IR systems as well, with little room for improvement.

To get great results, you need really great relevance models(1), a great query rewrite system(2), and, because query rewrites usually expand a query to include multiple disjunctions (OR terms and phrases), your search engine needs to be particularly efficient at handling those(3).

You also need to care for spelling suggestions and personalisation/content biases and factors, but those are secondary concerns.

I thoughts sales people would be the first to go. I mean, they are are often colloquially/affectiohally known as sales droids in the Valley :)

Kissing aside, if you got laws and said laws can be interpreted to the letter I.e deterministically then maybe this is bound to happen sooner rather than later.

When you are desperate, you are acting irrationally and, definitely, absolutely, not thinking long-term, but counting on potential short-gains to survive, and looks like that's Whalmart is doing.

They are doomed, of course, just a matter of how long it will take until they become irrelevant. And it's not like they couldn't study history or didn't have time or money to invest in whatever would have been required to mount a better defence, but in the end, hubris and misplaced confidence is going to claim another foolish company.

"Focus is a matter of deciding what not to do" --John Carmack

I wasn't familiar with this project. Thanks for mentioning it.

Yes, its called Trinity.

FWIW we will likely open source our search engine/IR technology sometime next month (hold up is the documentation and cleaning up some parts of the codebase).

It's written in C++, and the core features are performance, simplicity(operation and extension of functionality) and a sane, simple API (the codebase is quite small as well, at about 14k lines of code).

Its similar in some regards to Lucene, but does away with most of the exotic features and instead is optimised for rich queries support, fast execution and extensibility.

It should be on GH sometime in April.

My theory (everyone has one) is that Tim Cook is excellent at delegating and orchestrating operations, but he lacks the combination of qualities, charisma and personality of Jobs that pushed(forced?) people to go above and beyond and surpass expectations.

Jobs likely had zero tolerance for good enough products. Cook, I presume, would have wanted people to stay that course but looks like that didn’t happen, and he wouldn’t boss them around until it did, because maybe he himself doesn’t know what is great and what isn’t and delegates that to his lieutenants, and because that’s just not who he is and how he treats his people.

Apple execs have to do a lot of soul searching to do and should put their resources to a better use. Invest in quality products(that was their trademark but they kind of lost their way there), invest in ‘cloud’ services and AI/ML because they can’t afford not to, innovate in hardware, and understand that many of their competitors are constantly and consistently out-Apple-ing them so time is ticking.

I don't really get DDG. I guess it's nice that they pattern-match some queries and give you a a query specific UI on top of the results or maybe some results UI that makes a lot of sense for the query -- though Google and Bing do that too, and I don't believe they are hardcoding those rules/patterns like DDG seems to be doing.

I 've given it a few honest tries this year but the results are really not that great, certainly far inferior to Google's or even Bing's, and it 'feels' slow -- but then again, a few dozen ms slower than Google is 'slow' to me (and I am sure the difference is higher than that ).

I suppose the major selling point is that it doesn't track your queries and that's nice and all, but it definitely is not important enough for me to trade that for better results and responsiveness.

I wish them the best though.

That's a good question, and the answer has to do with, obviously, the cost of spawning OS threads/processes, context-switching among them, and how all that affects caches (cache hit/miss ratio dominates most workloads nowadays, more so than actual CPU instructions execution). Context switching can be cost on average 30micros of CPU overhead, but can reach as high as 1500micros. (You can reduce that by pinning threads to core, but the savings will likely get may be as much as 20% - maybe). Thankfully now, at least on Linux, AFAIK, a context switch doesn't result in a TLB flush - back in the day that was quite expensive. Whenever the OS scheduler needs to context switch, it needs to save old state(including regs), and restore another state and perform some other kind of book-keeping. This is more expensive and convoluted than doing it yourself -- you also usually don't need to care for all possible registers, so you can reducing switching costs by e.g not caring about SSE registers. Apps that create too many threads are constantly fighting for CPU time - you will end up wasting a lot of cpu cycles practically cycling between threads.

Another hidden cost that can severely impact server workloads is that, after your thread has been switched out, even if another process becomes runnable, it will need to wait in the kernel's run queue until a CPU core is available for it. Linux kernels are often compiled with HZ=100, which means that processes are given time slices of 10ms. If your thread has been switched out, but becomes runnable almost immediately, and there are 2 thread before your threads before it in the run queue waiting for CPU time, your thread may have to wait upto 20ms in a worse case scenario to get CPU time. Depending on the average length of the run queue (reflected in sys.load average), and how length threads typically run before getting switched out again, this can considerable affect performance.

Also, kernels don't generally do a good job at respecting CPU affinity -- even on an idle system. You can control that yourself.

If you are going to represent ‘jobs’ or tasks as threads, and you need potentially 100s or 1000s of those, it just won’t scale - the overhead is too high.

If you control context-switching on your application (in practice that’s about saving and restoring a few registers) -- cooperative multitasking -- you can have a lot more control on how that works, when its appropriate to switch etc, and the overhead is far lower.

Oh, and on average its 2.5-3x more expensive to context switch when using virtualisation.

This is a C++ coroutines framework( https://github.com/markpapadakis/coros-fibers ), but its trivial to “port” it to C.

I ‘ve also written a few things about coroutines and fibers(e.g https://medium.com/software-development-2/coroutines-and-fib... and https://medium.com/software-development-2/high-performance-s... ).

Coroutines based on stack manipulation(as opposed to simple FSMs) are extremely powerful and are particularly useful for implementing fair scheduling across runnable ‘processes’ and concurrent execution contexts. Fair scheduling in particular can be really important in the domain of distributed systems that need to process potentially long-running and/or expensive request which would otherwise stall processing other cheaper requests indefinitely. Combined with async I/O, this gives near optimal concurrency and resources utilisation. Coroutines are often associated (literally and figuratively) with futures/promises. See SeaStar framework for a great implementation of those ideas.

Thank you - yes, I was planning to base the implementation on etcd's. I appreciate the heads up:)

The consumers applications (which interface with Tank brokers via a Tank client library) are responsible for maintaining the sequence number they are consuming from.

Suppose one such application is consuming every new event that's publishing ("tailing the log"). As soon as another application successfully publishes 1 or more new messages, the consumer will get them immediately. If the application that attempted to publish failed to do so, or didn't get an ACK for success, then you are guaranteed that no new message(s) were published(i.e no partial message content).

I am not sure if that answers your question, if not, can you please elaborate?

The Tank Client will immediately publish to Tank (it doesn't buffer requests). You get at least once semantics /w Tank(exactly once pretty much means at least once but with dupes-detection).

Some benchmarks added https://github.com/phaistos-networks/TANK/blob/master/README.... Will add consumer benchmarks later (our ops folks are on it). Apologies for not backing the "high performance" claim with numbers in the first place.

Yes, single threaded, because the contention to the various files and the cost of serialisation would likely negate the benefits of using multiple threads.

Network I/O is obviously asynchronous - you may want to check the codebase. Disk I/O is synchronous, but: - uses sendfile() and read readahead() to reduce or eliminate the likelihood of blocking reads: see here please https://github.com/phaistos-networks/TANK/issues/14#issuecom...

- AIO is either broken or supported on XFS (depending on kernel release, and also in the past, appending to a file on an XFS fs could block and degrade performance). But not using DirectI/O so writes end up in memory and only get flushed if it hits the commit count, or periodically - so, particularly for local disks, HDDs or SSDs, this in practice never blocks for more than a few ms when flushing, if at all.

I think I, or someone else maybe?, needs to run some benchmarks and produce some meaningful comparison metrics -- as pointed out by commenters here, and elsewhere. I suppose I should have done that already. Apologies for the lack of concrete numbers. There's some information about performance in the Wiki and Issues though.