Tobi Waves

A Talk by Urs Hölzel, Vice President for Technology,

About Google

Mission: TO organize the worlds information and make it universally accessible and useful,

An international company: 250% traffic from outside US

Engine has 4 Billion pages in index

Profitable since q1/2001

23 Office Location Worldwide.

15k boxes, several TB disk storage

There are over 1000 queries a seconds on dec 25th, 2am.

Engineering Offices in the US, Zurich and Bangalore

About the Web

Static web 167 TB in 11 Giga Pages, but dynamic websize 92 PB. (Estimates)

1 in 4 hosts on the net run a webserver.

Problem: All data, users, hosts grow exponentially. This means the problem of finding useful information grows exponentially too which makes for interesting problems.

Google Infrastructure

A high reliable system based on low cost comodity hardware. Redundancy has to be built into the software and hardware. Monitoring, repair and maintain these boxes is a prime problem.

The Google Filesystem GFS

Stripe files across many boxes and replicate them on multiple servers.

Components: Master - keeps directory and plans file layout, ChunkServer - hold the data. Clients - use the data. (Chunksize is 64 MB. Data is cached on client once retrieved. SOSP'03 (www.cs.rochester.edu ...) )

10+ Clusters of 1000+ boxes.

350 TB Filesystem

How to be a Search Engine

Crawling: Recursive Process. Problem: dynamic pages, slow servers, management of the link list, session ids in the URL, how to prioritize the URLs, being nice to the web servers, detection of duplicates, avoiding traps, actively fill forms to pull "hidden" contents, figure out when the page needs to be re-crawled.

Indexing: Words by document and position in the document. One Terra Words in the index.

Ranking: Hard problem. All traditional assumptions on searching like long, coherent, high quality documents are not valid for web documents. Googles idea is to define a PageRank for figuring the importance of the page. The PageRank of a page is the sum of PageRanks of other pages pointing to this page. A page contributes its PageRank divided by number of out-links to each of its target pages. In reality it is more complex. Google has about 100 factors in its real PageRank function like font size, color, proximity to other words.

Serving: Partition the data to different servers and have each solve a sub problem of each query. Query goes to Google Webserver, it queries Index Farm, accesses the Doc Farm for the real data. Additional services from Add Server and Spelling Server. IEEE Micro, 2003 has more on the structure (www.computer.org ...) .

Advertising: Find the best add, relevant to the query. This is a very important problem as this is the main source of revenue. Only show an add which has a chance to be clicked on, if the click-through is low, the add will be dropped. Advertisers only pay for adds actually clicked.

Google Playground

There is lots of data and computing infrastructure at Google. Google pays people who spend their time on figuring new ways to analyze and present this data: (labs.google.co ...)

In the good old times, when men were still men and computer virus writers were still technically brilliant hackers. Viruses used the uncountable holes in Microsofts ubiquitous Outlook eMail software to spread.

But even then, generally the rule was simple. If you don't want to be infected, don't run any code you don't know where it's coming from. If you have Outlook, make sure it's patched and properly configured. In Unix circles, people made fun of the whole situation by sending out mails which claimed to be a solidarity Virus, calling upon the Unix User to copy this mail to all addresses in his address book, to emulate a virus, as a gesture of solidarity with the Windows crowd.

Now, a few years later, Outlook has matured to the point that there have been no major holes for months. Never the less, eMail viruses still crop up and spread. Virus writer started to attack the users mind directly, by writing messages into the body of the virus email with the purpose of confusing the user into clicking the virus attachment, forgetting all the good advice they got. Fortunately the anti-virus software gets updated so quickly, that viruses are normally contained quickly.

Today though, mark the date, the whole matter entered an all new stage. I got the first virus which was contained in a password protected zip file. The password was contained in the accompanying email, so it is easy for a human to unpack, but anti virus software has no chance as it can not decrypt the zip file containing the virus. As a concept this sounds fine, but what totally kills me is that it seems to work. Since this morning, I get an increasing number of encrypted zip file viruses. There must actually be people who get this virus, unzip it using the supplied password and then run the thing in order to get infected.

I wonder how many people would hang themselves if they got a rope in the mail. Warden make sure all the cells are locked.

by Ralf Hildebrandt

How to use Postfix as a crude but cheap filter against spam in front of the more complex filters like spamassassin.

Sources of Spam

An important source of spam these days are miss-configured web proxies which proxy to smtp ports as well and let outsiders connect.

Protection

Use RBL lists for open-proxies, open-relays,

Reject mail from faked sender address (see below).

Insist on RFC conformance (this can make you loose lots of real mail to as there are many missconfigured normal mailservers.

Content Filters: Altermime, SpamAssassin

On Postfix

Use the snapshot version of Postfix as it is realy stable and has all the latest features.

Use a cashing nameserver to speed-up dns lookups.

By default postfix is configured to only accept mail from your local network for external destinations. This has no influence on spam though.

Be careful choosing RBLs because there are many badly maintained blacklists out there. Blacklist must have clear criteria and a delisting procedure.

postmaster@yourdomain and abuse@yourdomain must accept all mail this must be explicitly listed in smtpd_recipient_restrictions.

A good RBL list cbl.abusenet.org recomended by Ralf.

When you are using RBLs make sure that you can quickly add exceptions to your system.

Rejecting mail to unknown users at the smtpd stage is very efficient as it first saves traffic and it also saves you from sending bounces.

Postfix can use various directory services to figure out which users exist. Postfix 2.1 will even cache answers

Use right hand sender black lists may also help. But be care full. Look at =dsn.rfc-ignorant.org, postmaster.rfc-ignorant.org, abuse.rfc-ignorant.org, whois.rfc-ignorant.org=.

RBL/RHSBL are expensive because of all the DNS lookups. Perform them as late in the restrictions list after the cheep mails.

Sender address verification

Check if the sender is either a known valid or can be verified to be valid. Postfix has special support for this as it can send test messages to the sending host. The sender will not notice this as postfix only starts sending mail but aborts before giving any message body.

Make sure you are really careful as this can cause you to loose mail from people who are not able to correctly spell their sender. One option is to apply these sender check restrictions only to suspected domains.

by Patrick Koetter

How to support mobile users to use your server as a mail relay. IP based restrictions do not work as the mobile users will have random IP addresses.

SMTP AUTH

Using Cyrus SASL2 and OpenSSL together with Postfix. You can configure postfix such that it allows relaying access for users who are properly authenticated. Most mail clients support snmtp authentication.

The problematic thing is to properly configure SASL. Get the CVS version as it is less buggy then the official 2.1.17, it even has some minimal documentation.

SASL configuration is governed by a config file called the same as the program using the sasl library. In our case this is smtpd.conf.

If you use SASL with plaintext passwords, make sure it only allows AUTH when TLS is in operation.

Check out Patricks howto on this (postfix.state-of-mind.de ...)

Certificate based Relaying

For people running mobile Unix it is possible to setup a local mailserver which just forwards all mail to the official mailserver of your site. By configuring the postfix smtp daemon to use TLS on the client, and you store the clients cert on the server. Now configure the server to ask clients for a certificate when they connect. If a client submits a vlid (known) certificate it will be allowed to relay even if it has an ip number outside the local network.

The cool thing about this is, that now any program on the mobile unix client can send mail via the local mail server to the company mailserver without further problem.

by Theodore Ts'o

History

VA Linux wanted to be the IBM of the Linux world, but forgot to ask whether maybe IBM wanted to become the IBM of Linux. This was a huge mistake.

What makes Linux significant

One of the first projects done primarily over the Internet without a central group contributing all the code.

Difference to other projects. Many of the people involved are on a mission to distribute the knowledge about the system. Even people who can not bootstrap their own system are welcome.

Open Source and Free Software

The Open Source movement brought the whole "making source available is cool" concept into the industry without the political issues of the GPL.

Intellectual property laws are going to become more and more of a problem, so we have to become involved.

The huge number of Open Source licenses leads to incompatibilities when working with libraries. The important lesson here is to pick the right license from the start, as relicensing is difficult as soon as you have received a lot of code contributions.

Rapid Development and Open Source

Infrastructure work or documentation writing are necessary tasks but they are not very sexy. We need to cater for them. Incremental changes are not the only thing.

Even though there has not been a lot of innovation coming from Redmond. This does not mean they are sitting on their hands. They are working on vertical integration technologies like their new user interface description language which will be used on all their products.

User Interface Testing

Have programmers watch a users working with their software. Do not let them talk to the users and help them. They will see all the problems which are to be fixed.

The Limits

Software with a short shelf life like tax software or games needs a huge investment in development and have to recover the cost quickly, So this will probably never work with opensource concepts.

Binary drivers are a fact of life due to paptent and even legal issues. There is not clear solution for this yet in connection with Open Source.

Closing

It's been a great 10 years, but there is still a lot todo.

by Robert Griessmer

For the technical Information, read my earlier entry about Urs Hoelzels talk.

About cheep hardware: If one writes his software under the assumption that hardware is going to fail anyway. This makes lots of problems much simpler. If the number of machines grows really high, you can employ people who spend their days swapping broken ones.

These days Google designs their own bare-bone boards with only the necessary components for the stuff, the machines are required to-do.

Google Philosophy

Make the worlds information search able.

Do things that matter, and do them algorithmically so that they are scalable.

Every engineer has a free day per week to work on his own fun projects.

Google Tricks

Spell checking happens statistically. Google does not know what is right, but what is most popular.

Google provides an API for programmers.

Experimental projects (labs.google.com ...)

Google Zurich Office

Right in the city center. Entire range of software development. Meant to attract European engineering talent. Tight integration with the Mountain View offices.

Jobs: (www.google.ch ...)

User Questions

Q: What is your crawling bandwidth

A: Well about this (shows with hands) Size.

...

A: oh and ... no comment ... I can't really talk about this.

by David Rosenthal

Open Source in Government

Could government require that only Open Source software be submitted for a new text processing system to be procured? Yes, but only if the fact of it being Open Source was directly tied to the core functionality of the software and requirements in this area. This point may be difficult to make, depending on the nature of the software.

If GPL software is modified by one branche of the governemnt and passed on to a different branch. This is a sort of publication. Accordning to the GPL license the second branche gets a license with the code which allows it to redristribute the modified version without restrictions, takeing it effectively out of the control of the first party.

Copyright

Every program of an "individual nature" is protected by copyright law. "Individual" means, that the code is potentially recognizable as being written by that particular author. This right does not have to be registered or patented or anything. Every author has it.

In Swiss law this means that I as an Author have the exclusive right to decide whether and how my product is used. I can give all or some of my rights up to a third party .. aka grant a license. GPL or any of the other Open Source licenses operate on this principle.

GPL can be enforced. 19.5.2004 the Munich District upheld the GPL in a case of netfilter team vs firewall vendor.

Contract Law

If I modify an Open Source product for a third party (contract) I can become liable for any problems with the whole product if I do not exclude this in the contract. This is not special for Open Source products but it may easily go under the radar. Becareful when drafting your contracts.

Warranty and liability can be limited, but only to the extent allowed in the law. Swiss Law: Any limitation of liability for gross negligence or willful intent is void.

Do not trust in disclaimers. Be open about the limitations of your product. Reduce the expectations in your product.

Software Patents

European patent law is fundamentally different from US patent law. In the US "everything under the sun, made by man" can be patented. In Europe patent are strictly limited to technoligical inventions. And even there. Patents have to be new, not obvious to someone skilled in the 'art' and there must be no prior art. This is not going to change in the next 10 to 20 years at least.

Patents are granted easily, but they may not be valid. In the first 9 Months after publication they are very simple to kill. Greenpeace does this all the time in the biotech area.

The likely hood of a big player (aka MS) going against a small one are slim as the PR damage would be huge, not to speak of all the anti-trust issues.

Conclusion

Open Source doesn't have particular legal problems. But make sure you read the fine print of the licenses.

Legal issues with OSS are very similar to commercial software.

Worrying about patents is of no use.

by Poul-Henning Kamp

Compters are now 50 years old. Unix is 30 years old.

We write code on the screen and not on paper. but thats about it.

Unix has blown more chances at being a big success than any other operating system. It's about making the same mistakes again.

The problem

Programming happens in the brain and not in the computer. Throw your thinking at problems not more hardware. Programmers should have slow machines.

Instead of baking a bigger cake. Unix companies fight about the same piece.

The state today

Uncountable Linux distros, a handfull of BSDs, IBM AIX - IBM the Unix way, Sun Solaris - Unix the Sun Way, HP-UX - Unix cul de sac, Mac OS X - yea, its Unix, but don't worry about it.

Unix Standards

Very weak, Incomplete, Ambigous,

POSIX. Everybody made sure that their product was covered by it. Its not a standard but rather a panorama of things to-do. MVS is POSIX compliant, and so is Windows.

The one good standard is the "POSIX 1E" security extension. Which was never formally adopted, but everybody sticks to it religiously.

The Linux Standards Base will fail because it defines what we have today. It repeats the mistakes of POSIX. Its not about how Unix should be.

Should we save Unix

_No_

Architectural mess.

No significant invention in the last 20 years

Everybody thinks in his box.

_Yes_

You get the source

The only alternative is LongHorn

Can Unix be saved - No

no market model

no cooperation to generate a market

too much politics

Can Unix be saved - Yes

Start thinking outside your box

Stop bickering about irrelevant details (BSD/Linux, Gnome/KDE)

Work on the real problems. Fight for open data. Fight the software patent mafia.

Invent things! Plan9 (namespaces), Sun (Java), Apple (User Interfaces), Your Name could be here,

Find the next Web.

Quotes

The only thing Unix has invented is Unix.

The KDE people sit in the KDE box. They have a little hole in their box to see the GNOME people.

I don't care about your license as long I get your source. I even wrote a license for it.

Tutorial by Theodore Ts'o

What to do when data got lost

Don't panic !

Stop and think, figure out what happened. create a backup with

|dd if/dev/hda1 of/dev/hdb1 bs1k convsync,noerrors|

If you have no spare disk, buy one. The disks are way cheaper than the data.

Disks have a life span of 2-3 years, if they are in heavy use ... you might want to swap them preventively just to be sure.

Physical issues

Harddrives can not only experience head crashes but also "high rides". This is the name for incidents when a head flies higher than normal. This condition will only get noticed when data is read back. The new solaris zfs tries to catch this problem by reading back recently written data whenever it has spare time.

Hard drives survive only about 50'000 power downs due to the controlled head crash happening in the landing zone ... This can be a real issues for laptop configurations where frequent disk spin-downs are used to save batteries.

Some harddrives are not designed for continuous use. This will be noted in the spec sheet ... Make sure you check the spec of cheap disks you plan on using in your web-server.

A small head crash will not necessarily cause an immediate disk failure. It could just chip off small amounts of material from the disk surface which will then fly around in the hard-drive case. This condition will cause an increasing number of additional head-crashes which again will chip of material ... This means that it is a good practice to take a full linear image backup of a 'damaged' disk as soon as possible. Errors may well increase as you work on fixing it.

Get a new disk if you find any bad blocks on a disk.

Modern disks

Disks used to have a simple physical geometry. This is still visible in the head, cylinders, sector geometry specifications. Modern disks use constant bit rate and multiple long spiraling tracks to fit more data. This is all hidden by the controller and exposed through a simple linear block number to the OS.

The only thing one can assume about physical disk layout is, that two blocks which are numerically close together will normally have a short seek time.

EFI/GUID partitioning schemes

_Universally Unique IDs (aka GUID)_

A GUID is a 16 Byte number. Either a random number. Collision probability 1/2^64 (birthday paradox). Another method is to take the mac address of the computer plus a hires time stamp. A 3 bit code in the UUID/GUID shows the method used to create the GUID.

The EFI/GUID partitioning scheme uses a GUID to identify each disk as well as each partition. Partition types are "well-known" GUIDs, but still GUIDs (16 Byte) this allows to have unique identifiers for each filesystem type without a central registry.

An EFI/GUID partitioned disk contains an old style MBR patition table in the first sector which claims that the whole disk is covered by a special partition type. This prevents old OSes from messing with an EFI disk. Linux can do EFI partitions on any machine you run linux on. The only special problem is to have a boot loader which is able to deal with it.

About the FAT FS

Because all files are stored as single linked lists, random access is very hard. This also makes file fragmentation very bad. On top of it FAT uses a first free block allocation scheme which again furthers fragmentation.

Inode based Filesystems (FFS)

Stores only the filename and a link to the inode in the directory. The inode then stores all the meta information on the file. This allows to create hard-links.

For short files all blocks are linked directly from the inode. Longer files are created with indirect blocks. Even longer ones are stored with double or even triple indirect blocks.

Inode based filesystems are very fragmentation resistant. This is the reason why there are no defragmenters for Linux.

Old FFS filesystems like UFS allow to specify the physical geometry of the disks to optimize the physical allocation of the filesystem elements. Newer FFS implementations do not bother with this anymore, as there is nothing to be known about disk geometry anyways.

How to recover from accidents

_Overview_

Ask yourself what has happened?

What is the lowest level where you have problems. Always fix the lowest level first.

How important is the data?

When was the last backup performed.

Create a plan of attack before you do anything else.

_Hardware Level_

First indication are often console messages from ide/scsi driver. If you catch a correctable error, you may be able to replace the drive before it actually breaks.

If you see BadCRC errors on a new system it may indicate a simple cabling problem.

The "dev xx:yz" elements in disk errors identify the device file minor/major number affected by the error and thus the partition.

Use |e2fsck -c| to mark bad blocks and see what files are affected.

Check S.M.A.R.T. logs.

In any case make a full image (dd) backup of the disk.

For the image backup you may use |dd_resque| from (www.garloff.de ...) it will alter its block size when it hits a problem to recover as much data as possible without loosing speed while reading is easy, and it has a progress bar.

Partition Table Corruption

If the filesystem can not be found, it may be "only" a problem with the partition table.

|fdisk -l| will show what is there.

Make a backup copy of the MBR. (dd is your friend)

|gpart -W /part.table /dev/hda| can scan the disk for filesystems and reconstruct the partition table. Old filesystems from old partitions still sitting on the disk may confuse gpart.

Filesystem Corruption Problem

Errors may be reported by |e2fsck| during quick boot check or during a full check.

EXT2/3 can also detect errors as it runs ... the actions it should take in this case can be configured at mount time or through tune2fs. For laptops 'remount-ro' is advisable. Servers should better 'panic' as this allows the system to get back into a sensible stat and not limp along. Often such minor corruptions are fixed in the |e2fsck| phase.

In general running |e2fsck| with -y (yes to everything) is fine as you can normally not do anything else than say yes anyway, but |e2fsck| may move orphaned inodes and disconnected directories into 'lostfound' and this should be cleaned up before booting the system fully. The 'file' command can help to identify files. The locate database can help identify the original location of the directory.

e2fsck will not notice blocks with wrong data which are part of a file as it does not maintain any CRCs.

Undeleting Files

In EXT3 unlink will zero out inodes and can thus not be recovered. (this may be 'fixed' at some point')

Undelete on a system level is not possible with EXT3.

Use userspace delete/undelete tools.

Oh and make backups.

|grep -ab regexp /dev/hda1 | awk -F: 'printf(%x\n", ($11023)/1024);}'| (use 4095,4096 for 4k blocks)

Gives the disk blocks where the regexp was found. Then use |lde| to examine the blocks visually.

e2image

The |e2image| tool lets you create a backup of the inode table.

The latest (not released yet) debugfs can use the inode table from an e2image backup, this allows to recover lost files. Even an accidental mkfs can be reverted to a large extent (contents of the root directory will be in lost+found).

It is good practice to run e2image every night.

S.M.A.R.T.

This is the internal health monitoring system of modern hard disks. It will give early warning about disk problems in the waiting.

|smartctl| and |smartd| are your friends here.

Conclusion

Make backups. Save your sanity.

by Greg Koah-Hartmann

Most Unix systems have a device filesystem. So does Linux with devfs. There are three main problems with it.

The code is ugly and beyond repair

The namespace is not LFS compliant

The author of the code has out of the loop for about two years.

A new solution has to be found, as the state of the /dev tree without some automatic management is not tenable. In Debian for example there are 18'000 static entries in there. And on the other hand there are USB plug and play devices which tend to get a different device name every time they are plugged in.

The only thing udev can not do, is to detect a process trying to access a device node that does not exist and then load the relevant driver. This feature of devfs does not seem crutial though.

In the kernel 2.6 there are two main components which make a new and simple solution possible:

The kernel can call a program called |/sbin/hotplug| whenever new devices are connected to the system.

The sysfs filesystem (mounted under /sys) contains all information about devices known to the kernel.

Udev provies a small userspace daemon which manages the /dev tree. It can populate it with a small set of default devices like ttys at boot time and then go on to add all other devices known to the system. It is configurable via simple text file with rules about the naming of the devices. These rules can be pretty sophisticated. Usb devices can be identified according to their vendor or product string as well as through any other property they provide. It is even possible to make udev run an external program which examines the device and then decides how the /dev entry should be called.

All distributions have adopted udev for their linux 2,6 editions. There are some teething problems with distros not using the official udev helper scripts. The author himself maintains the gentoo package.

Udev has to be started VERY early in the boot process, so that other programs can access the devices. Depending on the setup it may be necessary to add udev to initrd. Volume managers and RAID setups are mentioned.

*