Node.js typed array'lar milyon satırlık raporda JSON.parse'ı geçti ve OOM çökmelerine son verdi

Süreci sürekli öldüren bir sorgu

Oizom'daki bir hava kalitesi izleme arka ucu 2 GB'lık bir DigitalOcean droplet'inde çalışıyordu ve yaklaşık bir milyon sensör okumasını kapsayan rapor sorguları süreci bellek yetersizliği hatalarıyla çöktürüyordu. Şirketin yazılım ekibinin başındaki Panth Patel'in dev.to'daki yazısına göre her okuma; cihaz tanımlayıcısı, epoch timestamp, CO2 veya PM2.5 gibi sayısal ölçümlerin bir haritası ve konum veya firmware gibi serbest biçimli etiketlerin bir haritası içeren küçük bir JSON tarzı nesneydi.

Gönderi patlamayı uygulama kodunda hiç görünmeyen üç maliyete bağlıyor. Böyle nesnelerde özellik erişimi, bilinen bir offsette tek bir okuma yerine referans zincirlerini izliyor. Her nesnenin arkasında bir hash tablosu var, dolayısıyla on anahtarlı bir milyon nesne üzerinden tek bir geçiş, kabaca on milyon hash'li arama anlamına geliyor. Ve her nesne izlenen bir tahsis olduğundan çöp toplayıcı sorgunun kendisinden daha fazla çalışıyor, heap'e dağılmış boxed sayılarla.

Okumaları bir ızgara gibi yerleştirmek

Gönderideki temel fikir, timestamp'leri bir eksene, ölçülen büyüklükleri diğer eksene koyarak tüm veri setini bir sayı dikdörtgenine — özünde seyrek bir görüntüye — dönüştürmek ve tanıdık satır çarpı genişlik artı sütun hesabıyla indekslemek.

Depolama şöyle bölünüyor:

• Tüm ondalık değerleri tutan tek bir Float64Array, satır çarpı sütun boyutunda.
• Etiket değerleri için bir Int32Array; burada her girdi benzersiz dizeler sözlüğüne bir indeks. Şehir adı gibi etiketler neredeyse her satırda tekrarlandığından onları bir milyon kez saklamaya gerek yok.
• Üç küçük eksen dizisi: timestamp'ler, gaz adları ve etiket adları.

Boşlukları sentinel değerler işaretliyor: sıfır timestamp kullanılmayan bir satırı, boş dize kullanılmayan bir sütunu gösteriyor. Bir hücreyi okumak düz offset aritmetiği ve tüm tablo bir milyon nesne yerine tek bir tahsis.

Tek bir sınıf ham buffer'ları saklıyor

Buffer'lar doğrudan kullanmak için kullanışsız olduğundan her şey bir DataPointTable sınıfının arkasında duruyor. Tablo oluşturma, JSON'dan yükleme ve ArrayBuffer'dan canlandırma için factory metotlar; eksen aramaları ve mutasyon yardımcıları; hücre get ve set; ad-değer çiftleri veren satır iterasyonu; ayrıca toJSON, tarayıcıya göndermek için toBuffer, kullanılmayan satır ve sütunları geri kazanan bir compress adımı ve bir stats metodu sunuyor. Kod tabanının geri kalanının altında bir Float64Array olduğunun farkında olması gerekmiyor.

Birinci sürüm doğruydu — ve 8 kat yavaştı

İlk uygulama satırları timestamp'e göre azalan sırada tutuyordu, çünkü sorgular zaman sırası istiyor. Bu da eklemeyi pahalı hale getiriyordu: bir satır eklemek yerini bulmayı ve aradaki her şeyi kaydırmayı, bir sütun eklemek her satırdaki hücreleri taşımayı gerektiriyordu. Patel yeniden tahsini yumuşatmak için bir seferde beş yedek satır ve sütun aşırı tahsis etti. Tüm testler geçti — JSON dönüşümü üzerinden gidiş-dönüşler dahil — ve bir milyon nokta ve otuz sütunda süreç hiçbir zaman belleği tüketmedi; nesne sürümü bu boyutta her zaman tüketiyordu. Ancak yükleme, JSON.parse'tan sekiz kat daha yavaş çıktı.

Teşhis: sorun typed array'larda değil, kaydırmadaydı. İş yükü satırları veritabanından yükleyip dönüştürüyor ve yolluyor; bir tablonun ortasına neredeyse hiç ekleme yapmıyor. İkincil iki maliyet de ele alındı ya da çöpe atıldı — sütun adlarını çözme her hücre yazımında doğrusal taramadan kabaca otuz eksen girdisi üzerinden bir Map'e geçti ve sıralı timestamp'ler üzerinde ikili aramanın hiçbir zaman önemi olmadığı ortaya çıktı.

Sıralama gereksinimini bırakmak

Yeniden yazım satırları sıralı tutmayı tamamen bırakıyor. Tablo yerine kullanılmayan satır ve sütun indekslerinin boş listelerini, ayrıca timestamp'leri satırlara ve gaz adlarını sütunlara bağlayan iki Map tutuyor. Bir timestamp eklemek ya bir Map isabeti ya da boş listeden bir pop; kaldırmak satırı sıfırlayıp indeksini listeye geri veriyor. Sorgular okumadan önce sonuç boyutunu bildiğinden tablo baştan doğru boyutlandırılıyor ve büyüt-kopyala dalı neredeyse hiç çalışmıyor. Sıralama yalnızca okunduğu yerde geri kazanılıyor: times metodu canlı timestamp'leri topluyor ve her eklemede kaydırmak yerine sorgu başına bir kez sıralıyor.

Gönderide bildirildiği üzere, JSON nesneleri 2 GB'lık droplet'te belleği tüketti, birinci sürüm hiç tüketmedi ama JSON.parse'tan 8 kat yavaştı ve ikinci sürüm belleği düz tuttu ve JSON.parse'ı açıkça geçti.

Neden önemli

Bu, büyük satır sayılarında bir milyon küçük nesnenin yükünün — hash aramaları, referans kovalamaca, çöp toplama baskısı — verinin kendi boyutunu gölgede bırakabileceğinin ve bitişik typed-array depolamasının dize interning ile birleşiminin hesabı tamamen değiştirdiğinin somut bir kanıtı. Aynı zamanda bir veri yapısını erişim düzenine uyarlama dersi: ilk sürüm, okuma zamanı bir kaygıya hizmet etmek için her yüklemede sıralı ekleme bedelini ödedi ve hızlı sürümü hızlı yapan da bu tek varsayımın kaldırılmasıydı. Büyük tablosal sonuç kümeleri oluşturan herhangi bir Node.js servisi için bu desen — sütunsal buffer'lar, eksik hücreler için sentinel'ler, sınırda tek bir sarmalayıcı sınıf — doğrudan yeniden kullanılabilir ve gönderiye yapıyı ele alan dört bölümlük bir video serisi eşlik ediyor.