$ xmodmap - remove Lock = Caps_Lock keycode 0x42 = Tab <hit Ctrl-D now> 

This works till you logout. If it does work, you can make this persistent by adding those two lines to your empty or missing ~/.Xmodmap file:

 remove Lock = Caps_Lock keycode 0x42 = Tab 

If this doesn't work for you, it's possible your window manager doesn't take care of this file, but if you have a way to execute commands at each start of GNOME/KDE/whatever, just add the following command to those run it startup sequence:

 xmodmap ~/.Xmodmap 

by Gabrys

Maintaining Wikidot is a bit more complex, because, files uploaded to sites are located in web, side to side with some static Wikidot php and javascript files. Also for historical reasons, there are web/files--common and web/files--local directories, which maps to /common--* and /local--* URLs and in fact, the files--local is never served directly by the web server (need to check permissions first).

Also some time ago, we made static files versioned, so that we can apply more aggressive HTTP caching to them (reducing average page load time) and still be able to fix bugs on them without waiting a few days till the cache expire. In current model, URL to static file contains version hash, this may be for example: http://static.wikidot.com/v--b44e0ce810ee/common--javascript/WIKIDOT.js (notice the b44e0ce810ee). The whole static.wikidot.com is now hosted on Amazon's CloudFront, which means you get static Wikidot files from a server nearby your location and not always from USA.

This all become quite complicated, so we decided to make things really clear and simple in the source code. The primary rule: make the source code (updatable from git) separate from files uploaded by users and generated by Wikidot. Second rule: make files that are automatically generated during installation (not in the runtime) separate from persistent files (like the uploaded by users) and from source code.

And at the end there needs to be some place for logs and a place for temporary data (we need this to generate some random cool stuff, but after generating them, files are deleted).

So we end up with something like this:

• WIKIDOT_ROOT
  • data/
    • avatars/ — user avatars
    • sites/ — site files (both generated thumbnails and uploaded files)
  • generated/
    • static/ — generated static files. This dir can be server directly by a fast non-PHP webserver for static.wikidot.com in case we don't want CloudFront anymore
  • tmp/ — temporary files including Smarty compiled versions of templates. Content of this dir can be safely removed
  • logs/ — Wikidot logs
  • everything else — comes from git and is unchangeable by application

Application needs write-access to data, tmp and logs. Generated dir needs write access to one installing or upgrading application.

Wikidot persistent data is now ONLY database and data/ directory, so it's easy to backup and restore the application (if you have enough time to make full backup of this).

There is still one exception to this nice schema which is php/db/base directory, which is autogenerated during installation from XML database definition files, but the cleaning is not over, I still work on this.

Nice thing about this work is that it does not need a lot of code changing, because directory paths are usually stored in one (max two) places in application, so this kind of totally reorganizing directory structure does not break things. As such, it is very very worth doing it. In the end we get clean internal structure of files and it's clear which files you can safely remove, which you can restore from git (and thus you can experiment a little on them — in case of crash, just re-download application), which are "state" of the Wikidot and where to look for logs.

This all is also very important, because we aim to make current Wikidot.com source open and as such we want it to be a nice code.

by Gabrys

Wikidot was down for about 12 hours and the time it was down was full of work for us. We got a few things that could be broken starting from recent changes of the Wikidot software, hardware failure, high load-related kernel bugs or limitations to connection number or maximum possible number or file descriptors.

The problem is Wikidot kind of worked, so some people had their sites loading, some other not and getting "500" errors. We didn't want to stop it, but at some point Wikidot was completely unusable. We switched the database to the other machine, but this was not the solution, then we switched all Wikidot traffic to the machine, still no good, we switched the software to some previous version, but this still seemed bad.

Finally we worked out, there was a site, that had so big traffic, that it killed anything else (and itself as well). When we temporarily disabled it, the whole Wikidot started to work nicely again. Then Michał made some improvements for the high traffic site serving and the situation is stable again.

In the middle of everything, we had huge problems with our hosting company and their service called Portable IP addresses. It seems that switching DNS is much more reliable that using Portable IPs that took hours to switch (and were supposed to take seconds to switch)! DNS switching time was 15 minutes.

We learned a lot from the situation. Hardware upgrade postponed from really long time needs to be done quite quickly. We need more servers, to see which element breaks. For example if database server has high load, we know we need to tune database settings. If we have all on one massive server and one brick on it crashes, it usually causes all the server overloaded and this causes other bricks to crash as well, so it's hard too tell what the real problem is.

Another thing is that we see our users want information on what happens. It's bad when Wikidot crashes, but it's even worse, when it crashes and they have no information about this.

So, the next time a similar disaster happens we'll update on each technical detail possible, to let you know, that we know it's broken and we work hard to fix it. Other thing is, we plan having more fail-over servers in case something dies.

Thank you all for using Wikidot, it's a great pleasure working (and fixing things) for you!

by Gabrys

• Syck (native C library bindings to PHP)
• Symphony YAML (pure PHP)
• Spyc (pure PHP again)

This is the comparison.

What the hell is YAML

Have you heard about XML or JSON? YAML is similarly to JSON and XML a way to store (read and write) structured data like arrays (a.k.a. lists), dictionaries (a.k.a. hash maps) and atomic values like strings and numbers. The structures can be nested, to form a definition of near-real-life objects, for example:

 --- Piotr Gabryjeluk: company: Wikidot Inc. university: Nicolaus Copernicus University, Toruń, Poland lives_in: Toruń, Poland hobbies: - basketball - playing the guitar 

Which translates to PHP:

 <?php $data = array('Piotr Gabryjeluk' => array( 'company' => 'Wikidot Inc.', 'university' => 'Nicolaus Copernicus University, Toruń, Poland', 'lives_in' => 'Toruń, Poland', 'hobbies' => array('basketball', 'playing the guitar') )); 

So you see YAML is quite nice even when you need to write it yourself.

YAML has its specification (see http://yaml.org), so once we have standard YAML parser and standard YAML dumper we can send arrays from one machine to another and the result should be the same array as was sent.

PHP

So let's see what are the choices if you want to play with YAML in PHP.

Syck

This is the fastest and the most complete YAML dumper and loader library available. This is binding to C library and this is available in PEAR. It is also available as regular package in Ubuntu repository, so install it by simple:

 aptitude install php5-syck 

In some shared hosting environment this could be a problem, so you need a pure PHP solution.

Spyc

This was the first PHP YAML implementation I saw. It is both dumper and loader and it seemed to work fine, but then I found some bugs, that stopped me from using it as the base and only YAML loader and dumper for Wikidot.

This one has really nice thing, which is nice when you want your users to enter YAML to define things (like we do for forms). It is quite forgiving when it comes to the syntax and ignores things that don't fit and still parses the rest.

Unfortunately as I stated before Spyc dumper so, when you first dump an array and then load it with Spyc you get something different (for example multiple new-lines are treated as one). Not good. Also as a loader it does not fully understand the full YAML specification (which is quite huge BTW).

Symphony YAML

This one is pure-PHP as well, so you don't need special rights, to use it on a PHP-enabled machine.

It's loader does not understand full YAML specification, so for example you can't load documents dumped by Syck. Dumper is good.

Summary

Verdict: loader

Syck is the winner in loading YAML. If you cannot use Syck, use Symphony YAML. If you need to parse user input (which should be human readable/writable similar to YAML), use Spyc.

Actually, this is nice combination for loading:

 <?php try { // if syck is available use it if (extension_loaded('syck')) { return syck_load($string); } // if not, use the symfony YAML parser $yaml = new sfYamlParser(); return $yaml->parse($string); } catch (Exception $e) { // if YAML document is not correct, return Spyc::YAMLLoadString($string); } 

This way, you have the fastest library used if possible, then the best pure-PHP, and if it fails in a way, that document was badly written (by human being for example), you fall-back to Spyc.

Verdict: dumper

In my opinion Symphony YAML dumper is the best from the three in terms of usability, portability and interoperability, because its output can be read by both itself and Spyc.

However, if you dump YAML often, use (hell faster) Syck for both loading and dumping. The generated YAML won't be readable by Symphony YAML or Spyc, but this is because they don't follow the specification (so not Syck's problem in fact).

Also note, that any valid JSON dumper output is readable by standard YAML 1.2 loaders, because JSON is a subset of YAML 1.2. So if using for data exchange (and not for talking to human) any fast JSON dumper can be used.

by Gabrys

Brussels

Last month was full of adventures. It started 1st of July with me going to Brussels meat our friend to talk about wikipedia-like site about art. We're going to help this man build the most complete site about art using Wikidot software!

BTW, this was my first flight in lifetime. Quite a strange feeling, but generally fine.

Forms

I was working on some nice technical and UI improvements to Wikidot, that is crucial for the art site (but really really nice for Wikidot as well, like forms for editing, entering and viewing structured data to wiki pages).

Search issues

That week was also spent on some massive Wikidot.com search engine tweaks. A stupid one-line bug, which was not exporting proper LC_ALL environmental variable in indexing script, caused many sites that used Asian or East-European languages to be not indexed (most notably the great ИСТОРИЈСКА БИБЛИОТЕКА). At first we though that we can re-index the broken sites, but our re-indexing mechanism was way too slow (would last for weeks for all broken sites).

Pieter then challenged me. He said he can index whole Wikidot in 6 hours. I thought it's not even possible, but then I started to work on that and I managed to index the whole Wikidot in less than 2 hours without indexing tags at first. Then with tags, it took 2 hours and 10 minutes or so. That was damn fast!

Inspired by this and an accident of disk full error on /var partition of our webserver (but this is why we keep user-uploaded files and other important things on separate disks), I also rewrote the incremental indexer, to work in similar way to the whole-Wikidot-re-indexer.

search-api reindex

If you care about some technical details:

• all search operations are issued with use of search-api, a separate program that can:
  • re-index whole Wikidot
  • queue indexing page/thread
  • queue deleting page/thread
  • queue re-indexing site
  • flush queue
• search-api is written in Python
• search-api uses PyLucene - a native Java Lucene library binded to CPython objects with PyJCC. Compiled with GNU Java Compiler to native code (like C programs), this binding has improved performance over using Lucene with Sun's Java.
• before rewriting it to only-Python, search-api was written in BASH and was a wrapper to:
  • java -jar searchApiHelper.jar search "phrase-to-search"
  • php search-api-helper.php flush
• search-api also takes care of file locking to assure that
  • only one process tries to modify the index
  • items are added to queue one-after-another
  • when doing some big index modification (read: full re-index) queue is not flushed (so that after the re-index all changes are applied to new index)
  • when flushing queue takes more time, and cron tries to run more flushing processes, they simply end (so only one process flushes the queue at a time)

Union of Rock Festival

Just after week spent in Brussels in nice hotel I went to Węgorzewo, Mazury (Poland biggest lakes distinct) to have fun on rock music festival. Unfortunately, the music level was not very impressive, so I mainly enjoyed the atmosphere on the camping area.

The weather was not great. It was wet everywhere, the ground was covered in 20 centimeters of mud and it was hard to walk around without getting dirty. But during the first day of being there, I learned to do that.

Improved workflow at Wikidot

Some of you noticed, that recently we started to work more efficiently, but this is not quite true. In fact we work as efficiently as before, but we are better organized, and have better priorities on tasks. Also we keep track of what we do, so we can then tell what we've done. So for us, this is a little more work of "documenting" our work (so maybe we work even less efficiently than before?), but for the outside world, we make more noise (in a positive meaning) around that. So basically, people know what we do, what we are going to do, when they can expect changes and most importantly, they understand why some feature request is being postponed. This is (and was) because we have more important things to do, but before they couldn't tell it.

Squark turned into a professional project manager, that manages our time. pieterh decided to talk to the Community and listen to their complaints (he reads or at least skims every post on Community forums). He tells Łukasz what needs to be done, Łukasz knows when we will have time to do this. This way communication inside Wikidot improved. Also we (michal frackowiak and me) no longer look on Community forums (some of you may regret), but this allows us to concentrate on our work.

The work continues

As I mentioned before, we want to introduce a great feature to Wikidot, which is forms. But the implementation now concentrates on the open source version of Wikidot software (once it's ready, working and tested we'll copy the feature to the Wikidot.com service).

aptitude install wikidot

As forms is a huge change, I started to prepare a good ground for it and closed most important bugs in Wikidot open source and I'm about to start making Ubuntu packages for it to allow even-simpler installation on Debian-based systems. Now the installation involves only 6 child-easy steps and in fact can be done by copying&pasting a few commands.

Yesterday's party

Yesterday I went to met some old-school-times friends in the heart of the city. It was meant to be a meeting for "a beer or two" but evolved into beer and dancing till morning. That was first time I get a morning bus (not even the first) to my home just after partying.

It was such a great fun and great folks I met.

Summary

I hope with this long blog post (but divided into friendly sections ;) ) I recompensed long period of not-posting anything here.

by Gabrys

This work was done, because searching the whole Wikidot database was far from being fast. At first we used Google Custom Search Engine to solve the problem, but we wanted to be independent from it. Also we wanted to include search results that are accessible by the person that searches but not by search engines (like private sites).

This worked really good. The only problem was long time spent to display the results. It was like 20 seconds, which was far better than when using previous search, but much worse than Google. This was strange, because from previous tests, we calculated the average search time should be about a second or two.

It started to be clear, when we noticed that only 20-30 searches per day are performed. The index is quite big, and it needs to be cached in RAM to work with sufficient performance.

Today I did more tests under heavy load and it seams Lucene can handle big number of queries. When users search often, the index is partially or even fully cached by the filesystem and searches are really quick!

But our main problem to solve today was slow local search a.k.a. "search this site". Moreover many concurrent queries were degrading database performance (not only for searching), so we decided to enable Lucene for local searches as well.

I must say it works really nice, fast and has a nice set of syntax tricks you can do with it, for example you can search for pages with something in tags. Just search for youtube tags:embed. This would search for pages matching youtube (in tags, title or content) and with embed in tags. If no such pages are found, partial matches are also returned, like: pages matching youtube (but with no embed in tags) or pages with embed in tags, (but not matching youtube).

To sum up, new search is faster, gives more accurate results, saves the database performance (which was the main goal) and allows nicer syntax than the old one.

by Gabrys

At Wikidot we use PHP5 as FastCGI backend to Lighttpd light-and-fast webserver. It works like this:

• there are a few hundreds of php5-cgi processes (name is cgi, but they also support FastCGI mode) running and waiting to be used
• lighttpd (only one needed!) process manages the network connections to all the clients and once the request is ready serves a static file or forwards the request to one of PHP backends processes.

We used to use internal Lighttpd FastCGI process manager, meaning the lighttpd processes actually used to start the PHPs.

Problems

We encountered some known problems of 500 (server side) errors appearing after some random time, especially under a high traffic. The typical message appearing at the Lighttpd's error.log was:

 <some date>: (mod_fastcgi.c.2494) unexpected end-of-file (perhaps the fastcgi process died): pid: ... 

There are plenty of reports on this in both Lighttpd's and PHP's forums, bug trackers and even some blogs.

Workarounds

We managed to write some hacky scripts that detected the situation and restarted the backends when needed. The reaction was so quick, that almost no-one noticed the error, but damn, this is not how WE solve problems.

A blind try

We decided to give spawn-fcgi a shot. What is it? It is a program that spawns FastCGI backends (independently from Lighttpd server). Why trying it? I've read somewhere, that it works more reliably than the internal Lighttpd spawner. What's interesting is that this program comes from lighttpd package, so we're in family anyway. It's mainly intended to run the FastCGI backends from different user than the webserver user or to run them on different machine(s) than the webserver machine. This can be used naturally for some smart load-balancing.

The only problem of this solution we encountered was internal limit of number of processes to spawn by a single process which was 256 (hardcoded, fixed in next versions). But at the same time, we decided to build a few FastCGI bridges (each spawning ~200 PHPs) anyway so that was no longer a problem for us.

What was quite surprising (but honestly, I deeply believed in this), our problems with 500 server errors and PHP disappeared. This configuration works for about 2 weeks now with absolutely no hacky scripts involved and no restarting needed. Cool.

Why I wrote this

I wrote this short note just for the record and to let other people know, that using spawn-fcgi instead of the internal Lighttpd's FastCGI spawner might solve their problems with PHP (FastCGI) and 500 internal server errors.

Hope this helps someone.

by Gabrys

Read more on pymalist page, browse the source on GitHub project page.

by Gabrys

Also we decided to move from managing our code in SVN to Git — more precisely to www.github.com. Our project page at GitHub is the following: http://github.com/gabrys/wikidot. Feel free to just follow it or even fork!

Last times, I made Wikidot insanely easy to install (check out the installation guide). It totally rocks (you can install Wikidot within 10 commands and no file editing).

I want to state, that this post is the last about the Wikidot open source software on this blog, as I'm running a new blog just about the Wikidot software at wikidot.org. This will be more practical to filter the posts and will push some life into that site.

At the end I want to invite you to the Wikidot IRC channel #wikidot at irc.freenode.org. That would be probably the easiest way to contact the Wikidot team without much formalism.

(As many posts here were about Wikidot software, this blog will be less regularly updated, but if really care about Wikidot software news, just follow the new one and you won't be spammed about posts about Python, BASH or other things. I hope that blog-split will really help everyone.)

by Gabrys

 06:00.0 Network controller: Intel Corporation PRO/Wireless 4965 AG or AGN [Kedron] Network Connection (rev 61) 

I had problems since late Hardy or Intrepid, using different kernel from that time with no luck. The worst case was connecting to WPA2 Enterprise (user/password) secured network. In worst subcase, I had the connection for 5-20 minutes and after that the network card or driver hanged and then only computer reboot used to help.

I was used to see iwlist scan errors like "Resource temporarily unavailable" or "Busy". dmesg showed different things on different kernels.

My frustration was great, when the problem started (after some upgrades that meant to improve things) to appear even on unsecured network. The connection was broken and I had to notoriously reconnect with my NetworkManager.

Finally I found a version of kernel that plays well.

It's from jaunty-proposed repository (enable it in your Synaptic or other package manager). Don't use jaunty-backports (this one was only broken). The package that solves things is: linux-backports-modules-jaunty version 2.6.28.12.16. The install should also update the linux-image to 2.6.18-12 (update your grub.conf as usual to include the changes).

After rebooting, run uname, to verify the kernel version:

 # uname -a Linux vaio 2.6.28-12-generic #43-Ubuntu SMP Fri May 1 19:31:32 UTC 2009 x86_64 GNU/Linux 

This is crucial here: 2.6.28-12-generic. The original Ubuntu kernel is 2.6.28-11 not -12.

Hope this helps someone (with VAIO SZ or any other Intel AGN-enabled notebook with Ubuntu).

by Gabrys

The biggest change is Wikidot is now single wiki engine by default (you need additional configuration for the wiki farm mode).

What demonstrates the change is the simplified installation process.

Now it's as simple as installing any other software or service:

1. install the dependencies
   • for Ubuntu: sudo aptitude install lighttpd php5 php5-cli tetex-bin tetex-extra gs-gpl imagemagick libmagic1 subversion postgresql-8.3 php5-tidy php5-pgsql php5-gd zip make
2. get the code
   • svn co http://svn.wikidot.org/repos/wikidot1/trunk/ wikidot-install-dir
   • cd wikidot-install-dir
3. if on Ubuntu: configure conf/wikidot.ini and set user at [db] section to your login name
4. prepare database (create role and database)
   • as user postgres: make prepare_db
5. build Wikidot: configure files and make initial dabatase
   • as you: make
   • this prints a secret URL at the end, you'll use it to configure Admin password
6. start Wikidot
   • ./wikidotctl start
7. set Admin password
   • use your browser and navigate to the secret URL make prints at the end

We would like to finally create Debian/Ubuntu packages for that (once it gets more stable and have some bug fixed). So keep tuned!

by Gabrys

Single wiki mode

The main difference is introducing a new Wikidot installation mode: "sigle wiki mode" and setting it as the default instead of "wiki farm mode".

What does it mean?

• you don't have to bother about:
  • domains (DNS)
  • mail configuration
  • root access (you can start Wikidot on custom port — default 8080)
• you get direct administration panel for managing users

But:

• you get only ONE single wiki
• you cannot create more wikis
• every IP/DNS address pointing to the started server (and corresponding port) displays THE wiki
• no mail invitations or password recovery
• no HTTPS

Lighttpd

Our main webserver is now Lighttpd, we forget about Apache. We can do this, because now you can run your regular Apache server on :80 port and Lighttpd serving Wikidot on :8080 (or other). They don't overlap, so there's no need to keep the compatibility.

Wikidot is a full web service with its dedicated web server running on separate port. This is the philosophy.

Scripts

To make Wikidot easily installable, we're going to create a script (possibly a Makefile) that will simplify the whole process. It would be 4 steps:

• install dependencies
• setup the database
• edit ini file (supply database credentials)
• make

Dependencies are Lighttpd, PHP, PostgreSQL, ImageMagick and maybe a few other things. Each of them can be installed without root access, but with root access it would be just as easy as

• aptitude install lighttpd php5-cgi postgresql-8.3 ImageMagick

(or so)

Running/stopping Wikidot:

• ./wikidotctl start
• ./wikidotctl stop

Next steps

Once all this is done (which isn't too much work BTW), we could make a *.deb package, that would take care of dependencies, database, creating a special user for wikidot, setting the root directory by convention and installing init script in proper place. Then you would just:

• /etc/init.d/wikidot start/stop/restart

This should kill all Wikidot-is-to-hard-to-install issues.

… upgrade to wiki farm

Once you have your single-wiki Wikidot up and running you may want to upgrade to full featured wiki farm solution. The one-wiki would become the main wiki (as is www.wikidot.com for the Wikidot.com service), other wikis would be able to be created. On the other hand, as your getting more powerful, you need to configure your DNS (have a domain-class just for your wiki farm), mail service and move the service to the main HTTP port (80).

The hardest thing

Q: What is the hardest thing to do in that plan?
A: The hardest thing is to create a module to manage wiki users.

This should not be too hard, so in the overall, this should work!

I'm waiting for your opinions.

by Gabrys

But the API is also important, because it can enable developers (which are big fraction of our users) to create applications that use Wikidot.com as a service. This can be useful in many ways, the best example I can think of is creating an application, that get some photos from your disk, uploads them to Wikidot, creates a page for each of them and saves some metadata from them into it.

Today, I finally managed to start working on one of the most important API method which is page.save. This method obviously is for saving a page. The page saving mechanism in Wikidot is quite complex, because of advanced site permissions, various performance optimizations, caches and many scenarios of updating a page.

Also, we wanted to make page.save to be one method to update and create pages, which involves other permission checking, because in some cases you have permission to create a page, but not to edit. This is especially true if you have a site category with everybody-can-create-but-only-author-can-edit policy.

I started from dealing with updating already existing pages, so for now page.save can't yet create pages. We have more or less working page.save for the following activities:

Notes:

• the API service is XML-RPC based, so the syntax of calls is syntax of the programming language you use (Python used as an example syntax)
• site: quake and page: dev:api-save means http://quake.wikidot.com/dev:api-save page
• setting tags as a single string (comma- or space-separated) is also supported
• setting of parent page is also supported in similar way to setting the title

Now we're going to review the code, ensure there is no more caching mechanism I forgot about and make final polishing. This includes generating notifications to be send to page-watchers and saving revision comments.

This method is crucial for the API. Once it gets fully working (including creating pages), applications will be able to:

• create pages
• read pages
• modify pages

and this the core functionality we want to provide with the Wikidot API.

Check out the API methods to see if page.save is already out.

If you want to test the (beta) API, drop a comment at the Wikidot API page.

by Gabrys

I prepared a quick and highly subjective comparison.

First in what ares the two phones are comparable:

• they are phones
• they look and behave similarly (users can easily migrate from one to another)

OK, now what is different:

I just need to say, that developing application for Android is just easy as

• downloading and unpacking SDK (software development kit)
• running Android Debug/Development Bridge from the SDK:

 $ cd SDK $ tools/adb start-server 

• installing an Eclipse plug-in (via the Eclipse update dialog)
• creating virtual Android device (emulator)

 # cd SDK # tools/android create avd -t 1 -n "androidemulator" 

• running emulator

 # cd SDK # tools/emulator -avd "androidemulator" 

• and then, for every application you want to write:
  • creating new Android project with Eclipse
  • developing application in Java and Visual-Editors (mainly for GUI development)
  • testing on emulator (by clicking on Run in Eclipse)

The .apk files (which are fully-enclosed applications) are created automatically. You can then sign them with your key and sell on Android Application Market. This requires you to register for $50. 1/3 of your income is taken by Google.

I really need to say, this impresses me much, because the SDK (including emulator) and Eclipse plug-in are so well integrated, that I didn't need any Android-specific knowledge to start working on Android application. I would really, really like to develop something for iPhone, just for comparison, but I would need to have Mac and then enroll to the developer platform. Also I would need to learn Objective C, a language that is hardly used outside of areas influenced by Apple.

So to cut long story short from the developer point of view it seems that Android is much much better. Also the fact that your application will run on more devices in the future without any modifications is really nice.

by Gabrys

CUDA

Zaczynając od początku czyli od wczoraj: rano działy się niezłe CUDA. Konkretnie, chodzi o technologię firmy nVidia stosowaną w kartach graficznych, która nazywa się CUDA. Ogólny zamysł polega na wykorzystaniu jednostki GPU (procesor karty graficznej) do wykonywania napisanych w języku podobnym do C (i odpowiednio skompilowanych).

Procesory GPU różnią się znacznie od naszych CPU (centralnych procesorów). W procesorze CPU mamy zwykle 1, 2 lub 4 rdzenie. W procesorach graficznych kart nVidii mamy dziesiątki, czy nawet setki multiprocesorów (bliski procesorowi wielordzeniowemu).

Ogólnie, możemy uruchomić około 1000 i więcej "wątków" na jednej karcie graficznej. Daje to spore możliwości wykorzystania takiej architektury w obliczeniach równoległych. Przedtem taka architektura była tylko wykorzystywana przez zamknięte sterowniki karty graficznej w celu renderowania skomplikowanej grafiki 3D w czasie rzeczywistym (i nie tylko). Teraz moc obliczeniowa stoi przed zdolnymi programistami i czeka na wykorzystanie.

Oprócz niewątpliwej zalety jaką jest wysoka współbieżność, mamy również garść bardzo szybkiej pamięci do dyspozycji (tak szybka jak rejestry procesora). Po krótkiej analizie jednak okazało się, że konieczność współdzielenia jej przez wiele wątków redukuje nam średnią ilość tej szybkiej pamięci do kilku bajtów na wątek. Należy więc jednak trochę z tym uważać.

Odwołania do pamięci RAM karty graficznej są wolne, jednak procesor potrafi w czasie "czekania" na dane z RAM-u wykonywać inny wątek. Jest to również stosowane w zwykłych procesorach. Znane jest pod pojęciem wywłaszczenia procesu (np., gdy proces oczekuje na operację I/O na wolnym dysku na jego miejsce "wskakuje" inny proces). Jednak w odróżnieniu od zwykłego procesora, gdzie wywłaszczenie inicjuje system operacyjny, a samo przełączenie kontekstu jest dość kosztowne, w CUDA-ch wywłaszczenie jest częścią logiki realizowanej sprzętowo i jest bardzo bardzo szybkie. Zatem odpowiednio oprogramowując używanie pamięci globalnej, możemy uzyskać wykonywanie programu (złożonego z wielu — np. 256 — wątków) bez przerw w wykorzystywaniu mocy obliczeniowej GPU.

Oprócz zalet mamy oczywiście też wady. Jedną z nich (choć można to uznać za zaletę) jest brak mechanizmów cache'owania i stronicowania, co powoduje konieczność bardzo skrupulatnego zarządzania pamięcią.

Np. na moim laptopie nie udało się uruchomić prawie żadnej przykładowej aplikacji dołączonej do SDK CUDA-ów. Powód: za mało pamięci. Pamięci karty graficznej oczywiście. W przypadku tradycyjnego procesora pamięć zwykle nie stanowi problemu, ponieważ tak naprawdę nigdy nią nie zarządzamy. Jako podstawę mamy pamięć RAM. Gdy komórka pamięci jest często używana trafia (automatycznie) do keszu, który jest dużo szybszy. Z drugiej strony, jeśli pamięci brakuje, następuje przeniesienie nieużywanej pamięci do swapa, czyli na dysk, który z kolei jest bardzo wolny w porównaniu do pamięci RAM.

Efekt jest taki, że programując nie przejmujemy się gdzie będzie przechowywana zmienna. Na start trafia ona do RAM-u, ale może zostać skopiowana do szybkiego kesza, lub przeniesiona na wolny dysk. W CUDA-ch musimy sami zdecydować gdzie będą przechowywane poszczególne zmienne. Problem, który się pojawia, to nieznana ilość dostępnej pamięci. Każda karta ma inną dostępną pamięć każdego rodzaju, co więcej uruchomienie aplikacji graficznych (np. Compiz) zmniejsza ilość dostępnej pamięci.

Są zatem dwa wyjścia — albo programujemy na konkretną kartę grafiki i wymagamy, aby tylko nasz program był na niej uruchomiony (a nie np. jeszcze Quake ;) ), albo inwestujemy w jakiś system zarządzania pamięcią karty graficznej (czyli robimy kawałek systemu operacyjnego, tyle, że na GPU). Oczywiście druga rzecz jest trudna i zmniejsza wydajność całego systemu.

W praktyce pozostaje jeszcze jedno rozwiązanie. Zakupienie karty nVidia SPECJALNIE do obliczeń w technologii CUDA. Firma nVidia nie pozostawia nas w trudnej sytuacji i daje nam do dyspozycji kartę Tesla, która ma ze 4 GB RAM-u, dużo wszystkiego (wątków, multiprocesorów itd), za to w zasadzie ciężko ją nazwać graficzną, bo nie ma wyjścia wideo. Przewrotnie, co?

Android

Następny dzień, następna prezentacja. Dzisiaj dotyczyła ona systemu Android opierającego się na jądrze Linux przystosowanego dla telefonów komórkowych (takich jak HTC G1) i innych małych urządzeń. System, pomimo jądra Linuksa jest czymś zupełnie innym niż znane nam z desktopów Ubuntu, a nawet projekty uruchamiania Linuksa na telefonach (np. OpenMoko). Różnica polega na tym, że warstwa narzędzi GNU (shell, podstawowe programy, zarządzanie użytkownikami) zostaje zastąpiona przez warstwę bibliotek w C i w Javie.

Należy sobie jednak zdać sprawę z tego, że Java w Androidzie, to rzecz nieco inna niż Java używana na PC-tach, czy nawet w komórkach. Androidowa Java ma swoją implementację maszyny wirtualnej. Jest to DalvikVM, zoptymalizowany na maszyny o małej ilości RAM-u (64MB dla całego systemu) i wolnych procesorach (200-500 MHz i ARM). Z tej optymalizacji bierze się inny bytecode, który optymalizuje użycie CPU i RAM. Również w celu zwiększenia wydajności pracy z pakietami zmianie ulega sposób wewnętrznej organizacji pakietu.

Jednak wciąż pozostaje to Java i to dość niedaleko leżąca od tej Sunowej. W praktyce bowiem programowanie wygląda tak:

• programujemy w Javie (jednak mamy do dyspozycji mniej funkcji bibliotecznych)
• kompilujemy programy do bytecodu Sunowego (pliki class)
• tworzymy paczkę JAR
• korzystając z narzędzia dx konwertujemy plik JAR do pliku JAR, który zawiera bytecode przystosowany do maszyny DalvikVM. Otrzymany JAR jest zwykle ponad 2 razy mniejszy!

Poza zmianą formatu bytecode'u, czeka nas również zmiana w działaniu wszystkich istotnych części systemu. Odpowiednie klasy dostarczone w bibliotece Androida pozwalają nam na tworzenie "okien", zadań działających w tle, komunikowanie się z innymi procesami, dostęp do danych zapewnianych przez inne programy (np. książkę adresową), ustawień telefonu i sprzętu. Wszystko to jest opakowane przez zarządcę uprawnień, który przyznaje danej aplikacji prawa do różnych części systemu po uprzednim uzgodnieniu tego z użytkownikiem telefonu ;). W praktyce, wygląda to tak:

• twórca aplikacji definiuje w "opisie" aplikacji (plik AndroidManifest.xml) jakich uprawnień potrzebuje aplikacja (np. uprawnienie do wybierania numeru, uprawnienie do czytania z GPS-u, uprawnienie do uruchamiania aplikacji)
• użytkownik instalując aplikację przyznaje jej uprawnienia, o które aplikacja prosi. W przeciwnym razie instalacja nie dokonuje się
• aplikacja może robić cokolwiek zostało jej dozwolone, każde użycie niedozwolonej funkcji kończy się wyjątkiem

Dostęp do ograniczanych zasobów odbywa się przez specjalne Androidowe API. Dostęp w inny sposób nie jest możliwy, ponieważ każda aplikacja jest uruchamiana z innym numerem użytkownika i w zupełnym odizolowaniu (pewnie coś podobnego do chroota) od innych aplikacji.

Dostępna jest również komunikacja między aplikacjami. Ogólnie mówiąc jest to koncepcja podobna do D-BUS, jednak implementacja jest nieco inna.

Inną ciekawą funkcją aplikacji pracujących w systemie Android jest ich gotowość do bycia zabitym w każdym momencie. Z racji ograniczenia ilości pamięci dostępnej dla systemu i mimo wszystko (pomimo sporego postępu względem Javy Suna) wysokiego zużycia pamięci przez aplikacje Javove, system zawiera mechanizm zabijania procesów w przypadku, gdy zaczyna brakować zasobów (CPU lub RAM).

Każda aplikacja jednak może się przygotować na taką sytuację, ponieważ w momencie przykrycia aplikacji przez inną (kiedy to możliwe jest jej zabicie) wywołana jest metoda onStop (lub onPause w przypadku częściowego zakrycia), która umożliwia zrzut stanu aplikacji do systemowej bazy danych. Gdy użytkownik wraca do aplikacji (pomimo, że została w tle zabita, użytkownik wcale tego nie widzi), system ponownie uruchamia aplikację przywracając jej poprzedni stan. To jak aplikacja chce reprezentować swój stan zależy od samej aplikacji.

Problemem maszyny Dalvik, podobnie jak i maszyny wirtualnej Javy Suna, to długi czas uruchamiania się (mniej niż sekunda na Twoim Pentium4? Aparat G1 jest ~10 razy wolniejszy). DalvikVM na telefonie HTC G1 uruchamia się około 5 sekund. Jest to problem tym bardziej, że każda aplikacja uruchamiana jest w swojej własnej instancji tej maszyny (w celach zapewnienia wymaganej izolacji).

Tutaj do akcji wkracza specjalna usługa systemowa zygote, która jak tylko może przygotowuje proces maszyny wirtualnej Dalvik, który, gdy jest potrzeba zostaje oddany jakiemuś procesowi do natychmiastowego wykorzystania. Przez następne 5 sekund zygote znowu przygotowuje (kolejną) maszynę Dalvik i czeka aż jakiś proces o nią poprosi. Widać, że o ile nie uruchamiamy aplikacji częściej niż co pięć sekund, otrzymujemy złudzenie natychmiastowego uruchamiania aplikacji. Niezły trik.

Widać, że inżynierzy pracujący nad systemem Android stawali na głowie, żeby wszystko było naprawdę dopracowane. Nie inaczej jest z dopieszczeniem programistów. Każdy, kto chce napisać swoją aplikację dla systemu Android może sobie ściągnąć Android-SDK, które zawiera emulator (oparty o QEmu) i narzędzia potrzebne do budowania (dx, apkbuild), i debugowania aplikacji.

Dostępna jest również wtyczka do Eclipse'a o nazwie ADT (Android Developer Toolkit). Pozwala ona stworzyć aplikację dla Androida jednym kliknięciem, zbudować ją drugim, a uruchomić na wcześniej uruchomionym emulatorze trzecim :). Widziałem to w akcji i wygląda to naprawdę bardzo przyjemnie.

Minusem Androida są trudności jakie niesie przeportowanie istniejących nie-androidowych aplikacji:

• aplikacje w C trzeba dolinkować do Google'owego bionic — lekka wersja biblioteki standardowej C — coś w stylu uclibc
• aplikacje w Javie mogą nie działać, bo używają rzeczy niezaimplementowanych w bibliotece Javy Dalvika
• GUI Androida jest zupełnie inne od każdego innego (oparte o pliki XML - zatem może trochę podobne do XUL-a). Zatem GUI w przypadku każdej aplikacji trzeba przepisać

Naturalnym pytaniem, które się rodzi w czasie rozważań nad Androidem jest jego przyszłość. Choćby w porównaniu z iPhonem, którego w pierwszym miesiącu sprzedaży sprzedało się więcej niż wszystkich telefonów z Androidem na pokładzie. Zatem, co może przeważyć szalę zwycięstwa na stronę Androida? iPhone to jeden telefon (no konkretnie to dwa modele) i jeden software (no konkretnie to chyba trzy wersje). Android to otwarta platforma, która będzie stosowana nie tylko w telefonach firmowanych przez Google (póki co HTC G1 i G2), ale również przez inne telefony, takie jak FreeRunner (port i to całkiem dobrze działąjący na to urządzenie już dawno dostępny).

Czołowi producenci tacy jak Samsung, czy Motorola planują wprowadzić do swojej oferty po 2-3 modele z Androidem. Do tego dochodzą netbooki, samochody (ktoś już portuje Androida na samochód), również odtwarzacze MP3, a być może i komputery stacjonarne. Możliwość uruchomienia aplikacji Androidowej na komputerze pracującym pod kontrolą Linuksa byłaby bardzo miła (zwłaszcza, że nie ma żadnych technicznych przeszkód). No i najważniejsze, ogromny wkład w rozwój Androida na platformach innych niż wspierane komercyjnie ma rosnąca społeczność deweloperów i testerów.

Wiwat społeczność!

Podsumowanie

Ostatnie dwa dni w moim życiu pozwoliły na poszerzenie mojej wiedzy na temat technologii, które mogą w ciągu najbliższych 2 lat odmienić życie ludzi na naszej planecie. Oczywiście może się tak nie stać, ale samo poznawanie rzeczy, o których można powiedzieć "dobrze przemyślane, dopracowane, świeże, potrzebne i pomysłowe" przyprawia mnie o dreszczyk emocji.

Muszę powiedzieć, że choć początkowo byłem sceptyczny wobec Androida, myślę teraz, że ma spore szanse za szybki rozwój i wielki (również komercyjny) sukces. Jak pamiętamy na samym spodzie architektury, zaraz nad sprzętem znajduje się jądro Linuksa. Niektóre jego modyfikacje dokonane na potrzeby telefonu trafiły do głównej (lub testowej) gałęzi kernela, co świadczy o dobrej jakości tych zmian.

Pokazuje również, że praca nad tym systemem powoduje również szereg innych pożytecznych (choć pobocznych) zjawisk, co jest oczywiście bardzo budujące (i zupełnie nie występuje w przypadku zamkniętego oprogramowania).

Stop Cenzurze

Cały entuzjazm i moją ogólną radość mącą plany UE dotyczące ograniczenia dostępu do Internetu przez zmianę rozporządzeń europejskich, które są lobbowane przez duże firmy telekomunikacyjne, które prawdopodobnie mogą zwiększyć w ten sposób swoje zyski ze świadczenia usług internetowych i wykończyć małych providerów. Już raz Unia Europejska pokazała, że w sprawie informatycznej niezależności, potrafi się zachować w sposób rozsądny odrzucając propozycję wprowadzenia patentów na oprogramowanie. Miejmy nadzieję, że i tym razem nie zostanie ograniczona konkurencja w tym sektorze i kontrowersyjne rozwiązanie zostanie wyśmiane i zapomniane.

O szczegółach można przeczytać na specjalnej stronie poświęconej temu zagadnieniu: http://stopcenzurze.wikidot.com/ . Można tam również okazać swoje poparcie dla akcji przez wirtualne podpisanie petycji.

by Gabrys

Historia

Kiedyś nie było kart. Przeglądarki miały swoje okno, w którym wyświetlały jedną stronę. Jeśli chciałeś otworzyć dwie strony, musiałeś otworzyć dwie przeglądarki. (Nie będę się zagłębiał w różnice pomiędzy dwoma oknami przeglądarki, a dwoma przeglądarkami.)

Miało to swoje plusy. Można było otworzyć sobie dwie strony "side by side", czyli jedna obok drugiej i np. porównywać dwa teksty.

Potem, pewnego magicznego dnia, pojawiła się przeglądarka, która otwierała strony w tabach! Zaraz pod wszystkimi paskami narzędziowymi, a nad wyrenderowaną treścią strony pojawił się (czasami znikający) pasek tabów. Niczym klon paska okienek z systemu okienkowego, pokazywał otworzone w przeglądarce strony, pomiędzy którymi można się przełączać.

Technologia wnosi takie ciekawe i ważne opcje jak:

• otwieranie linków w nowym tabie zamiast w nowym oknie
• otwieranie nowych tabów w tle — niech się załadują, zanim skończę czytać aktualną stronę — bardzo sprytne i przydatne
• minimalizuje chaos na pasku zadań — po co osobny kwadracik dla każdej otworzonej strony

Teraźniejszość

Każda ważna przeglądarka posiada taby. Nawet Internet Explorer w wersji 7 ma taby. Ale ewolucja tabów idzie krok naprzód. Przeglądarki Chrome i Safari 4 posiadają taby na samej górze okna:

Czy powinno to kogoś dziwić? Według mnie nie, ponieważ taby zmieniają nie tylko wyświetlaną stronę, ale również adres wyświetlany w pasku adresu (URL) oraz znaczenie przycisków wstecz i dalej (bo cofamy się tylko w danym tabie). Oznacza to, że taby przełączają nam kontekst prawie całej przeglądarki.

Przyszłość

Skoro taby przełączają kontekst całej przeglądarki, to co byśmy powiedzieli na wyodrębnienie tabów do osobnych okien?

Ups! Przecież od tego wyszliśmy i myśleliśmy, że taby to krok naprzód, więc dlaczego mielibyśmy się cofać?

Taby odegrały ważną (jeśli nie bardzo ważną) rolę w systemach operacyjnych. Dziś znajdujemy je nie tylko w przeglądarkach, ale również w edytorach tekstu (GEdit, Kate), narzędziach developerskich (Eclipse), terminalach (Konsole, Gnome Terminal) oraz w innych programach.

Czy rola tabów w różnych aplikacjach jest inna? Według mnie nie. Zawsze chodzi o to, żeby (podobnie jak w przeglądarkach):

• grupować podobne zadania
• oszczędzić chaosu na pasku aplikacji
• pozwolić na szybkie przełączanie pomiędzy tabami (w odróżnieniu od przełączania między aplikacjami)
• pozwolić na otwieranie czegoś w tle (bez otwierania wkurzających okienek)

Tylko dlaczego w każdej z wymienionych przeze mnie aplikacji taby realizowane są inaczej? Firefox ma taby nad stroną, Chrome zupełnie na górze, Safari jako fragment paska tytułowego aplikacji, Konsole na dole strony, Kate jako listę plików po lewej stronie…

Proponuję, aby istotnie przenieść ideę taba na poziom zarządzania okienkami, a nie poszczególnych aplikacji.

Moje postulaty dla menedżerów okien:

• wyróżnienie aplikacji (czyli to, co teraz jest oknem) i jej okien (czyli to co teraz jest tabem)
• mechanizm otwierania nowego okna w tle
• możliwość prostego przełączania się między oknami jednej aplikacji w odróżnieniu od przełączania się między aplikacjami

W tym miejscu przychodzi mi do głowy jeszcze jedna funkcjonalność tabów, która bywa różnie implementowana w różnych aplikacjach: możliwość odrywania tabów do osobnych okien i późniejszego ich łączenia.

W Firefoksie jeśli dobrze się rozeznałem takiej możliwości nie ma, w Konsole możemy odrywać taby, ale nie możemy ich z powrotem łączyć, czyli nie ma pełnego mechanizmu przenoszenia tabów pomiędzy oknami danego typu.

Zamiast kazać się wysilać twórcom aplikacji, zróbmy to raz a dobrze! Dodajmy do listy postulatów dla menedżerów okien następujący punkt:

• swobodne przenoszenie okien pomiędzy aplikacjami tego samego typu

Implementacja

Z ciekawością obserwowałem możliwość grupowania okien i późniejszego przełączania się między nimi na zasadzie tabów w Compizie.

Brakuje natomiast jednej bardzo istotnej rzeczy, która pozwala zastąpić poszczególne mechanizmy tabów w aplikacjach jednym mechanizmem z Compiza wyjętym.

Otworzenie nowego okna przez okno z danej grupy okien powinno powodować automatyczne przejęcie tego okna przez tę grupę. Musimy sami "doklejać" nowo-otwarte okna do grupy. I to jest główny ból tego rozwiązania. Ciekaw jestem jak z punktu widzenia protokołów i bibliotek można zaimplementować moje postulaty oraz jak daleko posunięte zmiany musiałyby nastąpić, żeby to dało się zrealizować.

Czy warto?

No i pozostaje pytanie, czy warto. Zacznę od wad:

• prawdopodobnie potrzeba przebudowy (lub rozbudowy) kilku elementów systemu okienkowego (takich jak menedżery okien i API do nich)
• konieczność aktualizacji aplikacji, żeby korzystały z natywnych tabów, zamiast ze swoich implementacji
• być może utrata pewnych możliwości (takich jak "podczepienie" swojego menu do zakładek) przez aplikacje

Zalety:

• zunifikowanie tabów w całym systemie (!)
• możliwość przebudowy mechanizmu "grupowania podobnych zadań" na pasku zadań — teraz wiemy dokładnie jakie zadania są powiązane — być może będzie ktoś odważny, kto wprowadzi dwupoziomowy pasek aplikacji
• znaczne uproszczenie kodu aplikacji
• łatwiejsze pisanie nowych aplikacji (mechanizm tabów mamy od razu za darmo, nie musimy się tym przejmować, ani zastanawiać się czy będzie kiedyś potrzebny)
• możliwość połączenia zmiany okien danej aplikacji z pewnym efektem graficznym
• możliwość prezentowania wszystkich okien danej aplikacji naraz tak jak to robi Safari dla tabów (tylko, że u nas to będzie za friko i dla każdej aplikacji):

Czekam na Wasze opinie!

by Gabrys

This can be the option, when you send a bunch of files to an Internet service, that is generally fast, but the connection sequence is quite slow, so uploading 100 files one after one causes the script to wait 100 times to quickly upload a file.

Other situation could be when you have multi-core machine, for example you have eight processing units, but use only one in your script, and you have a bunch of files to compile or to process in some CPU-expensive manner.

We'll use only BASH to smartly parallelize the tasks and speed up the slow part of your script.

First of all you need to know how many jobs in parallel you want (if you have 8 cores and CPU-expensive part of script, having more than 8 jobs does not help, probably a number between 4 and 8 will do best in this case).

 #!/bin/bash PROC_NUM=4 

Generally, we'll ensure, than no more than PROC_NUM processes are forked into background and run another task. If there are PROC_NUM processes running in the background we'll wait a (fraction of) second and check again.

 #!/bin/bash PROC_NUM=4 function run_task() { # task to run # can be more than one-line # can take parameters $1, $2, ... } function run_parallel() { while [ `jobs | grep Running | wc -l` -ge $PROC_NUM ]; do sleep 0.25 done run_task "$@" & } 

run_task "$@" passes all the parameters passed to run_parallel to run_task. You can use "$@" in run_task to pass all the parameters to external command! The "$@" is the best choice when you have spaces, dollars and other special characters in parameters. It doesn't transform anything, it's completely safe (probably the only short way to pass all the parameters).

There are only two things left: invoking the run_parallel and synchronizing the tasks — you need to know when ALL the tasks ended, right?

 #!/bin/bash PROC_NUM=4 function run_task() { # task to run # can be more than one-line # can take parameters $1, $2, ... } function run_parallel() { while [ `jobs | grep Running | wc -l` -ge $PROC_NUM ]; do sleep 0.25 done run_task "$@" & } function end_parallel() { while [ `jobs | grep Running | wc -l` -gt 0 ]; do sleep 0.25 done } # script content cd /some/where/you/want # now the parallel operations # for example in some while find | while read file; do run_parallel "$file" done # now you want to continue when ALL parallel tasks ended end_parallel # the linear script code again cd /some/where/else make something 

That's all! Though, there is a different approach to this:

 #!/bin/bash function parallel() { local PROC_NUM="$1" local SLEEP_TIME="$2" shift; shift while [ `jobs | grep Running | wc -l` -ge $PROC_NUM ]; do sleep $SLEEP_TIME done "$@" & } 

This function acts as a wrapper to a non-parallel command and runs it in the background assuring that no more than PROC_NUM processes run at once. If there are PROC_NUM processes running in the background, the wrapper waits SLEEP_TIME to re-check the number of background jobs.

Invoking:

 parallel PROC_NUM SLEEP_TIME /usr/bin/some-command arguments ... 

so

 parallel 4 0.5 ls -R /tmp 

means: run ls -R /tmp in the background if there is no more than 3 processes already run in the background. Otherwise wait 0.5 seconds and try again. Then run ls -R /tmp if there is no more than 3 processes already run in the background. Otherwise wait 0.5 seconds and try again. Then run ls -R /tmp if …

Quite nice, isn't it?

by Gabrys

 echo $(($(printf '%d' "'`head -c 1 /dev/urandom | base64 | tr A D`")%4)) 

This prints a random number from 0 to 3. How it works?

Firstly the command below prints one random byte using special Unix /dev/urandom device:

 head -c 1 /dev/urandom 

Piping this to | base64 gives us base64 representation of the byte.

Base64 is a method of encoding 8-bit data as human-readable strings using only 64 visible characters (letters, digits and some !@ and stuff). Whitespace is always ignored when reading base64 string. The standard is really nice, because you can for example read a base64-encoded file with a phone or send a printout of it with a classic mail. Because all the characters are human-readable, one can enter them and decode the original message. The format is used widely for sending emails.

It is important for us, that running base64 on a random byte gives us 2 bytes that are only "normal" characters, ie don't have any special meaning in any context (like some white characters may have).

Now comes the tricky part:

 printf '%d' "'`head -c 1 /dev/urandom | base64`" 

printf '%d' "'a" would give us 97 — this is the ASCII code of letter a. Remember we get two bytes of data after base64? No problem, printf cares in this case only about the first character.

As you may notice the output of this is one of these:

• 43
• a number between 47 and 57
• a number between 65 and 90
• a number between 97 and 122

This gives us 64 possibilities. Great! 6 bits is just the same as 64.

This is when we get to BASH arithmetics. This is how it works:

 echo $((7*12)) 

This should print 84 obviously. Knowing that enclosing a string in $( and ) causes BASH to run the enclosed command and return its results (just like using the backticks: `command`) this is everything.

The % means modulo in BASH arithmetic (just like in C, Java, Python, PHP, …), so this:

 echo $(($(printf '%d' "'`head -c 1 /dev/urandom | base64`")%4)) 

prints the number we generated (one of 43, 47…57, 65…90, 97…122) modulo 4. This needs to be 0, 1, 2 or 3.

Let's now check what the probability of receiving each of the digits.

Suppose /dev/urandom prints every possible byte with equal probability. We'll now analyze each byte (possibly) generated by /dev/urandom, it's base64 representation, ASCII code of first byte of the representation and the modulo 4 of it. We'll use a table for it:

(Some of the symbols in the first column may appear not visible or otherwise look strange. This is normal, there are many characters in ASCII that has (or had) some special meaning.)

Let's count have many 0s, 1s, 2s and 3s did we get:

This is not ideal, because you get statistically slightly more 1s than 0s, but if you don't care too much, this is all!

If you care however, here is some solution. We need to get 4 results that give us 1 and convert them to some that gives 0:

 echo $(($(printf '%d' "'`head -c 1 /dev/urandom | base64 | tr A D`")%4)) 

Notice the tr A D. This changes each A to D in the base64 output. Thus four rows of table above (for 0 to 4 codes) should behave like the 12 to 15 codes, thus giving 0 at the end instead of 1.

We're done. Let's enclose the procedure in function clause and create a sample code that tells us how many 0s, 1s, 2s and 3s where hit within 100 shots.

 #!/bin/bash function random() { echo $(($(printf '%d' "'`head -c 1 /dev/urandom | base64 | tr A D`")%4)) } ret=`i=0; time while [ $i -lt 100 ]; do random ; i=$((i+1)); done` echo -n '0: ' ; echo "$ret" | grep 0 | wc -l echo -n '1: ' ; echo "$ret" | grep 1 | wc -l echo -n '2: ' ; echo "$ret" | grep 2 | wc -l echo -n '3: ' ; echo "$ret" | grep 3 | wc -l 

The program also shows how much time did it take to generate the numbers. Adjust the 100 to your needs ;).

UPDATE: having this article posted on reddit programming gave me actually much much better ways of doing a random function (see in comments). Thank you for your replies!

by Gabrys

I described the system extensively in blog post titled New search for Wikidot's gonna rock.

The new search system replaced the old Google-powered one.

The main advantages over Google Search Engine that has been used till now are:

• search in public sites + those you are a member of
• semantic search: tags, title are more important when searching
• simple to sophisticated queries
  • "blog site:community" — search for anything with "blog" in it but only on site community.wikidot.com
  • "tags:wikidot site:quake" — search for pages tagged "wikidot" on my site (quake.wikidot.com)
• poor quality content filtered

Things left to do:

• add site preview (thumbnail) like the one on right to the search results
• explain in simple words the search syntax
• promote good and/or active sites (give them higher rank)
• decrease delay from editing to updating search index (should be max 5 minutes)
• create custom search module searching in a bunch of (related) sites — this would be nice if you keep separate sites for different areas of a project like private site for project members and public one for project users. The search is intelligent enough to filter restricted items from search results if someone is not member of the private site the items come from.

by Gabrys

• low response time
• works for (hundreds of) thousands clients at once
• makes use of a client cache (i.e. send Not Modified header instead of the full page if page was not modified from last time)
• fault tolerance (if something crashes, this does not affect the rest of system)

After talking with Michał, reading some documents about HTTP, browsing Django documentation and testing tools and programs like Lighttpd, Nginx, Varnish I thought of a architecture pattern for hosting Django applications, that can be easily adapted to other frameworks and languages (including PHP).

The architecture

I'll describe the whole architecture from the application to the user's browser.

• [backend] Application served with WSGI, SGI or FastCGI
• [gateway] Web server talking to WSGI, SGI or FastCGI service
• [frontend] Cache proxy

The main reason for separating those things is different nature of particular levels

• Application may introduce big memory overhead (if it is a PHP or Python application for example)
• Web server may introduce big lags (if server-client connection is slow)
• Separate cache server may be precisely configurable depending on Cookies and other factors

Why joining backend and gateway (for example using mod_python or mod_php) is bad? The perfect example of this, is having a small and fast script (like echo "hello";) and extremely slow and unreliable client (may be some sort of attacker as well). The script should be run in milliseconds, but sending the data to client may take a few seconds. Having backend and gateway in one process makes the high memory consumption of PHP/Python interpreter last until the client receives the last byte of data.

Keeping backend and gateway separate solves this problem. The client requests a page from gateway, the gateway uses backend to generate the content, the backend generates it in milliseconds and the gateway then frees the backend and remembers the data (using much less memory than the backend process) until it is completely sent to the client. During (possibly) slow sending the response to client some other gateway process may use the backend that was just freed.

HTTP Cache

Application should at least set ETag headers (may be computed as simple as md5 from the whole response to the client). In Django, this can be done automatically using the cache system bundled with Django. Setting of this header makes client receive only the headers which greatly limits the amount of data sent to a browser (if the site is visited more often than it is modified).

Using a separate cache system you can easily deal so-called "Digg load peak". This is a situation when a huge amount of people visits a page after it is mentioned on a popular website like Digg. You can get as much as 1000 or 2000 requests per second. If you would ask the application to generate the content for every of the request, request could simply time out.

There are two or three answers to this: a simple and a precise one at least. The simple one is adjusting the frontend to cache response to each URL for a minute or two for every user not having a Cookie (so not logged in). The downside is that for non-logged user, there can be a delay before actually having the updated page. The upside is that 90% (or so) of traffic does not hit your application (and is server from cache).

The precise solution, would be setting the application to first check the ETag of the content and returning ONLY Not Modified header without actually running ANY heavy operations. This would work well, because after the first visitor asked for the page, the cache frontend saved the ETag for the page and would attach it to the consecutive requests for the same URL (even for another user). This however can be non-trivial to implement in some particular cases. Also, this method does not eliminate the use of application level, only minimize the time spent in it. On the good side, this should be completely safe to use and help the performance even in non-peak load. This means the system is worth implementing it!

Between the precise and simple solution, there is a variation of simple one, that would require more work to be done by the caching server. It would be applying the cache-for-one-minute rule after reaching some threshold request rate (like 20 reqs/s) for single URL, or for all system. This should quite good comprise between serving the most accurate data and actually being fast. I mean, if trying to be the most accurate you can, results in high load and not serving anything, it would be better to temporarily serve less accurate data.

The actual caching rules may be a combination of the ones depending on client location, referrer, cookies settings and so.

Notes on application level

In order to have your application behave well under high load, you'll need to concern the following designs:

• database reads caching (ideally on database-access library level)
• exporting non-realtime operations (like cronjobs) to different machine
• exporting non-database tasks (like making thumbnails of images) to other machine
• exporting static files serving to other machine (you'll need a separate domain and an IP address)
• exporting other expensive tasks (searching, summing big sets of data) to other machine
• finally database sharding (dividing the database schema or data into a bunch of machines)

Using Memcached for caching is really a good choice, because it was designed to support many caching hosts from the start. This means, that adding more "cache power" is as easy as adding a new machine to the caching cluster.

Bottom line

The nice thing about this design is that it works like a stack, each layer adding some features to the system. This means, that you can start with the simplest mod_python and with the growth of the service add a smart cache server, then change the mod_pyothn to WSGI and Nginx for example.

Also, the design allows to run two or three levels on one computer and then moving some services out. This gives much flexibility from the start, which means you don't have to worry about problems you'll encounter some day, because now you know, that you will be able to solve them. Just not having to, you can now concentrate on real thing — the application and care about the maintenance later.

My experiment

I would like to test Nginx (gateway) and its experimental mod_wsgi module to host sample Django application (backend) in WSGI mode using Varnish (frontent) as the cache proxy. The nice thing about Nginx is that it uses really small amount of system resources to talk with each client. The WSGI application makes a "pool" of backend processes that Nginx can use. Also I would like to try caching options of Nginx instead of setting up varnishd (but I assume the varnish would be better).

by Gabrys