Estimasi Cepat

Dalam wawancara desain sistem, terkadang Anda diminta untuk memperkirakan kapasitas atau persyaratan kinerja sistem menggunakan estimasi perkiraan cepat. Menurut Jeff Dean, Google Senior Fellow, "perhitungan perkiraan cepat adalah estimasi yang Anda buat menggunakan kombinasi eksperimen pemikiran dan angka kinerja umum untuk mendapatkan gambaran yang baik tentang desain mana yang akan memenuhi persyaratan Anda" [1].

Anda perlu memiliki pemahaman yang baik tentang dasar-dasar skalabilitas untuk melakukan estimasi perkiraan cepat secara efektif. Konsep-konsep berikut harus dipahami dengan baik: pangkat dua [2], angka latensi yang harus diketahui setiap programmer, dan angka ketersediaan.

Pangkat dua

Meskipun volume data dapat menjadi sangat besar ketika berurusan dengan sistem terdistribusi, perhitungannya kembali ke dasar-dasarnya. Untuk mendapatkan perhitungan yang tepat, penting untuk mengetahui satuan volume data menggunakan pangkat 2. Satu byte adalah urutan 8 bit. Karakter ASCII menggunakan satu byte memori (8 bit). Di bawah ini adalah tabel yang menjelaskan satuan volume data (Tabel 1).

Power

Approximate value

Full name

Short name

10

1 Thousand

1 Kilobyte

1 KB

20

1 Million

1 Megabyte

1 MB

30

1 Billion

1 Gigabyte

1 GB

40

1 Trillion

1 Terabyte

1 TB

50

1 Quadrillion

1 Petabyte

1 PB

Angka latensi yang harus diketahui setiap programmer

Dr. Dean dari Google mengungkapkan durasi operasi komputer pada umumnya pada tahun 2010 [1]. Beberapa angka sudah ketinggalan zaman karena komputer menjadi lebih cepat dan lebih bertenaga. Namun, angka-angka tersebut seharusnya masih dapat memberi kita gambaran tentang kecepatan dan kelambatan berbagai operasi komputer.

Operation name

Time

L1 cache reference

0.5 ns

Branch mispredict

5 ns

L2 cache reference

7 ns

Mutex lock/unlock

100 ns

Main memory reference

100 ns

Compress 1K bytes with Zippy

10,000 ns = 10 µs

Send 2K bytes over 1 Gbps network

20,000 ns = 20 µs

Read 1 MB sequentially from memory

250,000 ns = 250 µs

Round trip within the same datacenter

500,000 ns = 500 µs

Disk seek

10,000,000 ns = 10 ms

Read 1 MB sequentially from the network

10,000,000 ns = 10 ms

Read 1 MB sequentially from disk

30,000,000 ns = 30 ms

Send packet CA (California) ->Netherlands->CA

150,000,000 ns = 150 ms

Catatan

ns = nanosecond, µs = microsecond, ms = millisecond

1 ns = 10^-9 seconds

1 µs= 10^-6 seconds = 1,000 ns

1 ms = 10^-3 seconds = 1,000 µs = 1,000,000 ns

Seorang insinyur perangkat lunak Google menciptakan sebuah alat untuk memvisualisasikan angka-angka Dr. Dean. Alat tersebut juga mempertimbangkan faktor waktu. Gambar 2-1 menunjukkan angka latensi yang divisualisasikan per tahun 2020 (sumber gambar: materi referensi [3]).

../_images/figure-2-1-E4JWSLDE.svg

Gambar 1

Dengan menganalisis angka-angka pada Gambar 1, kami mendapatkan kesimpulan berikut:

  • Memori cepat, tetapi disk lambat.

  • Hindari pencarian disk jika memungkinkan.

  • Algoritma kompresi sederhana cepat.

  • Kompres data sebelum mengirimkannya melalui internet jika memungkinkan.

  • Pusat data biasanya berada di wilayah yang berbeda, dan membutuhkan waktu untuk mengirim data di antara keduanya.

Availability number Angka ketersediaan

Ketersediaan tinggi adalah kemampuan sistem untuk beroperasi secara terus-menerus dalam jangka waktu yang diinginkan. Ketersediaan tinggi diukur dalam persentase, dengan 100% berarti layanan yang memiliki 0 waktu henti. Sebagian besar layanan berada di antara 99% dan 100%.

Perjanjian tingkat layanan (SLA) adalah istilah yang umum digunakan untuk penyedia layanan. Ini adalah perjanjian antara Anda (penyedia layanan) dan pelanggan Anda, dan perjanjian ini secara formal mendefinisikan tingkat waktu aktif yang akan diberikan layanan Anda. Penyedia layanan cloud Amazon [4], Google [5], dan Microsoft [6] menetapkan SLA mereka pada 99,9% atau lebih. Waktu aktif secara tradisional diukur dalam angka sembilan. Semakin banyak angka sembilan, semakin baik. Seperti yang ditunjukkan pada Tabel 3, jumlah angka sembilan berkorelasi dengan perkiraan waktu henti sistem.

Availability %

Downtime per day

Downtime per week

Downtime per month

Downtime per year

99%

14.40 minutes

1.68 hours

7.31 hours

3.65 days

99.99%

8.64 seconds

1.01 minutes

4.38 minutes

52.60 minutes

99.999%

864.00 milliseconds

6.05 seconds

26.30 seconds

5.26 minutes

99.9999%

86.40 milliseconds

604.80

2.63 seconds

31.56 seconds

Contoh: Estimasi QPS dan kebutuhan penyimpanan Twitter

Harap dicatat bahwa angka-angka berikut hanya untuk latihan ini karena bukan angka sebenarnya dari Twitter.

Asumsi:

  • 300 juta pengguna aktif bulanan.

  • 50% pengguna menggunakan Twitter setiap hari.

  • Rata-rata pengguna memposting 2 tweet per hari.

  • 10% tweet berisi media.

  • Data disimpan selama 5 tahun.

Estimasi:

Estimasi kueri per detik (QPS):

  • Pengguna aktif harian (DAU) = 300 juta * 50% = 150 juta

  • QPS Tweet = 150 juta * 2 tweet / 24 jam / 3600 detik = ~3500

  • QPS Intip = 2 * QPS = ~7000

Kami hanya akan memperkirakan penyimpanan media di sini.

Rata-rata ukuran tweet:

  • tweet_id 64 byte

  • text 140 byte

  • media 1 MB

  • Penyimpanan media: 150 juta * 2 * 10% * 1 MB = 30 TB per hari

  • Penyimpanan media 5 tahun: 30 TB * 365 * 5 = ~55 PB

Tips

Estimasi perkiraan adalah tentang proses. Memecahkan masalah lebih penting daripada mendapatkan hasil. Pewawancara mungkin menguji kemampuan pemecahan masalah Anda. Berikut beberapa tips yang bisa diikuti:

Pembulatan dan Aproksimasi. Sulit untuk melakukan operasi matematika yang rumit selama wawancara. Misalnya, berapa hasil dari "99987 / 9,1"? Tidak perlu menghabiskan waktu berharga untuk menyelesaikan soal matematika yang rumit. Presisi tidak diharapkan. Gunakan angka bulat dan aproksimasi untuk keuntungan Anda. Soal pembagian dapat disederhanakan sebagai berikut: "100.000 / 10".

Tuliskan asumsi Anda. Sebaiknya tuliskan asumsi Anda untuk referensi nanti.

Beri label pada satuan Anda. Ketika Anda menulis "5", apakah itu berarti 5 KB atau 5 MB? Anda mungkin bingung dengan hal ini. Tuliskan satuannya karena "5 MB" membantu menghilangkan ambiguitas.

Estimasi perkiraan umum yang sering ditanyakan: QPS, QPS puncak, penyimpanan, cache, jumlah server, dll. Anda dapat berlatih perhitungan ini saat mempersiapkan wawancara. Latihan menjadikan sempurna.

Selamat telah mencapai tahap ini! Sekarang, beri tepuk tangan untuk diri Anda sendiri. Kerja bagus!

Referensi

[1] J. Dean.Google Pro Tip: Use Back-Of-The-Envelope-Calculations To Choose The Best Design: http://highscalability.com/blog/2011/1/26/google-pro-tip-use-back-of-the-envelope-calculations-to-choo.html

[2] System design primer: https://github.com/donnemartin/system-design-primer

[3] Latency Numbers Every Programmer Should Know: https://colin-scott.github.io/personal_website/research/interactive_latency.html

[4] Amazon Compute Service Level Agreement: https://aws.amazon.com/compute/sla/

[5] Compute Engine Service Level Agreement (SLA): https://cloud.google.com/compute/sla

[6] SLA summary for Azure services: https://azure.microsoft.com/en-us/support/legal/sla/summary/