ImprovingPerformanceUsingCaching

"How to prevent doing the same thing twice." or "Look, mummy, it has found the same hardware once again while booting."

Menu

Here are the caching opportunities we've identified so far:

1. Extract and cache unexpanded prefs values
   • Requires: tracking of changes to topics that provide prefs values. Re-parse such topics on change,
   • Requires: simple DB to store the values
   • Integrates closely with the prefs mechanisms, by providing value caches for each level in Gilmar's bitstring.
   • Impact on performance: medium
2. Precompute expanded prefs values. This would differ from the above by actually expanding finalised values that are used in later defs
   • Requires: tracking of changes to topics that provide prefs values, and a clear and unambiguous model of finalisation
   • Requires: simple DB to store the values
   • "Finalisation by implication" - for example TWiki variables whose values come from LocalSite.cfg (e.g. %SYSTEMWEB%)
   • May require: API to trigger dependency changes
   • Impact on performance: low
   • Existing work: PeterThoeny's VarCachePlugin does a limited form of this, and can deliver an excellent performance boosts in the right cases.
3. Baked permissions
   • Requires: tracking of changes to topics that provide permissions values. Re-parse such topics on change.
   • Requires: simple DB plus very fast perl and C-code lookup mechanisms (e.g. will be used by viewfile accelerator, webdav)
   • Requires: API for external agencies (e.g. user mappers) to trigger dependencies
   • May require: tracking of group membership?
   • Already have: implemented in WebDavPlugin (exemplar only, not re-usable)
   • Impact on performance: high
   • Existing work: CrawfordCurrie's WebDavPlugin has such a permissions cache using TDB
4. Pre-compute static template sections
   • Many TMPL:DEFs can be evaluated statically. Even more if integrated with (2).
   • Requires: somewhere (maybe simple DB) to store half-baked templates
   • Not really a cache, more a pre-compilation step
   • already done - there is a patch in Codev written by SvenDowideit - has a surprising side effect of measurably speeding up requests, presumably due to freeing up file cache
   • Impact on performance: low
5. Pre-compute template sections with invariants
   • Some more TMPL:DEFs are invariant in the face of precomputed prefs values (computed in 2)
   • Requires: because it depends on (2), requires changes to topics
   • Would require templates to be reorganised to leverage it effectively
   • Impact on performance: medium
6. Reverse proxy
   • This is Colas' "front end" as we understand it
   • Requires knowledge about relatively static/stable pages per URL, and user type (anonymous, lurkers, contributors)
   • Impact on performance: very high
   • Existing work: ColasNahaboo has an implementation (link?)
7. Pre-render HTML pages
   • The approach taken in TWikiCache
   • Requires: knowledge of changes to topics, knowledge of different users, API for plugin authors to add and fire dependencies based on knowledge within the plugin's domain
   • Impact on performance: very high
   • Existing work: MichaelDaum has an (unpublished) implementation
8. Pre-render page sections
   • Split down pages into sections, pre-render and cache invariant sections.
   • Requires: knowledge of changes to topics, knowledge of different users
   • Impact on performance: high
9. Result sets
   • Cache the results of searches
   • Cache partial results for common TML / combinations of TML
   • Requires: knowledge of changes to topics, knowledge of different users
   • Impact on performance: very high
10. Content indexing for fast querying
    • Transparent mirroring between twiki store and a real database; delegate search/index intensive operations to database engine
    • Requires: dynamic database scheme based on changes in TWikiForms
    • Interacts with TOM, Result sets
    • Impact on performance: very high
    • Existing work: CrawfordCurrie and MichaelDaum worked together on the DBCacheContrib (and friends), SvenDowideit has built QnD query search backend to use kinosearch
11. Topic Object Model (TOM)
    • Cache deconstruction of topics into meaningful pieces, e.g. sections, tables, thus getting away with siloed "island parsers", e.g. TablePlugin EditTablePlugin, SpreadsheetPlugin
    • Impact on performance: high
12. Content indexing for full-text search
    • aka: TWiki integration into Enterprise Search products
    • Use something like KinoSearch to index topic content for text searches
    • Requires: integration with third party search engines, capable to read all sorts of document types, capable of interfacing different content repositories, capable of natural language processing (stemming, tagging, etc), as well as proximity search, phrase search and ordering of search results according to relevance;
    • Interacts with Result sets
    • Impact on performance: medium (or very high, when used as the engine for query search (Which Sven is doing))

Discussion

the discussion started in ThinPrefs before moving here, which is why it seems to start mid-stream...

The real motivation here appears to be to make it easier to cache prefs values; excellent, I agree, this is overdue. Once you a better architecture for prefs cacheing, the issue becomes one of how you efficiently manage, and detect updates to, that cache. It always struck me as slightly crazy to implement such a cache separately from a topic cache (a cache that stores partially or totally rendered copies of topics) and a permissions cache (permissions are also read from topics, using a subtly different mechanism to preferences). So, what is the strategy for these other cache requirements? While I welcome initiatives that step closer to such a solution, I'm wary of changes that don't explicitly take it into account.

MichaelDaum has done a lot of existing work on caching topics, as so has ColasNahaboo. I did a lot of work on cacheing form fields, which was also improved on by Michael. I also implemented a fast (C-code) permissions cache. SvenDowideit has also implemented a DBMS-based TWiki store that has related attributes. Gilmar, perhaps it's time you put your leadership hat on, and formed a task-team to integrate all this learning?

-- CrawfordCurrie - 15 Oct 2008

The primary motivation of this proposal was reduction of the memory footprint, i.e. in perl-persistent execution modes. Caching prefs for speed was an extra burdon we raised

Caching rendered topics, i.e. html, is not necessarily connected to storing TWiki's preferences although prefs come from topics. The only similarity is that dependencies of cached objects have to be tracked down. Tracking these dependencies for preference caching is much easier compared to dependencies of generated html output. That's a much more general task with a potentially unknown set of plugins involved, whereas the construction of the pref objects is well defined and deterministic.

Caching in TWiki is done on multiple levels for various objects. Just having one upper level does not mean that lower levels have to be designed the same way. Therefore I see caching preferences as a "closed world" of its own, that is comparably well understood and which only has indirect connections to the other levels above.

-- MichaelDaum - 15 Oct 2008

About the cache problem, I'm in favor of using what already exists: CPAN:Cache::Cache family and related (like CPAN:Cache::FastMmap and CPAN:Cache::Memcached). And I thought about the possibility of adding a cache service to TWiki core (and maybe also to plugins): those objects that need cache would use this and it would be consistent (all TWiki using the same cache back end, that the admin could choose using configure). Probably I'll raise a proposal after one of my next steps: 5. Work on architectural refactoring.

Since a while I'm thinking about an ArchitectureTaskTeam or PerformanceTaskTeam, but I didn't initialize it yet because I don't like to make proposals when I'm not sure if I'll have conditions to make them reality. Currently I work on TWiki in my spare time and I don't have much of it (I waste about a total of 2.5 hours a day going to and coming from work). And I also share my spare time with my family, girlfriend, friends, other studies... Personally I'd like to have points 1 and 2 of my personal road map completely finished at least two or three months ago, but I couldn't

-- GilmarSantosJr - 15 Oct 2008

I've already done a cache service impl for TWiki, discussed in TWikiCache. I will check that in to TRUNK as soon as the TWiki trademark question is resolved.

I've been experimenting with different Cache::Cache backends for quite some time. Most of them are only of academic value. The only two interesting are Cache::FileCache and Cache::Memcached. I also did a memory LRU implementation, but only for testing purposes and benchmark comparisons. Cache::FastMmap is no option as far as I can say. There are alternative backends for Memcachd, i.e. Memcachdb that are backed up by a db for those buckets that are displaced from the memory. That's interesting for those cases where you really want longer caching not depending on a fixed cache size like Memcached offers. On top of that cache service a PageCache has been implemented. Together with your FastCGI backend, things are really fast already. However all this does not help on a cold cache: the first hit on twiki is still too expensive. The current PageCache impl hooks in inside View, which means it needs a completely initialized TWiki object including the gros of delegating objects, like the prefs cache. This means that currently even when on a cache hit, prefs are parsed in completely, which is bad. That's why I am interested in ThinPrefs as well.

-- MichaelDaum - 15 Oct 2008

Michael, I dislike code duplication, so I see dependency tracking as something that should be done once-only. If you can abstract the dependency tracking out from the cache management, then it can be used for Prefs (and perms) and I'm happy. Yes, there are different triggers, but the general concept of a dependency tree is common to a lot of cache requirements.

TWiki servers typically have a lot of slack time. It would be good if that slack time could be detected and used for pre-cacheing, to help the cold-cache problem.

Gilmar, I understand the constraints you face. I'm most impressed with the work you have done in the little time you have had available. But everyone else is in the same position, including current and potential task-team leaders. Don't let lack of time stop you! Form the team, and see what happens.

BTW yes, memory footprint of the loaded files is an important factor; possibly the most important.

-- CrawfordCurrie - 15 Oct 2008

Crawford, I am really not sure if these two kinds of dependency tracking have anything in common. Just imagine on which factors one preference value depends on, including finalization, web structure etc. It seems that these factors are much more finegrained and "application specific" compared to what the current dependency tracking of the PageCache does (which is collecting all raw file access). There's barely code to share and I prefer not to add a bogus abstraction layer.

-- MichaelDaum - 15 Oct 2008

On cache, I would separate the efforts between "source" cache (aka backend), where you kind of precompute "raw materials" of the data sources into ready-to consume data (analogy: standardized auto parts) for the TWiki logic (the car manufactury, the assembly line), and the "rendering" final cache (the car dealer). Both efforts will need some kind of common API to signal that something gets invalidated (dirty), but I have now the feeling that the 2 efforts are different.

• backoffice cache needs to have fine grained causality to track dependencies. It is more a database / data structure mindset, and can afford to take the time to be smart to avoid computations as much as possible, as it is often in the inner loop of computations
• frontoffice needs low overhead & speed, with a granularity based on user-level urls. it is more a web architecture mindset: using lightttpd to serve cache, serving files from another server, etc... tweaking the URLs to enable the most cacheability. It does not need to be smart. just fast and light on ressources.

I do think we should have 2 cache efforts based on these directions, and that one cache cannot fit all. If you look at other CMSes, they have distinct caches. Deki has many. I will try to write a in depth article on what I learned working on the rendering cache, mostly it provides you a kind of "firewall" that shields you from a whole class of performance problems, that the "backend" cache should concentrate on. I also think that the rendering cache is not needed for protected wikis, where the lower hits per seconds make the backend cache quite sufficient

I realize I am not making me very clear, but just trust me: forget the rendering cache issue for now. The unification effort should be on the backend cache(s).

-- ColasNahaboo - 15 Oct 2008

I don't really understand what "front end" cacheing is, in this context, but i think i get what you are driving at. It can be hard to get your head round all the cacheing options. To try to clarify, let's just review some opportunities and try to understand the requirements a bit better. I've made some rough guesses regarding where the greatest value for performance improvement comes from:

big list refactored up to the top of the topic

Oh look; almost everything needs to know about changes to topics. Surely we can leverage the same cache technology for all listeners to topic changes?

(Please hack / add to the descriptions above if you find them useful)

-- CrawfordCurrie - 16 Oct 2008

Please have a look at multitier architectures. Let's classify the different technologies to indicate on which tier they are located.

In Colas' work and similarly in 3rd party reverse proxies (valgrind squid), the caching effects are achieved by delaying content changes. Restrictions are: Urls are mapped to HTML pages. You will have to tinker with url params to encode more knowledge that is otherwise stored in session context. Purging is done on a per url base.

The approach in TWikiCache is different as it leverages knowledge about all ingredients of a single HTML page and recursively fires dependencies to immediately purge those cache entries that are affected. The design criterion here is 100% cache correctness (no delayed content).

Deki, for instance, does only cache pages for anonymous users there. That's because as soon as you log in, TWikiApplications might behave quite differently based on your access rights. While TWikiCache on the contrary is located on the third tier, sitting on top of the rendering loop. That's also the tier where partial pages can be cached.

There are a series of independent caching areas in the various subsystems of TWiki, all of which can be called a fourth tier. These are: prefs, users, group membership, perms, sort of information.

But we also have caching that happens further down, basically inside the storage engine itself like pre-parsed queries. This is technology part of a database engine itself, but makes also sense inside TWiki (IF, SEARCH). That's where result sets are located. Result sets in themselves need to be cached for a certain period of time. Result sets and their respective queries might need a way of chaining. There are dependencies propagated forward in a chain.

The most important cache, as far as I can see, will be a topic text cache, mirroring the TXT files into a database store. That's a technique that has been prototyped in DBCacheContrib and related plugins already, but is missing the real database connection at the back, the reason why this technology has a scalability problem. This problem will be gone once the TXT files are cached in a real database backend. This cache is actually the lowest level within that architecture as far as we are concerned here, leaving operating system related caching for now but which also play an important factor. OS level caching is not within the scope of TWiki as a software project.

Changes of topics is the key event for most caching modules, except probably the reverse proxy where time is the key event when to purge cached objects automatically. Each cached object comes with an array of dependencies, which are fired as a consequence of an event taking place. Cached objects might establish dependencies on each other within the cache leading to recursive purges. The knowledge about the consequences of an event, be it a topic changed event, a time expired event or a manually triggered event, are always the same: cache objects are purged. Sometimes, a purged object can be recomputed immediately, sometimes this is not feasible and it will be recomputed the next time it is requested in a lazy fashion.

Some of these dependencies are quite static and known in advance. Some of these dependencies cannot be established in advance, and only be tracked while the system processes a request. For instance, that's the difference between dependencies in the prefs cache and the page cache. We know in advance which preferences in a prefs cache have to be purged and then they are recomputed immediately. Not so in a page cache: you only know about all the ingredients that come together for one piece of HTML until you actually rendered it. These dependencies have to be stored explicitly because they are dynamic. Once all dependencies of a cached object are known, traversing them while they fire is comparably trivial.

-- MichaelDaum - 16 Oct 2008

Relative importance of caches kinda depends on how you are using TWiki. From a perspective of site which makes heavy use of searching, then caching topic data in a structured DB for fast generation of result sets, and then caching the results, could be the most important approach, as search time usually far outweighs rendering time. On a site where searching is used relatively rarely, but there is a lot of parameterised content, then rendering caches are the most important.

I'm cautious of assigning functions to layers or tiers. There is no consistent architectural plan to TWiki. The original concept was probably closest to MVC of anything, but really a number of different concepts are all jumbled up, usually justified by performance. IME you can harden the interfaces between layers to create tiers, but there is a penalty (usually performance) in doing that. My personal approach has always been to try and take TWiki in the direction of a SOA in which every component can have a service layer and/or be integrated directly into other services, thus accommodating both thin and thick client models, and both tight and loose integration. If you think this way then you see prefs, permissions, users etc as independent services, and use this model to build a picture of caching needs.

I understand the difference now what Colas means by "front end" and agree it is separate, in terms of requirements, from the other cache opportunities. But I would still argue that there is scope for a common dependency manager service (e.g. based on CPAN:Cache::Cache or CPAN:Cache) for those other opportunities.

Sure, different sites need different architecturing of tiers, including load balancing & caching around TWiki. TWiki itself is a renderer within a multitier architecture, located on tier 3. You won't need that kind of heavy setup for simple sites. On high end sites, you'll mostly locate TWiki on a 3rd tier. This tier in itself should then be redundant with multiple renderers. The other tiers further down are inside one TWiki renderer and play a role once the request got through that far.

-- MichaelDaum - 16 Oct 2008

-- CrawfordCurrie - 16 Oct 2008

Just a quickie: a factor often overlooked is that you should not do the same thing at the same time: avoid having 2 hits triggering building the same ressource at the same time, it is very important to ensure high performance at high loads.

-- ColasNahaboo - 16 Oct 2008

How?

-- CrawfordCurrie - 16 Oct 2008

when you rebuild a cache entry, use a lock to avoid doing it twice. Note that of course, you can decide to build it anyways if the lock is there for too long, and thus add extra checks on cache completion before installng the cached version to take care your lock was not broken, and not override the cached version then. For my cache, this was the main performance gain: it ensures the maximum machines ressources are free to perform the computations in the first place.

Michael, you write "In Colas' work [...] the caching effects are achieved by delaying content changes." No, I can reflect the changes immediately, I can invalidate the whole cache on each change (this is how I run it on my site for instance). And purging is not done per url, it is actually done per user, and globally for the whole site. Basically my cache is much more TWiki-aware than reverse proxies, and always accurate. Sorry if I do not have enough time now to develop, I will detail more tonight

-- ColasNahaboo - 16 Oct 2008

Just to detail what hooks I needed to add in TWiki code for my cache, so that we can shape a future cache API. I have summarized them at http://hg.colas.nahaboo.net/twiki-colas/twpc-needed-patches/rev/042eaabe73ce There are 3 patches:

1. lib/TWiki.pm This one is when we %INCLUDE an external URL. I guess we should have all code introducing a dependency on external events (date, external url, database call, user-specific data, ...) trigger this hook. For me I just decide to put a default expiration date. I use it to set the state of internal TWiki vars to keep tracl on external dependencies.
2. lib/TWiki/Func.pm This is the most important: I need to be warned at the end of saveFile. It triggers me on any change in TWiki data, topics of course but also data files of plugins like when you set tags, vote with the VotePlugin, etc... Anything changing a byte anywhere in the TWiki dir (except logs). It is the dependency on internal events.
3. lib/TWiki/UI/View.pm This one is at the end of successfully rendering a page. It is only needed because my cache is a separate wrapper process (in C), and cannot have access to TWiki pref vars tweaking the cache behavior for this page, you would not need it with a cache system build in TWiki code. But it allows to communicate TWiki vars (especially the ones set in case 1.) to C front ends so, it helps with high performance caches. It also allows me to get the content type of the page (html or rss) for easier processing.

These perl hooks call a minimal TWiki plugin http://hg.colas.nahaboo.net/twiki-colas/twpc/file/f3c8c98bd07e/PublicCachePlugin.pm

-- ColasNahaboo - 16 Oct 2008

• Surely the saveFile listener needs to be much deeper than TWiki::Func? Micha put it right down in TWiki::Store, IIRC. -- CrawfordCurrie - 17 Oct 2008
• Well, yes, but you also must track all saves, even to the working_area. Currently Micha does direct open/flock/seek/print on files there for the VotePlugin, so the API should also provide a declareCacheDirty API for plugin to call after their native file changes calls -- ColasNahaboo - 16 Oct 2008

The API is a fireDependency(web, topic) and a addDependency(web, topic). For instance, the VotePlugin calls fireDependency(web, topic) whenever a new vote has been collected. Thus all cached objects depending on web.topic, where the %VOTE{}% takes place, are purged recursively. There are similar plugins like that reading information from "outside", ie. those not accessible by TWiki::Store. It is then the plugin's responsibility to generate the necessary events and send them to the core by means of fireDependency().

-- MichaelDaum - 17 Oct 2008

I know this comment is a little off the main point of the discussion on this page, but re point #10: "Content indexing for fast querying": the content does not have to be cached in a database to do this. A program like recoll (for example) can index the text files themselves. I should note that recoll does store the index in a database.

-- RandyKramer - 19 Oct 2008

yup, thats why I've been working on integrating KinoSearch as a TWiki SEARCH backend. Its pretty damned fast, but not yet 100% compatible.

-- SvenDowideit - 19 Oct 2008

Good--thanks!

- RandyKramer - 20 Oct 2008

ah, you missed the point on 10. It means caching the form fields etc, a la DBCacheContrib. Though indexing is another valid point (I reworded 10 and added 12).

-- CrawfordCurrie - 20 Oct 2008

Rephrased point 12 to name the baby by its proper name. There are full-text engines that integrate with database products seamlessly. However, these come as a added feature that significantly extend the normal database capabilities. Both have a value in its own, that's why 10 and 12 are distinct wishlist items.

-- MichaelDaum - 20 Oct 2008

Added info from some of the work I've done. I'll updae and commit the tmpl pre-compile work soon-ish.

-- SvenDowideit - 20 Oct 2008

Commenting is disabled while not logged in