<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Mustafa Güneş on Medium]]></title>
        <description><![CDATA[Stories by Mustafa Güneş on Medium]]></description>
        <link>https://medium.com/@mgunes17?source=rss-a8a8c4718264------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/2*uXHhbfbz5mAJAlPsJertoQ.jpeg</url>
            <title>Stories by Mustafa Güneş on Medium</title>
            <link>https://medium.com/@mgunes17?source=rss-a8a8c4718264------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 16:21:31 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@mgunes17/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Skip List Veri Yapısı]]></title>
            <link>https://medium.com/@mgunes17/skip-list-veri-yap%C4%B1s%C4%B1-3814686e50dc?source=rss-a8a8c4718264------2</link>
            <guid isPermaLink="false">https://medium.com/p/3814686e50dc</guid>
            <category><![CDATA[veri-yapıları]]></category>
            <category><![CDATA[data-structures]]></category>
            <category><![CDATA[skip-list]]></category>
            <dc:creator><![CDATA[Mustafa Güneş]]></dc:creator>
            <pubDate>Sun, 16 Jun 2024 11:12:39 GMT</pubDate>
            <atom:updated>2024-07-17T17:52:38.566Z</atom:updated>
            <content:encoded><![CDATA[<p>Redis’in veri yapılarından biri olan Sorted Set yapısı sıkça kullandığım veri yapılarından biriydi. Nasıl çalıştığını anlamak için araştırma yapınca olasılıksal veri yapılarından (probabilistic data structures) Skip List (Atlamalı Liste) veri yapısının üzerine kurgulandığını gördüm ve bu veri yapısını araştırmaya başladım.</p><p>Skip List veri yapısını William Pugh, 1989 yılında yazdığı <a href="https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf">“Skip Lists: A Probabilistic Alternative to Balanced Trees”</a> isimli makale ile Balanced Tree’ lere alternatif olarak önermiştir. Detaylı açıklamasına ise<a href="https://api.drum.lib.umd.edu/server/api/core/bitstreams/17176ef8-8330-4a6c-8b75-4cd18c570bec/content"> A Skip List Cookbook</a> yazısında yer vermiştir.</p><p>Bir Linked List yapısında arama işlemi sıralı yapıldığından dolayı verimli değildir ancak arama sonuçlandıktan sonra yapılan ekleme veya silme işlemi oldukça hızlı gerçekleştirilir. Balanced Tree veri yapısı da benzer bir hız vaat etse de, özellikle yeniden dengeleme (rebalance) akışı sebebiyle, geliştirilmesi daha karmaşıktır.</p><p>Skip List veri yapısı temelde Linked List(ler) üzerine kurgulanmıştır. Linked List’ in aksine her eleman sadece kendinden sonrakini elamanı göstermez, daha ilerideki elemanlara da erişim olanağı sağlar (express lane, teleport gibi ifadeler de kullanılıyor) ya da daha doğru bir ifadeyle sağlayabilir.</p><h4>Olasılıksal Veri Yapıları</h4><p>Olasılıksal veri yapılarının oluşturulması veya üzerlerinde arama gibi işlemlerin yapılması olasılıksal olarak değişkenlik gösterir. Bu yüzden bu veri yapılarının bir “hata payı” olduğunu söyleyebiliriz.</p><p>Olasılıksal veri yapılarında bilinen en yaygın örnek <a href="https://en.wikipedia.org/wiki/Bloom_filter">Bloom Filter</a> veri yapısıdır. Hash fonksiyonları ile çalışan Bloom Filter, eğer bir değerin var olmadığını söylüyorsa bu kesinlikle doğrudur. Ancak eğer var olduğunu söylüyorsa bu yanlış olabilir, elimizdeki değer ile Bloom Filter’ ın bize getirdiği değeri birebir kıyaslamak durumunda oluruz. Bloom Filter, özellikle büyük veri kümelerinde çalışırken ihtiyacımız olan bellek optimizasyonunu yapmak pahasına doğruluğundan ödün verir.</p><p>Normalde bir veri yapısı aynı verilerle ve parametrelerle farklı zamanlarda oluşturulduğunda ortaya aynı sonuç çıkar. Rastgelelik içeren veri yapıları için ise bu durum böyle değildir. Rastgelelik fonksiyonu farklı zamanlarda farklı sonuçlar üreteceğinden veri yapısında oluşacak ilişkileri net olarak söylemek mümkün değildir.</p><p>Skip List yapısında kurulacak bağlantılar belirli bir olasılık dahilinde gerçekleşir. Bu olasılık da her eleman için rastgele olarak belirlenen bir seviye (yükseklik) dahilinde olur. Her eleman, kendinden sonraki elemanlardan, kendi ile aynı yüksekliğe sahip ilk elemana erişime sahiptir.</p><h4>Bir Örnek Üzerinden Skip List</h4><p>Örneğin 2,3,5,6,7,8,10,12 elemanlarından oluşan bir liste düşünelim. Bu liste ile oluşturulabilecek bir Skip List örneği aşağıdaki gibidir. Her eleman için yükseklik değeri rastgele belirlenmiştir (Belirlenme şekline ayrıca değineceğiz.)</p><p>Görselden de anlaşılabileceği üzere, Skip List yapısının aslında bir Linked List grubunu barındırdığını söyleyebiliriz. En alt seviyede tüm elemanların yer aldığı Linked List yapısı bulunurken, daha üst seviyelerde rastgelelik yardımıyla oluşturulmuş Linked List’ ler bulunmaktadır. Başlangıç noktasından (2 ve 3&#39;e uğramadan) doğrudan 5&#39;e, oradan da (6 ve 7&#39;ye uğramadan) doğrudan 8&#39;e gidebilmekteyiz. Bu hızlı erişim yolları (Express Lane, Teleport gibi ifadelerle de tanımlanabiliyor) Skip List veri yapısının temelini oluşturmaktadır.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*X3SXnYYA4-F_t7XG8-7DCw.png" /><figcaption>(2,3,5,6,7,8,10,12) elemanları için bir Skip List Örneği</figcaption></figure><h3>Veri Yapısının Bileşenleri</h3><p>Skip List Veri yapısını ifade etmek için 2 temel komponent ihtiyacımız bulunmaktadır. Bunların ilki veri yapısının genel bilgilerini tutarken, ikincisi her bir düğüm (node) için gerekli bilgileri tutmaktadır.</p><pre>const (<br> MaxLevel = 10 // bir düğümün erişebileceği maksimum yükseklik<br> P        = 0.5 // her bir deneme için, düğümün 1 seviye yükselme ihtimali<br>)<br><br>type SkipList struct {<br> topLevel int // mevcuttaki en yüksek seviye<br> head     *Node // başlangıç noktası<br>}<br><br>type Node struct {<br> data  int // saklanan bilgi<br> level int // seviyesi / yüksekliği<br> next  []*Node //komşuları, her seviye için bir sonraki düğümü belirtir<br>}</pre><p>Detaylı kod örneği yazının en sonunda yer almaktadır.</p><h3>Arama</h3><p>Bir elemanı ararken başlangıç noktasının en üst seviyesinden başlayıp sağdaki değeri kontrol ediyoruz. Eğer sağ taraf bir değere karşılık gelmiyorsa (None ise) bulunduğumuz noktadan 1 alt seviyeye inip tekrar sağdaki değeri kontrol ediyoruz. Hareket etme olanağımız kalmadıysa veya sağdaki değer aradığımız değerden büyük ise aranan değerin listede yer almadığını söyleyebiliriz.</p><p>Bu liste üzerinde 9 değerini arayalım:</p><ul><li>Başlangıç / Head noktasının en üst seviyesinden başlıyoruz.</li><li>Bir sonraki noktamız olan 5, aradığımız 9 değerinden daha küçük olduğundan 5 değerine geçiyoruz.</li><li>5 elemanının en yüksek seviyesi liste sonunu / None değerini gösterdiğinden bir seviye aşağı iniyoruz.</li><li>5 elemanının bir alt yükseklikte gösterdiği bir sonraki değer olan 8, aradığımız 9 değerinden daha küçük olduğundan 8 değerine geçiyoruz.</li><li>8 elemanı en yüksek seviyesi liste sonunu / None değerini gösterdiğinden bir seviye aşağı iniyoruz.</li><li>8 elemanı bu seviyede 10 değerini göstermektedir. Sağa ilerleyemiyoruz, 9 değerinin 1. seviyede 8 değeri tarafından gösterilme ihtimali nedeniyle 1 seviye daha aşağı iniyoruz.</li><li>8 değeri ilk seviyede yine 10 değerini göstermektedir. Sağa ve aşağı yönlü hareket edebileceğimiz bir yer olmadığından, 9&#39;un listemizde olmadığını söyleyebiliriz.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wcN5gEcqy36szMOY1xxQjw.png" /><figcaption>(2,3,5,6,7,8,10,12) elemanlarını içeren bir Skip List’te 9 değerini arama</figcaption></figure><p>Sadece 5 ve 8 elemanlarını ziyaret ederek 9 değerinin listede yer almadığını söyleyebildik. Eğer Linked List kullanıyor olsaydık 2,3,5,6,7 ve 8 değerleri üzerinden ilerlemek zorunda olacaktık.</p><h3>Ekleme</h3><p>Ekleme yapmak için ekleyeceğimiz değerin yüksekliğine karar vermeliyiz. Bu karar verme işlemi için çeşitli rastgelelik yöntemleri olsa da en çok kullanılan yöntem yazı-tura atma yöntemidir (coin-flipping).</p><p>Tura gelene kadar veya maksimum yüksekliğe erişene kadar yazı tura atıyoruz ve arka arkaya kaç defa yazı geldiyse, yeni elemanımızın yüksekliği o oluyor.</p><h4>Maksimum Yüksekliğin Belirlenmesi</h4><p>Maksimum yükseklik, tüm olasılıklar gerçekleşse de bir düğümün erişebileceği maksimum yüksekliği belirtir. Bir skip list için maksimum yüksekliği belirlemek için şu formül kullanılabilir:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/140/1*rZ2DkFMb333QKz9YssLdEg.png" /></figure><p>p, yeni bir yüksekliğe karar verme ihtimalimizi belirtir, yazı-tura atma işleminde bu değer 0.5 olur. n ise Skip List için belirlediğimiz (beklentimiz olan) toplam eleman sayısını belirtir. Yazı-tura yöntemiyle 1000 elemanlı olacağını düşündüğümüz bir Skip List veri yapısının maksimum yüksekliği için 10 değeri makul durmaktadır.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/426/1*-6nMui6GHvFugPJlNfFNZQ.png" /></figure><h4>Ekleme İşleminin Adımları</h4><p>Ekleme işlemi öncesinde, yeni elemanımızı ekleyebileceğimiz noktaları tutmak için bir liste tutmaya ihtiyacımız var. Yeni elemanı ekleyeceğimiz yeri bulmaya çalışırken, her seviyede hangi nokta ile bağlantı kuracağımızı bu liste sayesinde takip edeceğiz. Listenin boyutu maksimum yükseklik kadar olacak ve aramaya en üst seviyeden başladığımız için listeyi de sondan geriye doğru dolduruyor olacağız.</p><p>Yukarıdaki örnekteki Skip List veri yapısına 9 değerine ekleyelim:</p><ul><li>Başlangıç noktasının en yüksek seviyesinden (4) başlıyoruz, bir sonraki noktamız 5. Ekleyeceğimiz 9 değeri 5&#39;ten büyük olduğu için buraya ilerliyoruz.</li><li>5&#39;in bir sonraki noktası ise None. Ekleyeceğimiz değerin yerini bulmak için bir alt seviyeye inmemiz gerek. Aşağı inmeden önce listenin 4. elemanı olarak 5&#39;i ekliyoruz.</li><li>5 node’u, 3. seviyesinde 8&#39;i gösteriyor. Bu değer aradığımız 9 değerinden büyük olduğu için buraya ilerliyoruz.</li><li>8 değerinin 3. seviye yüksekliği None değerine çıkıyor. Yani 9&#39;u buraya eklememiz mümkün. Listenin 3. elemanı olarak 8 node’ unu ekliyoruz.</li><li>8 değerinin 2. seviye yüksekliği 10 değerini gösteriyor. 9 değeri buraya da eklenebilir. Listenin 2. elemanı olarak yine 8&#39; i ekliyoruz.</li><li>Bu seviyede de 8 değeri 10 değerini gösteriyor. Bu nokta da bizim için 9 değerini ekleyebileceğimiz bir nokta. Listenin 1. elemanı olarak yine 8&#39;i ekliyoruz.</li></ul><p>Artık sağa veya aşağı yönlü hareket edebileceğimiz bir nokta kalmadığından bu döngüyü sonlandırıyoruz. Listeye eklediğimiz bilgiler ise sıralı olarak şu şekilde oldu: 1, 2 ve 3. seviye yükseklikler için 8, 4. seviye yükseklik için ise 5.</p><p>Listenin ilk elemanı bize şunu söylüyor: 8&#39;in 1. seviye yüksekliği kimi gösteriyorsa artık 9&#39;un 1. seviye yüksekliği o değeri göstersin. 8&#39; in 1. seviye yüksekliği ise 9&#39;u göstersin.</p><p>Eğer 9 için belirlenen yükseklik 1 ise, listenin geri kalanını kullanmamıza gerek kalmıyor. Diğer taraftan 9&#39;un yüksekliği maksimum ise listede yer alan bütün değerleri kullanarak aynı işlemi yapmamız gerekir. Bu işlem ise göründüğü üzere Linked List’ e yeni eleman eklemek ile eşdeğerdir.</p><p>9&#39; un maksimum yüksekliğe (4) eriştiği ve yüksekliğinin 1 olduğu 2 farklı örnek şu şekildedir.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*CLugnLnvDvVTy9-Y25hxvA.png" /><figcaption>Yeni eklenen 9 değerinin yükseliği 4 olursa oluşacak yeni bağlantılar kırmızı ile gösterilmiştir</figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5Xf2kTZLNAbYEFqPdFg_Vw.png" /><figcaption>Yeni eklenen 9 değerinin yükseliği 1 olursa oluşacak yeni bağlantılar kırmızı ile gösterilmiştir</figcaption></figure><h3>Silme</h3><p>Skip List veri yapısının bir eleman silme işlemi, ekleme işlemiyle benzerdir. Sileceğimiz elemanı bulana kadar her seviyede takip edeceğimiz bağlantı noktasını bir listeye ilerleyerek ilerliyoruz. Silmek istediğimiz değeri bulduğumuzda ise bağlantıları güncelliyoruz</p><h4>Silme İşleminin Adımları</h4><p>Bir önceki bölümde 9&#39;un yüksekliğinin 1 olduğu örnek üzerinden, 10 değerini silelim:</p><ul><li>Başlangıç noktasının en üst seviyesinden (4) başlıyoruz. Sağ taraftaki değer None olduğu için bir alt seviyeye iniyoruz. Listemizin 4. sırasına 5 değerini ekliyoruz</li><li>Bir alt seviyede, 5 değeri 8 değerini gösteriyor. Silmek istediğimiz değer olan 10, 8&#39;in ilerisinde olacağı için bu noktaya ilerliyoruz.</li><li>8 değeri 3. seviyesinde None değerini gösteriyoruz. Listemizin 3. elemanı olarak 8 değerini ekleyip bir alt seviyeye iniyoruz.</li><li>8 değeri 2. seviyesinde silmek istediğimiz değer olan 10&#39;u gösteriyor. Listemizin 2. elemanı olarak yine 8&#39;i ekleyip bir seviye aşağı iniyoruz.</li><li>İlk seviyede 8&#39;in gösterdiği değer 9 değeri silmek istediğimiz değerden küçük olduğu için buraya ilerliyoruz.</li><li>9&#39;un ilk seviye gösterdiği değer 10. Listenin 1. elemanı olarak 9&#39;u ekliyoruz ve hareket alanımız kalmadığı için döngüyü sonlandırıyoruz.</li></ul><p>10 değerinin yüksekliği 2 olduğu için sadece 2 seviyedeki bağlantıları güncelleyeceğiz. Listemizin ilk elemanı olarak 9, ikinci elemanı olarak ise 8 vardı. Artık 9, 10&#39;un ilk seviyede gösterdiği değeri gösterirken, 8 ise 10&#39;un ikinci seviyede gösterdiği değeri gösterecek.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*8wLvOsJlXmIdBPMa8VL-Yg.png" /><figcaption>10 değeri silindikten sonra oluşacak yeni bağlantılar kırmızı ile gösterilmiştir</figcaption></figure><h3>Karmaşıklık</h3><p>Skip List veri yapısında arama, ekleme ve silme işlemlerinin zaman karmaşıklığı (time complexity) ortalamada (average case) O(logN)’ dir. Rastgeleliğin bizi götürebileceği en kötü nokta olan Skip List yapısındaki tüm elemanların yüksekliğinin aynı olması durumunda ise (bu durumda elimizde bir Linked List yapısı oluyor) karmaşıklık O(N) olur.</p><p>Bellek karmaşıklığı (space complexity) ise ortalamada O(n) iken en kötü durumda ise O(NlogN)’ dir.</p><p>Karmaşıklık hesaplamalarının detaylarına MIT’ nin <a href="https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/resources/mit6_046js15_lec07/">ilgili açık kaynak dersinden</a> erişebilirsiniz.</p><h3>Perfect Skip List</h3><p>Perfect ya da ideal Skip List olarak adlandırılan yapı, bağlantıların (hızlı erişim noktalarının) en optimum şekilde oluşturulduğu Skip List yapısıdır. Rastgelelik fonksiyonu ile ideal bir Skip List oluşturmak çok küçük bir ihtimal olduğundan, ideal bir Skip List yapısı static olarak oluşturulur. Ancak unutulmamalıdır ki, bu Skip List üzerinde yapacağımız bir ekleme ya da silme işlemi, Skip List’ i ideal olmaktan çıkarır.</p><p>2,3,5,6,7,8,9,12,13,15,17,19,20,22,23 elemanları ile ideal bir Skip List’i şu şekilde oluşturabiliriz:</p><ul><li>Sırasıyla ve ikinci elemandan başlayarak, her iki elemandan birinin yüksekliğini 1 artırıyoruz. 3,6,8,12,15,19 ve 22 elemanlarının yüksekliği 2 oluyor.</li><li>Yüksekliği 2 olan elemanların, sırasıyla ve yine ikinci elemandan başlayarak, her ikisinden birinin yüksekliğini 1 artırıyoruz. 6, 12 ve 19&#39;un yüksekliği 3 oluyor.</li><li>Aynı şekilde yüksekliği 3 olan elamanların her ikisinden birinin yüksekliğini 1 artırıyoruz böylece 12&#39;nin yüksekliği 4 oluyor.</li><li>Elimizdeki son listede tek eleman kaldığı için döngüyü bitiriyoruz.</li></ul><p>Bu yöntem ile sabit bir veri setinde sadece arama yapmak için ideal bir yapı elde etmiş oluruz.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*1ixGIKTxV4Qvnp58E9P9rg.png" /><figcaption>Örneğin yer aldığı içeriğe buradan erişebilirsiniz: <a href="https://www.youtube.com/watch?v=NDGpsfwAaqo">https://www.youtube.com/watch?v=NDGpsfwAaqo</a></figcaption></figure><h3>Özet</h3><p>William Pugh 1989 yılında yayımladığı makale ile, Linked List veri yapısı üzerine kurgulanmış ve arama konusunda iyi performans sunan, aynı zamanda benzer problemlerin çözümünde kullanılabilecek Balanced Tree’ lere nazaran daha basit bir yapı olan Skip List veri yapısını tanıttı.</p><p>Skip List veri yapısı rastgelelik içeren, olasılıksal bir veri yapısı olup içerdiği rastgelelik her elaman için farklı seviyede bir yüksekliğin tanımlanmasında kullanılır. Rastgelelik dağılımı ile bir Linked List üzerine, daha hızlı hareket etmemizi (atlamalar yapmamızı) sağlayan başka Linked Listler kurgulayarak işlemlerimizi daha hızlı gerçekleştirebiliyoruz.</p><h3>References</h3><ul><li><a href="https://jothipn.github.io/2023/04/07/redis-sorted-set.html">Redis Sorted Sets — Under the Hood</a></li><li><a href="https://15721.courses.cs.cmu.edu/spring2018/papers/08-oltpindexes1/pugh-skiplists-cacm1990.pdf">William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Trees (Skip List yapısının tanıtıldığı makale)</a></li><li><a href="https://api.drum.lib.umd.edu/server/api/core/bitstreams/17176ef8-8330-4a6c-8b75-4cd18c570bec/content">A Skip List Cookbook</a></li><li><a href="https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/resources/lecture-12-skip-lists/">Introduction To Algorithms, MIT Open Course, Lecture 12: Skip Lists</a></li><li><a href="https://cmps-people.ok.ubc.ca/ylucet/DS/SkipList.html">Skip List veri yapısının nasıl çalıştığını, sizin gireceğiniz değerlere göre, görselleştiren bir web sitesi</a></li><li><a href="https://www.amazon.com.tr/Data-Structures-Fun-Way-QuadTrees/dp/1718502605">Data Structures The Fun Way</a>, Chapter 14, by Jeremy Kubica</li><li><a href="https://www.youtube.com/watch?v=NDGpsfwAaqo%C3%BC">Skip Lists by Algorithms Lab</a> on YouTube</li><li>Kod Örneği</li></ul><pre>package main<br><br>import (<br> &quot;fmt&quot;<br> &quot;math/rand&quot;<br>)<br><br>const (<br> MaxLevel = 10<br> P        = 0.5<br>)<br><br>type SkipList struct {<br> topLevel int<br> head     *Node<br>}<br><br>type Node struct {<br> data  int<br> level int<br> next  []*Node<br>}<br><br>func NewSkipList() SkipList {<br> return SkipList{<br>  head:     NewNode(0, MaxLevel),<br>  topLevel: 1,<br> }<br>}<br><br>func (skipList *SkipList) Search(target int) bool {<br> current := skipList.head<br><br> for level := skipList.topLevel; level &gt;= 0; level-- {<br>  for current.next[level] != nil &amp;&amp; current.next[level].data &lt; target {<br>   current = current.next[level]<br>  }<br> }<br><br> result := current.next[0]<br> return result != nil &amp;&amp; result.data == target<br>}<br><br>func (skipList *SkipList) Add(newData int) {<br> current := skipList.head<br> list := make([]*Node, MaxLevel)<br><br> for i := skipList.topLevel - 1; i &gt;= 0; i-- {<br>  for current.next[i] != nil &amp;&amp; current.next[i].data &lt; newData {<br>   current = current.next[i]<br>  }<br>  list[i] = current<br> }<br><br> newLevel := randomLevel()<br> if newLevel &gt; skipList.topLevel {<br>  for i := skipList.topLevel; i &lt; newLevel; i++ {<br>   list[i] = skipList.head<br>  }<br><br>  skipList.topLevel = newLevel<br> }<br><br> newNode := NewNode(newData, newLevel)<br> for i := 0; i &lt; newLevel; i++ {<br>  newNode.next[i] = list[i].next[i]<br>  list[i].next[i] = newNode<br> }<br>}<br><br>func randomLevel() int {<br> level := 1<br> for rand.Float64() &lt; P &amp;&amp; level &lt; MaxLevel {<br>  level++<br> }<br><br> return level<br>}<br><br>func NewNode(data, level int) *Node {<br> return &amp;Node{<br>  data:  data,<br>  level: level,<br>  next:  make([]*Node, level),<br> }<br>}<br><br>func (skipList *SkipList) Delete(removedData int) bool {<br> current := skipList.head<br> list := make([]*Node, MaxLevel)<br><br> for i := skipList.topLevel - 1; i &gt;= 0; i-- {<br>  for current.next[i] != nil &amp;&amp; current.next[i].data &lt; removedData {<br>   current = current.next[i]<br>  }<br>  list[i] = current<br> }<br><br> result := current.next[0]<br> if result == nil || result.data != removedData {<br>  fmt.Println(&quot;No data to remove:&quot;, removedData)<br>  return false<br> }<br><br> for i := 0; i &lt; result.level; i++ {<br>  list[i].next[i] = result.next[i]<br> }<br><br> for skipList.topLevel &gt; 1 &amp;&amp; skipList.head.next[skipList.topLevel-1] == nil {<br>  skipList.topLevel--<br> }<br><br> fmt.Println(&quot;Data removed:&quot;, removedData)<br> return true<br>}<br><br>func (skipList *SkipList) Print() {<br> for i := MaxLevel - 1; i &gt;= 0; i-- {<br>  current := skipList.head<br>  fmt.Printf(&quot;Level %d: &quot;, i)<br>  for current != nil {<br>   if current == skipList.head {<br>    fmt.Printf(&quot;Head -&gt; &quot;)<br>   } else {<br>    fmt.Printf(&quot;%d -&gt; &quot;, current.data)<br>   }<br>   current = current.next[i]<br>  }<br>  fmt.Println(&quot;None&quot;)<br> }<br> fmt.Println()<br> fmt.Println()<br>}<br><br>func main() {<br> sl := NewSkipList()<br> sl.Add(1)<br> sl.Add(2)<br> sl.Add(11)<br> sl.Add(23)<br> sl.Add(47)<br> sl.Add(49)<br> sl.Add(156)<br> sl.Print()<br><br> fmt.Println(&quot;Searching for 13... &quot;, sl.Search(13))<br> fmt.Println(&quot;Searching for 200... &quot;, sl.Search(200))<br><br> fmt.Println(&quot;Searching for 156... &quot;, sl.Search(156))<br> sl.Delete(156)<br> sl.Delete(156)<br> fmt.Println(&quot;Searching for 156... &quot;, sl.Search(156))<br><br> sl.Print()<br><br> sl.Delete(11)<br> sl.Print()<br> fmt.Println(&quot;Searching for 11... &quot;, sl.Search(11))<br><br> sl.Add(11)<br> fmt.Println(&quot;Searching for 11... &quot;, sl.Search(11))<br>}</pre><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=3814686e50dc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Using HTTP Cache For Chart Data]]></title>
            <link>https://engineering.getmidas.com/using-http-cache-for-chart-data-814251c0b2d2?source=rss-a8a8c4718264------2</link>
            <guid isPermaLink="false">https://medium.com/p/814251c0b2d2</guid>
            <category><![CDATA[cache-control]]></category>
            <category><![CDATA[graphql]]></category>
            <category><![CDATA[fiber]]></category>
            <category><![CDATA[http-cache]]></category>
            <dc:creator><![CDATA[Mustafa Güneş]]></dc:creator>
            <pubDate>Thu, 16 May 2024 12:59:23 GMT</pubDate>
            <atom:updated>2024-06-03T07:24:19.252Z</atom:updated>
            <content:encoded><![CDATA[<h3>Introduction</h3><p>There are various types of charts that show the prices of investment instruments, such as line, bar, and candlestick charts. With these charts, we can display the price data of an investment instrument over different time intervals. The price data of an investment instrument changes over time, but the prices that occurred in the past are fixed. Therefore, if we have some of the points that make up the chart data, it is sufficient to obtain only the new points instead of trying to retrieve them all again.</p><p>The Midas application contains chart data for various investment instruments. This data is acquired from a data provider at the source, then processed into a usable format and presented to the mobile application. To obtain chart data, requests sent from the mobile application pass through various layers, creating a load on the network. This network load can be reduced by caching the relevant data at different layers.</p><p>There are various applications that can be used for caching, such as <a href="https://redis.io/">Redis</a>, <a href="https://hazelcast.com/">Hazelcast</a> and <a href="https://memcached.org/">Memcached</a>; patterns like <a href="https://docs.aws.amazon.com/whitepapers/latest/database-caching-strategies-using-redis/caching-patterns.html">cache-aside and write-through</a>; eviction strategies like <a href="https://en.wikipedia.org/wiki/Least_frequently_used">LFU</a> and <a href="https://en.wikipedia.org/wiki/Page_replacement_algorithm#Least_recently_used">LRU</a>; and hundreds of libraries that can be additionally utilized. However, these topics are beyond the scope of this article.</p><p>The given examples are created using the technologies utilized within Midas. While the code snippets and diagrams reflect Midas’s approach, they do not exactly represent the operation of the live environment.</p><h3>Presenting Chart Data to the Mobile Application</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/895/1*vw7WTOcZrdHLZQCVp5f_qQ.png" /></figure><p>When requests from the mobile application pass through GraphQL and reach the price-api, they are fetched from Redis according to the request content. Fetched and transformed data is always ready in Redis.</p><p>With the PoC using HTTP Cache, two points were optimized: the communication between the Mobile Application and GraphQL and the communication between GraphQL and the price-api.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/414/1*7mRp47NVTDISDQoatp8Fkg.png" /></figure><p>The chart data has two characteristics:</p><ul><li><strong>TimeRange: </strong>Defines the start and end points of the chart.</li><li><strong>Interval:</strong> Determines the intervals at which the chart data points will be placed.</li></ul><p>For example, a chart with 3-month time range displays data from 3 months ago up to now at 12-hour intervals.</p><p>In chart data, information for the current or incomplete TimeRange is not yet included. The last point on the chart represents the most recent price at which the investment instrument was traded and changes in real-time.</p><pre>type TimeRange string<br><br>const (<br>    Intraday    TimeRange = &quot;INTRADAY&quot;<br>    Day         TimeRange = &quot;DAY&quot;<br>    Week        TimeRange = &quot;WEEK&quot;<br>    Month       TimeRange = &quot;MONTH&quot;<br>    ThreeMonths TimeRange = &quot;THREE_MONTH&quot;<br>    Year        TimeRange = &quot;YEAR&quot;<br>    FiveYears   TimeRange = &quot;FIVE_YEAR&quot;<br>)<br><br>var (<br> intervalMap = map[TimeRange]string{<br>  Intraday:    &quot;5m&quot;, // 5 minutes<br>  Day:         &quot;15m&quot;, //15 minutes<br>  Week:        &quot;1h&quot;, //1 hour<br>  Month:       &quot;4h&quot;, // 4 hours<br>  ThreeMonths: &quot;12h&quot;, // 12 hours<br>  Year:        &quot;1d&quot;, // 1 day<br>  FiveYears:   &quot;1w&quot;, // 1 week<br> }<br>)</pre><p>For example, if the current time is 09:32, it is possible to cache the daily chart data until 09:45 and the weekly chart data until 10:00.</p><p>Let’s see this calculation as code.</p><pre>func CalculateExpiration(timeRange charttime.TimeRange) time.Duration {<br>    now := timeUtils.TimeNow().UnixMilli()<br>    interval := timeRange.GetIntervalMs()<br>    mode := int64(math.Mod(float64(now), float64(interval)))<br><br>    expiresAt := time.Duration(interval-mode) * time.Millisecond<br>    if expiresAt &lt; time.Second {<br>       return time.Second<br>    }<br><br>    return expiresAt<br>}</pre><p>The function <strong>GetIntervalMs()</strong> returns the value of the Interval for the corresponding TimeRange in milliseconds. For example, for a 15-minute interval, this value is found to be 900.000 milliseconds.</p><p>We can explain what the code snippet does with a simple example. Let’s say I’m counting multiples of 10 and I currently have 42. First, let’s find out how much progress we’ve made from the current value. We can do this with the modulo operation. The operation <strong>42 % 10</strong> gives a result of 2. This means that instead of progressing by 10, I have only progressed by 2. By subtracting 2 from 10, we can find the needed value of 8. In this example, the value 42 represents the current Epoch time, while the value 10 represents the Interval. The resulting value of 8 indicates how long we can cache this data for.</p><h3>HTTP Caching</h3><p><a href="https://developer.mozilla.org/en-US/docs/Web/HTTP">HTTP (Hyper-Text Transfer Protocol)</a> is a protocol that enables communication between a server and a client using a request-response model. It carries information needed by applications we use but may not be meaningful to end-users in the Header fields. Header fields consist of key-value pairs.</p><p>We can specify how long a service making the request does not need to resend the same request by adding the previously calculated time to the HTTP’s Cache-Control header.</p><p>It is possible to specify whether a response can be cached using the Cache-Control header, how long it can be cached if cacheable and whether this information is private or public for the user.</p><p>For example, a header like the following indicates that the data is suitable for use by every user and can be cached for 597 seconds:</p><pre>Cache-Control: public, max-age=597</pre><p>The service fulfilling the request can indicate that the response is not suitable for caching, while the service sending the request can also specify that it does not want a cached response. For detailed information on header usage covering such scenarios, you can access it from <a href="https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching">here</a>.</p><p>The service sending the request can use the information that the response can be cached for 597 seconds to set and store the data with a TTL of 597 seconds in a distributed cache structure. Additionally, they can prevent new responses from being sent through the HTTP library they use.</p><h3>Fiber</h3><p>When developing web applications with the Go programming language, there are many libraries available for handling requests/responses over the HTTP protocol. <a href="https://docs.gofiber.io/">Fiber</a> is one of them. In line with HTTP conventions, Fiber enables us to take advantage of cache features.</p><pre>func ChartCacheMiddleware() func(c *fiber.Ctx) error {<br>    return cache.New(cache.Config{<br>       CacheControl: true,<br>       ExpirationGenerator: func(ctx *fiber.Ctx, _ *cache.Config) time.Duration {<br>          tr := charttime.TimeRange(ctx.Query(&quot;timeRange&quot;))<br>          return CalculateExpiration(tr)<br>       },<br>    })<br>}</pre><p>The above function calculates how long the cache will be valid by passing the timeRange parameter from the incoming request to the CalculationExpiration function shared at the beginning of the text.</p><p>After the first request, we will see the following in the response header:</p><pre>X-Cache: miss</pre><p>When we send the same request for the second time, the response header will include the following headers:</p><pre>Cache-Control: public, max-age=638<br>X-Cache: hit</pre><p>If the requesting service adds the following information to their header, Fiber will populate its cache but will not use the cached data to respond to the requesting service:</p><pre>Cache-Control: no-cache</pre><h3>GraphQL — RESTDataSource</h3><p>One query sent to GraphQL can result in GraphQL making multiple HTTP requests on the backend. The RESTDataSource structure used with Apollo GraphQL server provides a default cache structure that can be used throughout the lifecycle of a query. If the same investment instrument’s TimeRange chart data is requested twice within the same query, the default cache structure will be sufficient. However, our situation requires different users’ requests to use the same GraphQL cache.</p><p>To prevent creating a new in-memory cache structure for each incoming query, we can ensure that operations are performed through a shared HTTPCache object defined within a DataSource.</p><pre>class CryptoBaseAPI extends RESTDataSource {<br>  constructor(protected context: ExpressContextFunctionArgument) {<br>    super();<br>    this.baseURL = `${API_GATEWAY_BASE_URL}`;<br>  }<br>  //other methods<br>}</pre><pre><br>const httpCache = new HTTPCache();<br><br>class CryptoPriceApi extends CryptoBaseAPI {<br>  constructor(context: ExpressContextFunctionArgument) {<br>    super(context);<br>    this.baseURL = this.baseURL + `${PORT}${PATH_PREFIX}/${API_VERSION}`;<br>    this.httpCache = httpCache;<br>  }<br>  //other methods<br>}</pre><p><a href="https://www.apollographql.com/docs/apollo-server/data/fetching-rest/">RESTDataSource</a> supports browser-style caching, so there is no need for additional configuration regarding maxAge usage.</p><h3>GraphQL — CacheControl</h3><p>Apollo GraphQL Server provides a <a href="https://www.apollographql.com/docs/apollo-server/schema/directives/">Directive</a> structure for adding Cache-Control information to a response’s header. We can use this structure either statically or dynamically.</p><p>If you want to use the Directive statically, you can do it as follows:</p><pre>enum CacheControlScope {<br>    PUBLIC<br>    PRIVATE<br>}<br><br>directive @cacheControl(<br>    maxAge: Int<br>    scope: CacheControlScope<br>    inheritMaxAge: Boolean<br>) on FIELD_DEFINITION | OBJECT | INTERFACE | UNION<br><br>type Chart @cacheControl(maxAge: 600, scope: PUBLIC){<br>    maxAggregateCount: Int!<br>    intervalMs: Int!<br>    chartItems: [ChartItem!]!<br>}</pre><p>In the scenario we are discussing, we need to calculate the cache duration based on the current time. Therefore, we should do this separately for each request. We can proceed with the dynamic method by determining the maxAge information within the resolver.</p><pre>import { cacheControlFromInfo } from &#39;@apollo/cache-control-types&#39;;<br><br>//other code blocks<br><br>async chart(root, _, {dataSources}, info) {<br>  //retrieve chart<br>  const cacheControl = cacheControlFromInfo(info)<br>  const expiresAt: number = getExpiresAt()<br>  cacheControl.setCacheHint({ maxAge: expiresAt, scope: &#39;PUBLIC&#39; });<br>}</pre><p>If there are multiple maxAge values in the same response, the smallest one will be considered. For example, if we include data in the response that cannot be cached (maxAge=0) along with graphical data, the response will have maxAge=0. Similarly, if the scope=private information is provided in the response, the Cache-Control header will be set to “scope private” for the entire response. Therefore, it would be beneficial to separate the queries of the types we want to cache in GraphQL.</p><h4><strong>Summary</strong></h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/996/1*4tw619KchDjMHofQOCdJbA.png" /></figure><p>This article explains how to use the HTTP Cache method to optimize inter-service communication. First, it describes how a service developed with Go can use HTTP caching with the Fiber library. Then, it discusses how a service developed with Apollo GraphQL can use HTTP caching to reduce both outgoing requests to other services and incoming requests to itself.</p><p><strong>References</strong></p><ul><li><a href="https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching">https://developer.mozilla.org/en-US/docs/Web/HTTP/Caching</a></li><li><a href="https://httpwg.org/specs/rfc9111.html">https://httpwg.org/specs/rfc9111.html</a></li><li><a href="https://docs.gofiber.io/api/middleware/cache/">https://docs.gofiber.io/api/middleware/cache/</a></li><li><a href="https://www.apollographql.com/docs/apollo-server/api/plugin/cache-control/#using-the-plugin">https://www.apollographql.com/docs/apollo-server/api/plugin/cache-control/#using-the-plugin</a></li><li><a href="https://www.apollographql.com/docs/apollo-server/data/fetching-rest/">https://www.apollographql.com/docs/apollo-server/data/fetching-rest/</a></li><li><a href="https://www.apollographql.com/docs/apollo-server/performance/caching/">https://www.apollographql.com/docs/apollo-server/performance/caching/</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=814251c0b2d2" width="1" height="1" alt=""><hr><p><a href="https://engineering.getmidas.com/using-http-cache-for-chart-data-814251c0b2d2">Using HTTP Cache For Chart Data</a> was originally published in <a href="https://engineering.getmidas.com/">Midas Engineering</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Spring ile Transaction Yönetimi]]></title>
            <link>https://medium.com/@mgunes17/spring-ile-transaction-y%C3%B6netimi-4c768a000593?source=rss-a8a8c4718264------2</link>
            <guid isPermaLink="false">https://medium.com/p/4c768a000593</guid>
            <category><![CDATA[transactions]]></category>
            <category><![CDATA[spring-data]]></category>
            <category><![CDATA[veritabanı]]></category>
            <category><![CDATA[spring]]></category>
            <category><![CDATA[isolation-level]]></category>
            <dc:creator><![CDATA[Mustafa Güneş]]></dc:creator>
            <pubDate>Sun, 03 May 2020 03:23:56 GMT</pubDate>
            <atom:updated>2021-10-20T20:03:48.899Z</atom:updated>
            <content:encoded><![CDATA[<p><em>Veritabanları üzerinde transaction yönetimi yıllardır geliştiriciler için önemli bir konu olarak varlığını sürdürüyor. Günümüzde iş akışlarının neredeyse tamamının veritabanlarından çıkarılarak servis uygulamaları üzerinde çalıştığını düşündüğümüzde bunların yönetiminden veritabanı seviyesinde soyutlanmış olduğumuzu söyleyebiliriz . Spring gibi geliştirme süreçlerimizde sıkça kullandığımız frameworkler ile bu yönetimi nispeten daha kolay yapabiliyoruz. Ama öncesinde temel kavramları bilmeli, sonrasında ise kullandığımız kütüphane veya framework’ü çok iyi tanımalıyız.</em></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*6SBsCgqKYWzPccLG" /><figcaption>Photo by <a href="https://unsplash.com/@nate_dumlao?utm_source=medium&amp;utm_medium=referral">Nathan Dumlao</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Bir veritabanı ile iletişim kurarak okuma/yazma yapan uygulamalar bir şekilde transaction yönetiminden sorumlu olmaktadır. En basit haliyle inisiyatif tamamen veritabanına bırakılarak ilgili veritabanının varsayılan değerleri yeterli görünebilir. Ancak iş akışlarının büyüdüğü ve eş zamanlı isteklerin yoğun olarak işlendiği durumlarda uygulamalar, transaction yönetimi ile ilgili özelleştirmelerini veritabanına iletmek isteyeceklerdir. Bunu en yalın haliyle native SQL kodunu uygulama tarafında hazırlayıp, veritabanı üzerinde çalıştırarak yapmak mümkündür. Bir ORM (Object Relational Mapping) aracının kullanıldığı durumlarda ise veritabanına yapılan soyutlamanın getirdiği kolaylıktan faydalanmak adına, ORM aracının sağladığı işlevsellik daha tercih edilir olmaktadır.</p><p><strong>Transaction Nedir</strong></p><p><em>Transaction,</em> genel anlamıyla veritabanı üzerinde gerçekleştirilen bir işlemi veya bir arada çalışınca anlam teşkil eden işlemler bütününü temsil eder. Yapı itibariyle bir transaction için 3 ana durum vardır: <strong><em>begin</em></strong>, <strong><em>commit</em></strong> ve <strong><em>rollback</em></strong>. <em>Begin</em>, transaction’ın başladığı andır. Bu andan itibaren elimizde bir transaction vardır ve bu transaction’ ın diğer transactionlar ile ilişkisi söz konusudur. <em>Commit</em>, transaction dahilinde veritabanında yapılan değişikliklerin kalıcı hale getirilip transaction’ ın sonlandığı durumdur. <em>Rollback</em> durumu ise yapılan işlemlerde bir hata meydana geldiğinde transaction içinde yapılan değişikliklerin geri alınıp (transaction’ ın başladığı andaki duruma getirilip) transaction<em>’ </em>ın sonlandığı durumdur.</p><p>Hem bir transaction’ ın çalışmasındaki hata durumlarını sağlıklı yönetebilmek hem de transactionlar arasındaki ilişkileri düzenleyebilmek adına transaction’ ların sağlaması gereken özellikler tanımlanmıştır. <a href="https://en.wikipedia.org/wiki/ACID">Daha çok ACID kısaltmasıyla kullanılan <em>Atomicity</em>, <em>Consistency</em>, <em>Isolation</em> ve <em>Durability</em> özellikleri ile transactionların çalışmalarında meydana gelebilecek hatalı durumlara karşın veritabanının “düzgün” kalmasını sağlamak amaçlanmaktadır.</a></p><p><strong>@Transactional Arayüzü</strong></p><p><a href="https://docs.spring.io/autorepo/docs/spring-framework/current/spring-framework-reference/data-access.html#spring-data-tier">Spring Framework’ ün sağlamış olduğu <em>@Transactional</em> arayüzü ile veritabanı transactionlar’ ının işleyişini yönetebiliriz.</a> Bu anotasyon ile işaretlenen metotların içerisinde yer alan işlemler, bu metot içerisinden çağrılan diğer metotların içerisindeki işlemler de dahil olmak üzere, bir transaction içerisine dahil edilmiş olur. Böylece bu işlemlerin ACID özelliklerini göstermelerini sağlayabiliriz.</p><p><em>@Transactional</em> bize iki temel işlevsellik sağlar: transaction yayılımlarındaki ilişki nasıl olacak ve <em>transaction</em> lar veriye erişme konusunda nasıl anlaşacak. Bu iki işlevsellik aslında 2 farklı problemin de çözüm seçeneklerini içerir.</p><p>Aşağıdaki kod parçası üzerinde transactional ile işaretlenmiş 2 metot görmekteyiz. Bu da bizi şu 2 soruyu sormaya itiyor: validateCreditCard metodu çağrıldığında yeni bir transaction başlayacak mı ve ilk transaction’ a ne olacak ? Bu sorulara detaylı olarak bir sonraki başlıkta (Transactionların Yayılım Sınırları) değinilmiştir.</p><pre>@Transactional<br>public void payWithCreditCard(String cardNumber) {<br>    validateCreditCard(cardNumber);<br>}<br><br>@Transactional<br>public void validateCreditCard(String cardNumber) {<br>    //<em>todo validate card info using database<br></em>}</pre><p>İkinci konu ise eş-zamanlılık kapsamında değerlendirmesi gereken bir durumu içerir. Aşağıdaki örnekte birbiri ile doğrudan ilişkisi olmayan 2 metot verilmiştir. Sorun şudur; ilk metot validasyon yaptıktan sonra henüz parayı çekmeden ikinci metot cüzdan hesabında kaç para olduğunu sorgularsa ve ardından ilk metot para çekme işlemini tamamlarsa, ikinci metotun okumuş olduğu değere güvenebilir miyiz ? Bu problem ile ilgili detaylara Isolation bölümünde yer verilmiştir.</p><pre>@Transactional<br>public void payWithWallet(Long walletId) {<br>    validateWalletBalance(walletId);<br>    withDrawFromWallet(walletId);<br>}<br><br>@Transactional<br>public void retrieveWalletBalance(Long walletId) {<br>    //<em>todo retrieve balance from database<br></em>}</pre><p><strong>Transactionların Yayılım Sınırları (Propagation)</strong></p><p>Transactionların yayılımlarındaki davranışları <em>@</em>Transactional arayüzüne ait olan propagation değeri ile yönetiyoruz. Burada, bir metodun transactional olup olmayacağı, olması durumunda kendisinin yeni bir transaction mı oluşturacağı yoksa transactional bir metot tarafından mı çağrılmak zorunda olacağı gibi konuların yönetimi söz konusudur. <a href="https://docs.spring.io/autorepo/docs/spring-framework/current/javadoc-api/">Spring bize Propagation enum sınıfına ait 7 farklı yayılım tipi sunmaktadır. </a>Buna göre @Transactional arayüzüne sahip bir metodun (onu çağıran metodun transactional olup olmadığına bağlı olarak) propagation tipine göre davranışları şu şekilde olur:</p><ul><li><strong>REQUIRED:</strong> Bu propagation tipine sahip bir metot, eğer transactional bir metot içerisinden çağrıldıysa ona dahil olur, aksi durumda yeni bir transaction oluşturup çalışmasına o şekilde devam eder. Required ayrıca Transactional arayüzünün varsayılan propagation tipidir.</li><li><strong>SUPPORTS:</strong> İlgili metot transactional bir metot tarafından çağrıldıysa o transaction’ a dahil olur, aksi halde normal şekilde çalışmasına devam eder.</li><li><strong>MANDATORY:</strong> Bu propagation tipine sahip bir metot, transactional bir metot içerisinden çağrılmak zorundadır, aksi halde hata fırlatır.</li><li><strong>REQUIRES_NEW:</strong> Bu propagation tipine sahip bir metot, transactional bir metottan çağrılıp çağrılmadığına bakmaksızın, yeni bir transactional süreç yaratıp onunla devam eder.</li><li><strong>NOT_SUPPORTED:</strong> Bu durumda ilgili metot eğer transactional bir metot içerisinden çağrılırsa onu askıya alıp çalışmasına transactional süreç dışında devam eder.</li><li><strong>NEVER:</strong> Eğer bu propagation tipine sahip bir metot, transactional bir süreç içerisinden çağrılırsa hata fırlatır.</li><li><strong>NESTED:</strong> İlgili metot kendisini çağıran metot transactional ise hata durumunda rollback edebileceği bir kayıt noktası oluşturarak devam eder, aksi durumda REQUIRED gibi davranır.</li></ul><p>Örnek kullanım:</p><pre>@Transactional(propagation = Propagation.<em>REQUIRED</em>)</pre><p><strong>Isolation</strong></p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*UXnQQhTK4BWUymk3" /><figcaption>Photo by <a href="https://unsplash.com/@markusspiske?utm_source=medium&amp;utm_medium=referral">Markus Spiske</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>Transactional veritabanlarının sağladığı ACID özelliklerinden biri olan Isolation, transactionlar arasındaki veriye erişim durumunu belirler. ACD özellikleri, veritabanında tek bir transaction çalışsa dahi söz konusudur. Isolation ise birden fazla transaction’ ın çalıştığı durumları dert edinir. Bu açıdan diğer 3 özellikten ayrıldığını söyleyebiliriz. Isolation aslında bir eş-zamanlılık (concurrency) problemidir. Çözüm olarak da eş-zamanlılık problemlerinde sıkça başvurulan <em>lock </em>mekanizmasından yararlanır.</p><p>Bir transaction için bir t anında diğer bir transaction ya henüz başlamamıştır, ya da sona ermiştir; bir transaction o an begin olan fakat henüz commit / rollback olmamış transactionların farkında değildir. Bu durum şöyle bir problem yaratmaktadır; bir transaction o an üzerinde çalışmak istediği <em>satır (row)</em> üzerinde çalışan başka transaction var olup olmadığını bilemez, dolayısıyla okuduğu / değiştirdiği veriyi o an başka bir transaction kullanıyorsa, o transaction’ ın çalışmasını olumsuz etkileyebilir veya kendisi bu durumdan olumsuz etkilenebilir. <a href="https://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt">İki transaction arasındaki bu eş-zamanlılık (concurrency) problemi ANSI/ISO standartları tarafından <em>read phenomena</em> olarak adlandırılan 3 senaryo ile tanımlanmıştır.</a> Verilen senaryolarda aynı satırlar üzerinde çalışan transactionlar’ dan T1 (Transaction1) okuyan, T2 (transaction 2) yazan taraftır.</p><p><strong>Dirty Reads:</strong> T2’ nin henüz commit etmediği rowların T1 tarafından okunması durumudur. T2 rollback edebilir veya yeni güncellemeler yaptıktan sonra commit edebilir. Bu durumda T1’ in okuduğu kayıtların değerleri değişmiştir fakat T1 halen eski değerlere sahiptir. Senaryo şu şekildedir:</p><p><em>T2 X kaydı için UPDATE sorgusu atar</em></p><p><em>T1 X kaydı için SELECT sorgusu atar</em></p><p><em>T2 X kaydı için yaptığı değişikliği rollback eder</em></p><p><strong>Non-repeatable Reads:</strong> T1&#39; in üzerinde çalışmaya devam ettiği kayıtların, T2&#39; nin araya girip değişiklik yapıp commit etmesi durumunda yaşanan senaryodur. Bu durumda T1’ in çalıştığı kayıtların değerleri artık T1 için geçersiz duruma düşmüş olur. Senaryo şu şekildedir:</p><p><em>T1 X kaydı için SELECT sorgusu atar</em></p><p><em>T2 X kaydı için UPDATE sorgusu atar ve commit eder</em></p><p><em>T1 X kaydı için SELECT sorgusu atar</em></p><p><strong>Phantom Reads:</strong> Non-repeatable Read senaryosunun gruplama işlemleri bazında özelleşmiş hali olduğunu söyleyebiliriz. Örneğin T1 n adet row için COUNT sorgusu atar, henüz commit atmadan T2 ilgili n adet row için ekleme veya silme yapar. Row sayısı değiştiği için T1&#39; in elindeki değeri geçersiz hale getirmiş olur.</p><p>Bu senaryoların neden olduğu olumsuz durumların önüne geçebilmek adına 4 farklı <em>isolation</em> seviyesi tanımlanmıştır. Her seviye belirli derece hatayı engeller. <a href="https://docs.spring.io/spring-framework/docs/current/javadoc-api/org/springframework/transaction/annotation/Isolation.html">Spring, ANSI/ISO standartlarında belirtilen 4 seviyeye ek olarak bir de çalışılan veritabanının varsayılan seviyesinin kullanıldığı DEFAULT tipini Isolation enum sınıfı içerisinde kullanıma sunmuştur.</a> Transactional arayüzü varsayılan olarak çalışılan veritabanının isolation seviyesini kullanınır.</p><ul><li><strong>SERIALIZABLE:</strong> Bahsedilen 3 senaryo için de çözüm sağlar. Transaction tamamlanana kadar üzerinde çalışılan kayıtların tamamına erişimi engeller (range-lock).</li><li><strong>REPEATABLE_READ:</strong> Commit edilmemiş bir row’ un okunmasını engeller (lock) ancak where koşuluna row kümesinin geneli için güvence sağlamaz (range-lock yok) yani Phantom Read problemi için çözüm sunmaz.</li><li><strong>READ_COMMITTED:</strong> Üzerinde çalışılan row’ un değiştirilmesini önler ancak okunmasına izin verir. Dolayısıyla bu seviye sadece dirty read problemini engeller. Non-repeatable read ve Phantom read gerçekleşebilir.</li><li><strong>READ_UNCOMMITTED:</strong> Herhangi bir <em>lock</em> mekanizması içermez dolayısıyla 3 read phenomena problemini de yaşayabiliriz.</li></ul><p>Örnek kullanım:</p><pre>@Transactional(isolation = Isolation.<em>READ_COMMITTED</em>)</pre><p>Eğer Transactional arayüzünü herhangi bir isolation level belirtmeden kullanırsanız, DEFAULT olarak tanımlanacaktır. Javadoc yorumunu okuduğumuzda DEFULT durumunda, kullanılan datastore’ un isolation level’ ına riayet edildiğini görüyoruz. hem JDBC’ nin[1] hem de Postgresql’ in [2] default isolation level’ ı READ_COMMITTED seviyesidir.</p><p>Transactionların güvenirliği açısından baktığımızda akla “Madem her problemi çözüyor, o halde neden sürekli SERIALIZABLE seviyesinde çalışmıyoruz ?” sorusu gelebilir. Bu sorunun cevabını tek kelime ile “Performans” tır. Isolation seviyeleri, güvenirliği sağlamak için üzerlerinde çalıştıkları kayıtlara diğer transactionların erişimlerini engeller dolayısıyla onların işlem süresini uzatır (veya çalışmalarını engeller). Bu noktada tutarlılık ve performans arasında bir trade-off yaşadığımızı söylemek yanlış olmaz.</p><p><strong>Ek Olarak</strong></p><p>@Transactional<em> </em>sınıf seviyesinde de kullanılabilir. Eğer sınıf seviyesinde kullanılırsa, o sınıfa ait tüm <em>public</em> metotlara uygulanmış olur.</p><p>Dikkat edilmesi gereken bir nokta anotasyonun public metotlara uygulanması ve anotasyon eklenen metodun aynı sınıftan değil, dışarıdan çağrılıyor olması gerekliliğidir (Spring’in proxy çalışması şekli nedeniyle).</p><p>Varsayılan olarak @Transactional sadece <em>RuntimeException</em> (ve ondan türeyen sınıflar) ile <em>Error</em> durumlarında veritabanında yapılan değişiklikleri geri sarar (<em>rollback</em>). Eğer <em>checked exception</em> lar kullanıyorsak <em>rollbackFor</em> veya <em>rollbackForClassName</em> parametreleriyle <em>rollback</em> edilmesini istediğimiz hata sınıflarını belirtebiliriz. (Bu hata sınıfları “Throwable” sınıfının alt sınıfı olmalıdır.)</p><p>Sadece okuma yapacağımız transactional metotlar için <em>readOnly</em> değerinin <em>true</em> olarak belirtilmesi, işlemimizi optimize edebilmek adına faydalı olacaktır.</p><p>Son olarak unutulmamalıdır ki Spring Data ile JPA’ yı, JPA ile de Hibernate gibi bir ORM aracını soyutlanmış olarak kullanmaktayız. Spring Data modülü ilişkisel veritabanları için Spring Data JPA alt modülünü sunarken, NoSQl veritabanları için (Redis, Cassandra MongoDB vs.) ayrı ayrı alt modüller sunmaktadır. Nihayetinde kullandığımız veritabanının transaction yönetimi ile ilgili bilgi sahibi olmak, soyutlama ile gelen işlevsellikleri kullanmayı bilmek kadar önemlidir.</p><p><strong>Referanslar</strong></p><p><strong>[1]</strong> https://docs.oracle.com/javadb/10.8.3.0/devguide/cdevconcepts15366.html</p><p><strong>[2] </strong><a href="https://www.postgresql.org/docs/9.5/transaction-iso.html">https://www.postgresql.org/docs/9.5/transaction-iso.html</a></p><p><strong>Kaynaklar / Ek Okumalar</strong></p><ul><li><a href="https://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt">https://www.contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt</a></li><li><a href="https://docs.spring.io/autorepo/docs/spring-framework/current/spring-framework-reference/data-access.html#spring-data-tier">https://docs.spring.io/autorepo/docs/spring-framework/current/spring-framework-reference/data-access.html#spring-data-tier</a></li><li><a href="https://en.wikipedia.org/wiki/ACID">https://en.wikipedia.org/wiki/ACID</a></li><li><a href="https://en.wikipedia.org/wiki/Isolation_(database_systems">https://en.wikipedia.org/wiki/Isolation_(database_systems</a>)</li><li><a href="https://stackoverflow.com/questions/12179130/what-are-range-locks">https://stackoverflow.com/questions/12179130/what-are-range-locks</a></li><li><a href="https://www.baeldung.com/spring-transactional-propagation-isolation">https://www.baeldung.com/spring-transactional-propagation-isolation</a></li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=4c768a000593" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>